The Design and Analysis of Reliable Communication Networks

Abstract

In this study, a communication network is represented by a graph, and the problem of designing a network that will operate as reliably as possible is investigated. Failure of the network is associated with the removal of a set of nodes which disconnects the graph or by the removal of a set of edges which disconnects the graph. We are interested in finding reliable graphs for which the probability of disconnection is as small as possible.We survey various reliability measures and then deal with the design of a reliable communication network based on the construction of graphs with the smallest number of minimum cut sets. The number of minimum size vertex cut sets may give a much better indication of the reliability of the graph than the connectivity alone, at least where the probability of failure of a vertex is close to 0. The determination of the number of minimum size vertex cut sets of such a graph is therefore of interest and we describe a construction of infinite families of such graphs in various cases. These cases are spread through the range3 ≤ k < 1, (where k = connectivity = degree of the graph, |v|= the number of vertices of the graph ) ,8 lVl Graphs with the smallest number of minimum cut sets are compared with other graphs of optimal connectivity, to assess their reliability when other values of the probability are considered. These values of the probability are; when the probability of failure of a vertex is close to 1, when the probability of failure of an edge is close to 0, and when the probability of failure of an edge is close to 1. In many cases the graphs proved to be highly reliable. Consideration is also given to the expected number of vertices disconnected from the largest component of a graph.

Date of Award	Feb 1986
Original language	English
Awarding Institution	Polytechnic of Wales