'Selfish Routing' Slows the Internet

Smaz writes "Science Blog reports that a little love could speed things up on the Net. "Self-interest can deplete a common resource. It seems this also applies to the Internet and other computer networks, which are slowed by those who hurry the most. Fortunately, say computer scientists at Cornell University in Ithaca, N.Y. , there is a limit to how bad the slowdown can get. And after developing tools to measure how much the performance of a particular network suffers, they say, the way to get improved performance on the Internet is the same as the way to maintain air and water quality: altruism helps."

Comments

Is altruism still possible on the Internet, tho?

[juanfe]

Given the growth of walled gardens, of email attacks, of DoS, of more traffic channeled through fewer fat pipes owned by fewer public/non-profit organizations, is this still possible?

Classic Prisoners Dilema problem

[acomj]

This is a classic example of the prisoners dilema problem.

Basically if everyone acts unselfishly they do better. But from each individuals perspective they do better when they act selfish, so it all falls apart. Its interesting stuff and the prisoners dilema game algorithms are interesting.

Prisoners Dilema

Play the dilema game online

Summary of main results.

[obnoximoron]

of the main paper : http://www.cs.cornell.edu/timr/papers/indep_full.p df and others.

1. Their basic idea is to model decentralized routing as a Nash game and then worst-case compare the performance of this game with the best achievable by ANY algorithm, decentralized or not. This sort of comparison is common in the field of competitive analysis .

2. Assuming a hop latency to increase linearly with additional traffic on it, selfish routing causes the average packet latency to increase by no more than 4/3 of that caused by ideal optimal routing. This worst-case figure had been earlier called "the Price of Anarchy" by Papadimitriou, a famous researcher in algorithmic complexity who every CS student loves to hate :P

3. Similar Prices of Anarchy have been derived by them for when the hop latency increases nonlinearly with the additional traffic on it.

4. The worst case is always achievable with a simple network of 2 nodes connected by parallel links. This is the exactly the example used in networking courses and textbooks to illustrate the oscillation problem caused by selfish routing. This paper says that using this simple network as example is justified since the worst case can be always be analysed with it.

5. Instead of optimizing routing to try reach the minimum possible average latency, you can keep the routing selfish but double each link capacity and achieve the same result.