| Title: | Network Reliability |
| Authors: | Ball, Michael O.
Colbourn, Charles J.
Provan, J.S. |
| Department/Program: | ISR |
| Type: | Technical Report |
| Keywords: | algorithms,
combinatorics, computational complexity, graph theory, reliability,
network reliability, networks, Systems Integration |
| Issue Date: | 1992 |
| Series/Report no.: | ISR; TR 1992-74 |
| Abstract: | This
paper provides a detailed review of the state of the art in the field
of network reliability analysis. The primary model treated is a
stochastic network in which arcs fail randomly and independently with
known failure probabilities. The inputs to the basic network reliability
analysis problem consist of the network and a failure probability for
each are in the network. The output is some measure of the reliability
of the network. The reliability measures treated most extensively in
this paper are: the two terminal measure, the probability that there
exists a path between two specified nodes; the all-terminal measure the
probability that the network is connected and the k-terminal measure,
the probability that a specified node subset, K, is connected. In all
cases the results concerning each problem's computational complexity,
exact algorithms, analytic bounds and Monte Carlo methods are covered.
The paper also treats more complex reliability measures including
performability measures and stochastic shortest path, max flow and PERT
problems. A discussion is provided on applications and using the
techniques covered in practice. |
| URI: | http://hdl.handle.net/1903/5255 |
| Appears in Collections: | Institute for Systems Research Technical Reports
|
@ARTICLE{4335422,
author={Ball, M.O.},
journal={Reliability, IEEE Transactions on},
title={Computational Complexity of Network Reliability Analysis: An Overview},
year={1986},
volume={35},
number={3},
pages={230-239},
abstract={This paper presents an overview of results related to
the computational complexity of network reliability analysis problems.
Network reliability analysis problems deal with the determination of
reliability measures for stochastic networks. We show how these problems
are related to the more familiar computational network problems of
recognizing certain subnetworks, finding optimal subnetworks, and
counting certain subnetworks. We use these relationships to show that
the k-terminal, the 2-terminal, and the all-terminal network reliability
analysis problems are at least as hard as the renowned set of
computationally difficult problems, NP-Complete. Finally, we discuss the
impact of these results on how one should approach problem solving in
this area.},
keywords={Algorithm design and analysis;Computational
complexity;Computer network reliability;Computer networks;Educational
institutions;Graph theory;Problem-solving;Reliability theory;Seismic
measurements;Stochastic processes},
doi={
10.1109/TR.1986.4335422},
ISSN={
0018-9529},}
@INPROCEEDINGS{12999,
author={Ray, G. A. and Dunsmore, J. J.},
booktitle={INFOCOM '88. Networks: Evolution or Revolution,
Proceedings. Seventh Annual Joint Conference of the IEEE Computer and
Communcations Societies, IEEE},
title={Reliability of network topologies},
year={1988},
pages={842-850},
abstract={The authors present some analytical results which can be
used to compute network reliability. Some simple techniques to make
asymptotic approximations based on parameters of the network topology
are derived. Explicit reliability formulae are computed for four network
topologies, including the star and counterrotating ring. Actual
manufacturer's data and failure models for laser diodes and LEDs are
used to compare the effects of transmitter reliability on the whole
network.<
>},
keywords={computer networks;graph theory;network
topology;reliability;LAN;LEDs;asymptotic approximations;counterrotating
ring;failure models;laser diodes;network reliability;network
topologies;network topology;reliability formulae;star
topology;transmitter reliability;Communication networks;Computer aided
manufacturing;Computer network reliability;Computer networks;Light
emitting diodes;Network topology;Optical transmitters;Reliability
theory;Telecommunication network reliability;Virtual manufacturing},
doi={10.1109/INFCOM.1988.12999},}
@ARTICLE{5220476,
author={Abraham, J.A.},
journal={Reliability, IEEE Transactions on},
title={An Improved Algorithm for Network Reliability},
year={1979},
volume={R-28},
number={1},
pages={58-61},
abstract={Boolean algebra has been used to find the probability of
communication between a pair of nodes in a network by starting with a
Boolean product corresponding to simple paths between the pair of nodes
and making them disjoint (mutually exclusive). A theorem is given, the
use of which enables the disjoint products to be found much faster than
by existing methods. An algorithm and results of its implementation on a
computer are given. Comparisons with existing methods show the
usefulness of the algorithm for large networks.},
keywords={Algorithm design and analysis;Boolean algebra;Computer
network reliability;Computer networks;Ducts;Fault
trees;Telecommunication network reliability;Boolean expressions;Disjoint
products;Reliability algorithm;Terminalpair reliability},
doi={
10.1109/TR.1979.5220476},
ISSN={
0018-9529},}
