'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

Could the bloody writer be specific

[jj_johny]

Attention Science Blog - We have things called protocols and such. Please use specific terms.

Maybe I am just a lowly CCNP but is this all just a theory paper about the problems with "routing" or were there specifics about current routing protocols that should be updated or current practices that should be changed. Please help, everyone knows that the current routing could be better but theory stuff just does not help us much.

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?

For those too lazy to read the article ...

[floppy ears]

It basically says that network congestion is like congestion on highways. If everybody is trying to change lanes all the time, they might save a bit of time for themselves, but on the whole they will slow down traffic for everybody.

In theory, this may slow down the internet by something like 50-60% at most. Nobody really knows how well the Internet conforms to the mathematical model, however. Any benefit from trying to fix the problem might be outweighed by the cost of implementing a solution.

Re:For those too lazy to read the article ...

[Smidge204]

It's funny you should mention how internet traffic is like highway traffic.

There's an amusing, if not somewhat interesting, article writting up on how you can single-handedly relieve traffic congestion here:

http://www.amasci.com/amateur/traffic/traffic1.h tm l

It's basically the same idea: If a few people just give a little slack, everybody wins out.
=Smidge=

Re:I'm confused

[PetWolverine]

How does this get modded insightful?

The article is not saying that using the Internet slows it down (that much is obvious). It's saying that with different routing techniques and the same level of use, it could go faster. So, using it slows it down, but so does building a bad infrastructure for it.

Hasn't something similar happened in the past?

[Jugalator]

I suppose this is the heart of the article, btw:

"if routers choose the route that looks the least congested, they are doing selfish routing. As soon as that route clogs up, the routers change their strategies and choose other, previously neglected routes. Eventually the system will settle to an equilibrium that mathematicians call a Nash flow, which will be, on the average, slower than the ideal. "

Now, hasn't there been a problem some time a long time ago in early Internet history where parts of the internet entered a state of self oscillation. I recall this was later fixed somehow to a point by revising some protocols.

I remember it basically as the problem where lots of routers (for some reason) started sending packets to one path, it got very congested, all routers switched to another, congested, etc.

I only have very vague memories since I took the course where I heard it some years ago. Perhaps I'm only full of bullshit. :-)

Re:Hasn't something similar happened in the past?

[Jugalator]

Ok, thanks for clarifying. Yes, since it was some time I heard about it, I guess it was related to BGP and "route flapping" as TheSpunkyEnigma mentioned. I see there's a lot of articles both regarding the BGP protocol and route oscillation and route flap dampening methods to find at Google, and I'm now pretty sure it was these things I was thinking about.

Re:Thanks Ron Howard

[PetWolverine]

And just as in A Beautiful Mind Nash's friends suspected him of coming up with a plan that would allow him to get the blonde, people will suspect Cornell of coming up with this plan to get more bandwidth. Also just as in the movie (/book, which I haven't read yet) that's probably not the case...or let's hope it's not.

these aren't the only things..

[Anonymous Coward]

Road traffic works this way too.

Tragedy of the Commons

[rrkap]

This is essentially a pricing problem.

Here's a quote from the original 1968 paper that used the term

The tragedy of the commons develops in this way. Picture a pasture open to all. It is to be expected that each herdsman will try to keep as many cattle as possible on the commons. Such an arrangement may work reasonably satisfactorily for centuries because tribal wars, poaching, and disease keep the numbers of both man and beast well below the carrying capacity of the land. Finally, however, comes the day of reckoning, that is, the day when the long-desired goal of social stability becomes a reality. At this point, the inherent logic of the commons remorselessly generates tragedy.

As a rational being, each herdsman seeks to maximize his gain. Explicitly or implicitly, more or less consciously, he asks, "What is the utility to me of adding one more animal to my herd?" This utility has one negative and one positive component.

1. The positive component is a function of the increment of one animal. Since the herdsman receives all the proceeds from the sale of the additional animal, the positive utility is nearly + 1.

2. The negative component is a function of the additional overgrazing created by one more animal. Since, however, the effects of overgrazing are shared by all the herdsmen, the negative utility for any particular decisionmaking herdsman is only a fraction of - 1.

Adding together the component partial utilities, the rational herdsman concludes that the only sensible course for him to pursue is to add another animal to his herd. And another.... But this is the conclusion reached by each and every rational herdsman sharing a commons. Therein is the tragedy. Each man is locked into a system that compels him to increase his herd without limit -- in a world that is limited. Ruin is the destination toward which all men rush, each pursuing his own best interest in a society that believes in the freedom of the commons. Freedom in a commons brings ruin to all.

There are two common solutions to this kind of problem. Regulate use of the common resource or sell it. Because of the structure of the internet, it is hard to fairly price bandwidth and no good regulatory scheme has developed, so I don't see any other answer than living with it.

Similar to Automobile Traffic

[Walker]

In many (but certainly not all), Internet traffic is similar to automobile traffic. Packets are discrete objects, like cars, and not continuous like a river or radio signal. Analysis on automobile traffic has already discovered properties like this. There are many simulations that show if we all ensured 3 car lengths between us and the next car, we would avoid the accordion and get to work significantly faster.

Re:DL managers

[bgarrett]

Download managers aren't really the problem, except when you don't have the bandwidth to sustain parallel downloading. If you have enough pipe, parallel DLs ARE faster than a single serial download.

The problem the paper is describing is at the larger "router's eye view" scale, where multiple routes out to the rest of the network exist, and where only the fastest route is used - the other two pipelines are basically starved of packets.

