×

The reliability analysis of \(k\)-ary \(n\)-cube networks. (English) Zbl 1460.68021

Summary: With the development of scalability and application of multiprocessor system, the components of the system possibly become faulty. It is desirable to know the reliability of the system. However, the exact reliability of a complicated network system is usually difficult to determine. A typical approach is to decompose the system into smaller ones based on a graph-theory model in which nodes are assumed to fail independently with known probabilities to measure the subsystem-based reliability, which is defined as the probability that a fault-free subsystem of a specific size is still available when the system has faults. In this paper, we use the probability fault model to establish upper and lower bounds on the subsystem-based reliability of \(k\)-ary \(n\)-cube networks, by taking into account the intersection of no more than five or four subgraphs. In addition, some numerical simulations of the subsystem-based reliability of \(k\)-ary \(n\)-cube networks are conducted.

MSC:

68M15 Reliability, testing and fault tolerance of networks and computer systems
05C40 Connectivity
68R10 Graph theory (including graph drawing) in computer science
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Anderson, E.; Brooks, J.; Grassl, C.; Scott, S., Performance of the CRAY T3E multiprocessor, (Proceedings of the 1997 ACM/IEEE Conference on Supercomputing, Association for Computing Machinery. Proceedings of the 1997 ACM/IEEE Conference on Supercomputing, Association for Computing Machinery, New York, USA, San Jose, CA, United states (1997)), 1-17
[2] Ashir, Y. A.; Stewart, I. A., On embedding cycles in k-ary n-cubes, Parallel Process. Lett., 7, 49-55 (1997)
[3] Adiga, N. R., Blue Gene/L torus interconnection network, IBM J. Res. Dev., 49, 2-3, 265-276 (2005)
[4] Bose, B.; Broeg, B.; Kwon, Y.; Ashir, Y. A., Lee distance and topological properties of k-ary n-cubes, IEEE Trans. Comput., 44, 8, 1021-1030 (1995) · Zbl 1054.68510
[5] Bhuyan, L. N.; Das, C. R., Dependability evaluation of multicomputer networks, (Proc. Int’l Con Parallel Processing (1986)), 576-583
[6] Chang, Y.; Bhuyan, L. N., A combinatorial analysis of subcube reliability in hypercubes, IEEE Trans. Comput., 44, 952-956 (1995) · Zbl 1057.68526
[7] Chen, J.-E.; Kanj, I.-A.; Wang, G.-J., Hypercube network fault tolerance: a probabilistic approach, J. Interconnect. Netw., 6, 1, 17-34 (2005)
[8] Chen, J.-E.; Wang, G.-C.; Lin, C.; Wang, T.; Wang, G.-J., Probabilistic analysis on mesh network fault tolerance, J. Parallel Distrib. Comput., 67, 100-110 (2007) · Zbl 1109.68020
[9] Dong, Q.; Yang, X.; Wang, D., Embedding paths and cycles in 3-ary n-cubes with faulty nodes and links, Inf. Sci., 180, 1, 198-208 (2010) · Zbl 1183.68089
[10] Das, C. R.; Kim, J., A unified task-based dependability model for hypercube computers, IEEE Trans. Parallel Distrib. Syst., 3, 3, 312-324 (1992)
[11] Fang, J.-F., The bipancycle-connectivity and the m-pancycle-connectivity of the k-ary n-cube, Comput. J., 53, 6, 667-678 (2010)
[12] Fan, W.; Fan, J.; Lin, C.-K.; Wang, Y.; Han, Y.; Wang, R., Optimally embedding 3-ary n-cubes into grids, J. Comput. Syst. Technol., 34, 2, 372-387 (2019)
[13] Fitzgerald, K.; Latifi, S.; Srimani, P. K., Reliability modeling and assessment of the star-graph networks, IEEE Trans. Reliab., 51, 49-57 (2002)
[14] Fortier, P. J.; Michel, H. E., Computer Systems Performance Evaluation and Prediction (2003), Digital Press, Elsevier Science: Digital Press, Elsevier Science New York
[15] Hsieh, S.-Y.; Kao, C.-Y., The conditional diagnosability of k-ary n-cubes under the comparison diagnosis model, IEEE Trans. Comput., 62, 4, 839-843 (2013) · Zbl 1365.68085
[16] Hsieh, S.-Y.; Lin, T.-J., Panconnectivity and edge-pancyclicity of k-ary n-cubes, Networks, 54, 1, 1-11 (2009) · Zbl 1205.05126
[17] Huang, Y.; Lin, L.; Wang, D., On the reliability of alternating group graph-based networks, Theor. Comput. Sci., 728, 9-28 (2018) · Zbl 1390.68104
[18] Kung, T.-L.; Hung, Y.-N., Estimating the subsystem reliability of bubblesort networks, Theor. Comput. Sci., 670, 45-55 (2017) · Zbl 1359.68028
[19] Kung, T.-L.; Teng, Y.-H.; Lin, C.-K.; Hsu, Y.-L., Combinatorial analysis of the subsystem reliability of the split-star network, Inf. Sci., 415-416, 28-40 (2017) · Zbl 1435.68051
[20] Kuo, S.-Y.; Huang, C.-Y.; Lyu, M.-R., Framework for modeling software reliability, using various testing-efforts and fault-detection rates, IEEE Trans. Reliab., 50, 3, 310-320 (2001)
[21] Latifi, S., Fault-tolerant hypercube multiprocessors, IEEE Trans. Reliab., 39, 361-368 (1990)
[22] Lv, Y.; Fan, J.; Hsu, D. F.; Lin, C.-K., Structure connectivity and substructure connectivity of k-ary n-cube networks, Inf. Sci., 433-434, 115-124 (2018) · Zbl 1436.68051
[23] Li, X.; Zhou, S.; Xu, X.; Lin, L.; Wang, D., The reliability analysis based on subsystems of \((n, k)\)-Star Graph, IEEE Trans. Reliab., 65, 1700-1709 (2016)
[24] Liang, M.; Xu, X.; Liang, J.; Shao, Z., Upper bounds on the connection probability for 2-D meshes and tori, J. Parallel Distrib. Comput., 72, 185-194 (2012) · Zbl 1242.68006
[25] Lin, L.; Xu, L.; Zhou, S.; Wang, D., The reliability of subgraph in the arrangement graph, IEEE Trans. Reliab., 62, 807-818 (2015)
[26] Shih, Y.-K.; Kao, S.-S., One-to-one disjoint path covers on k-ary n-cubes, Theor. Comput. Sci., 412, 35, 4513-4530 (2011) · Zbl 1223.68086
[27] Soh, S.; Rai, S.; Trahan, J. L., Improved lower bounds on the reliability of hypercube architectures, IEEE Trans. Parallel Distrib. Syst., 5, 4, 364-378 (1994)
[28] Stewart, I. A.; Xiang, Y., Embedding long paths in k-ary n-cubes with faulty nodes and links, IEEE Trans. Parallel Distrib. Syst., 19, 8, 1071-1085 (2008)
[29] Stewart, I. A.; Xiang, Y., Bipanconnectivity and bipancyclicity in k-ary n-cubes, IEEE Trans. Parallel Distrib. Syst., 20, 1, 25-33 (2009)
[30] Wang, S.; Feng, K.; Zhang, G., Strong matching preclusion for k-ary n-cubes, Discrete Appl. Math., 161, 18, 3054-3062 (2013) · Zbl 1287.05122
[31] Wu, X.; Latifi, S., Substar reliability analysis in star networks, Inf. Sci., 178, 2337-2348 (2008) · Zbl 1146.68348
[32] Wu, X.; Latifi, S.; Jiang, Y., A combinatorial analysis of distance reliability in star network, (Proc. the 21st IEEE International Parallel and Distributed Processing Symposium IPDPS (Mar. 2007)), 1-6
[33] Wang, G.; Wang, G.; Shan, Z., Fault tolerance analysis of mesh networks with uniform versus nonuniform node failure probability, Inf. Process. Lett., 112, 396-401 (2012) · Zbl 1243.68090
[34] Wang, S.; Zhang, G.; Feng, K., Fault tolerance in k-ary n-cube networks, Theor. Comput. Sci., 460, 34-41 (2012) · Zbl 1252.68044
[35] Wang, S.; Zhang, G.; Yang, Y., Hamiltonian path embeddings in conditional faulty k-ary n-cubes, Inf. Sci., 268, 463-488 (2014) · Zbl 1341.68139
[36] Xiang, Y.; Stewart, I. A., Bipanconnectivity in k-ary n-cubes with faulty edges under a conditional fault assumption, IEEE Trans. Parallel Distrib. Syst., 22, 9, 1506-1513 (2011)
[37] Yang, M.-C.; Tan, J. J.; Hsu, L.-H., Hamiltonian circuit and linear array embeddings in faulty k-ary n-cubes, J. Parallel Distrib. Comput., 67, 4, 362-368 (2007) · Zbl 1115.68032
[38] Yang, Y.; Wang, S.; Li, J., Conditional connectivity of recursive interconnection networks respect to embedding restriction, Inf. Sci., 279, 273-279 (2014) · Zbl 1354.68019
[39] Zhou, S.; Li, X.; Li, J.; Wang, D., Reliability assessment of multiprocessor system based on \((n, k)\)-star network, IEEE Trans. Reliab., 66, 4, 1025-1035 (2017)
[40] Zhang, S.; Wang, S., Many-to-many disjoint path covers in k-ary n-cubes, Theor. Comput. Sci., 491, 103-118 (2013) · Zbl 1277.68040
[41] Zhu, Q.; Xu, J. M.; Hou, X.; Xu, M., On reliability of the folded hypercubes, Inf. Sci., 177, 8, 1782-1788 (2007) · Zbl 1115.68034
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.