Bi-Objective Topology Design of Communication Networks Using Dynamic Programming
This paper provides an algorithm to design a communication network topology with minimal cost (C) and maximum (s, t) reliability (R) subject to a pre-defined bandwidth (Bmin) constraint, given (i) locations of the various computer nodes, (ii) their connecting links, (iii) each link’s reliability, co...
| Main Authors: | , , , |
|---|---|
| Format: | Journal Article |
| Published: |
RAMS Consultants
2015
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/20.500.11937/23690 |
| _version_ | 1848751219770654720 |
|---|---|
| author | Elshqeirat, Basima Soh, Sie Teng Rai, S. Lazarescu, Mihai |
| author_facet | Elshqeirat, Basima Soh, Sie Teng Rai, S. Lazarescu, Mihai |
| author_sort | Elshqeirat, Basima |
| building | Curtin Institutional Repository |
| collection | Online Access |
| description | This paper provides an algorithm to design a communication network topology with minimal cost (C) and maximum (s, t) reliability (R) subject to a pre-defined bandwidth (Bmin) constraint, given (i) locations of the various computer nodes, (ii) their connecting links, (iii) each link’s reliability, cost and bandwidth, and (iv) a minimum bandwidth for the network. The bi-objective optimization problem is known NP-hard; henceforth we call the problem NTD-CR/B. We use the dynamic programming (DP) formulation as the engine in our proposed approach, DPCR/B, to generate the topology for solving NTD-CR/B. Further, we propose three greedy heuristics that enumerate and order only k?n (s, t) paths, where n is the total number of (s, t) paths in the network. Each heuristic allows DPCR/B to obtain the selected paths to form the topology using only k paths, which improves the time complexity while producing near optimal topology. Extensive simulations on large networks with various sizes show that DPCR/B is able to generate 91.2% optimal results while using only 1.37-27% of all paths in the grid networks that typically contain up to 299 paths. |
| first_indexed | 2025-11-14T07:49:15Z |
| format | Journal Article |
| id | curtin-20.500.11937-23690 |
| institution | Curtin University Malaysia |
| institution_category | Local University |
| last_indexed | 2025-11-14T07:49:15Z |
| publishDate | 2015 |
| publisher | RAMS Consultants |
| recordtype | eprints |
| repository_type | Digital Repository |
| spelling | curtin-20.500.11937-236902017-01-30T12:38:41Z Bi-Objective Topology Design of Communication Networks Using Dynamic Programming Elshqeirat, Basima Soh, Sie Teng Rai, S. Lazarescu, Mihai bi-objective optimisation lagrange relaxation reliability network topology design bandwidth Dynamic programming This paper provides an algorithm to design a communication network topology with minimal cost (C) and maximum (s, t) reliability (R) subject to a pre-defined bandwidth (Bmin) constraint, given (i) locations of the various computer nodes, (ii) their connecting links, (iii) each link’s reliability, cost and bandwidth, and (iv) a minimum bandwidth for the network. The bi-objective optimization problem is known NP-hard; henceforth we call the problem NTD-CR/B. We use the dynamic programming (DP) formulation as the engine in our proposed approach, DPCR/B, to generate the topology for solving NTD-CR/B. Further, we propose three greedy heuristics that enumerate and order only k?n (s, t) paths, where n is the total number of (s, t) paths in the network. Each heuristic allows DPCR/B to obtain the selected paths to form the topology using only k paths, which improves the time complexity while producing near optimal topology. Extensive simulations on large networks with various sizes show that DPCR/B is able to generate 91.2% optimal results while using only 1.37-27% of all paths in the grid networks that typically contain up to 299 paths. 2015 Journal Article http://hdl.handle.net/20.500.11937/23690 RAMS Consultants restricted |
| spellingShingle | bi-objective optimisation lagrange relaxation reliability network topology design bandwidth Dynamic programming Elshqeirat, Basima Soh, Sie Teng Rai, S. Lazarescu, Mihai Bi-Objective Topology Design of Communication Networks Using Dynamic Programming |
| title | Bi-Objective Topology Design of Communication Networks Using Dynamic Programming |
| title_full | Bi-Objective Topology Design of Communication Networks Using Dynamic Programming |
| title_fullStr | Bi-Objective Topology Design of Communication Networks Using Dynamic Programming |
| title_full_unstemmed | Bi-Objective Topology Design of Communication Networks Using Dynamic Programming |
| title_short | Bi-Objective Topology Design of Communication Networks Using Dynamic Programming |
| title_sort | bi-objective topology design of communication networks using dynamic programming |
| topic | bi-objective optimisation lagrange relaxation reliability network topology design bandwidth Dynamic programming |
| url | http://hdl.handle.net/20.500.11937/23690 |