Selfish routing

Sun Apr 27 22:04:06 UTC 2003

On Sun, Apr 27, 2003 at 02:31:22PM -0700, Mike Lloyd quacked:
> 
> 
> 
> alex at yuriev.com wrote:
> >>But curiously, adding some 
> >>incremental capacity to a network can, under some conditions, actually 
> >>make it worse!
> >
> >Oh, rubbish.

To alex:  It's not necessary to add a tiny link to the network
to make things worse.  In fact, the actual Braess Paradox example
that roughgarden uses arises from the addition of a high-capacity,
low-latency link in the wrong place.  It presumes the existence of
a smaller capacity path through the network somewhere, but are you
arguing that those paths don't exist?  I can show you a lot of them,
since it's what my software (the aforementioned MIT RON project) is
designed to exploit.  The Internet is full of weird, unexpected paths
when you start routing in ways that the network designers didn't  intend.
And that's what selfish routing _does_.

In fact, another of Roughgarden's results is that it's fundamentally
hard (in the NP sense) to tell whether or not you're going to have
an occurrence of suboptimal selfish routing on your network.  There
may be simple guidelines that can help avoid them, but that remains
to be seen (yes, I asked).

> >Of course, the sales people of yet another equipment vendor trying to sell
> >yet another useless technology that claims in a yet another way eliminate
> >the need of people with a clue on staff in exchange for major $$$ do not
> >want to admit it.
> 
> Glad to be accused of offering a technology that can only do what smart 
> people can do (whether I agree or not).  Since the supply of clue in 
> this world is limited ...

And to reiterate this in a different light, note that the Roughgarden
work only deals with how far away from a theoretical latency optimum
networks are.  It may not apply at all when you're operating with
sub-optimal network information in the way that both current networks
and current selfish solutions (ron, routescience, sockeye, etc.) do.
And note that one of the big benefits that we observed from our own
software wasn't latency -- it was reliability, with improved time-to-fix
vs. BGP convergence.  And that's something that's hard to engineer around
from a single provider perspective, because it's all about the interaction
of multiple -- and variably clued -- ASes.

> In your own parallel posts, you acknowledge all the murky reasons why 
> other people don't build their networks in the way you'd like.  OK; so I 
> can make my own network and interconnects Yuriev-compliant, but that 
> still doesn't solve all the issues as long as I want to talk to people 
> across fabric that is not Y-c.  It's a network of networks we live in.

  Bingo.

  -Dave

-- 
work: dga at lcs.mit.edu                          me:  dga at pobox.com
      MIT Laboratory for Computer Science           http://www.angio.net/
      I do not accept unsolicited commercial email.  Do not spam me.