'Selfish' routers slow the Internet
By Sandeep Junnarkar
Staff Writer, CNET News.com
February 14, 2003, 11:34 AM PT
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.
http://news.com.com/2100-1033-984694.html?tag=fd_top
