Selfish routing

Sat Apr 26 17:56:27 UTC 2003

alex at yuriev.com wrote:
 > Having capacity *always* makes a network better.

True enough; given massive over-capacity, you'll have a hard time 
finding any congestion.  (Of course, you also won't find optimality 
without applying some kind of measurement.)  But curiously, adding some 
incremental capacity to a network can, under some conditions, actually 
make it worse!

Leo Bicknell wrote:
 > I mean, really, the fact that a secondary path is worse than a primary
 > path with no capacity is a no brainer, couldn't these people be doing
 > something more useful?

Roughgarden's point (as I see it) is that Braess' paradox applies.  Most 
people find it obvious that adding more capacity to a network will 
always help, but as it happens, that's not true.

That is not to say that adding capacity is always wrong.  It's usually 
right; it's just of some interest to note that there are conditions 
where harm can result, especially when independent actors act 
"selfishly".  The basic result is quite old, as Roughgarden observes; 
the same phenomenon exists in road networks, and he gives a nice example 
of strings and springs in his paper, which Jeffrey Arnold cited earlier:
   <http://wisl.ece.cornell.edu/ECE794/Apr2/roughgarden2002.pdf>
This contains a good deal more detail than the NY Times writeup that 
started this thread :-)

As Jeffrey observed, the assumptions in the model don't map well to the 
Internet we all know and love, but results like Braess' paradox come up 
again and again.  If you want an optimal network, you can:
   1/ sit in the middle and play at being the God of TE
   2/ have the various actors optimize "selfishly"
   3/ count hops and assume that's close enough
(Oh, and if you're into that sort of thing, I suppose you can try 
dropping some packets to speed things up.)

Roughgarden's result is that 2/ is not quite as good as 1/ at making 
fully optimal networks, but in a bounded way.  I think the bound is a 
really nice result, although it's a pity the model assumptions aren't 
all that close to the operating nature of the Internet.

alex at yuriev.com wrote:
 > However, claims "we have a special technology that magically
 > avoids problems in the networks that we do not control" is the
 > egineering religion.

And I wouldn't evangelize that faith, as stated.  I do happen to believe 
in "special" (or if you prefer, "selfish") technology that measures 
problems in networks I do not control, and if they can be avoided (say 
by using a different network or a different injection point), avoid 
them.  In practice, that extra "if" doesn't change the equation much, since:

Richard A Steenbergen wrote:
 > Random good luck just by having lots of paths to choose
 > from and a way to detect which one "works"... it's possible.

Quite so.  I won't comment on the degree of effectiveness, since that 
would be marketing :-)  Nobody should be surprised at what I'd say about 
that anyway.

Mike