Survivable Path Sets: A New Approach to Survivability in Multilayer Networks

We consider the problem of survivability in multilayer networks. In single-layer networks, a pair of disjoint paths can be used to provide protection for a source-destination pair. However, this approach cannot be directly applied to layered networks where risk-disjoint paths may not always exist. In this paper, we take a new approach, which is based on finding a set of paths that may not be disjoint but together will survive any single risk. We start with two-layered communication networks, where the risks are fiber failures. We prove that in general, finding the minimum survivable path set (MSPS) is NP-hard, whereas if we restrict the length of paths the problem can be solved in polynomial time. We formulate the problem as an integer linear program (ILP), and use this formulation to develop heuristics and approximation algorithms. Moreover, we study the minimum cost survivable path set problem, where the cost is the number of fibers used, and thus, nonadditive. Finally, we generalize the survivability problem to the networks with more than two layers. By applying our algorithms for survivable path set, we assess the survivability of communication networks that operate relying on power from a power grid.