A Practical Algorithm for Reliable Network Topology Design
Abstract
This paper addresses an NPhard 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 pathorders are proposed to improve the effectiveness of DPA. Further, the pathorders 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 pathorders, 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 nonoptimal 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.
Citation
Source Title
Additional URLs
ISSN
Collection
Related items
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 predefined bandwidth (Bmin) constraint, given (i) locations of the various ...

Elshqeirat, Basima; Soh, Sie Teng; Chin, K. (2015)This paper addresses an NPhard problem, called NTDCB/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 NPhard problem, referred to as Network Topology Design with minimum Cost subject to a Reliability constraint (NTDCR), to design a minimalcost communication network topology that satisfies a ...