DocumentCode :
2013668
Title :
A Greedy Technique for Finding the Most Reliable Edge-Disjoint-Path-Set in a Network
Author :
Loh, Ruen Chze ; Soh, Sieteng ; Lazarescu, Mihai ; Rai, Suresh
Author_Institution :
Dept. of Comput., Curtin Univ. of Technol., Perth, WA, Australia
fYear :
2008
fDate :
15-17 Dec. 2008
Firstpage :
216
Lastpage :
223
Abstract :
Multipath routing protocols (MRP) help improve the network quality of service (QoS), including load balancing, fault tolerance (reliability), aggregate bandwidth and delay. While multipaths communication provides better failure-tolerance, their resilience only holds if the multiple paths are selected carefully. Note that selecting an optimal path set is a NP-complete problem. Recently, several algorithms have appeared in the literature to help construct multiple node-disjoint paths or multiple edge-disjoint paths. This paper presents two algorithms, discussing the later issue. The first algorithm, called clique-based-approach (CBA), finds the edge-disjoint-path-set with the optimal reliability. The second algorithm, greedy-CBA (CBA-G), is a heuristic that reduces the computational complexity of CBA. Results show that CBA-G improves the efficiency of CBA without negatively affecting its effectiveness. We also provide an explanation as to why CBA-G is able to produce edge-disjoint-path-sets with reliabilities equal or better than a benchmark protocol, DPSP.
Keywords :
computational complexity; multipath channels; quality of service; routing protocols; NP-complete problem; aggregate bandwidth; clique-based-approach; computational complexity; edge-disjoint-path-set; fault tolerance; greedy technique; load balancing; multipath routing protocols; multipaths communication; optimal reliability; quality of service; Aggregates; Bandwidth; Disruption tolerant networking; Fault tolerance; Load management; Materials requirements planning; Quality of service; Resilience; Routing protocols; Telecommunication network reliability; cliques; disjoint paths; multipath routing; reliability; reliable routing;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Dependable Computing, 2008. PRDC '08. 14th IEEE Pacific Rim International Symposium on
Conference_Location :
Taipei
Print_ISBN :
978-0-7695-3448-0
Electronic_ISBN :
978-0-7695-3448-0
Type :
conf
DOI :
10.1109/PRDC.2008.16
Filename :
4725299
Link To Document :
بازگشت