Subject: Re: [Tsvwg] SCTP address specific routing

From: Mark Butler <[email-masked]>
Date: Fri, 10 Feb 2012 00:07:06 -0000

On 2/8/2012 2:24 PM, German Becker wrote:
> I have the exact same issue that you describe in your mail I found 
> from six years ago . I'm afraid I'm in the "found the problem but not 
> the solution situation"
> I was wandering if you know of any implementation that supports your 
> suggestions below?
> Many Thanks!
>
> [please see response below]
>
> [original post from 2006]
> Suppose I have two hosts A and B that are multihomed, each to a pair 
> of different providers. Each host has a source address based routing 
> policy so that traffic can be routed through either connected provider 
> by selecting the source address appropriately.
>
> Now each host has a choice of four paths to reach the other host. 
> However, the standard procedure described in RFC2960 does not allow 
> each of these four paths to be tested independently, resulting in 
> cases where associations fail even though viable connectivity is still 
> available just by switching source addresses.
>
> Moreover, among the four paths, even (especially) between two hosts in 
> the same city, one is likely to be much better than the other three, 
> and this path will often go missing if only two paths are used. Most 
> providers do not peer locally in most cities, so traffic typically 
> gets routed through several nearby states and back even if the 
> destination is across the street. But if two of the four possible 
> providers peer locally, or if the endpoints share a common provider, 
> that path will usually be the best by far, in terms of RTT, jitter, 
> packet loss, etc.
>
> So I suggest a scheme where failover and congestion control is done by 
> source / destination address pair rather than by destination address 
> alone. This is particularly important in the case where one host is 
> multihomed, and the other is not. Without path based (instead of 
> destination address based) failover support, the multihoming of the 
> first host is relatively pointless, because there is only one path 
> used the first host to the second, even though two are used in the 
> reverse direction.
> [......]
> By any chance has anyone implemented a scheme similar to this, with 
> (source address, dest address) based paths, heartbeats, and congestion 
> control instead of just (dest address) based paths?
>
Hello German,

I am afraid I am not aware of any protocol level implementation work 
done in this area. My suggestion to start out with would be to configure 
the endpoints and any necessary local routers with the appropriate 
destination address block specific routes so that each traffic to each 
destination address of a known endpoint gets routed through a different 
gateway to a different wide area network.

That should be relatively easy to do if the addressing pattern is such 
that all primary addresses use one group of network prefixes and all 
secondary addresses use a disjoint set. Ideally each end point site 
would have gateways to two independent network autonomous systems (AS), 
and each AS would (normally) only advertise a prefix for the local 
primary address block, and the local secondary address block, such that 
incoming traffic for primary and secondary addresses arrive via 
different gateways.

That will not provide full cross path redundancy, but done properly it 
should reliably establish two independent paths from every end point to 
every other end point.

Please note that without separate routes for primary and secondary 
destination addresses that are visible to the endpoint itself, or at 
least visible to the premises router, a change in destination address 
will not result in the choice of a new external gateway, and a single 
gateway failure (which ever one both destination addresses are routed 
through) will kill the association.

That is also the case if the primary and secondary addresses are not on 
separate address blocks that are (normally) advertised to only one of 
the AS (or internal equivalent) serving an endpoint site. If both the 
primary and secondary address blocks are advertised to the same AS, in 
all probability traffic directed at the primary and secondary addresses 
will be routed through that AS much of the time, and a failure of the 
gateway to that AS will likewise kill the association.

That is my understanding.  I hope that helps.

  - Mark Butler

---

From: German Becker <[email-masked]>
Date: Wed, 08 Feb 2012 21:25:54 -0000

Hi Mark,

Sorry to bother you. I have the exact same issue that you describe in your
mail I found from six years ago . I'm afraid I'm in the "found the problem
but not the solution situation"
I was wandering if you know of any implementation that supports your
suggestions below?
Many Thanks!

German

Suppose I have two hosts A and B that are multihomed, each to a pair of
different providers. Each host has a source address based routing policy so
that traffic can be routed through either connected provider by selecting
the source address appropriately.

