Slashdot Mirror

← Back to Stories (view on slashdot.org)

'Selfish Routing' Slows the Internet

Posted by ryuzaki0 on from the love-thy-neighboring-router dept.

Smaz writes "Science Blog reports that a little love could speed things up on the Net. "Self-interest can deplete a common resource. It seems this also applies to the Internet and other computer networks, which are slowed by those who hurry the most. Fortunately, say computer scientists at Cornell University in Ithaca, N.Y. , there is a limit to how bad the slowdown can get. And after developing tools to measure how much the performance of a particular network suffers, they say, the way to get improved performance on the Internet is the same as the way to maintain air and water quality: altruism helps."

9 of 249 comments (clear)

  1. If there's anything the Internet has taught me... by Anonymous Coward · · Score: 5, Funny

    If you've got to rely on the goodwill of others to get by, you're totally screwed.

  2. Are we sure... by creative_name · · Score: 5, Funny

    ...that this isn't the guys at Cornell just trying to capture more bandwidth for themselves? Seems like a good idea to me.

    Me: Don't use as much bandwidth and everyone will go faster!
    World: Hey! That seems like a good idea.
    Me: (aside) Mwuhahahaha

    --
    Posting as directed.
  3. I'm confused by hackwrench · · Score: 5, Funny

    Somehow the only conclusion I could draw from the article is that using the network slows it down. Right, so could somebody explain what the article is trying to say?

    1. Re:I'm confused by Randolpho · · Score: 5, Informative
      The author is not trying to say "those bastards over at network X are selfish and they're slowing us down" or anything like that. He's trying to point out that a fundamental aspect of internet routing, the concept of forwarding a packet via the fastest route to the destination, can in many cases slow down performance if the fastest route gets congested.

      Frankly, I'm surprised this is considered news; I learned it in a networking course on my way to a CS degree. I can only assume that the author is trying to push a new algorithm for congestion control and is using "selfish routing" as a marketing scheme. The thing is, I can't seem to find the suggested reprieve.

      Ahh, here it is:
      Roughgarden has a suggestion that wouldn't be expensive to implement. Before deciding which way to send information, he says, routers should consider not only which route seems the least congested, but also should take into account the effect that adding its own new messages will have on the route it has chosen. That would be, he says, "just a bit altruistic" in that some routers would end up choosing routes that were not necessarily the fastest, but the average time for all users would decrease.
      --
      "Times have not become more violent. They have just become more televised."
      -Marilyn Manson
    2. Re:I'm confused by zackbar · · Score: 5, Insightful

      I'm confused too.

      The article states that computers test the routes, and pick the least congested route to use. Thus, it slows everything down for everyone.

      What should it do? Pick the MOST congested route?

      Either I'm just confused, the author didn't understand the situation correctly, or the whole thing is BS.

  4. Thanks Ron Howard by scotay · · Score: 5, Funny

    Eventually the system will settle to an equilibrium that mathematicians call a Nash flow, which will be, on the average, slower than the ideal.

    If nobody goes for the blond, we all get laid. Somebody go tell the routers.

  5. Is altruism still possible on the Internet, tho? by juanfe · · Score: 5, Interesting

    Given the growth of walled gardens, of email attacks, of DoS, of more traffic channeled through fewer fat pipes owned by fewer public/non-profit organizations, is this still possible?

    --
    ***Foucault is watching you..***
  6. Classic Prisoners Dilema problem by acomj · · Score: 5, Interesting
    This is a classic example of the prisoners dilema problem.

    Basically if everyone acts unselfishly they do better. But from each individuals perspective they do better when they act selfish, so it all falls apart. Its interesting stuff and the prisoners dilema game algorithms are interesting.

    Prisoners Dilema

    Play the dilema game online

  7. Summary of main results. by obnoximoron · · Score: 5, Interesting

    of the main paper : http://www.cs.cornell.edu/timr/papers/indep_full.p df and others.

    1. Their basic idea is to model decentralized routing as a Nash game and then worst-case compare the performance of this game with the best achievable by ANY algorithm, decentralized or not. This sort of comparison is common in the field of competitive analysis .

    2. Assuming a hop latency to increase linearly with additional traffic on it, selfish routing causes the average packet latency to increase by no more than 4/3 of that caused by ideal optimal routing. This worst-case figure had been earlier called "the Price of Anarchy" by Papadimitriou, a famous researcher in algorithmic complexity who every CS student loves to hate :P

    3. Similar Prices of Anarchy have been derived by them for when the hop latency increases nonlinearly with the additional traffic on it.

    4. The worst case is always achievable with a simple network of 2 nodes connected by parallel links. This is the exactly the example used in networking courses and textbooks to illustrate the oscillation problem caused by selfish routing. This paper says that using this simple network as example is justified since the worst case can be always be analysed with it.

    5. Instead of optimizing routing to try reach the minimum possible average latency, you can keep the routing selfish but double each link capacity and achieve the same result.