Update to Link-State Routing Algorithms

Terry Slattery
Principal Architect

Network World’s Tim Greene posted an article about a new algorithm, called Approximate Link State (XL), for use in link-state routing protocols.  The algorithm was developed by researchers at the University of California at San Diego.   The algorithm allows link-state protocols to determine when to not forward updates to neighbors, potentially reducing the overhead of the routing protocols.  The ACM paper on the algorithm says that it can reduce overhead by an order of magnitude.

The key concept behind the algorithm is that it reduces the need to manually configure areas within OSPF or IS-IS.  Areas are used to limit the distribution of link-state updates, reducing the total volume of updates that each individual router has to process to only those updates that occur within its area.  Are areas that important?  I’ve heard some senior routing protocol designers say something like:

EIGRP allows people who don’t have a clue to build larger networks than OSPF, but to build a very large network you have to have a clue.

The reason for this statement is that summarization is used to limit the sizes of routing domains in order to have a large network remain stable. Areas are much like water-tight doors in ships — they limit the scope of damage when bad things happen.  Even with XL, I would want to use areas to aid in troubleshooting and to restrict the extent of the network that is impacted by any number of routing problems.  With these other requirements driving the need to use areas, I don’t see areas disappearing as a basic network design feature.  I can see that XL may allow for larger areas, potentially simplifying the design of some networks.

Another thought that I had about XL was whether the increased memory usage in routers would be worth the savings in routing overhead.  The researchers have not implemented XL within a real OSPF code base, so there is no way to judge where the tradeoff exists for memory and CPU vs routing protocol traffic overhead.  Overall, it may actually save CPU time, at the cost of some additional memory.  We’ll have to see as these researchers continue their work.  It would be nice to see a follow-up paper that reports how it works in the real world.  In particular, I could see XL being a big benefit in military networks that have limited bandwidth, especially mobile networks.



Re-posted with Permission 

NetCraftsmen would like to acknowledge Infoblox for their permission to re-post this article which originally appeared in the Applied Infrastructure blog under http://www.infoblox.com/en/communities/blogs.html


Leave a Reply


Nick Kelly

Cybersecurity Engineer, Cisco

Nick has over 20 years of experience in Security Operations and Security Sales. He is an avid student of cybersecurity and regularly engages with the Infosec community at events like BSides, RVASec, Derbycon and more. The son of an FBI forensics director, Nick holds a B.S. in Criminal Justice and is one of Cisco’s Fire Jumper Elite members. When he’s not working, he writes cyberpunk and punches aliens on his Playstation.


Virgilio “BONG” dela Cruz Jr.

CCDP, CCNA V, CCNP, Cisco IPS Express Security for AM/EE
Field Solutions Architect, Tech Data

Virgilio “Bong” has sixteen years of professional experience in IT industry from academe, technical and customer support, pre-sales, post sales, project management, training and enablement. He has worked in Cisco Technical Assistance Center (TAC) as a member of the WAN and LAN Switching team. Bong now works for Tech Data as the Field Solutions Architect with a focus on Cisco Security and holds a few Cisco certifications including Fire Jumper Elite.


John Cavanaugh

CCIE #1066, CCDE #20070002, CCAr
Chief Technology Officer, Practice Lead Security Services, NetCraftsmen

John is our CTO and the practice lead for a talented team of consultants focused on designing and delivering scalable and secure infrastructure solutions to customers across multiple industry verticals and technologies. Previously he has held several positions including Executive Director/Chief Architect for Global Network Services at JPMorgan Chase. In that capacity, he led a team managing network architecture and services.  Prior to his role at JPMorgan Chase, John was a Distinguished Engineer at Cisco working across a number of verticals including Higher Education, Finance, Retail, Government, and Health Care.

He is an expert in working with groups to identify business needs, and align technology strategies to enable business strategies, building in agility and scalability to allow for future changes. John is experienced in the architecture and design of highly available, secure, network infrastructure and data centers, and has worked on projects worldwide. He has worked in both the business and regulatory environments for the design and deployment of complex IT infrastructures.