Edge disjoint paths with minimum delay subject to reliability constraint
MetadataShow full item record
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 k1, 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.
Copyright © 2009 IEEE This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.
Showing items related by title, author, creator and subject.
Loh, Ruen Chze (2010)Most of today’s computer communications use only a single (s,t) path to transmit a message from a source node s to a destination node t. There are two major problems with this single path communication. Firstly, the ...
A high-resolution underwater acoustic communication propagation simulator with multi-path transient sea-surface interactionsCaley, M.; Duncan, Alec (2015)A channel simulation has been developed to explore the fine time-scale Doppler and multi-path arrival-time delay spreading imparted to underwater communication signals by interaction with the transient ocean surface. The ...
Elshqeirat, B.; Soh, Sieteng; Rai, S.; Lazarescu, Mihai (2013)This paper addresses an NP-hard problem of designing a network topology with maximum (s, t) reliability subject to given constraints, such as the computer centers location (nodes), their connecting links reliability and ...