Efficient Mapping Algorithms for Survivable GMPLS Networks

摘要

With the advent of intelligent IP over optical networks, like GMPLS, connections can be protected against failures effectively; however, to capitalize the advantages, novel sophisticated methods are needed. This paper addresses the task of finding efficient mapping in a survivable multilayer network in order to ensure high availability for connections. Known methods (like running a shortest path algorithm) do not consider finding physically disjoint paths in the upper layer and thus cause failure propagation. Besides formulating the problem, we propose a randomized heuristic method to solve it. The quality of the solution is evaluated (1) by the number of node-pairs for which a physically-disjoint path-pair can be found in the upper layer, or (2) by the number of spans used by both working and protection paths (i.e., failure propagation effect). It is shown with numerous simulations that our proposed method finds solution for significantly more node pairs (86% instead of 45% in the 35-node network) than traditional methods. Furthermore, it yields connection availabilities near to the optimum.