A Practical Algorithm for Reliable Network Topology Design
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 cost, and the maximum budget cost to install the links. Cost is a major issue in...
| Main Authors: | , , , |
|---|---|
| Format: | Journal Article |
| Published: |
RAMS Consultants
2013
|
| Subjects: | |
| Online Access: | http://www.ijpe-online.com/attachments/article/696/pp.397-408%20Paper%205%20IJPE%20443.12%20Soh%2029.08.12.pdf http://hdl.handle.net/20.500.11937/29118 |
| _version_ | 1848752718724726784 |
|---|---|
| author | Elshqeirat, B. Soh, Sieteng Rai, S. Lazarescu, Mihai |
| author_facet | Elshqeirat, B. Soh, Sieteng Rai, S. Lazarescu, Mihai |
| author_sort | Elshqeirat, B. |
| building | Curtin Institutional Repository |
| collection | Online Access |
| description | 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 cost, and the maximum budget cost to install the links. Cost is a major issue in the network design, and thus the problem is applicable for networks requiring maximized reliability. This paper presents a dynamic programming (DP) scheme to solve the problem. Then, it describes a DP approach, called DPA, to generate the topology using all (s, t) paths in the network. Five different path-orders are proposed to improve the effectiveness of DPA. Further, the path-orders allow DPA to generate only k=1 paths dynamically from the graph model of the network and stops if a path inclusion leads to an insignificant addition in the resulting topology’s reliability. This step reduces the time complexity significantly while producing almost equal results as compared to using all (s, t) paths. Extensive simulations using benchmark networks with various sizes show the merits of path-orders, and the effectiveness and advantage of our DPA vis-à-vis to three existing techniques. Our proposed DPA is able to generate 92% optimal results on the networks using only 6% to 11% of the (s, t) paths for large networks. Further, its non-optimal results are no more than 0.77% off that of optimal. Finally, for a 2×100 grid network that contains 299 paths, DPA requires only up to k=987 paths to generate topology with cost 99% of the total cost and reliability 99.35% of that of the original network. |
| first_indexed | 2025-11-14T08:13:05Z |
| format | Journal Article |
| id | curtin-20.500.11937-29118 |
| institution | Curtin University Malaysia |
| institution_category | Local University |
| last_indexed | 2025-11-14T08:13:05Z |
| publishDate | 2013 |
| publisher | RAMS Consultants |
| recordtype | eprints |
| repository_type | Digital Repository |
| spelling | curtin-20.500.11937-291182017-01-30T13:10:25Z A Practical Algorithm for Reliable Network Topology Design Elshqeirat, B. Soh, Sieteng Rai, S. Lazarescu, Mihai network reliability terminal reliability network optimization Dynamic programing network topology design 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 cost, and the maximum budget cost to install the links. Cost is a major issue in the network design, and thus the problem is applicable for networks requiring maximized reliability. This paper presents a dynamic programming (DP) scheme to solve the problem. Then, it describes a DP approach, called DPA, to generate the topology using all (s, t) paths in the network. Five different path-orders are proposed to improve the effectiveness of DPA. Further, the path-orders allow DPA to generate only k=1 paths dynamically from the graph model of the network and stops if a path inclusion leads to an insignificant addition in the resulting topology’s reliability. This step reduces the time complexity significantly while producing almost equal results as compared to using all (s, t) paths. Extensive simulations using benchmark networks with various sizes show the merits of path-orders, and the effectiveness and advantage of our DPA vis-à-vis to three existing techniques. Our proposed DPA is able to generate 92% optimal results on the networks using only 6% to 11% of the (s, t) paths for large networks. Further, its non-optimal results are no more than 0.77% off that of optimal. Finally, for a 2×100 grid network that contains 299 paths, DPA requires only up to k=987 paths to generate topology with cost 99% of the total cost and reliability 99.35% of that of the original network. 2013 Journal Article http://hdl.handle.net/20.500.11937/29118 http://www.ijpe-online.com/attachments/article/696/pp.397-408%20Paper%205%20IJPE%20443.12%20Soh%2029.08.12.pdf RAMS Consultants restricted |
| spellingShingle | network reliability terminal reliability network optimization Dynamic programing network topology design Elshqeirat, B. Soh, Sieteng Rai, S. Lazarescu, Mihai A Practical Algorithm for Reliable Network Topology Design |
| title | A Practical Algorithm for Reliable Network Topology Design |
| title_full | A Practical Algorithm for Reliable Network Topology Design |
| title_fullStr | A Practical Algorithm for Reliable Network Topology Design |
| title_full_unstemmed | A Practical Algorithm for Reliable Network Topology Design |
| title_short | A Practical Algorithm for Reliable Network Topology Design |
| title_sort | practical algorithm for reliable network topology design |
| topic | network reliability terminal reliability network optimization Dynamic programing network topology design |
| url | http://www.ijpe-online.com/attachments/article/696/pp.397-408%20Paper%205%20IJPE%20443.12%20Soh%2029.08.12.pdf http://hdl.handle.net/20.500.11937/29118 |