AuthorsS. Kini, S. Ramasubramanian, A. Kvalbein and A. F. Hansen
TitleFast Recovery From Dual-Link Or Single-Node Failures in IP Networks Using Tunneling
Afilliation, Communication Systems
Publication TypeJournal Article
Year of Publication2010
JournalIEEE/ACM Transactions on Networking
Date PublishedDecember

This paper develops novel mechanisms for recovering from failures in IP networks with proactive backup path calculations and IP tunneling. The primary scheme provides resiliency against up to two link failures in a packet path in the network. The highlight of the developed routing approach is that a node re-routes a packet around the failed link without the knowledge of the second link failure. The proposed technique requires three protection addresses for every node, in addition to the normal address. Associated with every protection address of a node is a protection graph. Each link connected to the node is removed in at least one of the protection graphs and every protection graph is guaranteed to be two-edge connected. The network recovers from the first failure by tunneling the packet to the next-hop node using one of the protection addresses of the next-hop node; and the packet is routed over the protection graph corresponding to that protection address. We prove that it is sufficient to provide up to three protection addresses per node to tolerate any arbitrary two link failures in a three-edge connected graph. An extension to the basic scheme provides recovery from single node failures in the network. It involves identification of the failed node in the packet path and then routing the packet to the destination along an alternate path not containing the failed node. The effectiveness of the proposed techniques were evaluated by simulating the developed algorithms over several network topologies.

Citation KeySimula.netsys.4