Bi-Objective Network Topology Design with Reliability Constraint
This paper addresses an NP-hard problem, called NTD-CB/R, whose solution is of importance to applications requiring one or more Quality of Service (QoS). Specifically, the problem calls for a network topology that meets two objectives, i.e., minimal cost and maximum bandwidth, subject to a predefine...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Conference Paper |
| Published: |
IEEE
2015
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/20.500.11937/13724 |
| _version_ | 1848748422691028992 |
|---|---|
| author | Elshqeirat, Basima Soh, Sie Teng Chin, K. |
| author2 | Omar Al-Jarrah |
| author_facet | Omar Al-Jarrah Elshqeirat, Basima Soh, Sie Teng Chin, K. |
| author_sort | Elshqeirat, Basima |
| building | Curtin Institutional Repository |
| collection | Online Access |
| description | This paper addresses an NP-hard problem, called NTD-CB/R, whose solution is of importance to applications requiring one or more Quality of Service (QoS). Specifically, the problem calls for a network topology that meets two objectives, i.e., minimal cost and maximum bandwidth, subject to a predefined (s, t) reliability constraint. We approach the problem by converting it into one with a single objective. This is achieved via a ratio, called bcr, between network bandwidth and cost to measure the goodness of each topology, and by applying Lagrange relaxation. Then we propose a dynamic programming (DP) scheme, and propose a heuristic solution, called DPCB/R, to generate each topology using all of its n (s, t) paths. This paper also proposes three heuristic path orders that allow DPCB/R to generate and use only k≤n paths to reduce its time complexity while producing similar results. Extensive simulations using 125 benchmark networks with various sizes show the merits of the path-orders, and effectiveness of our approach. DPCB/R is able to generate 88% optimal results for the networks. Further, its non-optimal results have a bcr ratio, bandwidth, and cost of only up to 1.56%, 0.9%, and, 2.1% off from the optimal, respectively. Further, for a grid network that contains 299 paths it uses only 1.1-27% of the paths while producing a topology that is only 0.92% off from optimal, with respect to bcr metric. |
| first_indexed | 2025-11-14T07:04:48Z |
| format | Conference Paper |
| id | curtin-20.500.11937-13724 |
| institution | Curtin University Malaysia |
| institution_category | Local University |
| last_indexed | 2025-11-14T07:04:48Z |
| publishDate | 2015 |
| publisher | IEEE |
| recordtype | eprints |
| repository_type | Digital Repository |
| spelling | curtin-20.500.11937-137242023-02-27T07:34:27Z Bi-Objective Network Topology Design with Reliability Constraint Elshqeirat, Basima Soh, Sie Teng Chin, K. Omar Al-Jarrah Mohammad Al-Rousan network optimisation reliability Lagrange relaxation network topology design bandwidth Dynamic programming This paper addresses an NP-hard problem, called NTD-CB/R, whose solution is of importance to applications requiring one or more Quality of Service (QoS). Specifically, the problem calls for a network topology that meets two objectives, i.e., minimal cost and maximum bandwidth, subject to a predefined (s, t) reliability constraint. We approach the problem by converting it into one with a single objective. This is achieved via a ratio, called bcr, between network bandwidth and cost to measure the goodness of each topology, and by applying Lagrange relaxation. Then we propose a dynamic programming (DP) scheme, and propose a heuristic solution, called DPCB/R, to generate each topology using all of its n (s, t) paths. This paper also proposes three heuristic path orders that allow DPCB/R to generate and use only k≤n paths to reduce its time complexity while producing similar results. Extensive simulations using 125 benchmark networks with various sizes show the merits of the path-orders, and effectiveness of our approach. DPCB/R is able to generate 88% optimal results for the networks. Further, its non-optimal results have a bcr ratio, bandwidth, and cost of only up to 1.56%, 0.9%, and, 2.1% off from the optimal, respectively. Further, for a grid network that contains 299 paths it uses only 1.1-27% of the paths while producing a topology that is only 0.92% off from optimal, with respect to bcr metric. 2015 Conference Paper http://hdl.handle.net/20.500.11937/13724 10.1109/IACS.2015.7103233 IEEE restricted |
| spellingShingle | network optimisation reliability Lagrange relaxation network topology design bandwidth Dynamic programming Elshqeirat, Basima Soh, Sie Teng Chin, K. Bi-Objective Network Topology Design with Reliability Constraint |
| title | Bi-Objective Network Topology Design with Reliability Constraint |
| title_full | Bi-Objective Network Topology Design with Reliability Constraint |
| title_fullStr | Bi-Objective Network Topology Design with Reliability Constraint |
| title_full_unstemmed | Bi-Objective Network Topology Design with Reliability Constraint |
| title_short | Bi-Objective Network Topology Design with Reliability Constraint |
| title_sort | bi-objective network topology design with reliability constraint |
| topic | network optimisation reliability Lagrange relaxation network topology design bandwidth Dynamic programming |
| url | http://hdl.handle.net/20.500.11937/13724 |