Edge disjoint paths with minimum delay subject to reliability constraint

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)D_min, for k¿1, and D_min 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.