Now each host has a choice of four paths to reach the other host. However,
the standard procedure described in RFC2960 does not allow each of these
four paths to be tested independently, resulting in cases where
associations fail even though viable connectivity is still available just
by switching source addresses.

Moreover, among the four paths, even (especially) between two hosts in the
same city, one is likely to be much better than the other three, and this
path will often go missing if only two paths are used. Most providers do
not peer locally in most cities, so traffic typically gets routed through
several nearby states and back even if the destination is across the
street. But if two of the four possible providers peer locally, or if the
endpoints share a common provider, that path will usually be the best by
far, in terms of RTT, jitter, packet loss, etc.

So I suggest a scheme where failover and congestion control is done by
source / destination address pair rather than by destination address alone.
This is particularly important in the case where one host is multihomed,
and the other is not. Without path based (instead of destination address
based) failover support, the multihoming of the first host is relatively
pointless, because there is only one path used the first host to the
second, even though two are used in the reverse direction.

The standard problem with doing this is N^2 path explosion. I suggest the
following techniques to mitigate this problem:

(1) Advertise only one address per interface per next hop when bound to
INADDR_ANY.

(2) When generating local address lists for INIT and INIT ACK, check to see
if routes to any of the peer addresses exist from a given local address
when bound to the interface of that address. If not, eliminate the address.

(3) Whenever transmitting with an INADDR_ANY derived source address, use
the same interface as the address. If a destination cannot be reached
through that interface, for whatever reason, let the routing layer select
both the source address and interface.

(4) Track whether each path is confirmed or unconfirmed, where the default
is unconfirmed.

(5) When replying to an INIT or an INIT ACK (with an INIT ACK or a COOKIE
ECHO) use the original source address as the destination address, and the
original destination address as the source address.

(6) Mark the (dest address, source address) pair of a valid packet bearing
a valid INIT ACK or COOKIE ECHO as a confirmed path.

(7) Use a heartbeat info structure that includes forward path information.

(8) Upon receiving a HEARTBEAT ACK, mark the forward path confirmed using
the information in the heartbeat info structure.

(9) Send DATA only through confirmed paths

Rationale:

(R1) More addresses than that is pointless except with very unusual
configurations

(R2) Avoid creating degenerate (completely overlapping) paths, e.g. for
addresses on interfaces that will never be used by the association, such as
stub network interfaces.

(R3)  Avoid using degenerate paths.

(R5) Necessary for initial forward path confirmation. The reverse path is
most likely to be up as well.

(R6) The confirmation procedure eliminates invalid cross paths between two
redundant networks, as well as paths that are reverse routable, but not
forward routable.

(R8) Same as R6.

(R9) Sending data only on confirmed paths reduces failover latency. There
will always be one confirmed path after a valid INIT ACK or COOKIE ECHO is
received. The others will normally be confirmed by initial heartbeats.

---

A further refinement would standardize the heartbeat info prefix to include
information about which path the heartbeat ack should be sent on, and the
time elapsed between HEARTBEAT arrival and HEARTBEAT ACK departure (similar
to DCCP). That would allow proper forward path transit time estimation
(where proper means adjusted for asymmetric forward and reverse routes,
bandwidth, transit time, and congestion) with the objective of selecting
the path with the lowest forward transit time for DATA and SACK
transmissions.

By any chance has anyone implemented a scheme similar to this, with (source
address, dest address) based paths, heartbeats, and congestion control
instead of just (dest address) based paths?

- Mark

---

From: Randy Stewart <[email-masked]>
Date: Tue, 13 Mar 2012 13:41:42 -0400

Mark/German:

There are methods that can be used without using sourced based routing. One
such would be something along the lines of the following.

You have two ISP's (A&B), each giving you a default router
to use.

You place each of these into your routing table. Note that on Linux you can
do this, on BSD I believe you may be able to do it with a  option compiled
into the kernel (years ago I hacked such behavior into the BSD kernel but that
was in 4.x FreeBSD to give you a time frame.). 

