On Sun, Apr 27, 2003 at 02:31:22PM -0700, Mike Lloyd quacked:
alex@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@lcs.mit.edu me: dga@pobox.com MIT Laboratory for Computer Science http://www.angio.net/ I do not accept unsolicited commercial email. Do not spam me.