'Selfish' routers slow the Internet

A little altruism could go a long way in speeding up the Internet.

That's the conclusion two Cornell University computer scientists came to after finding that computer networks tend to be "selfish" when each tries to route traffic by the fastest pathway, causing that path to become congested and slow.

If the routers that direct the packets of data could be programmed with some altruism, the information might be able to reach its destination a little faster while allowing other packets to also move more quickly.

Eva Tardos and Tim Roughgarden described their work on Friday in a talk titled "Selfish Routing and the Price of Anarchy," at the annual meeting of the American Association for the Advancement of Science in Denver. Their presentation was part of a symposium called "Game Theoretic Aspects of Internet Computation" which explores the application of economic principles to the Internet.

A packet of data has many ways to reach its destination and relies on the routers it encounters to direct it. Routers today, the computer scientists said, have several means to decide which way to send the information. They might send out test packets and time them. At other times, the routers might exchange information about the condition of networks close to them. More often than not, the router will choose the least congested path until it, too, becomes clogged. At that time, the router will settle on a previously neglected route.

The system will eventually stream to an equilibrium that mathematicians call a Nash flow, which is usually slower than an ideal system. The researchers constructed a mathematical analysis of how routers direct packets and found that the average time of travel increased by up to 1.33 times compared with an ideal system.

Adding more interconnected pathways to the network can also be counterproductive because of an effect called Braess' paradox, the researchers said. According to the paradox, the packets of information would simply hop from one path to another--much like drivers switching lanes in a traffic jam--actually slowing down all the other packets traveling on those pathways.

To improve how routers direct traffic, Roughgarden suggested they consider not only which route is least congested, but also how sending packets in that direction would affect that path. Being more altruistic, a router in some cases may end up choosing pathways that are not necessarily the fastest, which could still result in lower average times for all the transmitted data.

The scientists said 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," Roughgarden said.