Selfish Routing
February 17th, 2003 | by Tony Steidler-Dennison |This article on ScienceBlog.com poses an interesting question on Internet use while drawing a comparison to the Tragedy of the Commons.
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.
A similar behavior on a computer network is “selfish routing,” where each routing computer tries to send data via the fastest route, causing that route to become the most crowded and slow down. You don’t have to understand computer networking to grasp the concept. It also happens on highways: If everyone takes the express lane, pretty soon the local route is faster.
The solution proposed for this problem is that routers should consider not only the traffic on a given route, but the impact of the increased traffic on that route. Theoretically, this would create a more “altrusitic” system that both decreases traffic on specific routes and increases average throughput for users. It’s an interesting way to look at Internet use and the current routing structure.
6 Responses to “Selfish Routing”
By Greg on Feb 17, 2003 | Reply
I don’t see the problem, frankly. I thought that the whole point of a router was so that not one path got too crowded. So, by my thinking, if one pathway gets crowded, then another one opens up. The same on the highway, like you said. If everyone takes the express route, then the other ways will be faster. That’s the whole point!
Maybe I just don’t get it.
By joseph castleschouldt on Feb 17, 2003 | Reply
I read the term Nash flow and was saddened. I wonder what John Nashs contributions would have been if his mind hadn’t failed him at his most prolific time.
I’m surprised the internet works as well as it does. There are lot of brilliant hardworking people keeping it up. And, I thank them.
By MasterRa on Feb 17, 2003 | Reply
Hey.. nice new look Tony. It’s even more broken in IE5@800×600
By Sean on Feb 18, 2003 | Reply
“So, by my thinking, if one pathway gets crowded, then another one opens up.”
That was one of the points of the article. One pipe gets full, so routers choose another path. Eventually that pipe gets full, they choose another path. The steady-state of this ends up being something much less than optimal.
By Greg on Feb 18, 2003 | Reply
Ok, I just reread it and I get the point now. By evenly distributing traffic, rather than just cramming all in the fastest route, the average speed for all (hence, the term “altruistic”) improves, even though one or two may be a little slower. Ok.
By Matt on Feb 19, 2003 | Reply
You’re quite right you don’t get it.
say I have two pipes, both lead to the same place.
1 pipe takes 1 second (when empty) to send a ball from my end to the other.
The other one takes 1.5 s(again when empty)
me and three other people are wanting to chuck balls down as fast as possible. But we don’t talk to each other.
To start with we see the fast pipe and go ‘wahey’ lets chuck everything down here.
At a certain point the number of balls we chuck interfere with each other to the point that it takes 2 seconds (or more) on the first pipe. We all at pretty much the same time say ‘I could be faster on the other one’ and start chucking _all_ our balls down the other.
This rapidly leads to it taking 2 seconds and again we all pretty much at the sae time take the decision to go for the *locally* (both in time and in terms of self) optimal step of switching pipes.
Over time this leads to balls taking around 2 seconds to get there on average.
If we had talked to each other we could have said. hey two of use use the fast pipe and one the slow and we will all get an average of about 1.5 (with big numbers it’s much easier to get a balance that is fair) that’s better than 2.
this is not truly altristic. One way is if one of the users took a worse performance than the others for the good of the group (even though you could still say that if they were 1.6 and we were 1.5 then they are still beating what would happen if we all got 2)
the other is pure altruism and is one user saying ‘I’m less important I’ll take a path with cost higher than I’d get if we competed but you guys get much better.
This is more a case of quality of service considerations though.
People tend to be hugely selfish in their decisions and this can cascade to others (witness the number of people who sit in the middle lane thus causing you to spend more time in the fast lane thus holding up others in that lane)