Slashdot Mirror
'Selfish Routing' Slows the Internet
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."
'the internet' is faster then my connection to it, does it really matter?
The Kruger Dunning explains most post on
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.
Really?
I pledge allegiance to the flag...
of the Corporate States of America...
The problem is not that service providers pick the route that gets the packet to its destination quickest; it's that they pick the route that gets the packet off their network the fastest. Those two are not the same thing at all. Think about it geographically. Let's say I'm a square network and I receive a packet at the northern end of my western border destined for somewhere to my northeast. I know that the quickest way to get it to its destination is to move it east across my own network and deliver it to my eastern neighbor. However, I also know that if I pass it on to my northern neighbor it will still get there without coming to me again, and my northern neighbor is closer. So, if I'm a selfish bastard, what do I do? I ship it northward, minimizing the time that it spends on my own network but increasing the total time before it reaches its destination. If everyone does this same sort of "hot potato" routing, total load on the network increases for everyone. In fact, my northern neighbor might very well be doing the same for packets lying to our southwest. We'd both be better off if we'd "play nice" but since we're both trying to be selfish we both lose.
Yes, folks, it's an instance of the prisoners' dilemma and these researchers are not the first to notice the fact.
Slashdot - News for Herds. Stuff that Splatters.
my home setup
LAN switch DSL modem ISP world
we have sDSL all routable IPs, at about 80-100K in any direction
i have no way to throttle anything when he is running eDonkey, downloading 5-10 movies at once with over a dozen connections between each. i dont believe eDonkey allowes any kind of throttling, unlike Kazaa.
I lost entire messages over AIM while he was doing that shit.
my http server is set up to allow only 5 connections max now, sincew someone a few months ago started leaching movies from me with FlashGet, killing my own overall speed.
Sure its not related to the article, but when i saw 'selfish' and 'routing' I had to rant a bit.
"I would say that 99 per cent of what my father has written about his own life is false." - L. Ron Hubbard Jr.
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.
Thank you. I was sitting there reading it, thinking "this sounds like a load of shit. Either I am a blithering idiot (entirely possible) or this article is worthless."
Its sounds like a purely acedemic exercise that is being underwritten by someone with too much money, that has NO practical application.
Glad to know I'm not alone in the confusion.
Tequila: It's not just for breakfast anymore!
How does this get modded insightful?
You must be new here.
It's not so much a theory piece as it is a GROSS misunderstanding, on the author's part, of the design principles behind the internet in the first place.
... capable of suvivng a nuclear attack) ...
... it reads, to me, that he's complaining because the defined routing protocols work THE WAY THEY"RE SUPPOSED TO. Well, DUHH!
The internet isn't, wasn't, never has been intended to be a high-performance network. It IS and was intended to be a high-availability network (read
One of the ways the 'net accomplishes this is by detecting damage and routing around it by trying to always use the "lowest cost" route from point A to point B. A significant factor in "lowest cost" is least time.
By always seeking to use the fastest (or most efficient by some other measure than time) route from point A to point B, performance levels on the 'net get leveled out and really fat pipes draw lots of traffic, while "pin-holes" don't.
For the life of me I can't understand just what the hell the author's complaint is
Just my US$0.02
utter rubbish
Ipv6 supports better Qos so if the fastest route is congested the router can more easily find out and select an alternative route.
Internet2 has an extremely fast backbone and is based on Ipv6. This will help greatly since the backbone of the current internet can be quite congested at times. Lets hope its implemented soon as the current problem will likely go away.
http://saveie6.com/
I mean, the metrics a network uses to determine the best route are not at
all necessarily what is fastest, or what is closest..... it can be completely arbitrary.
Lowest latency, least used, least hops, least dollar cost, etc.
Some networks try to offload traffic to other networks as fast as possible. Others try to get data as close to the destination as possible before offloading it. In both cases, everything would work fine, if only everyone played by the same rules.
Ok, this has to be the most convoluted article I've ever read.. They're effectively saying, don't use the best route, pick another, because your extra traffic may break the best route.
:)
We diagramed a sample network here in the office, to try and explain what we just read to ourselves.. We picked 5 cities (New York, Chicago, Los Angeles, Dallas, and Miami), and drew direct routes between Miami, LA, and NY to each other. Chicago gets routes to NY and LA. Dallas gets routes to everything but Chicago.
We then contemplated what a packet from LA to NY would be looking at.
On our mythical network, we have the following ping times.
LA -> NY 20ms
LA -> Chicago -> NY 25ms
LA -> Dallas -> NY 40ms
LA -> Miami -> NY 60ms
So, we shoudn't be selfish, and take the LA->NY route? We should direct our traffic LA->Dallas->NY ? If this route is already slow or conjested, what good does that do? Now instead of using a perfectly good route, we're killing a conjected one.
If LA->NY is the best/fastest at the time, use it. If/when that becomes more conjested, it will no longer be the best choice, and the new best choice will be chosen..
Not everyone is going to be using YOUR best choice all the time.. Very doubtful that Miami will be routing to LA to go to NY. If they do, it's because Miami->LA is already overloaded. But as it usually works, For Miami->NY, there is already a second best choice (Miami->Dallas->NY).
No matter how we look at it, this doesn't make any sense.. Here's a sample of the lines for our example.
LA->NY OC192
LA->Chicago OC48
Chicago->NY OC48
LA->Dallas OC48
Dallas->NY OC24
So, we'll leave the LA->NY route empty, and keep dumping our load onto the lesser routes?
I do like the idea though, to keep the best choice (LA->NY) open for myself.. Everyone else chooses the second best route.. Go ahead and flood those OC48's, I'll use the OC192 that no one else uses..
Serious? Seriousness is well above my pay grade.
The same observation applies to the problem where traffic alternates between two routes rather than dividing itself evenly. That is elementary control theory. The problem is that the response has too high a gain factor, in effect the gain factor is infinite so instead of being shared across the routes the system is going into oscillation.
The control theory you refer to is for linear systems with feedback. Routing is a highly nonlinear system and the analysis is much harder. However the basic concept of high gain leading to oscillation is the roughly the same. Multicommodity flow theory researchers have been working on flow allocation and stability for years. Recently this work has caught the attention of the MPLS crowd in IETF.
You are right about IETF inertia though. I have given up on any bold progressive thinking in IETF for now with their attitudes such as "If it basically works, why fix it?"
Is unfortunate proof that altruism breaks down on a large scale. This is the fundamental flaw of socialism - humans evolved from simian ancestors, who basically lived in small tribal groups. We are altruistic up to a maximum of about 75 or so individuals, then it breaks down.
I have seen videotape of a psychology experiment, where an individual feigned a serious medical problem and keeled over in the middle of the street. When the test subject tried this on a busy urban thoroughfare, large passing crowds actually stepped over the guy. But in a small village, shopkeepers rushed out onto the street to try and help him.
There was a famous murder case in NYC where over 100 neighbours heard a woman begging for help as she was having her life snuffed out over a sadistic killer over a period of time. Nobody reported it or tried to intervene, they all assumed somebody else would do something about it. This resulted in the passage of a law, which as I recall was the subject of the final Seinfeld episode.
My rights don't need management.
What you're really relying on is the selfishness of the hardware. If the hardware itself did something different, then the people that bought them would live with that. Case in point is ethernet devices.
Each of these has an altruistic collision avoidance method: when a collision happens, stop sending and wait a random amount of time before sending again. A selfish ethernet device would always immediately attempt to send under the assumption that the other device would be waiting, and it would get to go first. But of course, that's very bad for the network, so it's not done.
The fact that we've got selfish routers is not a sign that they're selfish, per se, but that selfish routing is somewhere near the most effective a means of communication that they could think of at the time when they where invented.
Mod me down and I will become more powerful than you can possibly imagine!