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