A Dynamic Programming Algorithm for Reliable Network Design

Abstract

This paper addresses an NP-hard problem to design a network topology with maximum all-terminal reliability subject to a cost constraint, given the locations of the various computer centers (nodes), their connecting links, each link’s reliability and cost, and the maximum budget cost to install the links. Because cost is always a major focus in network design, this problem is practical for critical applications requiring maximized reliability. This paper first formulates a Dynamic Programming (DP) scheme to solve the problem. A DP approach, called DPA-1, generates the topology using all spanning trees of the network (ST_G). The paper shows that DPA-1 is optimal if the spanning trees are optimally ordered. Further, the paper describes an alternative DP algorithm, called DPA-2, that uses only k spanning trees (k <=n , where n = |ST_G| ) sorted in increasing weight and lexicographic order to improve the time efficiency of DPA-1 while producing similar results. Extensive simulations using hundreds of benchmark networks that contain up to 1.899^102 spanning trees show the merits of using the sorting method, and the effectiveness of our algorithms. DPA-2 is able to generate 85% optimal results, while using only a small number of k spanning trees, and up to 16.83 CPU seconds. Furthermore, the non-optimal results are only up to 3.4% off from optimal for the simulated examples.