tragedy of the commons

[urbazewski]

This is not the main point of the article but:

The Tragedy of the Commons , often cited by environmentalists, describes 14th-century Britain, where each household tried to gain wealth by putting as many animals as possible on the common village pasture. Overgrazing ruined the pasture, and village after village collapsed.

The "tragedy of the commons" that Hardin's article is devoted to is increasing world population. What evidence is there for overgrazing in England before as opposed to during and after the forced transition to private ownership? Most cultures with a common land tradition also have a set of rules for governing land use that avoids such tragedies, for example, irrigation systems in Bali where the farmer who gets the water last controls the water flow. Ones that didn't solve the problem of overuse of resources are conspicuous by their non-existence (Easter Island, some settlements in the Southwest US, some populations on islands in the South Pacific ).

The 'tragedy of the commons' is one of the most misunderstood and overused metaphors of our times. The idea that a system with resources held in common is necessarily unworkable is false --- what is needed is institutions that effectively manage common resources, and such institutions have emerged repeatedly and continue to exist. Often it is when these cultures come into contact with market-oriented societies that the traditional systems are undermined and collapsed. Often what happens is not "the tragedy of the commons" but "the tragedy of failed privatization" in which a traditional management system is destroyed without establishing a viable alternative.

How does this relate to the internet? It's a cautionary tale --- be very very careful when introducing monetary incentives into a system that has previously relied on cooperation and cultural norms.

blog-O-rama

Re:Light Precipitation

[peculiarmethod]

Already happens here [MIDS IWR, internetweather.com]

-former employee

pm

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

reference on Balinese water temples

[urbazewski]

This summary of the Balinese water temple system is from an article by Bradley J. Ruffle and Richard H. Sosis that looks at the use of religious practice to encourage cooperation via field experiments in kibbutzim.

It follows that multinational corporations and foreign institutions investing in the developing world and dependent on collaboration with the indigenous people may profit from preserving indigenous ritual practices and the environment in which they take place. The well-documented water temple system of Bali represents a case in point (see Lansing, 1991, for an authoritative study). A lake in a volcanic crater on the island as well as the rains that run off of the volcano irrigate Bali's rice fields. The Balinese have developed what has proven to be an ingenious cooperative system of aqueducts to supply water in equitable amounts to the surrounding farmers. At the heart of this coordinated effort lies an indigenous religion that worships, among other deities, Dewi Danu, the goddess of the waters emanating from the volcano in whose honor an immense temple stands at the volcano's summit. Smaller temples for worship are located at every branch of the irrigation system and at the fields onto which the aqueducts empty.

The wisdom and success of the Balinese water temple system became clear when the Asian Development Bank imposed a farming alternative on the Balinese in the 1980s. The Asian Development Bank concluded in 1988 that, "The substitution of the "high technology and bureaucratic" solution proved counter-productive and was the major factor behind the yield and cropped areas declines experienced between 1982 and 1985 ... The cost of the lack of appreciation of the merits of the traditional regime has been high. Project experience highlights the fact that the irrigated rice terraces of Bali form a complex artificial ecosystem which has been recognized locally over centuries" (quoted from Lansing, 1991, p. 124).

Lansing, J. S. (1991) "Priests and Programmers: Technologies of power in the engineered landscape of Bali ", Princeton: Princeton University Press. Leviatan, U., H. Oliver, J. Quarter (1998)

blog-O-rama

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.

Re:I'm confused too!

[JWSmythe]

Good.. I was thinking we're idiots too.. Either that, or I need to start routing all my traffic down the most conjested pipes to watch it go faster. :)

I've worked with our provider a bit with routing. We have mirrored servers in colo's around the country. If one city is conjested, we move traffic *AWAY* from the conjestion. Usually our traffic makes a difference for everyone else. I can have 500Mb/s added or removed from any given city within an hour, without flinching. Of course, before I do something like that, I put in a call first.. "Hey, can this city take 500Mb/s right now?"

We wrote a program to take traceroutes from all the cities to various points, and plot them all onto a big network map, with ping times and the like.. We know which cities, peerings, or lines have problems at a glance..

http://www.voyeurweb.com/network.12.23.2002-11h.pn g
Warning: This picture is *BIG*. It's of our networks in Los Angeles, New York, Tampa, between each other, and to all of the root nameservers.. It makes a rather extensive map that is 11580x2669. It won't fit on your screen. Save it, and take it into your favorite image editing software to view it..

This map is a little old (Dec 23, 2002 at 11am), but it gives a good impression of what the networks immediately around our servers looked like, and how they interact with each other.. Shitty networks stand out in red.. I definately wouldn't want to MORE of my traffic that way. Sometimes we don't have a choice. If your ISP uses a shitty provider, we have to send it that way..

Altruism

[jbl81]

Altruism is not the way we keep air and water clean. Air and water quality are public goods (in the economics sense of the term), and keeping them clean is a collective action problem. It's straightforward game theory to show that the rational choice, in a system where you have no reason to trust people, is to make sure you don't get screwed before you have a chance to "get yours".

The way people and governments get out of a collective action problem (like an arms race, or like EMU monetary/fiscal policy, etc) is not through altruism, but through formal cooperation. In order to ensure that everyone cooperates, you need to (1) clearly define what constitutes cooperation, (2) make it transparent (obvious) who is cooperating and who is not, and (3) decide on mechanisms for enforcement.