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."
If you've got to rely on the goodwill of others to get by, you're totally screwed.
another resource depleting mechanism known as "Slashdotting"
__________
[Big Brick Wall]
...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.
Reasearch networks are particular well at this sports: For example, the German Research Network (DFN) has a strict anti-peering policy. GÉANT, a European research network, appears to accepts only links to a single research network operator in each member country.
Of course, the most important aspect of such networks is that the bandwidth they offer is helpful in Dick Size Wars at supercomputing conferences, so it's not a terribly loss for the Internet at large.
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?
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.
Maybe I am just a lowly CCNP but is this all just a theory paper about the problems with "routing" or were there specifics about current routing protocols that should be updated or current practices that should be changed. Please help, everyone knows that the current routing could be better but theory stuff just does not help us much.
'Cool! One meg left! .......huh? WTF?!!? Disconnected?! You dirty SOB!..FUUuuuuuuuccCCCKKK!'
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..***
It seems the researchers at Pinko U finally realize that routers have always been programmed using the enlightened-self-interest model of bandwidth utilization. It's time to shut them down.
The last thing we need is lazy, welfare dependant internet backbones sitting around all day watching The Dukes of Hazzard and drinking Lite Beer. If the altruists win this round, AOL transforms from the gated-suburb of the internet into the "Projects". Aren't we taxed enough?
It basically says that network congestion is like congestion on highways. If everybody is trying to change lanes all the time, they might save a bit of time for themselves, but on the whole they will slow down traffic for everybody.
In theory, this may slow down the internet by something like 50-60% at most. Nobody really knows how well the Internet conforms to the mathematical model, however. Any benefit from trying to fix the problem might be outweighed by the cost of implementing a solution.
"If I could live to be several hundred
I could take a walk and really wander, really wonder."
this is why I hate download managers, especially ones that create dozens of connections to download segments of large files.
My flatmate does that with eDonkey on TWO of his computers and squashed our bandwidth for a week (downloading pr0n of course)
"I would say that 99 per cent of what my father has written about his own life is false." - L. Ron Hubbard Jr.
I suppose this is the heart of the article, btw:
:-)
"if routers choose the route that looks the least congested, they are doing selfish routing. As soon as that route clogs up, the routers change their strategies and choose other, previously neglected routes. Eventually the system will settle to an equilibrium that mathematicians call a Nash flow, which will be, on the average, slower than the ideal. "
Now, hasn't there been a problem some time a long time ago in early Internet history where parts of the internet entered a state of self oscillation. I recall this was later fixed somehow to a point by revising some protocols.
I remember it basically as the problem where lots of routers (for some reason) started sending packets to one path, it got very congested, all routers switched to another, congested, etc.
I only have very vague memories since I took the course where I heard it some years ago. Perhaps I'm only full of bullshit.
Beware: In C++, your friends can see your privates!
If the "altruistic" behavior results in a better network, then isn't there a benefit for the altruistic behavior? Doesn't it cease being altruistic if there is a benefit? Aaggh! I'm caught in another Prisoner's Dilemma with an uncertain number of moves!
Where's my Dawkins? (That's twice today I've thought of him).
GF.
Lots of petrified grits
I would have had first post but it got stuck in a jam in Toronto.
Modest doubt is called the beacon of the wise. - William Shakespeare
It appears that they are claiming routers pick the fastest route to push packets down, which can in turn cause that route to become congested, thus slowing it down, and then the router picks a new route, causing it to become congested and slow down, and so on.
Supposedly, if the router picked the fastest AND least congested route, then some packets might take a little longer to get to their destination, but the overall latency of the internet would decrease.
In theory. In reality, I don't know how much peering arrangements change the equation. You see, if you are a network provider, you have two goals with peering: dump enough traffic onto your peer points so that you are exchanging about equal amounts with your peer AND get traffic that isn't bound for your network OFF your network as quickly as possible.
In practice, this means ISPs who peer have a large incentive to route packets coming from peer parter A directly to peer partner B, without regard for what that does to the latency of the packet, nor the congestion of the peering partners. The peered packets become more like the hot potato, bouncing around peer points until they actually arrive near the destination network. That lowers overall efficiency as well. (companies like Internap don't peer for this reason; they pay for all connection points even though they have enough traffic to get peering points for free. They cost more, but they have very low latency, packet loss, etc).
Natural != (nontoxic || beneficial)
This is essentially a pricing problem.
Here's a quote from the original 1968 paper that used the term
There are two common solutions to this kind of problem. Regulate use of the common resource or sell it. Because of the structure of the internet, it is hard to fairly price bandwidth and no good regulatory scheme has developed, so I don't see any other answer than living with it.
I like my beverages with warning labels!
In many (but certainly not all), Internet traffic is similar to automobile traffic. Packets are discrete objects, like cars, and not continuous like a river or radio signal. Analysis on automobile traffic has already discovered properties like this. There are many simulations that show if we all ensured 3 car lengths between us and the next car, we would avoid the accordion and get to work significantly faster.
This article makes no sense from a proper real world routing perspective.
Any provider who is doing anything slightly serious will be using BGP4 routing for their EGP. It does NOT send out magic packets to find best paths. It learns routes from it's peers and will choose the best route based on a defined set of decisions. Routers do not keep a list of "neglected routes." If one route goes away, the router will simply pick the next best path.
Read more about BGP4 from Cisco's website. You will find little in common with this article and the one linked in the story.
Good routing relies on good admins with a well defined routing policy. There is no such thing as a "selfish" router.
Tim
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
Actually, just think about it from a larger perspective. There are many independent routers out there, and they each decide how to route their traffic simultaneously. Now, imagine that the least congested path (#1) is only slightly better than other potential paths. The problem is that _everyone makes the same decision_ and chooses this one path for their traffic. The result is congestion on the one popular path everyone chose. If that was the only effect, nobody would really care - but here's the catch : at the next time interval the same thing is likely to happen again! Everyone chooses #2 on the list, since #1 is now toast. They all crash into each other.
At the same time, I don't see how their suggestion really helps things that much. If everyone uses the same deterministic algorithm to choose a path, this sort of mass collision is still likely to happen (although it should happen less often with more complicated algorithms). I think that overall network performance would benefit from a little randomness in the routing algorithms. I'm not a CS, so there is probably already a random component that I don't know about.
In Soviet America the banks rob you!
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.
of the main paper : http://www.cs.cornell.edu/timr/papers/indep_full.p df and others.
:P
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
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.
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.