×

Sixty years of network reliability. (English) Zbl 1432.68045

Summary: The study of network reliability started in 1956 with a groundbreaking paper by E. F. Moore and C. E. Shannon [J. Franklin Inst. 262, 191–208 (1956; Zbl 0123.12408)]. They introduced a probabilistic model of network reliability, where the nodes of the network were considered to be perfectly reliable, and the links or edges could fail independently with a certain probability. The problem is to determine the probability that the network remains connected under these conditions. If all the edges have the same probability of failing, this leads to the so-called reliability polynomial of the network. Sixty years later, a lot of research has accumulated on this topic, and many variants of the original problem have been investigated. We review the basic concepts and results, as well as some recent developments in this area, and we outline some important research directions.

MSC:

68M15 Reliability, testing and fault tolerance of networks and computer systems
05C31 Graph polynomials
05C85 Graph algorithms (graph-theoretic aspects)
05C90 Applications of graph theory
68M10 Network design and communication in computer systems
90B25 Reliability, availability, maintenance, inspection in operations research
94C15 Applications of graph theory to circuits and networks

Citations:

Zbl 0123.12408
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Agarwal, PK; etal., The resilience of WDM networks to probabilistic geographical failures, IEEE/ACM Trans. Netw., 21, 1525-1538, (2013) · doi:10.1109/TNET.2012.2232111
[2] Amin, AT; Siegrist, KT; Slater, PJ, On the nonexistence of uniformly optimal graphs for pair-connected reliability, Networks, 21, 359-368, (1991) · Zbl 0736.90034 · doi:10.1002/net.3230210307
[3] Amin, AT; Siegrist, KT; Slater, PJ, On uniformly optimally reliable graphs for pairconnected reliability with vertex failures, Networks, 23, 185-193, (1993) · Zbl 0780.90044 · doi:10.1002/net.3230230306
[4] Anderson, I.: Combinatorics of Finite Sets. Dover Books on Mathematics. Dover, New York (1987). ISBN: 9780486422572 · Zbl 0604.05001
[5] Ball, MO; Scott Provan, J, Bounds on the reliability polynomial for shellable independence systems, SIAM J. Algebr. Discrete Methods, 3, 166-181, (1982) · Zbl 0504.05053 · doi:10.1137/0603016
[6] Ball, MO; Scott Provan, J, Calculating bounds on reachability and connectedness in stochastic networks, Networks, 13, 253-278, (1983) · Zbl 0569.68053 · doi:10.1002/net.3230130210
[7] Barrera, J; Cancela, H; Moreno, E, Topological optimization of reliable networks under dependent failures, Oper. Res. Lett., 43, 132-136, (2015) · Zbl 1408.90048 · doi:10.1016/j.orl.2014.12.014
[8] Boesch, F.T.: On the synthesis of optimally reliable networks having unreliable nodes but reliable edges. In: INFOCOM ’88. Networks: Evolution or Revolution, Proceedings of the Seventh Annual Joint Conference of the IEEE Computer and Communcations Societies, pp. 829-834. IEEE (1988)
[9] Brecht, TB; Colbourn, CJ, Lower bounds on two-terminal network reliability, Discrete Appl. Math., 21, 185-198, (1988) · Zbl 0665.90036 · doi:10.1016/0166-218X(88)90065-0
[10] Brown, J; Mol, L, On the roots of the node reliability polynomial, Networks, 68, 238-246, (2016) · Zbl 1387.05116 · doi:10.1002/net.21697
[11] Brown, JI; Cox, D; Ehrenborg, R, The average reliability of a graph, Discrete Appl. Math., 177, 19-33, (2014) · Zbl 1297.05233 · doi:10.1016/j.dam.2014.05.048
[12] Brown, JI; Li, X, Uniformly optimal digraphs for strongly connected reliability, Networks, 49, 145-151, (2007) · Zbl 1112.05044 · doi:10.1002/net.20148
[13] Bulka, D., Dugan, J.B.: A lower bound on the reliability of an n-dimensional hypercube. In: Proceedings Ninth Symposium on Reliable Distributed Systems, pp. 44-53 (1990)
[14] Bulka, D; Dugan, JB, Network s-t reliability bounds using a 2-dimensional reliability polynomial, IEEE Trans. Reliab., 43, 39-45, (1994) · doi:10.1109/24.285106
[15] Burgos, JM, Factorization of network reliability with perfect nodes II: connectivity matrix, Discrete Appl. Math., 198, 91-100, (2016) · Zbl 1327.05310 · doi:10.1016/j.dam.2015.06.005
[16] Burgos, JM; Amoza, FR, Factorization of network reliability with perfect nodes I: introduction and statements, Discrete Appl. Math., 198, 82-90, (2016) · Zbl 1327.05311 · doi:10.1016/j.dam.2015.06.006
[17] Canale, E; etal., Diameter constrained reliability: complexity, distinguished topologies and asymptotic behavior, Networks, 66, 296-305, (2015) · Zbl 1386.05182 · doi:10.1002/net.21654
[18] Canale, E; etal., Full complexity analysis of the diameter-constrained reliability, Int. Trans. Oper. Res., 22, 811-821, (2015) · Zbl 1338.90425 · doi:10.1111/itor.12159
[19] Cancela, H; etal., Diameter constrained reliability of ladders and Spanish fans, Yugosl. J. Oper. Res., 26, 17-32, (2016) · Zbl 1464.05349 · doi:10.2298/YJOR140721004C
[20] Chen, Y; He, Z, Bounds on the reliability of distributed systems with unreliable nodes and links, IEEE Trans. Reliab., 53, 205-215, (2004) · doi:10.1109/TR.2004.829152
[21] Colbourn, CJ, Edge-packing of graphs and network reliability, Discrete Math., 72, 49-61, (1988) · Zbl 0657.90041 · doi:10.1016/0012-365X(88)90193-8
[22] Colbourn, CJ, Network resilience, SIAM J. Algebr. Discrete Methods, 8, 404-409, (1987) · Zbl 0654.68035 · doi:10.1137/0608033
[23] Colbourn, C.J.: The Combinatorics of Network Reliability. Oxford University Press, New York (1987). ISBN 0-19-504920-9
[24] Colbourn, CJ; Harms, DD; Myrvold, WJ, Reliability polynomials can cross twice, J. Frankl. Inst., 330, 629-633, (1993) · Zbl 0825.93076 · doi:10.1016/0016-0032(93)90102-Z
[25] Abreu, NMM, Old and new results on algebraic connectivity of graphs, Linear Algebra Appl., 423, 53-73, (2007) · Zbl 1115.05056 · doi:10.1016/j.laa.2006.08.017
[26] Doty, LL, Extremal connectivity and vulnerability in graphs, Networks, 19, 73-78, (1989) · Zbl 0675.05038 · doi:10.1002/net.3230190106
[27] Dugas, MR; Samaniego, FJ, On optimal system designs in reliability-economics frameworks, Nav. Res. Logist., 54, 568-582, (2007) · Zbl 1143.90324 · doi:10.1002/nav.20245
[28] El-Amawy, A; Latifi, S, Properties and performance of folded hypercubes, IEEE Trans. Parallel Distrib. Syst., 2, 31-42, (1991) · doi:10.1109/71.80187
[29] Ellens, W; etal., Effective graph resistance, Linear Algebra Appl., 435, 2491-2506, (2011) · Zbl 1222.05155 · doi:10.1016/j.laa.2011.02.024
[30] Elspas, B.: Topological constraints on interconnection-limited logic. In: 1964 Proceedings of the Fifth Annual Symposium on Switching Circuit Theory and Logical Design, pp. 133-137 (1964)
[31] Evans, T; Smith, D, Optimally reliable graphs for both edge and vertex failures, Networks, 16, 199-204, (1986) · Zbl 0642.90042 · doi:10.1002/net.3230160208
[32] Frank, O; Gaul, W, On reliability in stochastic graphs, Networks, 12, 119-126, (1982) · Zbl 0488.62081 · doi:10.1002/net.3230120204
[33] Gertsbakh, I., Shpungin, Y., Vaisman, R.: Ternary Networks: Reliability and Monte Carlo. Springer, Berlin (2014). ISBN 3319064398 · Zbl 1398.90005 · doi:10.1007/978-3-319-06440-6
[34] Gertsbakh, I.B., Shpungin, Y.: Models of Network Reliability: Analysis, Combinatorics, and Monte Carlo, 1st edn. CRC Press, Boca Raton (2009). ISBN: 1439817413 · Zbl 1200.62128
[35] Gertsbakh, I.B., Shpungin, Y.: Network Reliability and Resilience. Springer, Berlin (2011). ISBN 978-3-642-22373-0 · Zbl 1051.60089 · doi:10.1007/978-3-642-22374-7
[36] Goldschmidt, O; Jaillet, P; Lasota, R, On reliability of graphs with node failures, Networks, 24, 251-259, (1994) · Zbl 0824.90067 · doi:10.1002/net.3230240407
[37] Gross, D.J., Saccoman, J.T., Suffel, C.L.: Spanning Tree Results for Graphs and Multigraphs: A Matrix-Theoretic Approach. World Scientific, Singapore (2014). ISBN: 9789814566056 · Zbl 1321.05003 · doi:10.1142/8963
[38] Gunawan, I.: Fundamentals of Reliability Engineering: Applications in Multistage Interconnection Networks. Wiley, New York (2014). ISBN: 978-1-118-54956-8 · doi:10.1002/9781118914410
[39] Guo, L; Guo, X, Fault tolerance of hypercubes and folded hypercubes, J. Supercomput., 68, 1235-1240, (2014) · doi:10.1007/s11227-013-1078-5
[40] Harms, D.D., et al.: Network Reliability. Experiments with a Symbolic Algebra Environment. CRC Press, Boca Raton (1995). ISBN: 0-8493-3980-4 · Zbl 0880.68004
[41] Hu, XD; Hwang, FK, Reliabilities of chordal rings, Networks, 22, 487-501, (1992) · Zbl 0768.90023 · doi:10.1002/net.3230220506
[42] Hu, X.D., Hwang, F.K.: Survival reliabilities of double loop networks. In: Global Telecommunications Conference, 1990, and Exhibition. ‘Communications: Connecting the Future’ (GLOBECOM’90), vol.2, pp. 674-677. IEEE (1990)
[43] Hu, XD; Hwang, FK; Li, W-CIW, Most reliable double loop networks in survival reliability, Networks, 23, 451-458, (1993) · Zbl 0803.90068 · doi:10.1002/net.3230230502
[44] Hwang, FK; Wright, PE, Survival reliability of some double-loop networks and chordal rings, IEEE Trans. Comput., 44, 1468-1471, (1995) · Zbl 1048.68507 · doi:10.1109/12.477253
[45] Hwang, FK, A survey on multi-loop networks, Theoret. Comput. Sci., 299, 107-121, (2003) · Zbl 1038.68004 · doi:10.1016/S0304-3975(01)00341-3
[46] Hwang, FK; Li, W-CW, Reliabilities of double-loop networks, Probab. Eng. Inf. Sci., 5, 255272, (1991) · Zbl 1134.90361 · doi:10.1017/S0269964800002072
[47] Hwang, FK; Wright, PE; Hu, XD, Exact reliabilities of most reliable double-loop networks, Networks, 30, 81-90, (1997) · Zbl 0883.90062 · doi:10.1002/(SICI)1097-0037(199709)30:2<81::AID-NET2>3.0.CO;2-G
[48] Jukna, S.: Extremal Combinatorics: With Applications in Computer Science. Texts in Theoretical Computer Science. An EATCS Series. Springer, Berlin (2001). ISBN 9783540663133 · Zbl 0978.05001 · doi:10.1007/978-3-662-04650-0
[49] Karp, RM; Luby, M, Monte-Carlo algorithms for the planar multiterminal network reliability problem, J. Complex., 1, 45-64, (1985) · Zbl 0596.90033 · doi:10.1016/0885-064X(85)90021-4
[50] Katerinis, P, Toughness of graphs and the existence of factors, Discrete Math., 80, 81-92, (1990) · Zbl 0739.05047 · doi:10.1016/0012-365X(90)90297-U
[51] Kelmans, A, Connectivity of probabilistic networks, Autom. Remote Control, 29, 444-460, (1967)
[52] Kelmans, A, Some problems of network reliability analysis, Autom. Remote Control, 26, 564-573, (1965) · Zbl 0228.94025
[53] Kirchhoff, G, Über die auflösung der gleichungen, auf welche man bei der untersuchung der linearen vertheilung galvanischer ströme geführt wird, Ann. Phys., 148, 497-508, (1847) · doi:10.1002/andp.18471481202
[54] Kuo, SY; Yeh, FM; Lin, HY, Efficient and exact reliability evaluation for networks with imperfect vertices, IEEE Trans. Reliab., 56, 288-300, (2007) · doi:10.1109/TR.2007.896770
[55] Liu, S; Cheng, K-H; Liu, X, Network reliability with node failures, Networks, 35, 109-117, (2000) · Zbl 0957.90017 · doi:10.1002/(SICI)1097-0037(200003)35:2<109::AID-NET2>3.0.CO;2-N
[56] Long, X., Tipper, D., Gomes, T.: Measuring the survivability of networks to geographic correlated failures. In: Optical Switching and Networking 14, Part 2 (2014). Special Issue on RNDM, pp. 117-133 (2013)
[57] McAssey, MP; Samaniego, FJ, On uniformly optimal networks: a reversal of fortune?, Commun. Stat. Theory Methods, 43, 2452-2467, (2014) · Zbl 1297.68025 · doi:10.1080/03610926.2013.792353
[58] Mohamed, MHS; etal., An efficient evaluation for the reliability upper bound of distributed systems with unreliable nodes and edges, Int. J. Eng. Technol., 2, 107-110, (2010)
[59] Monakhova, E.A.: A survey on undirected circulant graphs. In: Discrete Mathematics, Algorithms and Applications 04.01 (2012), p. 1250002 · Zbl 1247.05115
[60] Moore, EF; Shannon, CE, Reliable circuits using less reliable relays, J. Frankl. Inst., 262, 191-208, (1956) · Zbl 0123.12408 · doi:10.1016/0016-0032(56)90559-2
[61] Myrvold, W.: Reliable network synthesis: some recent developments. In: Proceedings of International Conference on Graph Theory, Combinatorics, Algorithms, and Applications. vol. 2, pp. 651-660 (1999)
[62] Page, LB; Perry, JE, A practical implementation of the factoring theorem for network reliability, IEEE Trans. Reliab., 37, 259-267, (1988) · doi:10.1109/24.3752
[63] Petingi, L; Rodriguez, J, Reliability of networks with delay constraints, Congr. Numer., 152, 117-123, (2001) · Zbl 0999.68021
[64] Peyrat, C, Diameter vulnerability of graphs, Discrete Appl. Math., 9, 245-250, (1984) · Zbl 0549.05036 · doi:10.1016/0166-218X(84)90024-6
[65] Politof, T; Satyanarayana, A, A linear-time algorithm to compute the reliability of planar cube-free networks, IEEE Trans. Reliab., 39, 557-563, (1990) · Zbl 0711.68010 · doi:10.1109/24.61311
[66] Politof, T; Satyanarayana, A, Efficient algorithms for reliability analysis of planar networks—a survey, IEEE Trans. Reliab., 35, 252-259, (1986) · Zbl 0604.90059 · doi:10.1109/TR.1986.4335427
[67] Provan, SJ, The complexity of reliability computations in planar and acyclic graphs, SIAM J. Comput., 15, 694-702, (1986) · Zbl 0606.68066 · doi:10.1137/0215050
[68] Rodriguez-Velazquez, JA; Kamisalic, A; Domingo-Ferrer, J, On reliability indices of communication networks, Comput. Math. Appl., 58, 1433-1440, (2009) · Zbl 1189.90031 · doi:10.1016/j.camwa.2009.07.019
[69] Samaniego, F.J.: System Signatures and their Applications in Engineering Reliability. International Series on Operations Research and Management Science. Springer, Berlin (2007). ISBN: 978-0-387-71797-5 · Zbl 1154.62075 · doi:10.1007/978-0-387-71797-5
[70] Satyanarayana, A; Chang, MK, Network reliability and the factoring theorem, Networks, 13, 107-120, (1983) · Zbl 0504.90031 · doi:10.1002/net.3230130107
[71] Satyanarayana, A., Tindell, R.: Efficient Algorithms for the Evaluation of Planar Network Reliability. Tech. rep. DTIC Document (1993). http://oai.dtic.mil/oai/oai?verb=getRecord&metadataPrefix=html&identifier=ADA263602
[72] Satyanarayana, A; KevinWood, R, A linear-time algorithm for computing K-terminal reliability in series-parallel networks, SIAM J. Comput., 14, 818-832, (1985) · Zbl 0575.68072 · doi:10.1137/0214057
[73] Shier, D.R.: Network Reliability and Algebraic Structures. Oxford University Press, Oxford (1991) · Zbl 0729.90033
[74] Shpungin, Y.: Networks with unreliable nodes and edges: Monte Carlo lifetime estimation. Int. J. Electr. Comput. Energ. Electron. Commun. Eng. 1(3):458-463. (2007). ISSN: 2010-376X
[75] Smith, DH, Optimally reliable graphs for both vertex and edge failures, Comb. Probab. Comput., 2, 93100, (1993) · Zbl 0799.90058 · doi:10.1017/S0963548300000493
[76] Smith, DH, Optimally reliable networks, Ann. Oper. Res., 33, 107-112, (1991) · Zbl 0743.90061 · doi:10.1007/BF02073595
[77] Smith, DH; Doty, LL, On the construction of optimally reliable graphs, Networks, 20, 723-729, (1990) · Zbl 0716.90041 · doi:10.1002/net.3230200603
[78] Soh, S; Rai, S; Trahan, JL, Improved lower bounds on the reliability of hypercube architectures, IEEE Trans. Parallel Distrib. Syst., 5, 364-378, (1994) · doi:10.1109/71.273045
[79] Theologou, OR; Carlier, JG, Factoring and reductions for networks with imperfect vertices, IEEE Trans. Reliab., 40, 210-217, (1991) · Zbl 0729.90647 · doi:10.1109/24.87131
[80] Tripathy, CR; Mahapatra, RN; Misra, RB, Reliability analysis of hypercube multicomputers, Microelectron. Reliab., 37, 885-891, (1997) · doi:10.1016/S0026-2714(96)00128-X
[81] Slyke, RM; Frank, H, Network reliability analysis: part I, Networks, 1, 279-290, (1971) · Zbl 0239.94041 · doi:10.1002/net.3230010307
[82] Vertigan, D, The computational complexity of Tutte invariants for planar graphs, SIAM J. Comput., 35, 690-712, (2005) · Zbl 1089.05017 · doi:10.1137/S0097539704446797
[83] Wood, RK, Factoring algorithms for computing k-terminal network reliability, IEEE Trans. Reliab., 35, 269-278, (1986) · Zbl 0602.90064 · doi:10.1109/TR.1986.4335431
[84] Yu, S; Shao, F-M; Meng, H, Uniformly optimal graphs in some classes of graphs with node failures, Discrete Math., 310, 159-166, (2010) · Zbl 1189.05167 · doi:10.1016/j.disc.2009.08.006
[85] Zhou, Q., et al.: Network Robustness under Large-Scale Attacks. Springer, Berlin (2013). ISBN: 978- 1-4614-4859-4 · Zbl 1267.68019 · doi:10.1007/978-1-4614-4860-0
[86] Zhu, Q; etal., On reliability of the folded hypercubes, Inf. Sci., 177, 1782-1788, (2007) · Zbl 1115.68034 · doi:10.1016/j.ins.2006.11.003
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.