×

The restricted \(h\)-connectivity of the data center network DCell. (English) Zbl 1332.05133

Summary: Traditional data center networks (DCNs) are faced with many challenges with the development of cloud computing. This fact makes design of new DCNs represented by DCell networks become a hot research topic. For any integers \(k \geq 0\) and \(n \geq 2\), the \(k\)-dimensional DCell with \(n\)-port switches and \(t_{k, n}\) nodes, \(D_{k, n}\), has been proposed for an important DCNs as a server-centric DCN structure. In this paper, we prove that under the condition that each fault-free node of the \(D_{k, n}\) has at least \(h\) fault-free neighbor(s) its restricted \(h\)-connectivity is \((h + 1)(k - 1) + n\) (resp. \((n + k - h - 1) t_{h - n + 1, n}\)) with \(0 \leq h \leq n - 1\) (resp. \(n \leq h \leq n + k - 2\)), which is almost as \((h + 1)\) (resp. \(t_{h - n + 1, n}\)) times as traditional connectivity of \(D_{k, n}\). When the DCell network is used to model the topological structure of a large-scale DCN, this result can provide a more accurate measure for the fault tolerance of the network.

MSC:

05C82 Small world graphs, complex networks (graph-theoretic aspects)
05C40 Connectivity
05C90 Applications of graph theory
68M10 Network design and communication in computer systems
68M15 Reliability, testing and fault tolerance of networks and computer systems
68R10 Graph theory (including graph drawing) in computer science
Full Text: DOI

References:

[2] Balbuena, C.; Marcote, X., The \(k\)-restricted edge-connectivity of a product of graphs, Discrete Appl. Math., 161, 1, 52-59 (2013) · Zbl 1262.05091
[3] Chang, N.-W.; Tsai, C.-Y.; Hsieh, S.-Y., On 3-extra connectivity and 3-extra edge connectivity of folded hypercubes, IEEE Trans. Comput., 63, 6, 1594-1600 (2014)
[4] Cheng, E.; Lipták, L.; Yang, W.; Zhang, Z.; Guo, X., A kind of conditional vertex connectivity of cayley graphs generated by 2-trees, Inform. Sci., 181, 19, 4300-4308 (2011) · Zbl 1244.05111
[5] Day, K., The conditional node connectivity of the \(k\)-ary \(n\)-cube, J. Interconnect. Netw., 5, 1, 13-26 (2004)
[6] Esfahanian, A.-H., Generalized measures of fault tolerance with application to \(n\)-cube networks, IEEE Trans. Comput., 38, 11, 1586-1591 (1989)
[7] Fan, J.; Jia, X.; Cheng, B.; Yu, J., An efficient fault-tolerant routing algorithm in bijective connection networks with restricted faulty edges, Theoret. Comput. Sci., 412, 29, 3440-3450 (2011) · Zbl 1216.68055
[8] Fan, J.; Jia, X.; Liu, X.; Zhang, S.; Yu, J., Efficient unicast in bijective connection networks with the restricted faulty node set, Inform. Sci., 181, 11, 2303-2315 (2011) · Zbl 1216.68056
[9] Fan, J.; Li, K.; Zhang, S.; Zhou, W.; Cheng, B., One-to-one communication in twisted cubes under restricted connectivity, Front. Comput. Sci. China, 4, 4, 489-499 (2010) · Zbl 1267.68033
[12] Harary, F., Conditional connectivity, Networks, 13, 3, 347-357 (1983) · Zbl 0514.05038
[13] Hong, Y.; Meng, J.; Zhang, Z., Edge fault tolerance of graphs with respect to super edge connectivity, Discrete Appl. Math., 160, 4, 579-587 (2012) · Zbl 1239.05108
[14] Hu, S.-C.; Yang, C.-B., Fault tolerance on star graphs, Internat. J. Found Comput. Sci., 8, 2, 127-142 (1997) · Zbl 0880.68098
[16] Latifi, S.; Hegde, M.; Naraghi-Pour, M., Conditional connectivity measures for large multiprocessor systems, IEEE Trans. Comput., 43, 2, 218-222 (1994)
[19] Li, X.; Xu, J., Generalized measures of fault tolerance in exchanged hypercubes, Inform. Process. Lett., 113, 14, 533-537 (2013) · Zbl 1284.68082
[20] Li, X.; Xu, J., Generalized measures for fault tolerance of star networks, Networks, 63, 3, 225-230 (2014) · Zbl 1387.05131
[21] Li, X.; Xu, J., Fault-tolerance of \((n, k)\)-star networks, Appl. Math. Comput., 248, 525-530 (2014) · Zbl 1338.05255
[22] Lin, L.; Zhou, S., Conditional connectivity for \((n, k)\)-arrangement graph, J. Math. Study, 45, 4, 350-364 (2012) · Zbl 1289.05248
[23] Manzano, M.; Bilal, K.; Calle, E.; Khan, S. U., On the connectivity of data center networks, IEEE Commun. Lett., 17, 11, 2172-2175 (2013)
[24] Oh, A. D.; Choi, H.-A., Generalized measures of fault tolerance in \(n\)-cube networks, IEEE Trans. Parallel Distrib. Syst., 4, 6, 702-703 (1993)
[25] Tsai, C.-H.; Lai, Y.-C., Conditional edge-fault-tolerant edge-bipancyclicity of hypercubes, Inform. Sci., 177, 24, 5590-5597 (2007) · Zbl 1132.68019
[26] Wan, M.; Zhang, Z., A kind of conditional vertex connectivity of star graphs, Appl. Math. Lett., 22, 2, 264-267 (2009) · Zbl 1163.05323
[27] Wang, X.; Erickson, A.; Fan, J.; Jia, X., Hamiltonian properties of dcell networks, Comput. J. (2015)
[29] Wu, J.; Guo, G., Fault tolerance measures for \(m\)-ary \(n\)-dimensional hypercubes based on forbidden faulty sets, IEEE Trans. Comput., 47, 8, 888-893 (1998) · Zbl 1392.68110
[30] Yang, W.; Li, H.; Meng, J., Conditional connectivity of cayley graphs generated by transposition trees, Inform. Process. Lett., 110, 23, 1027-1030 (2010) · Zbl 1379.05069
[31] Zhang, Z.; Xiong, W.; Yang, W., A kind of conditional fault tolerance of alternating group graphs, Inform. Process. Lett., 110, 22, 998-1002 (2010) · Zbl 1379.68263
[32] Zhou, S.; Xu, J., Conditional fault tolerance of arrangement graphs, Inform. Process. Lett., 111, 21, 1037-1043 (2011) · Zbl 1260.68309
[33] Zhu, Q.; Xu, J.; Lv, M., Edge fault tolerance analysis of a class of interconnection networks, Appl. Math. Comput., 172, 1, 111-121 (2006) · Zbl 1088.68022
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.