- 12 myths about how the Internet works
- Smartphone smackdown: Storm vs. iPhone
- IETF: Should we ignore the Kaminsky bug?
- Top 10 wicked cool algorithms
- How to recession-proof yourself
A team of computer scientists has proposed a new algorithm that makes routers operate more efficiently by automatically limiting the number of network route or link-state updates they receive.
The algorithm could be important in large heterogeneous corporate networks where the oldest, slowest routers make all the others wait while they absorb updates and recalculate their path tables. The Approximate Link State (XL) algorithm suppresses the updates so only those routers that are directly affected receive them, says Professor Stephan Savage, who along with three other computer scientists at the University of California at San Diego developed the algorithm. Savage presented a paper this week about XL at the Association for Computing Machinery's conference of its Special Interest Group on Data Communications.
Without XL, routers typically flood the network with route updates, with every router receiving every update. In very large networks the sheer number of routers and inevitable link-state changes would episodically grind routers to a halt.
"Updates may only be relevant to very localized areas," Savage says. Using a map analogy to illustrate the point, he says that a driver on the East Coast doesn't care if Interstate 5 is flooded out in Portland, Ore.. "But metaphorically, we tell everyone that information in networking."
To deal with that problem, large networks are manually engineered to create areas -- conceptually isolated groups of routers -- that limit the number of routers any flood reaches. Routers still receive floods, but only from the routers within their areas.
Savage says XL can eliminate manual configuration of areas. Instead, each router automatically figures out what other routers it needs should pass along updates so all destinations can still be reached and loops don't occur that effectively black-hole packets.
The XL algorithm selectively withholds some updates, creating a trade-off. If a new link becomes available after a failure, the algorithm decides whether forwarding the information beyond a router's immediate neighbors will improve enough paths and by a great enough percentage to warrant passing it along.
If not, the router suppresses the update by not forwarding it. The result is updates are sent only to the immediate areas where topology has changed, making the distribution less disruptive.
Partner Content
Simplify Your Branch Infrastructure
Learn how to simplify your branch infrastructure while dramatically increasing app performance with Citrix Branch Repeater.
Download the Free Info Kit
Next-Gen Load Balancing
Free Guide: "Next Gen Load Balancing: 8 Things You Need to Handle Today's Network Traffic" shows you the functionality needed in your next load balancer.
Download the Free Guide
Accelerate Your Web Apps by up to 5x
Free Guide: "The Secret to Getting Maximum Speed from your Web Applications." Learn how you can deliver Web apps up to 5x faster.
Download the Free Guide
Comments (12)
Nice idea but....By Old CCIE on September 4, 2008, 9:12 amThe concept is pretty cool, as IGPs are really inefficient when you look into them deeply. I think it will be more applicable to new applications like wireless mesh...
Reply | Read entire comment
Will the vendors really buy itBy Anonymous on August 24, 2008, 12:41 pmAim of vendors is to sell as many new boxes as quickly as possible. Will they really want to add it so that I can continue to run my old kit??
Reply | Read entire comment
Kudos - doesn't seem like much until you consider what it could By Anonymous on August 22, 2008, 11:01 amCombine XL with mesh networks, and unusual radio propogation and you have something interesting and suddenly usable. One problem with large (10's of thousands of...
Reply | Read entire comment
RE:CoolBy Anon on August 21, 2008, 5:12 pmSo you are advocating for dumb/cheap engineers with products which are so intelligent that a monkey could configure them? What happens when these products don't...
Reply | Read entire comment
Selfish and ContextBy Schratboy on August 21, 2008, 12:30 pmMy commentary was formulated from a business context. Personal Web surfing and Internet use on one's own time is perfectly fine. I do think that you're a bit...
Reply | Read entire comment
View all comments