Selfish routing
Mike Lloyd
drmike at routescience.com
Fri Apr 25 14:28:14 UTC 2003
Deepak, Sean,
Deepak Jain wrote:
> The article (mentioned RouteScience's "product").
> ...
> How is this a bad thing? How is this different than what SAVVIS or Internap
> claim to do?
>
> Or did I miss the point of the discussion on selfish routing?
No, I wouldn't say you missed the point at all :-)
Dr Roughgarden's results are, in brief:
1/ networks can, in principle, be routed for minimal latency
2/ strict "selfish" routing will (under certain conditions) fall
short of that ideal, but by a bounded amount - at most, a factor of 4/3
3/ some simple workarounds exist to eliminate the suboptimality
Note what's missing from the list: if you just plug in and run a complex
network, does it achieve the optimum from point 1? Dr Roughgarden
doesn't say. On this list, I think I can leave it as a rhetorical
question.
If you're part of a network that's not working optimally, you can
attempt to optimize it centrally/globally, you can optimize locally, or
you can leave it alone. Dr Roughgarden observes that the first answer
is sometimes better than the second, but it's impractical. He certainly
does not say that the second - local route optimization - is in any way
a step backwards relative to the third - living with whatever your
network happens to be doing.
So let me put this another way: I agree with Sean's original comment
that adding more bandwidth makes networks better, but only on condition
that you know how to use it.
Mike Lloyd
CTO, RouteScience
More information about the NANOG
mailing list