DocumentCode
1857641
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
fYear
2010
fDate
2-5 Aug. 2010
Firstpage
1
Lastpage
6
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;
fLanguage
English
Publisher
ieee
Conference_Titel
Computer Communications and Networks (ICCCN), 2010 Proceedings of 19th International Conference on
Conference_Location
Zurich
ISSN
1095-2055
Print_ISBN
978-1-4244-7114-0
Type
conf
DOI
10.1109/ICCCN.2010.5560082
Filename
5560082
Link To Document