# American Institute of Mathematical Sciences

October  2007, 3(4): 625-643. doi: 10.3934/jimo.2007.3.625

## On the partial path protection scheme for WDM optical networks and polynomial time computability of primary and secondary paths

 1 Department of Computer Science and Engineering, Arizona State University, Tempe, AZ 85287, United States, United States, United States 2 School of Computer Science, University of Oklahoma, Norman, OK 73019, United States

Received  October 2006 Revised  July 2007 Published  October 2007

As a generalization of the traditional path protection (PP) scheme in WDM networks where a backup path is needed for each active path, the partial path protection (PPP) scheme uses a collection of backup paths to protect an active path, where each backup path in the collection protects one or more links on the active path such that every link on the active path is protected by one of the backup paths. While there is no known polynomial time algorithm for computing an active path and a corresponding backup path using the PP scheme for a given source destination node pair, we show that an active path and a corresponding collection of backup paths using the PPP scheme can be computed in polynomial time, whenever they exist, under each of the following four network models: (a) dedicated protection in WDM networks without wavelength converters; (b) shared protection in WDM networks without wavelength converters; (c) dedicated protection in WDM networks with wavelength converters; and (d) shared protection in WDM networks with wavelength converters. This is achieved by proving that that for any given source $s$ and destination $d$ in the network, if one candidate active path connecting $s$ and $d$ is protectable using PPP, then any candidate active path connecting $s$ and $d$ is also protectable using PPP. It is known that the existence of PP implies the existence of PPP while the reverse is not true. We demonstrate a similar result in the case of segmented path protection. This fundamental property of the PPP scheme is of great importance in the context of achieving further research advances in the area of protection and restoration of WDM networks.
Citation: Guoliang Xue, Weiyi Zhang, Tie Wang, Krishnaiyan Thulasiraman. On the partial path protection scheme for WDM optical networks and polynomial time computability of primary and secondary paths. Journal of Industrial and Management Optimization, 2007, 3 (4) : 625-643. doi: 10.3934/jimo.2007.3.625

2021 Impact Factor: 1.411