Fault diagnosability of data center networks. (English) Zbl 1423.68080
Summary: A kind of generalization of diagnosability for a network \(G\) is \(g\)-good-neighbor diagnosability which is denoted by \(t_g(G)\). Let \(\kappa^g(G)\) be the \(R^g\)-connectivity. L. Lin et al. [Theor. Comput. Sci. 618, 21–29 (2016; Zbl 1335.68186)] and X. Xu et al. [Theor. Comput. Sci. 659, 53–63 (2017; Zbl 1355.68027)] gave the same problem independently that: the relationship between the \(R^g\)-connectivity \(\kappa^g(G)\) and \(t_g(G)\) of a general graph \(G\) needs to be studied in the future. In this paper, this open problem is solved for general regular graphs. We firstly establish the relationship of \(\kappa^g(G)\) and \(t_g(G)\), and obtain that \(t_g(G)=\kappa^g(G)+g\) under some conditions. Secondly, we obtain the \(g\)-good-neighbor diagnosability of data center network \(D_{k,n}\) which are \(t_g(D_{k,n})=(g+1)(k-1)+n+g\) for \(1\le g\le n-1\) under the PMC model and the MM* model, respectively. Furthermore, we show that \(D_{k,n}\) is tightly super \((n+k-1)\)-connected for \(n\ge2\) and \(k\ge2\) and we also prove that the largest connected component of the survival graph contains almost all of the remaining vertices in \(D_{k,n}\) when \(n+2k-2\) vertices removed.
MSC:
| 68M15 | Reliability, testing and fault tolerance of networks and computer systems |
| 68R10 | Graph theory (including graph drawing) in computer science |
Keywords:
data center network; \(g\)-good-neighbor diagnosability; PMC model; MM* model; fault-toleranceReferences:
| [1] | Chang, N.-W.; Hsieh, S.-Y., Conditional diagnosability of augmented cubes under the PMC model, IEEE Trans. Depend. Secure Comput., 9, 1, 46-60 (2012) |
| [2] | Chang, N.-W.; Hsieh, S.-Y., Structural properties and conditional diagnosability of star graphs by using the PMC model, IEEE Trans. Parallel Distrib. Syst., 25, 11, 3002-3011 (2014) |
| [3] | Chang, N.-W.; Lin, T.-Y.; Hsieh, S.-Y., Conditional diagnosability of \(k\)-ary \(n\)-cubes under the PMC model, ACM Transact. Des. Automat. Electron. Syst., 17, 4 (2012), vol. 46, pp. 1-14 |
| [4] | Dahbura, A. T.; Masson, G. M., An \(O(n^{2.5})\) fault identification algorithm for diagnosable systems, IEEE Trans. Comput., 33, 6, 486-492 (1984) · Zbl 0537.68043 |
| [5] | Fábrega, J.; Fiol, M. A., On the extra connectivity graphs, Discrete Math., 155, 49-57 (1996) · Zbl 0857.05064 |
| [6] | Fan, J., Diagnosability of crossed cubes under the comparison diagnosis model, IEEE Trans. Parallel Distrib. Syst., 13, 10, 687-692 (2002) |
| [7] | Guo, C.; Wu, H.; Tan, K.; Shi, L.; Zhang, Y.; Lu, S., DCell: a scalable and fault-tolerant network structure for data centers, (Special Interest Group on Data Communication (SIGCOMM) (2008)), 75-86 |
| [8] | Guo, J.; Lu, M., Conditional diagnosability of bubble-sort star graphs, Discrete Appl. Math., 201, 141-149 (2016) · Zbl 1329.05271 |
| [9] | Hao, R.-X.; Feng, Y.-Q.; Zhou, J.-X., Conditional diagnosability of alternating group graphs, IEEE Trans. Comput., 62, 4, 827-831 (2013) · Zbl 1365.05125 |
| [10] | Hao, R.-X.; Gu, M.-M.; Feng, Y.-Q., The pessimistic diagnosabilities of some general regular graphs, Theoret. Comput. Sci., 609, 413-420 (2016) · Zbl 1331.68033 |
| [11] | Hsieh, S.-Y.; Tsai, C.-Y.; Chen, C.-A., Strong diagnosability and conditional diagnosability of multiprocessor systems and folded hypercubes, IEEE Trans. Comput., 62, 7, 1472-1477 (2013) · Zbl 1365.94699 |
| [12] | 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 |
| [13] | Lai, P. L.; Tan, J. M.; Chang, C. P.; Hsu, L. H., Conditional diagnosability measures for large multiprocessor systems, IEEE Trans. Comput., 54, 2, 165-175 (2005) |
| [14] | Li, X.-J.; Xu, J.-M., Fault-tolerance of \((n, k)\)-star networks, Appl. Math. Comput., 248, 525-530 (2014) · Zbl 1338.05255 |
| [15] | Lin, L.; Xu, L.; Wang, D.; Zhou, S., The \(g\)-good-neighbor conditional diagnosability of arrangement graphs, IEEE Trans. Depend. Secure Comput., 15, 3, 542-548 (2018) |
| [16] | Lin, L.; Zhou, S.; Xu, L.; Wang, D., Conditional diagnosability of arrangement graphs under the PMC model, Theoret. Comput. Sci., 548, 79-97 (2014) · Zbl 1408.68034 |
| [17] | Lin, L.; Zhou, S.; Hsieh, S.-Y., The extra connectivity, extra conditional diagnosability and \(t / m\)-diagnosability of arrangement graphs, IEEE Trans. Reliab., 65, 3, 1248-1262 (2016) |
| [18] | Maeng, J.; Malek, M., A comparison connection assignment for self-diagnosis of multiprocessors systems, (Proceedings of the 11th International Symposium on Fault-Tolerant Computing (1981), ACM Press: ACM Press New York), 173-175 |
| [19] | Peng, S.-L.; Lin, C.-K.; Tan, J. J.M.; Hsu, L.-H., The \(g\)-good-neighbor conditional diagnosability of hypercube under PMC model, Appl. Math. Comput., 218, 10406-10412 (2012) · Zbl 1247.68032 |
| [20] | Preparata, F. P.; Metze, G.; Chien, R. T., On the connection assignment problem of diagnosis systems, IEEE Trans. Electron. Comput., 16, 12, 848-854 (1967) · Zbl 0189.16904 |
| [21] | Sengupta, A.; Dahbura, A., On self-diagnosable multiprocessor systems: diagnosis by the comparison approach, IEEE Trans. Comput., 41, 11, 1386-1396 (1992) · Zbl 1395.68062 |
| [22] | Wang, D., Diagnosability of hypercubes and enhanced hypercubes under the comparison diagnosis model, IEEE Trans. Comput., 48, 1369-1374 (1999) · Zbl 1392.68061 |
| [23] | Wang, M.; Guo, Y.; Wang, S., The 1-good-neighbor diagnosability of Cayley graphs generated by transposition trees under the PMC model and MM* model, Int. J. Comput. Math., 94, 3, 620-631 (2017) · Zbl 1362.05062 |
| [24] | Wang, M.; Liu, Y.; Wang, S., The 2-good-neighbor diagnosability of Cayley graphs generated by transposition trees under the PMC model and MM* model, Theoret. Comput. Sci., 628, 92-100 (2016) · Zbl 1338.68036 |
| [25] | Wang, X.; Fan, J.; Zhou, J.; Lin, C.-K., The restricted \(h\)-connectivity of the data center network DCell, Discrete Appl. Math., 203, 144-157 (2016) · Zbl 1332.05133 |
| [26] | Wang, S.; Han, W., The \(g\)-good-neighbor conditional diagnosability of \(n\)-dimensional hypercubes under the MM* Model, Inform. Process. Lett., 116, 574-577 (2016) · Zbl 1357.68016 |
| [27] | Wang, S.; Wang, Z.; Wang, M., The 2-good-neighbor connectivity and 2-good-neighbor diagnosability of bubble-sort star graph networks, Discrete Appl. Math., 217, 691-706 (2017) · Zbl 1358.05267 |
| [28] | Xu, J.-M., Theory and Application of Graphs (2003), Kluwer Academic Publishers: Kluwer Academic Publishers Dordrecht/Boston/London · Zbl 1035.05003 |
| [29] | Xu, X.; Li, X.; Zhou, S.; Hao, R.-X.; Gu, M.-M., The \(g\)-good-neighbor diagnosability of \((n, k)\)-star graphs, Theoret. Comput. Sci., 659, 53-63 (2017) · Zbl 1355.68027 |
| [30] | Yuan, J.; Liu, A.; Ma, X.; Liu, X.; Qin, X.; Zhang, J., The \(g\)-good-neighbor conditional diagnosability of \(k\)-ary \(n\)-cubes under the PMC model and MM* model, IEEE Trans. Parallel Distrib. Syst., 26, 1165-1177 (2015) |
| [31] | Yuan, J.; Liu, A.; Qin, X.; Zhang, J.; Li, J., \(g\)-good-neighbor conditional diagnosability measures for 3-ary \(n\)-cube networks, Theoret. Comput. Sci., 626, 144-162 (2016) · Zbl 1336.68018 |
| [32] | Zhou, S., The conditional fault diagnosability of \((n, k)\)-star graphs, Appl. Math. Comput., 218, 9742-9749 (2012) · Zbl 1245.05122 |
| [33] | Zhou, S.; Xu, J.-M., Fault diagnosability of arrangement graphs, Inform. Sci., 246, 177-190 (2013) · Zbl 1337.68215 |
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.
