DESIGN OF RELIABLE NETWORKS

In many applications, the network designer may want to know how to synthesize a reliable network. Assume that a network, denoted as G(n,e), has the number of nodes n and the number of edges e, and the operational probability of each edge is known. The system reliability of the network is defined to be the probability that every pair of nodes can communicate with each other. A network synthesis problem considered in this paper is to find a network G(n,e)* that maximizes system reliability over the class of all networks having n nodes and e edges. We find the optimal networks for the classes of networks G(n,n-1), G(n,n) and G(n,n+1), respectively. In addition, an upper bound of maximum reliability for the networks with n nodes and e edges (e greater-than-or-equal-to n + 2) is derived in terms of node degrees. Computational experiments for the reliability upper bound are also presented. The results show that the proposed reliability upper bound is effective.