Combinatorial Approach to Reliability Evaluation of Network with Unreliable Nodes and Unreliable Edges
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.
[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.
[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.
@article{"International Journal of Information, Control and Computer Sciences:64265", author = "Y. Shpungin", title = "Combinatorial Approach to Reliability Evaluation of Network with Unreliable Nodes and Unreliable Edges", 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.", volume = "1", number = "12", pages = "4087-5", }
