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

作者：Loh Ruen Chze^*; Soh Sieteng; Lazarescu Mihai

来源：IEEE Transactions on Reliability, 2011, 60(1): 88-93.

DOI：10.1109/TR.2010.2103592

• Approximate algorithm
• lagrange-relaxation
• multi-constrained edge-disjoint paths
• network delay
• network reliability

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 describes the lambda DP/DR problem to obtain lambda >= 1 edge-disjoint (s, t)-paths (lambda 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 lambda DP with delta(lambda DP) <= D, and reliability bounded by vertical bar Log(R(min))vertical bar <= vertical bar log(rho(lambda DP))vertical bar <= (1 + k)*vertical bar log(R(min))vertical bar, 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 lambda DP with delay and reliability comparable to those obtained by the optimal but exponential time algorithm.

• 出版日期2011-3