Now once you have both routes in your routing table, you need additional code
within your routing table/lookup mechanism besides the typical "find a route" routine.
What you want is to have a "find an alternate route" routine. That way you can do a
lookup in the normal way on the first entry. Then do the find_alt(existing route, dest); to
locate the other default route. And of course if your providers are not doing ingress address
filtering you can then easily change the source address used when sending to the routes and
have four paths, though I think that unrealistic (most providers will do ingress filtering).

Now I had such a facility working in 4.x FreeBSD quite some time ago, and one of these
days I will circle back and put it in again..just have never had time.

The only caveat that my solution did have was that it assumed that the provider was doing
ingress filtering, and so it always tried to use the src address of the egress interface.

And I did test it in various scenarios, and it did avoid the breakages y'all refer to below
with non-multi-homed to multi-homed as well as multi-homed to multi-homed.

In fact it even would re-route if the number of retransmissions was rising on a path.. it worked
quite well.. shame I never got it in ;-) (maybe one of these days :-D)

Its not quite source based routing (which has security issues besides being more of an experimental
topic talked about for a long time now) but it does work…

R

On Feb 9, 2012, at 7:05 PM, Mark Butler wrote:

>> I have the exact same issue that you describe in your mail I found from six years ago . I'm afraid I'm in the "found the problem but not the solution situation"
>> I was wandering if you know of any implementation that supports your suggestions below?
>> Many Thanks!
>> 
>> Suppose I have two hosts A and B that are multihomed, each to a pair of different providers. Each host has a source address based routing policy so that traffic can be routed through either connected provider by selecting the source address appropriately.
>> 
>> Now each host has a choice of four paths to reach the other host. However, the standard procedure described in RFC2960 does not allow each of these four paths to be tested independently, resulting in cases where associations fail even though viable connectivity is still available just by switching source addresses.
>> 
>> Moreover, among the four paths, even (especially) between two hosts in the same city, one is likely to be much better than the other three, and this path will often go missing if only two paths are used. Most providers do not peer locally in most cities, so traffic typically gets routed through several nearby states and back even if the destination is across the street. But if two of the four possible providers peer locally, or if the endpoints share a common provider, that path will usually be the best by far, in terms of RTT, jitter, packet loss, etc.
>> 
>> So I suggest a scheme where failover and congestion control is done by source / destination address pair rather than by destination address alone. This is particularly important in the case where one host is multihomed, and the other is not. Without path based (instead of destination address based) failover support, the multihoming of the first host is relatively pointless, because there is only one path used the first host to the second, even though two are used in the reverse direction.
>> [......]
>> By any chance has anyone implemented a scheme similar to this, with (source address, dest address) based paths, heartbeats, and congestion control instead of just (dest address) based paths?
>> 
> Hello German,
> 
> I am afraid I am not aware of any protocol level implementation work done in this area. My suggestion to start out with would be to configure the endpoints and any necessary local routers with the appropriate destination address block specific routes so that each traffic to each destination address of a known endpoint gets routed through a different gateway to a different wide area network.
> 
> That should be relatively easy to do if the addressing pattern is such that all primary addresses use one group of network prefixes and all secondary addresses use a disjoint set. Ideally each end point site would have gateways to two independent network autonomous systems (AS), and each AS would (normally) only advertise a prefix for the local primary address block, and the local secondary address block, such that incoming traffic for primary and secondary addresses arrive via different gateways.
> 
> That will not provide full cross path redundancy, but done properly it should reliably establish two independent paths from every end point to every other end point.
> 
> Please note that without separate routes for primary and secondary destination addresses that are visible to the endpoint itself, or at least visible to the premises router, a change in destination address will not result in the choice of a new external gateway, and a single gateway failure (which ever one both destination addresses are routed through) will kill the association.
> 
> That is also the case if the primary and secondary addresses are not on separate address blocks that are (normally) advertised to only one of the AS (or internal equivalent) serving an endpoint site. If both the primary and secondary address blocks are advertised to the same AS, in all probability traffic directed at the primary and secondary addresses will be routed through that AS much of the time, and a failure of the gateway to that AS will likewise kill the association.
> 

-----
Randall Stewart
[email-masked]