New Algorithm Boosts Network Efficiency 114
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."
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?
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)
Re: (Score:2)
Re: (Score:2)
where have you been?
Re: (Score:1)
Actually, if it's perl, it should be
$Coewzio6gfsd gk;lsdf8 0trdstkgl sdflkgj7yu 98hfs tu95 ydtkjguf 87)(& 98Z&Y8 sdaiu7trs8 7)(* 09794w8 kjs hfe97 4(HkjKLU98 8Y* Yiudhfdsiuyf7yt rjytrtyrut r;
Re: (Score:2)
If it's Perl, you never know which way the author will choose!
Maybe:
$connection->drop unless $hostname ne "slashdot.org";
Or:
$hostname ne "slashdot.org" or $connection->drop;
Or even:
my $rule = <<EoR;
if($hostname ne "slashdot.org") {
$connection->drop();
}
EoR
eval( $rule );
Isn't it grand?
Re: (Score:1)
Sack the third guy - he was so busy trying (and failing) to be clever, he fscked up the logic. Unforgivable.
( The 'ne' should be a 'eq')
Re: (Score:2)
if ($hostname eq "slashdot.org")
$connection->drop();
There. Fixed it for both of you. Note that "==" does numerical comparison, so "foo" == "bar"; it works just like it works in C on numbers, so it should be obvious. Also, invoking methods (and accessing members) on objects is done with the arrow notation, not the dot notation, since behind the surface it's a pointer, so again it's intuitive just like C.
Sheesh, get with the program. And don't throw glass shards if you live
significant boost to algorithm (Score:5, Insightful)
Re: (Score:1)
modded flamebait while he's right. yup....
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.
Re: (Score:2)
*swoosh*
What does Nike have to do with any of this? Or were you saying an Air Jordan powered sneakernet would be more efficient?
Re: (Score:2)
They don't. We're talking about the routing protocol, which determines layer-3 routing tables from topology information. OSPF, EIGRP, RIP, that sort of thing. Deep Packet Inspection isn't involved in this process. There's plenty to complain about in your ISP inspecting your traffic, but "slows down OSPF" isn't on the list.
Thoughts that never occur to anonymous cowards (Score:1, Insightful)
"Maybe my offensive odor is the reason I've never been touched by another human being" and "maybe living in my parent's basement really does make me a loser"
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 :)
Re: (Score:1)
Re: (Score:2)
Fresh out of ligers, sorry. Would you accept leoplurodons?
Re: (Score:1)
Numbers Re:I'd think it would've been... (Score:1)
On 'backbone' circuits, how much traffic is:
a) SPAM e-mail
b) P2P traffic (on those port 'special' port numbers)
c) pr0n downloads
d) encrypted VPN - corporate
e) encrypted - 'zombie PC' private networks (based on IP addr)
It would be interesting to compare this number with the number for the 'last mile' circuits, just to see what the 'network management' issues are
Re: (Score:3, Interesting)
Re: (Score:1, Interesting)
I find this hard to believe. Chat applications
chat? a bit of text = a t m o s t p e o p l e ' s t y p i n g s p e e d s... barely any impact whatsoever.
legitimate web surfing
again, grab a few k of pages every so often. Nothing done. (but.. see later)
games
now we might be getting somewhere, but games tend to be reasonably local loops (as those gamers like to brag about their ping times) and the traffic that is sent is reasonably low (or the game would be dog slow) so I don't
Re: (Score:1)
Re: (Score:2)
You should check out the number of porn website's on Alexa's top 100 sites for the US. Also compare things like isohunt's zeitgeist. Ninety percent is an extremely high estimate, but the question really depends on what you are measuring. Do you mean the percentage of network traffic, the percent of web pages, or perhaps the percent of publicly accessible storage?
This article [technewsworld.com] (2004) is talking about the percentage of web traffic (as distinct from internet traffic) that is porn-related as being about 20%
This [slashdot.org]
Re: (Score:2)
Large portions of chat, P2P, spam and websurfing is for porn.
Re: (Score:2)
I do believe, sir, that you might be interested in these butterfly nets and dog collars I have for sale. please visit our website for more information.
Re: (Score:1)
fp (Score:5, Funny)
Re:fp (Score:5, Funny)
Maybe your ISP hasn't updated its routers yet...
Re: (Score:1, Interesting)
Re: (Score:1, Insightful)
Aside from the fact that you actually didn't get first post, faster routing == faster for all.
Re: (Score:2)
Aside from the fact that you actually didn't get first post
What's that "wooshing" sound?
Re: (Score:2, Funny)
Re: (Score:1)
The Researchers at the University of California?
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.
Re: (Score:2)
Re: (Score:1)
How many esses does the plural of ess have?
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.
The real question is... (Score:1)
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)
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.
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:1)
oh wait...
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: (Score:2)
If I read this right though, it's more a replacement for Interiors like OSPF or EIGRP, rather than BGP. So it'd help scale big enterprises, but probably wouldn't get used on big Internet carrier links...
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?
Re: (Score:1)
well, the overhead would probably be in communicating both ways, so if you could skip a cycle, it would lower your latency a bit. it would also increase bandwidth over the network, but whether that'd get passed on to a user without said user paying more for it... well, idunno. i doubt it.
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)
Re: (Score:1, Interesting)
It just means that convergence time will be quicker, not necessarily related to better throughput, just better response to when things change. I do not think network convergence time is going to matter to most people. It will not speed up packets/throughput/bandwidth or lower latency it just makes the routing protocol more efficient.
I'd imagine Cisco would stay away from this since resource hungry software drives sales.
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: (Score:1)
Re:Patent? (Score:5, Funny)
You must be new here.
Prior art is like kryptonite to the Patent Office.
Re: (Score:1, Funny)
That's right. Kryptonite has no effect at all on the patent office.
Re: (Score:1)
Re: (Score:2, Informative)
Re:Patent? (Score:5, Funny)
Redundant, I know, but when has the law ever stopped a patent troll?
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
Re: (Score:1)
Nice catch, I didn't know that one...
However, the fact that they've published is stopping anybody else than the authors (like a patent troll) to file for a patent, right?
Re: (Score:1)
Re: (Score:2)
However, the fact that they've published is stopping anybody else than the authors (like a patent troll) to file for a patent, right?
Nope; that doesn't necessarily stop anyone from filing. All you have to do is fill out the papers and pay the application fee. Of course, if the Patent Office discovers that someone else published it earlier, they'll reject your application. But you can certainly file. If your lawyers can write it with terminology that's sufficiently obscure, the Patent Office's examiners
Re: (Score:2)
How can you nullify something that doesn't exist.
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.
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.)
Re: (Score:2)
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:1)
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:1)
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.
Re: (Score:1)
FYI: University of California is well, a University. San Diego is a campus of said University.
Campuses:
Berkeley
Davis
Irvine
Los Angeles
Merced
Riverside
San Diego
San Francisco
Santa Barbara
Santa Cruz
CVP improvement (Score:2)
Botnet and spam (Score:1)
Moar Spam! Bigger Botnet! Gogogo
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!
Genetic Algorithm? (Score:2, Interesting)
Why not use a genetic algorithm to discover such algorithms? Assuming you can simulate typical network usage patterns reasonably accurately, then one can apply GA's to the simulation find a near-optimum algorithm.
Full PDF (Score:2)
For the technically inclined, the full research publication (PDF) is available."
You must be new here.
For the technically inclined... (Score:1)
Overstatement (Score:1)
Nothing to see here, move along.