A Polynomial-Time Algorithm for Computing Disjoint Lightpath Pairs in Minimum Isolated-Failure-Immune WDM Optical Networks

作者：Xue Guoliang^*; Gottapu Ravi; Fang Xi; Yang Dejun; Thulasiraman Krishnaiyan

来源：IEEE/ACM Transactions on Networking, 2014, 22(2): 470-483.

DOI：10.1109/TNET.2013.2257180

• Disjoint lightpath pairs
• minimum isolated failure immune networks
• partial 2-trees
• wavelength division multiplexing (WDM) optical network

A fundamental problem in survivable routing in wavelength division multiplexing (WDM) optical networks is the computation of a pair of link-disjoint (or node-disjoint) lightpaths connecting a source with a destination, subject to the wavelength continuity constraint. However, this problem is NP-hard when the underlying network topology is a general mesh network. As a result, heuristic algorithms and integer linear programming (ILP) formulations for solving this problem have been proposed. In this paper, we advocate the use of 2-edge connected (or 2-node connected) subgraphs of minimum isolated failure immune networks as the underlying topology for WDM optical networks. We present a polynomial-time algorithm for computing a pair of link-disjoint lightpaths with shortest total length in such networks. The running time of our algorithm is, where is the number of nodes, and is the number of wavelengths per link. Numerical results are presented to demonstrate the effectiveness and scalability of our algorithm. Extension of our algorithm to the node-disjoint case is straightforward.

• 出版日期2014-4