A Practical Algorithm for Reliable Network Topology Design
MetadataShow full item record
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.
Showing items related by title, author, creator and subject.
Elshqeirat, Basima; Soh, Sie Teng; Rai, S.; Lazarescu, Mihai (2015)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 ...
Elshqeirat, Basima; Soh, Sie Teng; Chin, K. (2015)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 ...
Elshqeirat, Basima; Soh, Sieteng; Rai, S.; Lazarescu, M. (2015)This paper addresses an NP-hard problem, referred to as Network Topology Design with minimum Cost subject to a Reliability constraint (NTD-CR), to design a minimal-cost communication network topology that satisfies a ...