The purpose of this paper is to propose a computational technique for evaluating the reliability of networks subject to stochastic failures. In this computation, a mathematical model is provided using a technique which incorporates the effect of the factoring decomposition theorem using polygon-to-chain and series-parallel reductions. The algorithm proceeds by identifying iteratively one of seven polygons and when it is discovered, the polygon is immediately removed and replaced by a simple chain after having changed the individual values of the reliability of each edge and each node of the polygon. Theoretically, the mathematical development follows the results presented by Satyanarayana & Wood and Theologou & Carlier. The computation process is recursively performed and less constrained in term of execution time and memory space, and generates an exact value of the reliability.
References
[1]
Institute of Electrical and Electronics Engineers (1990) IEEE Standard Computer Dictionary: A Compilation of IEEE Standard Computer Glossaries. IEEE Std 610, 1-217.
[2]
Deo, N. and Medidi, M. (1992) Parallel Algorithms for Terminal-Pair Reliability. IEEE Transactions on Reliability, 41, 201-209. https://doi.org/10.1109/24.257782
[3]
Dotson, W.P. and Gobien, J. (1979) A New Analysis Technique for Probabilistic Graphs. IEEE Transactions Circuits and Systems, 26, 855-865.
https://doi.org/10.1109/TCS.1979.1084573
[4]
Fratta, L. and Montanari, U.G. (1973) A Boolean Algebra Method for Computing the Terminal Reliability in a Communication Network. IEEE Transactions on Circuit Theory, 20, 203-211. https://doi.org/10.1109/TCT.1973.1083657
[5]
Heidtmann, K.D. (1989) Smaller Sums of Disjoint Products by Subproduct Inversion. IEEE Transactions on Reliability, 38, 305-311.
https://doi.org/10.1109/24.44172
[6]
Kuo, S.Y., Yeh, F.M. and Lin, H.Y. (2007) Efficient and Exact Reliability Evaluation for Networks with Imperfect Vertices. IEEE Transactions on Reliability, 56, 288-298. https://doi.org/10.1109/TR.2007.896770
[7]
Lin, H.Y., Kuo, S.Y. and Yeh, F.M. (2003) Minimal Cutset Enumeration and Network Reliability Evaluation by Recursive Merge and BDD. Proceedings of the 8th IEEE International Symposium on Computers and Communication, 2, 1530-1346.
[8]
Liu, H.H., Yang, W.T. and Liu, C.C. (1993) An Improved Minimizing Algorithm for the Summation of Disjoint Products by Shannon’s Expansion. Microelectronic Reliability, 33, 599-613.
[9]
Misra, K.B. (1970) An Algorithm for the Reliability Evaluation of Redundant Networks. Transactions on Reliability, R-9, 146-151.
https://doi.org/10.1109/TR.1970.5216434
[10]
Tarjan, R.E. (1972) Depth First Search and Linear Graph Algorithms. SIAM Journal of Computing, 1, 146-160. https://doi.org/10.1137/0201010
[11]
Yan, L. and Taha, H.A. (1994) A Recursive Approach for Enumerating Minimal Cutsets in a Network. IEEE Transaction on Reliability, 43, 383-388.
https://doi.org/10.1109/24.326430
[12]
Yoo, Y.B. and Deo, N. (1988) A Comparison of Algorithms for Terminal-Pair Reliability. IEEE Transactions on Reliability, 37, 210-215.
https://doi.org/10.1109/24.3743
[13]
Locks, M.O. and Wilson, J.M. (1992) Note on Disjoint Products Algorithms. IEEE Transactions on Reliability, 41, 81-84. https://doi.org/10.1109/24.126676
[14]
Simard, C. (1996) Contribution au problèmed’évaluation de la fiabilité des réseaux. Master Thesis, Laval University, Quebec, Canada, TJ-7.5-UL-1996.
[15]
Moskowitz, F. (1958) The Analysis of Redundancy Networks. Transactions of the American Institute of Electrical Engineers, Part I: Communication and Electronics, 77, 627-632.
[16]
Page, L.B. and Perry, J.E. (1988) A Practical Implementation of the Factoring Theorem for Network Reliability. IEEE Transactions on Reliability, 37, 259-267.
https://doi.org/10.1109/24.3752
[17]
Page, L.B. and Perry, J.E. (1989) Reliability of Directed Network Using the Factoring Theorem. IEEE Transactions on Reliability, 38, 556-562.
https://doi.org/10.1109/24.46479
[18]
Rebaiaia M.L. (2011) A Contribution to the Evaluation and Optimization of Networks Reliability. PhD Thesis, Laval University, Canada.
[19]
Resende, M.G.C. (1986) A Program for Reliability Evaluation of Undirected Networks via Polygon-to-Chain Reductions. IEEE Transaction on Reliability, 35, 24-29.
https://doi.org/10.1109/TR.1986.4335334
[20]
Satyanarayana. A. and Chang M. (1983) Network Reliability and the Factoring Theorems. Networks, 13, 107-120. https://doi.org/10.1002/net.3230130107
[21]
Satyanarayana, A. and Wood, R.K. (1985) A Linear-Time Algorithm for Computing K-Terminal Reliability in Series-Parallel Networks. SIAM Journal on Computing, 14, 818-832. https://doi.org/10.1137/0214057
[22]
Theologou, R. and Carlier, J.G. (1991) Factoring & Reduction for Networks with Imperfect Vertices. IEEE Transactions on Reliability, 40, 210-217.
https://doi.org/10.1109/24.87131
[23]
Hardy, G., Lucet, C. and Limnios, N. (2007) K-Terminal Network Reliability Measures with Binary Decision Diagrams. IEEE Transaction on Reliability, 56, 506-515.
https://doi.org/10.1109/TR.2007.898572
[24]
Rudell, R. (1993) Dynamic Variable Ordering for Ordered Binary Decision Diagrams. Proceedings of the IEEE International Conference on Computer Aided Design, Santa Clara, CA, 7-11 November 1993, 42-47.
[25]
Nakazawa, H. (1976) Bayesian Decomposition Method for Computing Reliability of Oriented Network. IEEE Transactions on Reliability, R-25, 77-80.
https://doi.org/10.1109/TR.1976.5214983
[26]
Kubat, B. (1989) Estimation of Reliability for Communication/Computer Networks-Simulation/Analytic Approach. IEEE Transactions on Reliability, 37, 927-933.
https://doi.org/10.1109/26.35372
[27]
Rebaiaia, M.-L. and Ait-Kadi, D. (2015) Reliability Evaluation of Imperfect K-Terminal Stochastic Networks Using Polygon-to-Chain and Series-Parallel Reductions. Proceedings of the 11th ACM Symposium on QoS and Security for Wireless and Mobile Networks, Cancun, Mexico, 2-6 November 2015, 115-122.
[28]
Valian, L.G. (1979) The Complexity of Enumerating and Reliability Problems. SIAM Journal of Computing, 8, 410-421. https://doi.org/10.1137/0208032
[29]
Ball, M.O. (1986) Computational Complexity of Network Reliability Analysis: An Overview. IEEE Transactions on Reliability, 35, 230-239.
https://doi.org/10.1109/TR.1986.4335422
[30]
Rosenthal, A. (1974) Computing Reliability of Complex Systems. PhD Thesis, University of California, Berkeley.
[31]
Wood, R.K. (1986) Factoring Algorithms for Computing K-Terminal Network Reliability. IEEE Transactions on Reliability, 35, 269-278.
https://doi.org/10.1109/TR.1986.4335431
[32]
Barlow, E.B. and Proschan, F. (1975) Statistical Theory of Reliability and Life Testing: Probability Models (International Series in Decision Processes), (Ed.) Rinehart & Winston, Holt.
[33]
Moore, E.F. and Shannon, C.E. (1956) Reliable Circuits Using Less Reliable Relay. Journal of the Franklin Institute, 262, 281-297.
[34]
Murchland, J. (1973) Calculating the Probability That a Graph Is Disconnected. Working Paper No. 18.
[35]
Wang, S.-D. and Sun, C.-H. (1996) Transformations of Star-Delta and Delta-Star Reliability Networks. IEEE Transactions on Reliability, 45, 120-126.
https://doi.org/10.1109/24.488927
[36]
Choi, M.S and Jun, C-H. (1995) Some Variants of Polygon-to-Chain in Evaluating Reliability of Undirected Networks. Microelectronics Reliability, 35, 1-11.
https://doi.org/10.1016/0026-2714(94)P1833-X
