Is the Internet becoming a "tragedy of the commons" through selfish routing? Cornell researchers suggest altruistic way

Roughgarden

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.

Braess' Paradox

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.

Media Contact

Media Relations Office