Novel algorithms for shared segment protection

The major challenges in designing survivable schemes are how to allocate minimal amount of spare resources (e.g., bandwidth) using fast (e.g., polynomial-time) algorithms, and in case a failure occurs, to be able to quickly recover from it. All existing approaches invariably make tradeoffs. In this paper, we propose novel shared segment protection algorithms which make little or no compromise. We develop an elegant integer linear programming (ILP) model to determine an optimal set of segments to protect a given active path. Although the ILP approach is useful for a medium-size network, it is too time consuming for large networks. Accordingly, we also design a fast heuristic algorithm based on dynamic programming to obtain a near-optimal set of segments. Although the heuristic algorithm has a polynomial time complexity, it can achieve a bandwidth efficiency as high as some best-performing shared path protection schemes and at the same time, much faster recovery than these shared path protection schemes. The proposed scheme is also applicable to a wide range of networking technologies including Internet protocol and wavelength-division multiplexing networks under the generalized multiprotocol label switched framework.