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 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-a-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 2~(99) 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.