[57904] in North American Network Operators' Group
Re: Selfish routing
daemon@ATHENA.MIT.EDU (Mike Lloyd)
Sat Apr 26 13:57:00 2003
Date: Sat, 26 Apr 2003 10:56:27 -0700
From: Mike Lloyd <drmike@routescience.com>
To: nanog@merit.edu
Errors-To: owner-nanog-outgoing@merit.edu
alex@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@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
