North American Network Operators Group
Date Prev | Date Next | Date Index | Thread Index | Author Index | Historical

Re: Selfish routing

  • From: Mike Lloyd
  • Date: Fri Apr 25 10:32:32 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