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
[1]

Mohsen Abdolhosseinzadeh, Mir Mohammad Alipour. Design of experiment for tuning parameters of an ant colony optimization method for the constrained shortest Hamiltonian path problem in the grid networks. Numerical Algebra, Control and Optimization, 2021, 11 (2) : 321-332. doi: 10.3934/naco.2020028

[2]

Shinji Imahori, Yoshiyuki Karuno, Kenju Tateishi. Pseudo-polynomial time algorithms for combinatorial food mixture packing problems. Journal of Industrial and Management Optimization, 2016, 12 (3) : 1057-1073. doi: 10.3934/jimo.2016.12.1057

[3]

Arman Hamedirostami, Alireza Goli, Yousef Gholipour-Kanani. Green cross-dock based supply chain network design under demand uncertainty using new metaheuristic algorithms. Journal of Industrial and Management Optimization, 2021  doi: 10.3934/jimo.2021105

[4]

Yi Gao, Rui Li, Yingjing Shi, Li Xiao. Design of path planning and tracking control of quadrotor. Journal of Industrial and Management Optimization, 2022, 18 (3) : 2221-2235. doi: 10.3934/jimo.2021063

[5]

Kyosuke Hashimoto, Hiroyuki Masuyama, Shoji Kasahara, Yutaka Takahashi. Performance analysis of backup-task scheduling with deadline time in cloud computing. Journal of Industrial and Management Optimization, 2015, 11 (3) : 867-886. doi: 10.3934/jimo.2015.11.867

[6]

Hirotada Honda. On a model of target detection in molecular communication networks. Networks and Heterogeneous Media, 2019, 14 (4) : 633-657. doi: 10.3934/nhm.2019025

[7]

Joseph D. Skufca, Erik M. Bollt. Communication and Synchronization in Disconnected Networks with Dynamic Topology: Moving Neighborhood Networks. Mathematical Biosciences & Engineering, 2004, 1 (2) : 347-359. doi: 10.3934/mbe.2004.1.347

[8]

Aiwan Fan, Qiming Wang, Joyati Debnath. A high precision data encryption algorithm in wireless network mobile communication. Discrete and Continuous Dynamical Systems - S, 2019, 12 (4&5) : 1327-1340. doi: 10.3934/dcdss.2019091

[9]

Karim El Mufti, Rania Yahia. Polynomial stability in viscoelastic network of strings. Discrete and Continuous Dynamical Systems - S, 2022, 15 (6) : 1421-1438. doi: 10.3934/dcdss.2022073

[10]

Gaidi Li, Jiating Shao, Dachuan Xu, Wen-Qing Xu. The warehouse-retailer network design game. Journal of Industrial and Management Optimization, 2015, 11 (1) : 291-305. doi: 10.3934/jimo.2015.11.291

[11]

Gabriella Bretti, Roberto Natalini, Benedetto Piccoli. Fast algorithms for the approximation of a traffic flow model on networks. Discrete and Continuous Dynamical Systems - B, 2006, 6 (3) : 427-448. doi: 10.3934/dcdsb.2006.6.427

[12]

Dandan Hu, Zhi-Wei Liu. Location and capacity design of congested intermediate facilities in networks. Journal of Industrial and Management Optimization, 2016, 12 (2) : 449-470. doi: 10.3934/jimo.2016.12.449

[13]

Eugenia N. Petropoulou, Panayiotis D. Siafarikas. Polynomial solutions of linear partial differential equations. Communications on Pure and Applied Analysis, 2009, 8 (3) : 1053-1065. doi: 10.3934/cpaa.2009.8.1053

[14]

Young-Pil Choi, Jan Haskovec. Cucker-Smale model with normalized communication weights and time delay. Kinetic and Related Models, 2017, 10 (4) : 1011-1033. doi: 10.3934/krm.2017040

[15]

Kazuhiko Kuraya, Hiroyuki Masuyama, Shoji Kasahara. Load distribution performance of super-node based peer-to-peer communication networks: A nonstationary Markov chain approach. Numerical Algebra, Control and Optimization, 2011, 1 (4) : 593-610. doi: 10.3934/naco.2011.1.593

[16]

Tanka Nath Dhamala. A survey on models and algorithms for discrete evacuation planning network problems. Journal of Industrial and Management Optimization, 2015, 11 (1) : 265-289. doi: 10.3934/jimo.2015.11.265

[17]

Hari Nandan Nath, Urmila Pyakurel, Tanka Nath Dhamala, Stephan Dempe. Dynamic network flow location models and algorithms for quickest evacuation planning. Journal of Industrial and Management Optimization, 2021, 17 (5) : 2943-2970. doi: 10.3934/jimo.2020102

[18]

Ashkan Mohsenzadeh Ledari, Alireza Arshadi Khamseh, Mohammad Mohammadi. A three echelon revenue oriented green supply chain network design. Numerical Algebra, Control and Optimization, 2018, 8 (2) : 157-168. doi: 10.3934/naco.2018009

[19]

Robert Ebihart Msigwa, Yue Lu, Xiantao Xiao, Liwei Zhang. A perturbation-based approach for continuous network design problem with emissions. Numerical Algebra, Control and Optimization, 2015, 5 (2) : 135-149. doi: 10.3934/naco.2015.5.135

[20]

Michelle L.F. Cheong, Rohit Bhatnagar, Stephen C. Graves. Logistics network design with supplier consolidation hubs and multiple shipment options. Journal of Industrial and Management Optimization, 2007, 3 (1) : 51-69. doi: 10.3934/jimo.2007.3.51

2020 Impact Factor: 1.801

Metrics

  • PDF downloads (77)
  • HTML views (0)
  • Cited by (2)

[Back to Top]