Mechanisms for a multi-homed host to pick the best router

Brighten Godfrey pbg at cs.berkeley.edu
Fri Sep 19 06:00:14 UTC 2008


> When the server sends TCP traffic for that same connection back to  
> host A,
> it needs to pick one of the N routers, in other words, it needs to  
> pick an
> outbound interface from its N interfaces.
...
> The problem is that some routers are "better" than other routers in  
> the
> sense that they are closer to the final destination address A. (For  
> example,
> each router could be connected to a different ISP.)
>
> One way for the server to pick the "optimal" downstream router, is  
> to run
> "stub BGP" between the server and each of the routers.
...
> While this approach would certainly allow the server to pick the  
> optimal
> downstream router in all cases, I would prefer not to run routing  
> protocols
> on this server for a number of reasons:

It's probably good to keep in mind that this would be "optimal", not  
optimal.  As far as I know the best you would get is to minimize the  
number of AS hops, which is probably correlated with, but definitely  
not the same as, metrics you actually care about like latency.  All  
in all, running BGP does seem like an awful lot of work just to let  
you optimize for the wrong metric.

Here's another thought, though.  You don't need to run BGP to get the  
data that BGP will give you.  There exist approximate maps of the  
Internet at the router or AS level with IP prefixes attached.  It  
would be possible to periodically obtain one of these graphs, e.g.  
from CAIDA, and then run a shortest-paths algorithm on that graph to  
decide based on the destination IP address which router is best.  Not  
only does this let you avoid running BGP, it also saves memory since  
you need only one copy of the graph, rather than one copy for each of  
the N BGP sessions.  Of course, it's not real-time data, but if all  
you need is a good guess as to which of the outbound interfaces is  
best, it might be sufficient.

Does anyone actually do something like this in practice?  (I'm  
guessing no)

> Someone suggested an idea to me which seems almost to simple to  
> work, but I
> cannot find any good reason why it would not work.
>
> The idea is "the server simply sends all outbound traffic for the TCP
> connection out over the same interface over which the most recent TCP
> traffic for that connection was received".

So the underlying idea here is that the source (or its ISP) has  
effectively done the work of picking a good path, and by replying on  
the same interface, you use the reverse of that path, which is also  
likely to be pretty good.

Some of the assumptions in that reasoning seem imperfect:

- There's a good chance the forward path (i.e. the one the source  
picked) isn't the best.
- Asymmetry, as you noted: Even if the forward path was the best, the  
reverse of it is not necessarily the best.
- A different asymmetry: Even if the forward was best and the reverse  
of it is best, the path followed by sending on the same interface is  
not necessarily the reverse of the forward path.

So I understand that this heuristic could perform pretty well in  
practice, and certainly better than sending on a random interface (in  
terms of latency, not traffic engineering).  But I can't see how it's  
the optimal strategy.

I think there are commercial products that solve this problem the  
"right" way, by automatically and dynamically monitoring path quality  
and availability, and selecting paths for you.  I think the Avaya  
Converged Network Analyzer is one.  I recall speaking with an  
operator from a major content provider who said that they use an  
intelligent route selection product similar to this for their  
outbound traffic.  I'd be personally interested to hear what other  
operators typically use.

~Brighten Godfrey




More information about the NANOG mailing list