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 applicat...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Conference Paper |
| Published: |
ieee
2009
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/20.500.11937/28840 |
| _version_ | 1848752643672899584 |
|---|---|
| author | Loh, Rue-chze Soh, Sieteng Lazarescu, Mihai |
| author2 | na |
| author_facet | na Loh, Rue-chze Soh, Sieteng Lazarescu, Mihai |
| author_sort | Loh, Rue-chze |
| building | Curtin Institutional Repository |
| collection | Online Access |
| description | 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. |
| first_indexed | 2025-11-14T08:11:53Z |
| format | Conference Paper |
| id | curtin-20.500.11937-28840 |
| institution | Curtin University Malaysia |
| institution_category | Local University |
| last_indexed | 2025-11-14T08:11:53Z |
| publishDate | 2009 |
| publisher | ieee |
| recordtype | eprints |
| repository_type | Digital Repository |
| spelling | curtin-20.500.11937-288402017-10-02T02:27:39Z Edge disjoint paths with minimum delay subject to reliability constraint Loh, Rue-chze Soh, Sieteng Lazarescu, Mihai na network reliability - network delay. - I Lagrange relaxation approximate algorithm - multi-constrained edge disjoint paths 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. 2009 Conference Paper http://hdl.handle.net/20.500.11937/28840 ieee fulltext |
| spellingShingle | network reliability - network delay. - I Lagrange relaxation approximate algorithm - multi-constrained edge disjoint paths Loh, Rue-chze Soh, Sieteng Lazarescu, Mihai Edge disjoint paths with minimum delay subject to reliability constraint |
| title | Edge disjoint paths with minimum delay subject to reliability constraint |
| title_full | Edge disjoint paths with minimum delay subject to reliability constraint |
| title_fullStr | Edge disjoint paths with minimum delay subject to reliability constraint |
| title_full_unstemmed | Edge disjoint paths with minimum delay subject to reliability constraint |
| title_short | Edge disjoint paths with minimum delay subject to reliability constraint |
| title_sort | edge disjoint paths with minimum delay subject to reliability constraint |
| topic | network reliability - network delay. - I Lagrange relaxation approximate algorithm - multi-constrained edge disjoint paths |
| url | http://hdl.handle.net/20.500.11937/28840 |