Novel algorithms for shared segment protection

The major challenges in designing survivable schemes are how to allocate a 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 recover quickly from it. All existing approaches invariably make tradeoffs. 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.