Dynamic lightpath protection in WDM mesh networks under wavelength-continuity and risk-disjoint constraints

Path protection requires finding a working path and a protection path that are link disjoint. In this paper, we consider two fundamental problems on dynamic lightpath protection in WDM mesh networks. In the first problem, we consider a network without wavelength converters; thus both the working lightpath and protection lightpath are subject to the wavelength continuity constraint. Existing polynomial time algorithms can be applied to find a pair of link-disjoint lightpaths on a single wavelength; however, such algorithms fail if the working and protection lightpaths are on two different wavelengths. In the second problem, we consider a network with full wavelength conversion; thus the wavelength continuity constraint does not apply. Yet a single factor can cause multiple fiber links to fail simultaneously. The problem becomes finding link-disjoint lightpaths that are also risk disjoint. We prove that both of the two problems are NP-complete. We develop ILP formulations and heuristic algorithms for the two NP-complete problems. Practical constraints such as service level agreement (SLA) and priority are also considered. Computer simulations are conducted to evaluate the performance of the heuristic algorithms. (c) 2004 Elsevier B.V. All rights reserved.