Combinatorial Approach to Reliability Evaluation of Network with Unreliable Nodes and Unreliable Edges

Authors: Y. Shpungin

Abstract:

Estimating the reliability of a computer network has been a subject of great interest. It is a well known fact that this problem is NP-hard. In this paper we present a very efficient combinatorial approach for Monte Carlo reliability estimation of a network with unreliable nodes and unreliable edges. Its core is the computation of some network combinatorial invariants. These invariants, once computed, directly provide pure and simple framework for computation of network reliability. As a specific case of this approach we obtain tight lower and upper bounds for distributed network reliability (the so called residual connectedness reliability). We also present some simulation results.

Keywords: Combinatorial invariants, Monte Carlo simulation, reliability, unreliable nodes and unreliable edges.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1084712

References:

[1] Agraval, R. E. Barlow, "A survey of network reliability and domination theory", Operation Research, vol. 32, 1984, pp. 478-492.
[2] M.O. Ball, "Complexity of network reliability computation", Networks, 10, 1980, 153-165.
[3] R. E. Barlow, F. Proschan, Statistical Theory of Reliability and Life Testing, 1975. Holt, Rinehart & Winston.
[4] C. J. Colbourn, The Combinatorics of Network Reliabilty. Oxford Univ. Press.
[5] C.J. Colbourn, A. Satyanarayana, C. Suffel, K. Sutner, "Computing residual connectedness reliability for restricted networks", Discrete Applied Mathematics, 44, 1993, 221-232.
[6] Lucia I. P. Resende, "Implementation of factoring algorithm for reliability evaluation of undirected networks", IEEE,Trans. Reliability, vol 37, 1988, pp. 462-468.
[7] M. C. Easton, C. K. Wong, "Sequential destruction method for Monte Carlo evaluation of system reliability", IEEE Trans. Reliaility, vol R-29, 1980, pp. 27-32.
[8] T. Elperin, I. Gertsbakh, M. Lomonosov, "Estimation of network reliability using graph evolution models", IEEE Transactions on Reliability, 40(5), 1991, 572-581.
[9] T. Elperin, I. Gertsbakh, M. Lomonosov, "An evolution model for Monte Carlo estimation of equilibrium network renewal parameters", Probability in the Engineering and Informational Sciences, 6, 1992, 457-469.
[10] G. S. Fishman, "A Monte Carlo sampling plan for estimating network reliability", Operations Research, vol 34, 1986, pp. 581-592.
[11] G. S. Fishman, "A Monte Carlo sampling plan for estimating reliability parameters and related functions", Networks, vol. 17, 1987, pp 169-186.
[12] K-P. Hui, N. Bean, M. Kraetzl, and D P. Kroese, "The Tree Cut and Merge Algorithm for Estimation of Network Reliability", Probability in the Engineering and Informational Sciences, 17(1):24-25, 2003.
[13] H. Kumamoto, T. Kazuo, I. Koichi, E. J. Henley, "State transition Monte Carlo for evaluating large, repairable systems", IEEE Trans. Reliability, vol R-29, 1980, pp 376-380.
[14] M. Lomonosov, "On Monte Carlo estimates in network reliability", Probability in the Engineering and Information Sciences, 8, 1994, 245- 64.
[15] M Lomonosov, Y. Shpungin, "Combinatorics of Reliability Monte Carlo", Random Structures & Algorithms, 14,1999, No. 4, 329-343.
[16] Y.Shpungin, "Combinatorial and Computational Aspects of Monte Carlo Estimation of Network Reliability", Ph. D. Dissertation, Dept. of Mathematics and Computer Science, Ben Gurion University of the Negev, 1996.
[17] Gertsbakh and Y. Shpungin, "Combinatorial approaches to Monte Carlo estimation of network lifetime distribution", Appl. Stochastic Models Bus. Ind., 2004, 20:49-57.
[18] C. J. Colbourn, D. D. Harms, "Bounding all-terminal reliability in computer networks", Networks, 1988, pp. 1-12.
[19] Z. He, Y. Tian and Y. Chen, "Simulating the Reliability of Distributed Systems with Unreliable Nodes", I. J. of Simulation, vol 3, 1-2, pp. 68- 78.
[20] K-P. Hui, "Reliability Estimation", Ph D. dissertation, Faculty of Engineering, Computer and Mathematical Sciences, University of Adelaide, 2005.