'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."

Comments

Another article

[aengblom]

Cnet's got a write up on this too.

Somewhat interesting

[rabtech]

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).

Re:Somewhat interesting

[albanac]

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.

Hi,

This depends entirely on your policy decisions. For example, the traffic engineering that I do at my place of work is based around a cold-potato routing policy rather than hot; that is, we will carry our traffic to the point closest to it's destination, thus keeping it in our network for as long as possible rather than vice versa.

There are arguments both sides of each issue, and it really depends on one's own topology and decision-making criterion.

~cHris

Re:Are we sure...

[ZeldorBlat]

I'd say we have plenty of bandwidth here (Cornell). I believe it's an OC-3, but I'm not sure.

Anyway, this woman (Eva Tardos) was one of my professors for an algorithms course (CS 482). She definitely liked to talk about this stuff in lecture...

Needless to say, I didn't think she was a very good teacher.

Re:I'm confused

[Randolpho]

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.

This is a very odd article.

[BusDriver]

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

Re:Could the bloody writer be specific

[SquadBoy]

Yes it was a very light article but if you had followed the links, well not so much links as URLs, you would have found this. http://www.cs.cornell.edu/timr/ and this http://www.cs.cornell.edu/People/eva/eva.html

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:I'm confused

[Zeinfeld]

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.

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.

Re:Thanks Ron Howard

[JoeBuck]

As has been pointed out, 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.

Re:I'm confused too!

[Zork the Almighty]

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.

Re:If there's anything the Internet has taught me.

[SpectreGadget]

If there's anything the Internet has taught me. is that Mr. George Hull (not P.T. Barnum) was right.

I would give you all five of my mod points

[BeBoxer]

if I could.

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.

Re:Use Poor Routing - Better Performance?

[Anonymous Coward]

Congratulations, you have successfully missed the point.

They're effectively saying, don't use the best route, pick another, because your extra traffic may break the best route.

Nope. They're saying "don't always use the best route."

You should distribute your path amongst these based upon ping time and (more importantly) bandwidth.

If you saturate one connection, you'll have a large number of collisions, but if you distribute your packets among all available connections, over all it will take less time for the packets to traverse the network.

Dijkstra's SPF, MPLS, Offline Weight Optimization

[sireenmalik]

Maybe I did not understand the article but chances are that maybe i did!

For distributed routing every router takes its own decision. SPF is used. Assume OSPF now. Routers
basically set weights on its interfaces/ports. There are two types of weights: static and dynamic.For static weights there is nothing much a router can do except obey (a lazy) administrator's decision.Dynamic weight setting gives a router some freedom. It may set its interface weights depending upon the available bandwidth. It could even penalize congestion by choosing very high weights for loads more than say 95% of the link capacity.

But there is a small problem commonly known as "osciallation". Consider two links A and B connected to a router. Router finds out that A is congested so it sets a high weight on interface A. This leads to shift of traffic from link A to link B. At some point link B will become loaded. Now the router sets interface B weight high.
Question: where will the traffic of link B go now? Right. To link A!! This is oscillation.

MPLE/IP:
In MPLS/IP networks it is possible to do load balancing based on the utilization of the links. The traffic being virtual-circuit would use the same path for the duration of its existance as LSP. No unnecessary oscillations here.

Offline Weight Optimization:
Bandwidth is the resource. Customers produce demand. The objective function, for example, could be to minimize Maximum Link Utilization. There are some constraints, for example, total demand will not exceed the link capacity, etc etc. How this global (entire network) optimization problem is solved is not a big deal, the big deal, however, is the result. The solution provides a set of weights which when set on the interfaces leads to a load-balanced and better utilized network.

Point : Humans maybe greedy but mathematics is generous!