Title :
Finding Maximum Reliable Path in Mesh Networks under Multiple Failures
Author :
Yuan, Shengli ; Raghavachari, Balaji ; Patel, Ankitkumar
Author_Institution :
Dept. of Comput. & Math. Sci., Univ. of Houston - Downtown, Houston, TX, USA
Abstract :
In this work, we study the NP-hard problem of finding the path of maximum reliability between two end nodes in mesh networks against simultaneous failures of multiple links. The links belong to shared risk link groups (SRLGs) that have arbitrary failure probabilities. We propose a novel algorithm to find the optimal path with semi-polynomial running time and prove its correctness.
Keywords :
computational complexity; optical fibre networks; optimisation; polynomials; telecommunication network reliability; NP-hard problem; maximum reliable path; mesh networks; multiple failures; multiple links; path finding; reliability; semipolynomial running time; shared risk link groups; Complexity theory; Computer network reliability; Mesh networks; Optical fiber networks; Optical fibers; Reliability;
Conference_Titel :
Computer Communications and Networks (ICCCN), 2010 Proceedings of 19th International Conference on
Conference_Location :
Zurich
Print_ISBN :
978-1-4244-7114-0
DOI :
10.1109/ICCCN.2010.5560082
