AuthorsS. Kini, S. Ramasubramanian, A. Kvalbein and A. F. Hansen
TitleFast Recovery From Dual Link Failures in IP Networks
Afilliation, Communication Systems
Publication TypeProceedings, refereed
Year of Publication2009
Conference NameProceedings INFOCOM 2009
ISBN Numberxx

This paper develops a novel mechanism for recovering from dual-link failures in IP networks. The highlight of the developed routing approach is that a node re-routes a packet around the next-hop 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, in which some of the links connected to the node are removed. Every protection graph is guaranteed to be two-edge connected, hence can recover from one failure. The network recovers from the first failure by tunneling with protection address; and the tunneled packet is routed over the corresponding protection graph. We prove that it is sufficient to provide up to three protection graphs per node to tolerate any arbitrary two link failures in a three-edge connected graph. We evaluate the effectiveness of the proposed technique over several network topologies.

Citation KeySimula.ND.251