Dual-link failure resiliency through backup link mutual exclusion

One of the strategies to recover from dual-link failures is to employ link protection for the two failed links independently which requires that two links may not use each other in their backup paths if they may fail simultaneously. Such a requirement is referred to as backup link mutual exclusion (BLME) constraint and the problem of identifying a backup path for every link that satisfies the above requirement is referred to as the BLME problem. This paper explores the BLME problem in depth by: (1) formulating the backup path selection as an integer linear program; and (2) developing a pseudo-polynomial time approximation algorithm based on minimum cost path routing. The ILP formulation and heuristic are applied to six networks and their performance is compared to approaches that assume precise knowledge of dual-link failure. The heuristic approach is shown to obtain feasible solutions that are resilient to most dual-link failures, although the backup path lengths may be significantly higher than optimal. In addition, the paper demonstrates the significance of the knowledge of failure location by illustrating that network with higher connectivity may require lesser capacity than one with a lower connectivity to recover from arbitrary dual-link failures.