ZDNet UK / News and Analysis / Workspace IT / Desktop Hardware

'Selfish' routers slow the Net

By Sandeep Junnarkar, CNET News, 17 February, 2003 11:23

Daily Newsletters

Sign up to ZDNet UK's daily newsletter.

Topics

selfish, neck, bottle, Tardos, Roughgarden, slow, Network, Router, EVA, tim

NEWS
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 also allowing other packets to move more quickly. Eva Tardos and Tim Roughgarden described their work last 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 counter-productive 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.
Networks and networking products have seen huge innovation and growth in the last few years. High bandwidth LANs and Storage Area Networks are now in common use. ZDNet UK's Networking Central keeps you up to date with the latest news and views. Let the editors know what you think in the Mailroom.

Related stories

Survey: Web use trends ever upward

Protocol holds out faster Web services promise

Apple bucks a falling PC trend in UK and France

Apple takes top PC spot from HP

Post your comment

In order to post a comment you need to be registered and logged in.

You can also log in with Facebook. Log in or create your ZDNet UK account below

  • Login

Will not be displayed with your comment

By signing up for this service, you indicate that you agree to our Terms and Conditions and have read and understood our Privacy Policy. Questions about membership? Find the answers in the Community FAQ

Get ZDNet UK's daily newsletter

Enter your email address to sign up

ZDNet UK Live

GrueMaster

Nice review and very informative. One thing I'd like to add (in reply to whs001's 1st question), the main reason to have the same interface from...

6 minutes ago by GrueMaster on A tale of two distros: Ubuntu and Linux Mint
Frederick Wrigley

I'be been using Mint 12 since the RC came out, and I am far more happy with the Cinnamon, the Mate, and, yes (with extensions), theGnome 3...

53 minutes ago by Frederick Wrigley via Facebook on A tale of two distros: Ubuntu and Linux Mint
bdantas

Excellent article. One small correction, though--although a fresh installation of Linux Mint 12 will, indeed, provide the user with a version of...

2 hours ago by bdantas on A tale of two distros: Ubuntu and Linux Mint
Alan Ralph

In related news, the ISPs club together to get the members of the Home Affairs Select Committee (ya goofed on that part, ZDNet UK) copies of "The...

2 hours ago by Alan Ralph via Facebook on MPs urge ISPs to take down terrorist material
Alan Ralph

In related news, the ISPs club together to get the members of the Home Affairs Select Committee (ya goofed on that part, ZDNet UK) copies of "The...

2 hours ago by Alan Ralph via Facebook on MPs urge ISPs to take down terrorist material
Moley

For Gnome 2 die-hards, it is possible to add icons to the bottom panel (or top top panel, if you prefer) which provide the exact Gnome 2...

3 hours ago by Moley on A tale of two distros: Ubuntu and Linux Mint
ramwellian

Your comments would seem pretty naive and immature. Your 'solution' appears to be, "gee, let's all just give in to the hackers and give them...

3 hours ago by ramwellian on Cloud computing security: no more oxymoron?
BugStalker

"Interesting thought ... If you installed Win7 as a dual boot on a machine that previously only had Linux, and it wrecked your Linux installation,...

3 hours ago by BugStalker on Windows 7 Declares War on GRUB
whs001

This is an excellent summary of Ubuntu and Mint and the interface differences between them. Most such articles take a very partisan position for...

4 hours ago by whs001 on A tale of two distros: Ubuntu and Linux Mint
Moley

@ewallace. Not so clear. Anyone can obtain the text, for example from here http://www.ustr.gov/webfm_send/2379. I support ACTA so long as it and...

4 hours ago by Moley on ACTA: Facts, misconceptions and questions
45283

I think WinRT is fantastic. I just wish it was an option for people that didn't want to go through Microsoft's App Store with its attendant...

7 hours ago by 45283 on Why Windows 8 needs architectural hygiene for WOA
Burn-IT

Nine people? £30m? Who's back pocket is that lot going in? And IF they say it is for new buildings, what about all the ones the government has...

8 hours ago by Burn-IT on Police set to launch three £30m e-crime hubs
ewallace

Just to be clear, nobody knows what is in the text of ACTA, here is a photograph of the text of ACTA http://twitpic.com/8h9iju as submitted to the...

8 hours ago by ewallace on ACTA: Facts, misconceptions and questions
fgvrg56

Unfortunately main issue is that ASUS is refusing to accept that they make some mistake on this version of asus Transformer prime. 1 - GPS sensor...

9 hours ago by fgvrg56 on Asus Eee Pad Transformer Prime Wi-Fi & GPS problems?
Ben Woods

@Marcus A fair question. Just talked with Archos which said it was working on an announcement for next week....

10 hours ago by Ben Woods on Archos confirms G9 Ice Cream Sandwich update schedule
Marcus Karlsson

Any update on this, considering the claimed "first week of February"?

12 hours ago by Marcus Karlsson via Facebook on Archos confirms G9 Ice Cream Sandwich update schedule
apexwm

Bill Goodrich : Just as al_langevin pointed out, with Windows Server 2008 there is no Services for Macintosh anymore. It's gone, not available....

20 hours ago by apexwm on Windows Server 2008 drops the ball for Mac compatibility
txtrainguy

Replying to an old topic that I'm currently facing with my CEO (who is on a Mac). Our servers are primarily Windows Servers, office is about...

1 day ago by txtrainguy on Windows Server 2008 drops the ball for Mac compatibility
k0tcs3

Sure, that makes perfect sense. Pay wrong-doers money and thank them for breaching your security and pointing out your flaws, that would surely...

1 day ago by k0tcs3 on US indicts Romanian over NASA climate change hack
Random_Error

I think he's referring specifically to Android apps, as Apple do regulate their App Store, but Google seem to let any old crap onto the Android store!

1 day ago by Random_Error on RIM: BlackBerry will keep 'garbage' apps out of store

Latest in Desktop Hardware

Apple bucks a falling PC trend in UK and France

Apple takes top PC spot from HP

Featured white papers

Tech breakthroughs to watch in 2012

ZDNet UK

Tech breakthroughs to watch in 2012

From invisibility cloaks to virtual atom smashing, from Cern to Nasa, this ZDNet UK guide presents the discoveries to watch in... Read more

10 must-read silicon.com Cheat Sheets

silicon.com

10 must-read silicon.com Cheat Sheets

This exclusive e-book covers 10 of the most important issues facing business and technology professionals today, from cloud computing to... Read more

The virtual presenter's handbook

Citrix Online

The virtual presenter's handbook

Web seminars or webinars can be interactive and engaging, just like having every person in the same room, and this white paper outlines how they can benefit your... Read more

Inside ZDNet UK

A tale of two distros: Ubuntu and Linux Mint

A tale of two distros: Ubuntu and Linux Mint

2012 Predictions: VCE FastPath, VI SAN Probe & Hadoop

2012 Predictions: VCE FastPath, VI SAN Probe & Hadoop

BlackBerry Bold 9790

BlackBerry Bold 9790

Case study: How cloud enables growth

Case study: How cloud enables growth

Ten factors that make Ubuntu 11.10 a hit

Ten factors that make Ubuntu 11.10 a hit

Toshiba Portégé Z830-10P Review

Toshiba Portégé Z830-10P Review

BT's archive: Pictures from the vault

BT's archive: Pictures from the vault