Mechanisms for a multi-homed host to pick the best router
pbg at cs.berkeley.edu
Fri Sep 19 01:00:14 CDT 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
> sense that they are closer to the final destination address A. (For
> 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
> downstream router in all cases, I would prefer not to run routing
> 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
> 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.
More information about the NANOG