×

The extra connectivity, extra conditional diagnosability and \(t/k\)-diagnosability of the data center network DCell. (English) Zbl 1417.68024

Summary: Connectivity and diagnosability are two important metrics in evaluating the fault tolerability of a network. The \(g\)-extra connectivity and the \(g\)-extra conditional diagnosability are both defined under the restraint that every component of the network removing a faulty vertex set has at least \(g + 1\) fault-free vertices. The \(t / k\)-diagnosability is an outstanding diagnosis strategy, in which the identified faulty vertex set is allowed to contain at most \(k\) fault-free vertices. As a well-known model for a large-scale data center network (DCN) with a server-centric structure, the \(m\)-dimensional DCell with \(n\)-port switches and \(t_{m, n}\) servers, \(D_{m, n}\), has many desirable properties. In this paper, we first investigate the \(g\)-extra connectivity of \(D_{m, n}\) for \(0 \leq g \leq n - 1\). Based on this, we establish the \(g\)-extra conditional diagnosability of \(D_{m, n}\) under the PMC model for \(0 \leq g \leq n - 1\). Finally, we evaluate the \(t / k\)-diagnosability of \(D_{m, n}\) under the PMC model for \(1 \leq k \leq n - 1\).

MSC:

68M15 Reliability, testing and fault tolerance of networks and computer systems
68M10 Network design and communication in computer systems

Software:

Bigtable; Dryad
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Dahbura, A. T.; Masson, G. M., An \(O(n^{2.5})\) faulty identification algorithm for diagnosable systems, IEEE Trans. Comput., 33, 6, 486-492 (1984) · Zbl 0537.68043
[2] Sengupta, A.; Dahbura, A., On self-diagnosable multiprocessor system: diagnosis by the comparison approach, IEEE Trans. Comput., 41, 11, 1386-1396 (1992) · Zbl 1395.68062
[3] Somani, A. K.; Peleg, O., On diagnosability of large fault sets in regular topology-based computer systems, IEEE Trans. Comput., 45, 8, 892-903 (1996) · Zbl 1057.68535
[4] 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. Special Interest Group on Data Communication, SIGCOMM (2008)), 75-86
[5] Li, D.; Wu, J.; Liu, Z.; Zhang, F., Towards the tradeoffs in designing data center network architectures, IEEE Trans. Parallel Distrib. Syst., 28, 1, 260-273 (2017)
[6] Wang, D., Diagnosability of enhanced hypercubes, IEEE Trans. Comput., 43, 9, 1054-1061 (1994) · Zbl 1061.68507
[7] Xiang, D.; Zhang, Y.; Pan, Y., Practical deadlock-free fault-tolerant routing in meshes based on the planar network fault model, IEEE Trans. Comput., 58, 5, 620-633 (2009) · Zbl 1368.68099
[8] Xiang, D., Deadlock-free adaptive routing in meshes with fault-tolerance ability based on channel overlapping, IEEE Trans. Dependable Secure Comput., 8, 1, 74-88 (2011)
[9] Chang, F.; Dean, J.; Ghemawat, S.; Hsieh, W. C.; Wallach, D. A.; Burrows, M.; Chandra, T.; Fikes, A.; Gruber, R. E., Bigtable: a distributed storage system for structured data, ACM Trans. Comput. Syst., 26, 2-4, 1-26 (2008)
[10] Preparata, F. P.; Metze, G.; Chien, R. T., On the connection assignment problem of diagnosable systems, IEEE Trans. Electron. Comput., 16, 6, 848-854 (1967) · Zbl 0189.16904
[11] Harary, F., Conditional connectivity, Networks, 13, 3, 347-357 (1983) · Zbl 0514.05038
[12] Maeng, J.; Malek, M., A comparison connection assignment for self-diagnosis of multiprocessors systems, (Proceeding of 11th International Symposium on Fault-Tolerant Computing (1981)), 173-175
[13] Fan, J., Diagnosability of the Möbius cubes, IEEE Trans. Parallel Distrib. Syst., 9, 9, 923-928 (1998)
[14] Fàbrega, J.; Fiol, M. A., On the extra connectivity of graphs, Discrete Math., 155, 1-3, 49-57 (1996) · Zbl 0857.05064
[15] Fan, J.; Yang, J.; Zhou, G.; Zhao, L.; Zhang, W., Diagnosable evaluation of DCC linear congruential graphs under the PMC diagnostic model, Inform. Sci., 179, 11, 1785-1791 (2009) · Zbl 1176.68034
[16] Fan, J.; Lin, X., The \(t / k\)-diagnosability of the BC graphs, IEEE Trans. Comput., 54, 2, 176-184 (2005)
[17] Hsu, L.-H.; Lin, C.-K., Graph Theory and Interconnection Networks (2008), CRC Press
[18] Lin, L.; Xu, L.; Zhou, S.; Hsieh, S.-Y., The \(t / k\)-diagnosability for regular networks, IEEE Trans. Comput., 65, 10, 3157-3170 (2016) · Zbl 1360.68237
[19] Lin, L.; Xu, 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)
[20] Lin, L.; Zhou, S.; Xu, L.; Wang, D., The extra connectivity and conditional diagnosability of alternating group networks, IEEE Trans. Parallel Distrib. Syst., 26, 8, 2352-2362 (2015)
[21] Lin, L.; Xu, L.; Zhou, S.; Hsieh, S.-Y., The extra, restricted connectivity and conditional diagnosability of split-star networks, IEEE Trans. Parallel Distrib. Syst., 27, 2, 533-545 (2016)
[22] Isard, M.; Budiu, M.; Yu, Y.; Birrell, A.; Fetterly, D., Dryad: distributed data-parallel programs from sequential building blocks, (European Conference on Computer Systems. European Conference on Computer Systems, EuroSys (2007)), 59-72
[23] Manzano, M.; Bilal, K.; Calls, E.; Khan, S. U., On the connectivity of data center networks, IEEE Commun. Lett., 17, 11, 2172-2175 (2013)
[24] Kliegl, M.; Lee, J.; Li, J.; Zhang, X.; Guo, C.; Rincon, D., Generalized DCell structure for load-balanced data center networks, (International Conference on Computer Communications. International Conference on Computer Communications, INFOCOM (2010)), 1-5
[25] Zhu, Q.; Wang, X.-K.; Cheng, G., Reliability evaluation of BC networks, IEEE Trans. Comput., 62, 11, 2337-2340 (2013) · Zbl 1365.68100
[26] Wang, S.; Wang, Z.; Wang, M., The 2-extra connectivity and 2-extra diagnosability of bubble-sort star graph networks, Comput. J., 59, 12, 1839-1856 (2016)
[27] Wang, S.; Yang, Y., The 2-good-neighbor (2-extra) diagnosability of alternating group graph networks under the PMC model and \(MM^\ast\) model, Appl. Math. Comput., 305, 241-250 (2017) · Zbl 1409.68050
[28] Hsieh, S.-Y.; Chang, Y.-H., Extra connectivity of \(k\)-ary \(n\)-cube networks, Theoret. Comput. Sci., 443, 20, 63-69 (2012) · Zbl 1246.68172
[29] Zhou, S.; Lin, L.; Xu, L.; Wang, D., The \(t / k\)-diagnosability of star graph networks, IEEE Trans. Comput., 64, 2, 547-555 (2015) · Zbl 1360.68182
[30] Ghemawat, S.; Gobioff, H.; Leung, S., The Google file system, (Symposium on Operating Systems Principles. Symposium on Operating Systems Principles, SIGOPS (2003)), 29-43
[31] Zhang, S.; Yang, W., The \(g\)-extra conditional diagnosability and sequential \(t / k\)-diagnosability of hypercubes, Int. J. Comput. Math., 93, 3, 482-497 (2016) · Zbl 1358.68047
[32] Han, W.; Wang, S., The \(g\)-extra conditional diagnosability of folded hypercubes, Appl. Math. Sci., 9, 146, 346-357 (2015)
[33] Yang, W.; Lin, H.; Qin, C., On the \(t / k\)-diagnosability of BC networks, Appl. Math. Comput., 225, 366-371 (2013) · Zbl 1334.68031
[34] Wang, X.; Erickson, A.; Fan, J.; Jia, X., Hamiltonian properties of DCell networks, Comput. J., 58, 11, 2944-2955 (2016)
[35] 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
[36] Wang, X.; Fan, J.; Jia, X.; Lin, C.-K., An efficient algorithm to construct disjoint path covers of DCell networks, Theoret. Comput. Sci., 609, 197-210 (2016) · Zbl 1331.68159
[37] Wang, X.; Fan, J.; Lin, C.-K.; Jia, X., Vertex-disjoint path in DCell networks, J. Parallel Distrib. Comput., 96, 38-44 (2016)
[38] Li, X.; Fan, J.; Lin, C.-K.; Jia, X., Diagnosability evaluation of the data center network DCell, Comput. J., 61, 1, 129-143 (2018)
[39] Yang, X.; Tang, Y., A \((4 n - 9) / 3\) diagnosis algorithm on \(n\)-dimensional cube network, Inform. Sci., 177, 8, 1771-1781 (2007) · Zbl 1116.68018
[40] Li, Y.; Gu, H., Fault-tolerant routing algorithm based on the artificial potential field model in network-on-chip, Appl. Math. Comput., 217, 7, 3226-3235 (2010) · Zbl 1204.82038
[41] Li, Z.; Yang, Y., GBC3: a versatile cube-based server-centric network for data center, IEEE Trans. Parallel Distrib. Syst., 27, 10, 2895-2910 (2016)
[42] Chang, N.-W.; Hsieh, S.-Y., \(\{2, 3 \}\)-Extraconnectivities of hypercube-like networks, J. Comput. System Sci., 79, 5, 669-688 (2013) · Zbl 1268.68133
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.