Addressing the Most Reliable Edge-Disjoint Paths With a Delay Constraint

Recently, multipath solutions have been proposed to improve the quality-of-service of the source to destination (s,t)-path in communication networks (CNs). This paper de scribes the λDP/DR problem to obtain λ ≥ 1 edge-disjoint (s,t)-paths (λDP) such that its reliability is maximized while keeping its delay no longer than a delay constraint D ≥ 1. This problem is NP-hard, and thus this paper proposes an approximate solution using Lagrange-relaxation. Our algorithm generates λDP with δ(λDP) ≤ D, and reliability bounded by |log(R_min)| ≤ |log(ρ(λDP))| ≤ (1 + k)*|log(R_min)|, where R_min is the minimum reliability of any (s, t)-path in the CN, and k ≥ 1. Our simulations on forty random CNs and large grid networks show that our solution produces λDP with delay and reliability comparable to those obtained by the optimal but exponential time algorithm.