Improving reliability bounds in computer networks

✍ Scribed by Timothy B. Brecht; Charles J. Colbourn

• Publisher: John Wiley and Sons
• Year: 1986
• Tongue: English
• Weight: 538 KB
• Volume: 16
• Category: Article
• ISSN: 0028-3045
• DOI: 10.1002/net.3230160404

✦ Synopsis

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 wRh these new bounds is reported, by comparing the new lower bounds to existing lower bounds.