|
North American Network Operators Group Date Prev | Date Next | Date Index | Thread Index | Author Index | Historical Re: Selfish routing
[email protected] 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. [email protected] 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
|