Tim Roughgarden: Posing a cure for Internet's 'tragedy of the commons'

Roughgarden

By Bill Steele

The Tragedy of the Commons, as explained by Garrett Harding in his classic 1968 book, is that 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 Cornell computer scientists, 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.

This analysis comes from work by Tim Roughgarden, a postdoctoral research associate in the Department of Computer Science, and Éva Tardos, professor of computer sci-ence. Roughgarden described the work in a talk, "Selfish Routing and the Price of Anarchy," at the annual meeting of the American Association for the Advancement of Science in Denver, Feb. 14. The talk was part of a sym-posium, "Game Theoretic Aspects of Internet Computation," which examined the application of the principles of economics to the Internet.

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.

In the above example, the diagram on the left shows two routes: a lower, fixed route and an upper route that is the function of the number of users. When those on the lower route switch to the upper route, as shown in the diagram on the right, all traffic is slower.

A similar behavior on a computer network is "selfish routing," where each routing computer tries to send data via the fastest route, causing that route to become the most crowded and slow down. You don't have to understand computer networking to grasp the concept. It also happens on highways: If everyone takes the express lane, pretty soon the local route is faster.

The Internet is "fault-tolerant," so there are always many routes a message can take. A packet of data traveling from New York to San Francisco might hop from New York to Columbus to Miami to Omaha to Denver to San Francisco. At each stop the packet is processed by a computer called a router, which checks the address and chooses the most likely direction to send each packet to get it to its ultimate destination.

Routers have many ways to decide. Sometimes they send out test packets and time them. Sometimes routers exchange information
about the condition of the network in their vicinities. But 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.

It's theoretically possible to impose a set of traffic-control rules on the system that might increase the time for some users but reduce the average time for all, but is it worth the bother? Recently Roughgarden and Tardos made a mathematical analysis of the effect of selfish routing and found that it causes the average time of travel to increase to up to one and one-third times what could be achieved by an ideal system, a result that has been dubbed "the price of anarchy." The figure was based on the assumption that the time required to travel a given route would increase linearly in proportion to the amount of additional traffic. In later work, Roughgarden considered networks where the increase might be based on a more complex formula and found that even in the worst case the slowdown would be just one and two-thirds times the ideal.

Roughgarden found that the worst case was also the simplest: two nodes with only two possible routes between them. They also found that doubling the capacity of the system would provide the same benefits as a managed system. <