[57858] in North American Network Operators' Group
Re: Selfish routing
daemon@ATHENA.MIT.EDU (Mike Lloyd)
Fri Apr 25 10:30:40 2003
Date: Fri, 25 Apr 2003 07:28:14 -0700
From: Mike Lloyd <drmike@routescience.com>
To: deepak@ai.net
Cc: Sean Donelan <sean@donelan.com>, nanog@merit.edu
In-Reply-To: <GPEOJKGHAMKFIOMAGMDIAEJFLDAB.deepak@ai.net>
Errors-To: owner-nanog-outgoing@merit.edu
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
