On achieving optimal survivable routing for shared protection in survivable next-generation Internet

This paper proposes a suite of approaches to solve the survivable routing problem with shared protection. We first define in mathematics the maximum extent of resource sharing for a protection path given the corresponding working path according to the current network link-state. Then the problem of...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on reliability 2004-06, Vol.53 (2), p.216-225
Main Authors: Pin-Han Ho, Tapolcai, J., Mouftah, H.T.
Format: Article
Language:English
Subjects:
Algorithms
Computational modeling
Costs
Heuristic
Heuristic algorithms
Integer linear programming
Internet
Iterative algorithms
Linear programming
Mathematics
Protection
Resource management
Routing
Studies
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:This paper proposes a suite of approaches to solve the survivable routing problem with shared protection. We first define in mathematics the maximum extent of resource sharing for a protection path given the corresponding working path according to the current network link-state. Then the problem of solving the least-cost working & protection path-pair (in terms of the sum of the cost) is formulated into an Integer Linear Programming process. Due to the dependency of the protection path on its working path, however, the formulation is not scalable with the network size, and takes an extra effort to solve. Therefore, we introduce two heuristic algorithms, called Iterative Two-Step-Approach (ITSA) & Maximum Likelihood Relaxation (MLR), which aim to explore the approximating optimal solutions with less computation time. We evaluate the performance of the proposed schemes, and make a comparison with some reported counterparts. The simulation results show that the ITSA scheme, with a properly defined tolerance to optimality, can achieve the best performance at the expense of more computation time. On the other hand, MLR delivers a compromise between computation efficiency & performance.
ISSN:0018-9529
1558-1721
DOI:10.1109/TR.2004.829141