Slashdot Mirror
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."
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.
Your sig(k) has been stolen. There is a puff of smoke!
Just for the record, it looks like this was developed at UCSD. I'm no Californian, but I wasn't aware of a "University of California" school..I'm pretty sure they're all UC-something-something. Just giving credit where credit is due...
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.
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.
This cannot happen. Once something is published, nobody can claim a patent on it at a later date... Even for the authors to apply for a patent, the application has to predate the publication.
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.
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)
Network performance, in this context, is actually discussing the ability of the network to respond to change. This does nothing for the throughput of a non-congested link, but link-state protocols today can assign costs for links based on many factors, including availability and utilization. To the normal person on the street, this would not seem to matter, but in reality outages happen pretty often on large networks. The design of the networks today is often dictated by the limits of the link-state databases and the CPUs that power them - the bigger the database, the more CPU power it takes to run the algorithm to calculate the new best path when there is any change.
As the link-state database contains a list of every link in the network and the cost of crossing it, as well as every other link that it is connected to - you can see how that quickly becomes computationally heavy on a large network. Also, the larger the network, the more likely it is that you have some change in the network at any one moment - just probability working against you.
However, this adds a little bit of overhead into the actual database, and will make troubleshooting problems more complex in the real world. The implementation is a really key part of this, and will probably actually dictate if this gets picked up and used going forward. There is a real need for faster convergence time on modern networks as we move into more internet video feeds, as the loss of even a few packets can deeply impact the user experience - so the interest will be there, but the devil is always in the details.