Slashdot Log In
'Selfish Routing' Slows the Internet
Posted by
michael
on Fri Feb 14, 2003 04:06 PM
from the love-thy-neighboring-router dept.
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."
This discussion has been archived.
No new comments can be posted.
The Fine Print: The following comments are owned by whoever posted them. We are not responsible for them in any way.
Full
Abbreviated
Hidden
Loading... please wait.
If there's anything the Internet has taught me... (Score:5, Funny)
Re:If there's anything the Internet has taught me. (Score:4, Insightful)
Parent
The phenomenon is dwarfed by... (Score:4, Funny)
Are we sure... (Score:5, Funny)
Me: Don't use as much bandwidth and everyone will go faster!
World: Hey! That seems like a good idea.
Me: (aside) Mwuhahahaha
Research networks (Score:5, Funny)
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.
I'm confused (Score:5, Funny)
Re:I'm confused (Score:3, Interesting)
The article is not saying that using the Internet slows it down (that much is obvious). It's saying that with different routing techniques and the same level of use, it could go faster. So, using it slows it down, but so does building a bad infrastructure for it.
Re:I'm confused (Score:5, Insightful)
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.
Parent
Re:I'm confused too! (Score:5, Informative)
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.
Parent
Re:I'm confused too! (Score:4, Interesting)
I've worked with our provider a bit with routing. We have mirrored servers in colo's around the country. If one city is conjested, we move traffic *AWAY* from the conjestion. Usually our traffic makes a difference for everyone else. I can have 500Mb/s added or removed from any given city within an hour, without flinching. Of course, before I do something like that, I put in a call first.. "Hey, can this city take 500Mb/s right now?"
We wrote a program to take traceroutes from all the cities to various points, and plot them all onto a big network map, with ping times and the like.. We know which cities, peerings, or lines have problems at a glance..
http://www.voyeurweb.com/network.12.23.2002-11h.p
Warning: This picture is *BIG*. It's of our networks in Los Angeles, New York, Tampa, between each other, and to all of the root nameservers.. It makes a rather extensive map that is 11580x2669. It won't fit on your screen. Save it, and take it into your favorite image editing software to view it..
This map is a little old (Dec 23, 2002 at 11am), but it gives a good impression of what the networks immediately around our servers looked like, and how they interact with each other.. Shitty networks stand out in red.. I definately wouldn't want to MORE of my traffic that way. Sometimes we don't have a choice. If your ISP uses a shitty provider, we have to send it that way..
Parent
Re:I'm confused (Score:5, Informative)
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:
Parent
Re:I'm confused (Score:5, Informative)
Yep, if you have three available routes A, B, C with bandwidths 10, 4 and 1 the selfish router would send all trafic through route A in every case. An altruistic router would make a random choice between A, B, C such that A was chosen 2/3rds of the time and B, C were chosen in proportion 4:1 the rest of the time.
You can then tweak further by using traffic information. If the system is unloaded then use A all the time.
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.
There is an obvious solution to that problem, you measure the change in the traffic statistics and moderate your response to changes.
This is the sort of thing the IETF should be doing. Unfortunately the IETF has been out to lunch for many years now. They have failled to respond with any urgency to most of the issues facing the net. Most of the participants seem to use it as a substitute social life rather than as a place to get things done.
Parent
Thanks Ron Howard (Score:5, Funny)
If nobody goes for the blond, we all get laid. Somebody go tell the routers.
Re:Thanks Ron Howard (Score:4, Interesting)
Parent
Re:Thanks Ron Howard (Score:4, Informative)
As has been pointed out [variagate.com], the movie got the Nash equilibrium principle entirely wrong. Since a cheater can benefit by going for the blonde at the last minute, after the other guys have already committed themselves, it's not an equilibrium.
Parent
Another article (Score:4, Informative)
Could the bloody writer be specific (Score:5, Interesting)
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.
Re:Could the bloody writer be specific (Score:5, Funny)
No, it's no longer "CCNP"; the Soviet Socialists are now calling themselves the nationlists, the Union is gone, and the country's just named Russia.
But thanks, "Comrade". We'll open a dossier on you anyway.
Parent
Re:Could the bloody writer be specific (Score:3, Informative)
Which although I have not even starte to read it yet appears to have more than enough detail to satisfy almost anyone. Have fun I know I will.
Re:Could the bloody writer be specific (Score:4, Insightful)
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
Parent
Please send this article to (Score:5, Funny)
'Cool! One meg left! .......huh? WTF?!!? Disconnected?! You dirty SOB!..FUUuuuuuuuccCCCKKK!'
Re:Please send this article to (Score:3, Funny)
Don't worry, I read it. But I'm still not changing.
Although I had a sad revelation last night, after saying to a friend "Yeah, hopefully when I get back from work tomorrow night those music videos will be finished." I then realized the interest of my Friday night is determined by whether or not my Utada Hikaru MTV Unplugged (JP) videos will be completed.
I then realized I must get out more. Good thing my girlfriend gets back on Thursday...
Is altruism still possible on the Internet, tho? (Score:5, Interesting)
Objectivists Unite (Score:4, Funny)
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?
For those too lazy to read the article ... (Score:5, Interesting)
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.
Re:For those too lazy to read the article ... (Score:5, Interesting)
There's an amusing, if not somewhat interesting, article writting up on how you can single-handedly relieve traffic congestion here:
http://www.amasci.com/amateur/traffic/traffic1.
It's basically the same idea: If a few people just give a little slack, everybody wins out.
=Smidge=
Parent
Re:For those too lazy to read the article ... (Score:3, Funny)
scary how much thought this guy has put into it....but i bet the transportation department would fund him to do a study
DL managers (Score:5, Funny)
My flatmate does that with eDonkey on TWO of his computers and squashed our bandwidth for a week (downloading pr0n of course)
Re:DL managers (Score:3, Interesting)
The problem the paper is describing is at the larger "router's eye view" scale, where multiple routes out to the rest of the network exist, and where only the fastest route is used - the other two pipelines are basically starved of packets.
Re:DL managers (Score:3, Insightful)
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.
Hasn't something similar happened in the past? (Score:5, Interesting)
"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.
Re:Hasn't something similar happened in the past? (Score:3, Interesting)
Altruism is actually selfish (Score:5, Funny)
Where's my Dawkins? (That's twice today I've thought of him).
GF.
You selfish bastards! (Score:5, Funny)
Somewhat interesting (Score:5, Informative)
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).
as long as (Score:3, Insightful)
Tragedy of the Commons (Score:4, Interesting)
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.
what routing protocol are they referring to? (Score:3)
it isn't RIP, OSPF, EIGRP, or BGP. i don't know ISIS, but i strongly suspect these people are talking out of their asses.
Similar to Automobile Traffic (Score:5, Interesting)
This is a very odd article. (Score:5, Informative)
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 [cisco.com]. 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
I would give you all five of my mod points (Score:4, Informative)
I think whoever wrote this article is far removed from the real world. They are finding theoretical problems with the routing protocols we would like to be running. As you pointed out, pretty much the entire backbone is using BGP4 to make routing decisions. And BGP4 doesn't really have any measure of how congested links are, nor how long the latency is. The basic measure of BGP4 is how many different providers (called AS's or Autonomous Systems) a packet might have to traverse.
Hmmm, the router says, is the best route thru C&W->AT&T->Bob's_ISP or just Level3->Bob's_ISP? I'll pick the two hop route. Sure, we all do some manual tuning, where the engineer says "I know the L3->Bob link is slow, so I'll make it look like L3->L3->Bob", but BGP4 is fundamentally a really stupid protocol. In theory. In practice, it works fine almost all of the time.
The most telling quote from the article is this:
They also found that doubling the capacity of the system would provide the same benefits as a managed system.
No shit Sherlock. I could've told you that five years ago. Why do you think QoS is still facing an uphill struggle? It's far cheaper and easier to just keep cranking up the bandwidth than to replace BGP4 with something smarter, or to deploy QoS protocols Internet wide.
Don't get me wrong, I think they are doing great research. It's good to try and figure out what might go wrong with next-gen protocols before the get deployed. But I don't think they are talking about problems on todays Internet.
Parent
tragedy of the commons (Score:4, Interesting)
The Tragedy of the Commons , often cited by environmentalists, describes 14th-century Britain, where each household tried to gain wealth by putting as many animals as possible on the common village pasture. Overgrazing ruined the pasture, and village after village collapsed.
The "tragedy of the commons" that Hardin's article is devoted to is increasing world population. What evidence is there for overgrazing in England before as opposed to during and after the forced transition to private ownership? Most cultures with a common land tradition also have a set of rules for governing land use that avoids such tragedies, for example, irrigation systems in Bali where the farmer who gets the water last controls the water flow. Ones that didn't solve the problem of overuse of resources are conspicuous by their non-existence (Easter Island, some settlements in the Southwest US, some populations on islands in the South Pacific ).
The 'tragedy of the commons' is one of the most misunderstood and overused metaphors of our times. The idea that a system with resources held in common is necessarily unworkable is false --- what is needed is institutions that effectively manage common resources, and such institutions have emerged repeatedly and continue to exist. Often it is when these cultures come into contact with market-oriented societies that the traditional systems are undermined and collapsed. Often what happens is not "the tragedy of the commons" but "the tragedy of failed privatization" in which a traditional management system is destroyed without establishing a viable alternative.
How does this relate to the internet? It's a cautionary tale --- be very very careful when introducing monetary incentives into a system that has previously relied on cooperation and cultural norms.
blog-O-rama [annmariabell.com]
They botched others' ideas (Score:4, Insightful)
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' [brynmawr.edu] dilemma [vub.ac.be] and these researchers are not the first [gildertech.com] to notice the fact [zdnet.com.au].
Re:They botched others' ideas (Score:3)
I didn't say it was going northwest; it was going northeast, and the shortest route would have been "straight across my network". That's all besides the fact that real networks don't have such simple geometry, so line algorithms are utterly irrelevant.
If only. The whole point is that it's not handled that way. Did you look up from your graphics-algorithm textbook to read what I actually wrote?
Classic Prisoners Dilema problem (Score:5, Interesting)
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 [drexel.edu]
Play the dilema game online [plocp.com]
Lets here if for ipv6 (Score:3, Insightful)
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.
Use Poor Routing - Better Performance? (Score:5, Insightful)
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..
Summary of main results. (Score:5, Interesting)
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.
The existance of so much spam (Score:4, Insightful)
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.
Re:Light Precipitation (Score:3, Interesting)
-former employee
pm