Interesting People mailing list archives
Like a Swerving Commuter, a Selfish Router Slows Traffic -- Is this another case of PR science?
From: Dave Farber <dave () farber net>
Date: Fri, 25 Apr 2003 12:44:27 -0400
When I read the Times article, I had two reactions. The first and loudest was that scientific publication by news paper "press releases" is poor science. It brought cold fusion etc etc. The second reaction was -- that is old news and besides it does not work in the current net. I asked Dave Reed to independently read it and comment. Lets report "new" ideas via the peer system not by calling reporters. Cornell should set an example. Dave ------ Forwarded Message From: "David P. Reed" <dpreed () reed com> Date: Fri, 25 Apr 2003 08:59:52 -0400 To: Dave Farber <dave () farber net> Subject: Re: Is this another case of PR science? There is no connection between this work and anything that goes on in the current Internet, that's for sure. Packets don't drive themselves, there is no framework under which packets could possibly be "selfish". Packet routing is done by decentralized algorithms, whose job is collectively to seek a global optimum that balances interests. I'm sure it's very interesting theory, but why in the world are they being covered in the New York Times? How can they honestly claim that their work applies to today's Internet? There's lots of interesting research to cover in the academic world, without this sort of distorted lens. At 06:16 PM 4/24/2003 -0400, Dave Farber wrote:
Like a Swerving Commuter, a Selfish Router Slows Traffic April 24, 2003 By IAN AUSTEN TIM ROUGHGARDEN is a computer scientist who studies the packets of data that rocket along the Internet at the speed of light. But while developing his theories, he often contemplates something far less dynamic: commuters stuck in traffic. "In my mind, it's the easiest way to think about networks," said Dr. Roughgarden, a researcher at Cornell University. Along with ?va Tardos, a professor of computer science at Cornell University, Dr. Roughgarden has come up with a moral lesson of sorts for both motorists and the routers that keep the Internet's traffic flowing. Shortcuts that serve the selfish interests of individuals, they have discovered, ultimately reduce the overall speed of both highways and the Internet. "This is something of a rediscovery," Dr. Roughgarden said. The phenomenon was first studied by civil engineers who were planning roads in the 1950's, he said. "We initially wanted to know how much better you could do with central control of traffic rather than just leaving everybody alone to do what they want," Dr. Roughgarden said. Routers, the specialized computers that move bits of data along the Internet, are not as calculating about their moves as many car drivers are. In general, the paths they select for data packets are based on commercial considerations like traffic-sharing agreements among Internet service providers rather than on speed. "It's the cheapest path, not the shortest path," Dr. Roughgarden said. The resulting routing can sometimes give new meaning to "indirect." Internet traffic between two points in the United States, for example, sometimes travels by way of England, Dr. Roughgarden said. The delays caused by even more roundabout routes can be a particular problem for some time-sensitive activities, like streaming video. So, unsurprisingly, systems are under development that would allow network operators seeking more efficient routing to direct their packets rather than abandoning them to the Internet's free-for-all. RouteScience, a company based in San Mateo, Calif., sells a system that allows Internet service providers and others to control their packets during part of their routes. There are, in theory at least, different ways for routers to find faster routes. In the same way that some motorists listen to traffic reports on the radio in the hope of avoiding congested roads, routers could send test packets in different directions to determine the swiftest path to the destination. Like motorists who cut off other cars as they swerve onto residential streets to speed their own trips, an Internet based on what Dr. Roughgarden and Dr. Tardos call "selfish routing" might indeed speed up the journeys of some data packets. But over all, the two researchers found, the result is quite different. Those shortcuts through side streets often have the effect of delaying other drivers, or in the Internet's case, packets. Individually, the delays may not amount to much. But when multiplied by thousands of other drivers, or packets, the overall drain on the system can be significant, Dr. Roughgarden said. The researchers calculate that, depending on various factors, packet trips can be 33 percent slower than an ideal system. Another factor affects the impact of selfish actions. As intuition would suggest, Dr. Roughgarden said that the effects of selfishness are most pronounced in a crowded road system or a communications network working at or close to its capacity. One antidote to selfish routing, the two researchers found, is more capacity. Optimum overall system speeds can be restored despite selfish routing by either doubling the number of lanes on a highway or doubling the bandwidth of a communications link. Particularly in the case of roads, however, that is rarely practical or even desirable. The researchers also did calculations to see what would happen if selfish drivers and selfish routers were forced to think of others. That is, they forced a conceptual router to consider the impact that sending its packets down a less congested route would have on other routers' packets. Before making a decision, the router had to deduct all the delays it would cause others from the potential time savings offered by a shortcut. To their surprise, Dr. Tardos and Dr. Roughgarden found that introducing such "altruistic routing" brought a network up to its optimum speed. For the Internet as a whole, their findings may not have much impact. "Even if it would tremendously improve the Internet, the logistics of getting it deployed may be insurmountable," Dr. Roughgarden said. He suggested that the findings could have some application within small self-contained networks. They could, for example, lead to proposed systems for improving the delivery of video and other delay-sensitive data by introducing special routers that use the Internet to create a secondary network, he said. Not all researchers are persuaded that selfish actions by routers have much effect on the Internet's speed. "It's not a drastic issue," said Eric Friedman, an associate professor in the School of Operations Research and Industrial Engineering at Cornell. He said that congestion controls already exist in the structure of the Internet. "But I think selfish routing is problematic for other reasons," he said. In a paper, Dr. Friedman has argued that selfish routing can make the Internet unstable. His favorite analogy involves bars and drinkers rather than motorists and highways. "The stability problems come from people's reactions to each other's behavior," he said. He starts with two neighboring identical bars. The first night, one is extremely crowded and the other is nearly empty. The chances are good that the following evening most people will switch locations to avoid the crush of the crowd, Dr. Friedman said. The result, of course, is that they bring the crowd with them. So the following night, the crowd shift will occur again. This flipping back and forth between the bars - or routes on the Internet - can potentially spin out of control. In one experiment, he had students use laptop computers to choose the speeds at which fictional data packets were transmitted. The catch was that if too many players used high speeds, other players would be negatively affected. The group never found a pattern that brought balance. "They never seemed to settle down," Dr. Friedman said. "They kept hitting each other on the head with a hammer." As for Dr. Roughgarden, he is sticking with the commuter analogy. His latest work centers on the impact that tollbooths of the theoretical variety might have on Internet traffic. http://www.nytimes.com/2003/04/24/technology/circuits/24next.html?ex=1052222 547&ei=1&en=5fed303bc02c8957 HOW TO ADVERTISE --------------------------------- For information on advertising in e-mail newsletters or other creative advertising opportunities with The New York Times on the Web, please contact onlinesales () nytimes com or visit our online media kit at http://www.nytimes.com/adinfo For general information about NYTimes.com, write to help () nytimes com. Copyright 2003 The New York Times Company ------ End of Forwarded Message
------ End of Forwarded Message ------------------------------------- You are subscribed as interesting-people () lists elistx com To manage your subscription, go to http://v2.listbox.com/member/?listname=ip Archives at: http://www.interesting-people.org/archives/interesting-people/
Current thread:
- Like a Swerving Commuter, a Selfish Router Slows Traffic -- Is this another case of PR science? Dave Farber (Apr 25)