Complexity analysis of an efficient heuristic for shared backup tree protection in MPλS networks

Abstract

In the Multi-Protocol Lambda Switching (MPλS) networks, shared backup tree lightpath protection is a promising paradigm because of its fast recovery from single failure and its efficiency in terms of consumed capacity. The objective of the backup tree protection is to minimize the total cost of working paths and backup trees for a given working network demand. The Successive Greedy Source Placement (SGSP) heuristic is an efficient solution in order to solve this optimization problem. The SGSP heuristic gives a good trade-off between optimality and processing time. The computation complexity analysis shows that the SGSP heuristic scales up to large topologies and large network demand vector.