Full size image available through contact |
DENVER --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 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.
This analysis comes from work by Tim Roughgarden, a Cornell postdoctoral research associate in the Department of Computer, and Éva Tardos, professor of computer science. Roughgarden describes 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 is part of a symposium, "Game Theoretic Aspects of Internet Computation," which examines 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.
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 go by way of Chicago or Dallas, or might even 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.
Full size image available through contact |
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 by 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 -- technically a quadratic equation -- 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.
Whether or not it's worth making changes to reduce delay depends on the cost to make the changes, Roughgarden says, pointing out that these mathematical analyses are based on hypothetical networks. "The extent to which the real Internet conforms to these mathematical models is not yet well understood," he admits.
Adding more interconnections to a network won't necessarily help, Roughgarden says. Then, you might run into something called Braess' paradox, which says that if you introduce more interconnections so that messages can hop from one path to another partway along, this actually makes the trip longer for everyone -- again, pretty much like changing lanes in a traffic jam.
Roughgarden has a suggestion that wouldn't be expensive to implement. Before deciding which way to send information, he says, routers should consider not only which route seems the least congested, but also should take into account the effect that adding its own new messages will have on the route it has chosen. That would be, he says, "just a bit altruistic" in that some routers would end up choosing routes that were not necessarily the fastest, but the average time for all users would decrease.
Papers on this topic by Roughgarden and Tardos include, "How Bad Is Selfish Routing," published in the Journal of the Association for Computing Machinery (ACM), March, 2002, and "The Price of Anarchy is Independent of the Network Topology," presented at the 34th ACM Symposium on Theory of Computing in May, 2002, and to be published in the Journal of Computer and System Sciences.
Related World Wide Web sites: The following sites provide additional information on this news release. Some might not be part of the Cornell University community, and Cornell has no control over their content or availability.
Tim Roughgarden's page: http://www.cs.cornell.edu/timr
Eva Tardos' page: http://www.cs.cornell.edu/People/eva/eva.html
E-Mail: deb27@cornell.edu