Premium
Improving reliability bounds in computer networks
Author(s) -
Brecht Timothy B.,
Colbourn Charles J.
Publication year - 1986
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230160404
Subject(s) - terminal (telecommunication) , reliability (semiconductor) , computer science , upper and lower bounds , mathematical optimization , algorithm , mathematics , computer network , mathematical analysis , power (physics) , quantum mechanics , physics
The probability that a computer network is operational in an environment of statistically independent link failures has been widely studied. Three natural problems arise, when all nodes are to be connected (all‐terminal reliability), when two nodes are to communicate (2‐terminal reliability), and when k specified nodes are to communicate ( k ‐terminal reliability); the latter case includes the first two. Each of these reliability measures is NP‐hard to compute, and thus efficiently computable reliability bounds are of significant interest. To date, the all‐terminal and 2‐terminal cases have been treated separately, and few results apply to the k ‐terminal case. In this paper, we develop a simple strategy to obtain k ‐terminal reliability bounds. In the process, we demonstrate improvements on the previous best bounds for all‐terminal, k ‐terminal, and 2‐terminal reliability. Computational experience with these new bounds is reported, by comparing the new lower bounds to existing lower bounds.