Novel algorithms for shared segment protection

doi:10.1109/JSAC.2003.816624

Novel algorithms for shared segment protection

2003-10-01

108

PRE

AI

DOI：10.1109/JSAC.2003.816624

Original

Original request for help

Save

Abstract

En 中文

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.

Keywords:

bandwidth sharing

dynamic provisioning

multi-protocol label switched (MPLS)

optical network

protection

Novel algorithms for shared segment protection

Abstract

AI Summary

Journal

Organization