The Combinatorics of Network Reliability

Communications networks form the 'nervous system' of modern information transfer, for instance, in computers and telephony. The analysis of the reliability of these pathways becomes increasingly important as the complexity of the networks escalates. This research monograph presents a simple network model, which is then used throughout for the development of reliability problems and the introduction of combinatorial ideas. The network design is predicated on the relationship between the enduser (e.g. a terminal or a device), and the traffic it generates, with its concomitant delay and routing requirements. Failures can arise in the local network or in the 'backbone' network; the latter would be a catastrophic event that must be analyzed carefully to prevent its occurrence. As the reliability problems are found to be intractable, algorithms are studied that are applicable to restricted classes of networks. Proofs of the major combinatorial theorems are included, as well as a survey of relevant work.