Hitless recovery from link failures in networks with arbitrary topology

Link failures in wide area networks are common. To recover from such failures, a number of methods such as SONET rings, protection cycles, and source rerouting have been investigated. Two important considerations in such approaches are the recovery time and the needed spare capacity to complete the recovery. Usually, these techniques attempt to achieve a recovery time less than 50 ms. In this paper we introduce an approach that provides link failure recovery in a hitless manner, or without any appreciable delay. This is achieved by means of a method previously introduced, named diversity coding. We present an algorithm for the design of an overlay network to achieve hitless recovery from single link failures in arbitrary networks via diversity coding. This algorithm is designed to minimize spare capacity for recovery. We compare the spare capacity performance of this algorithm against conventional techniques from the literature via simulations. Based on these results, we conclude that the spare capacity requirements of the proposed technique are favorably comparable to existing techniques, while its recovery time performance is much better, since it can provide hitless recovery.