Like a Swerving Commuter, a Selfish Router Slows Traffic -- Is this another case of PR science?

[Dave Farber <dave () farber net>]

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/