A Single Backup-Table Rerouting Scheme for Fast Failure Protection in OSPF


IEICE TRANSACTIONS on Communications   Vol.E91-B   No.9   pp.2838-2847
Publication Date: 2008/09/01
Online ISSN: 1745-1345
DOI: 10.1093/ietcom/e91-b.9.2838
Print ISSN: 0916-8516
Type of Manuscript: Special Section PAPER (IEICE/IEEE Joint Special Section on Autonomous Decentralized Systems Theories and Application Deployments)
Category: Theories
routing,  link protection,  the Internet,  OSPF,  

Full Text: PDF>>
Buy this Article

We propose a practical link protection scheme, called Single Backup-table Rerouting, (SBR) as an extension for Open Shortest Path First (OSPF). SBR protects against any single link failure as soon as the failure occurs if the topology of every area in OSPF is two-link-connected. An efficient algorithm to compute a set of backup tables is provided for networks with symmetric link costs. The foremost feature of SBR is that the backup process is fully distributed, so no message exchange is required and the modification of OSPF is minor. OSPF is extended with the following: only one extra backup routing table, a 2-bit flag at each traffic packet, and a process for handling the backup table. There are no changes to the message format of OSPF. In this paper, we present the practical link protection scheme by fitting SBR into several OSPF specific mechanisms such as OSPF areas, Equal Costs Multipath (ECMP), and virtual links with proofs of their correctness. Furthermore, together with a loop-free routing technique for link-state routing, SBR guarantees the consistency of every route against a single link failure, even during the path recomputation phase, until it converges to the new shortest paths.