Graceful Convergence in Link-State IP Networks: A Lightweight Algorithm Ensuring Minimal Operational Impact
IEEE/ACM Transactions on Networking · 2013
Abstract
The use of real-time multimedia or mission-critical applications over IP networks puts strong pressure on service providers to operate disruption-free networks. However, after any topological change, link-state Interior Gateway Protocols (IGPs), such as IS-IS or OSPF, enter a convergence phase during which transient forwarding loops may occur. Such loops increase the network latency and cause packet losses. In this paper, we propose and evaluate an efficient algorithm aimed at avoiding such traffic disruptions without modifying these IGPs. In case of an intentional modification of the weight of a link (e.g., to shut it down for maintenance operations or to perform traffic engineering), our algorithm iteratively changes this weight, splitting the modification into a sequence of loop-free transitions. The number of weight increments that need to be applied on the link to reach its target state is minimized in order to remain usable in existing networks. Analysis performed on inferred and real Internet service provider (ISP) topologies shows that few weight increments are required to handle most link shutdown events (less than two intermediate metrics for more than 85% of the links). The evaluation of our implementation also reveals that these minimal sequences can be computed in a reasonable time.
People
Cite (BibTeX)
@article {FPJPO13,
title = {Graceful Convergence in Link-State IP Networks: A Lightweight Algorithm Ensuring Minimal Operational Impact},
journal = {IEEE/ACM Transactions on Networking},
volume = {to appear},
author = {Francois Clad and Pascal Merindol and Jean-Jacques Pansiot and Pierre Francois and Olivier Bonaventure},
year = {2013},
note = {http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=6512633 or contact Olivier Bonaventure for a preprint},
}