Slashdot Log In
New Algorithm Boosts Network Efficiency
Posted by
Soulskill
on Thu Aug 28, 2008 09:35 AM
from the more-is-better dept.
from the more-is-better dept.
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."
Related Stories
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.
Network efficiency algorithm (Score:5, Funny)
if($hostname==slashdot.org)
connection.drop();
routers in perl? (Score:3, Funny)
That would make them blazing fast!
Re:Network efficiency algorithm (Score:4, Funny)
fixed it for you:
if($hostname=="slashdot.org")
connection.drop();
What no compile/test cycle prior to submitting your post?
Parent
Re: (Score:2)
Actually, if it's Perl, then it should be:
connection.drop() if $hostname eq "slashdot.org";
Re: (Score:2)
$connection->drop if $hostname eq "slashdot.org";
Re: (Score:3, Funny)
Re: (Score:3)
Re: (Score:2, Funny)
Code has grammar, too.
youve not seen some of the code ive had to fix then.
Re: (Score:2)
significant boost to algorithm (Score:5, Insightful)
Parent
Re: (Score:2)
And if you do use deep packet inspection, you got it all wrong. It should be:
if ($packet->['httpHeader']['HTTP_REFERER'] eq "slashdot.org") {
$packet->sendICMP(ICMP_TYPE_RST, SEND_ICMP_TO_SOURCE);
$packet->sendICMP(ICMP_TYPE_RST, SEND_ICMP_TO_DESTINATION);
$packet->drop();
return 1; # packet was reinjected or handled in this layer; do not continue to propagate through filter chain
}
Emphasis mine.
Interesting ...I'd think it would've been... (Score:5, Funny)
{
route_to_local_garbage()
}
else{
on_its_way()
}
Re:Interesting ...I'd think it would've been... (Score:5, Funny)
Actually, I bet spam outnumbers even the pr0n. Imagine a world without spam! All the pretty butterflies playing tag, and cute puppies rolling in the sunshine! Ahhh :)
Parent
Re: (Score:3, Interesting)
Re: (Score:2)
Fresh out of ligers, sorry. Would you accept leoplurodons?
fp (Score:5, Funny)
Re:fp (Score:5, Funny)
Maybe your ISP hasn't updated its routers yet...
Parent
Re:fp (Score:5, Funny)
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.
Parent
Re: (Score:2)
Re: (Score:2)
Aside from the fact that you actually didn't get first post
What's that "wooshing" sound?
Re: (Score:2, Funny)
nearly as good? (Score:4, Interesting)
so if my packets don't make it I know why. Not a skeptic but the Internet is already barely holding together and I'm not confident that "nearly as good" routing info can help. Of course if trying 2-3 times using this is still faster than first time hit using the old one then sure, why not?
Re: (Score:2)
Ex: the time-to transmit and/or path length, removing time to calculate path, is 10-15% longer, on average, would be not as good, even if it is just as reliable.
Is this really new? (Score:5, Interesting)
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? (Score:5, Informative)
Parent
Re:Is this really new? (Score:5, Informative)
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.
Parent
CRAP. Mis-moused! (Score:2)
I'm so sorry, Mezoth. I just moderated this redundant, when I meant to moderate it interesting.
Please, someone compensate for my mouse-slip.
Re: (Score:3, Informative)
By posting, you have removed your moderation, so you already did it yourself ;)
You can't post and moderate in the same story, otherwise you could post and then mod yourself, or mod down people who disagree with you etc.
Re: (Score:3, Funny)
Re: (Score:2)
To the end user, this would mean that the internet would respond faster to outages, and better route around congestion on any one link.
Thank you. That's the statement that I came in here for.
Re:Is this really new? (Score:4, Interesting)
Ok, you seem to know what the hell is going on, so I'll ask you.
The summary talks about it being a huge boost to network efficiency and how it cuts overhead, but it seems like that wouldn't necessarily make a huge difference for most people's network use unless overhead is large and networks are hugely inefficient. I mean, if overhead is .0001%, then cutting it in half isn't going to give you too much of a boost in your ability to transmit data unless you're pushing around huge amounts of data and really need to squeeze every last bit of bandwidth. Right?
So I trust I'll get yelled at by someone if that logic is wrong, but just let me ask, what kind of benefit would this improvement actually yield? Do I get much better bandwidth, much lower latency, both? Or is it the sort of improvement than only a real network guru could love?
Parent
Re: (Score:3, Informative)
I think you're looking at this in the wrong way. If the network is stable then this work is completely irrelevant. Its when the network changes (i.e., links going up and down) that you care about routing protocols. In this case you care how long it takes to converge on a new set of consistent forwarding tables (why? because you may find your packets dropped on the floor in the mean-time)
Re: (Score:3, Informative)
Patent? (Score:5, Interesting)
So has the team applied for a patent? We wouldn't want just any ISP to be able to use this algorithm, would we? And if they don't patent it, one of the many patent-troll companies will, denying the researchers the right to use the results of their own work.
Re: (Score:3, Insightful)
And unless they have millions to fight it out in court this is perfectly possible.
Re: (Score:2)
Prior art wouldn't apply?
Re:Patent? (Score:5, Funny)
You must be new here.
Prior art is like kryptonite to the Patent Office.
Parent
Re: (Score:2, Informative)
Re:Patent? (Score:5, Funny)
Redundant, I know, but when has the law ever stopped a patent troll?
Parent
Re: (Score:3, Interesting)
Except in the US, where you have up to 1 year to file after initial public disclosure. Of course, the problem is that you can't get a foreign patent (because while the initial filing date is recognized by them, the fact it was published potentially nullifies any foreign patent. However, there are probably tons of except
The most important part (Score:4, Informative)
Finally, we argue that existing link-state protocols, such as OSPF, can incorporate XL routing in a backwards compatible and incrementally deployable fashion.
My first question upon reading the summary was, but is it backwards compatable... and they appear to answer that in the thesis statement. Looks like some good lunch reading here.
Re:The most important part (Score:4, Funny)
They meet the âoecentral challengeâ of determining which updates are important and which can be suppressed by using three rules for update propagation, said team member Ramamohan Paturi.
1. The routing algorithm may not injure the network or, through inaction, allow the network to come to harm.
2. The routing algorithm must obey orders given to it by human beings, except where such orders would conflict with the First Rule.
3. The routing algorithm must protect its own existence as long as such protection does not conflict with the First or Second Rules.
Seems pretty foolproof to me.
Parent
Re: (Score:3, Funny)
Nah, you just present it with a situation where acting will harm one human and failing to act will harm another. Then it jams up and starts vibrating and sparks shoot out of its ears. (Or at least that's how it works for robots. To be honest I don't know where a routing algorithm's ears are, but this seems as good a way as any to find out.)
University of California *San Diego* (Score:2, Informative)
Re: (Score:2)
Errr you might not know [wikipedia.org], but that doesn't mean it doesn't exist [university...fornia.edu].
I like to think of the University of California as a sort of Oxford/Cambridge college system on steroids. So yes its at UCSD, also writers of a very fine version of Pascal, but its still UC.
Re: (Score:2)
The name "University of California", when unqualified, refers to the Berkeley campus.
It's just a convention. Other examples:
1) University of Michigan -> Ann Arbor campus
2) University of Wisconsin -> Madison campus
3) University of Illinois -> Urbana-Champaign campus
4) University of Maryland -> College Park campus
Re: (Score:2)
Re: (Score:2)
I'm a San Diegan, though I don't know much about UCSD. However all the University of California schools are affiliated [university...fornia.edu]. I don't think it's wrong to refer to the University of California, but it's not that common. Probably since UCSD is quicker to say by 1/3 and is also more specific.
CVP improvement (Score:2)
A new Al Gore rhythm (Score:4, Funny)
A new and improved Al Gore rhythm would dramatically boost network efficiency. Since he invented the internets, and actually routes every single packet on the internets by hand, if he learned how to work in a syncopated rhythm the efficiency of the network would nearly double.
Check and mate!