New Algorithm Boosts Network Efficiency

palegray.net writes "Researchers at the University of California have developed a new network routing algorithm that has the potential to significantly boost Internet traffic routing efficiency. This new approach focuses on the needs of dynamic networks, where connections are frequently transient. From the article: 'What the team did with their new routing algorithm, according to Savage's student Kirill Levchenko, was to reduce the "communication overhead" of route computation — by an order of magnitude.' For the technically inclined, the full research publication (PDF) is available."

Comments

Network efficiency algorithm

[LiquidCoooled]

if($hostname==slashdot.org)
    connection.drop();

Interesting ...I'd think it would've been...

[BitterOldGUy]

If( traffic == P2P || traffic == porn)
{
route_to_local_garbage()
}
else{
on_its_way()
}

fp

[bigfatwill]

Amazing! I've never been able to get first post before, but with faster routing to slashdot.org, it was a sinch.

Re:fp

[eln]

Maybe your ISP hasn't updated its routers yet...

Re:fp

[Thornburg]

Somebody give the guy at least a Score:1 Funny...

I mean, c'mon, "it was a sinch". Kind of like spelling better than most of /. is a cinch, only with more S's.

Is this really new?

[Mezoth]

So, from reading the article, I see that the great leap forward here is "smaller routing domain in a link-state protocol leads to faster routing updates". But, looking at the existing link-state protocols, they were designed from the ground up with the ability to limit your routing domain manually so increase the convergence time and decrease memory footprint.

I guess that means the achievement here is to have a link-state protocol that automatically limits your routing domain by limiting propagation of routes. This however seems like it could lead to seriously suboptimal routing which is probably a bad idea in most network environments today.

Re:Is this really new?

[Pysslingen]

The central point of the algorithm is to define bounds on when a routing change should be propagated. The point being that only an increase in routing efficiency above a certain threshold should be propagated. This disallows small fluctuations to have an impact on the wider network. He also shows that the impact of the propagation changes will be limited with respect to total network speed.

Re:Is this really new?

[Mezoth]

After reading a portion of the PDF supplied, I am actually far more satisfied that this is new research and not a restatement of fundamental network principles. The PDF has the equations where he proves a few simple criteria can define the scope of any network topology changes based on the difference in cost of the new route. This allows you to limit the recalculation of routes, blocking them from most of the routers where the recalculation would have provided no change in the actual routing topology.

The challenges he states are real challenges, and many modern networks are defined by the limits of the link-state protocols. In essence, this is like auto-summarization of prefixes in bgp, only applied to links in the link-state database - a possible slight loss in accuracy for a large boost in routing performance. This would allow the (faster converging) link-state protocols to scale to larger networks, rather then having to divide them into areas or use BGP to route between different sections of the network (resulting in loss of convergence time).

To the end user, this would mean that the internet would respond faster to outages, and better route around congestion on any one link.

significant boost to algorithm

[Lars T.]

Don't use deep packet inspection for routing.