Title :
Edge disjoint paths with minimum delay subject to reliability constraint
Author :
Loh, Ruen Chze ; Soh, Sieteng ; Lazarescu, Mihai
Author_Institution :
Dept. of Comput., Curtin Univ. of Technol., Perth, WA, Australia
Abstract :
Recently, multipaths solutions have been proposed to improve the quality-of-service (QoS) in communication networks (CN). This paper describes a problem, ¿DP/RD, to obtain the ¿-edge-disjoint-path-set such that its reliability is at least R and its delay is minimal, for ¿¿1. ¿DP/RD is useful for applications that require non-compromised reliability while demanding minimum delay. In this paper we propose an approximate algorithm based on the Lagrange-relaxation to solve the problem. Our solution produces ¿DP that meets the reliability constraint R with delay¿(1+k)Dmin, for k¿1, and Dmin is the minimum path delay of any ¿DP in the CN. Simulations on forty randomly generated CNs show that our polynomial time algorithm produced ¿DP with delay and reliability comparable to those obtained using the exponential time brute-force approach.
Keywords :
quality of service; telecommunication network reliability; Lagrange-relaxation; edge disjoint paths; exponential time brute-force; minimum delay subject; non-compromised reliability; quality-of-service; reliability constraint; Approximation algorithms; Communication networks; Computer networks; Costs; Delay effects; Lagrangian functions; Optimized production technology; Polynomials; Quality of service; Telecommunication network reliability; Lagrange relaxation; approximate algorithm; multi-constrained edge disjoint paths; network delay; network reliability;
Conference_Titel :
Communications, 2009. APCC 2009. 15th Asia-Pacific Conference on
Conference_Location :
Shanghai
Print_ISBN :
978-1-4244-4784-8
Electronic_ISBN :
978-1-4244-4785-5
DOI :
10.1109/APCC.2009.5375519
