Networks with Unreliable Nodes and Edges: Monte Carlo Lifetime Estimation

Authors: Y. Shpungin

Abstract:

Estimating the lifetime distribution of computer networks in which nodes and links exist in time and are bound for failure is very useful in various applications. This problem is known to be NP-hard. In this paper we present efficient combinatorial approaches to Monte Carlo estimation of network lifetime distribution. We also present some simulation results.

Keywords: Combinatorial spectrum, Monte Carlo, Networklifetime, Unreliable nodes and edges.

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

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, pp. 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, pp. 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, pp. 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 an Informational Sciences, 6, 1992, pp. 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,
[15] M Lomonosov, Y. Shpungin, "Combinatorics of Reliability Monte Carlo", Random Structures & Algorithms, 14,1999, No. 4, pp. 329-343.
[16] Y.Shpungin, "Combinatorial and Computational Aspects of Monte Carlo Estimation of Network Reliability", PhD. 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.
[21] Y. Shpungin, Combinatorial Approaches to Monte Carlo estimation of dynamic systems reliability parameters, Communication of Dependability and Quality Management: An International Journal, Volume 9, Number 1, 2006, pp. 69-75.
[22] Y. Shpungin, Combinatorial Approach to Reliability Evaluation of Network with Unreliable Nodes and Unreliable Edges, International Journal of Computer Science, Vol 1, num. 3, 2006, pp. 177-183.
[23] I. Gertsbakh, Reliability Theory, Springer-Verlag, 2000.