A quadratic-time heuristic method for reliable network design with arbitrary traffic loads

The goal of a reliable network is to ensure that all transmitted messages arrive at their intended destinations uncorrupted. Most network design techniques concern themselves with channel capacity allocation and cost constraints and ignore reliability analysis. Conversely, network reliability analysis methods focus on connectivity and ignore traffic loads and channel capacities. This paper presents a design strategy to enhance the reliability of an existing network by modifying its topology. This method takes into account traffic distributions. A new reliability metric is introduced which is the probability that all transmitted messages arrive at their intended destinations under the given traffic distribution. The design strategy adds links to the network to maximize the probability that all transmitted messages arrive at their intended destinations. The network design technique uses an approximate network reliability analysis algorithm to achieve quadratic-time performance