Authors

Xi Wang, Alejandro Erickson, Jianxi Fan, Xiaohua Jia

Abstract

DCell has been proposed for data centers as a server centric interconnection network structure. DCell can support millions of servers with high network capacity by only using commodity switches. With one exception, we prove that a \( k \) level DCell built with \( n \) port switches is Hamiltonian-connected for \( k \geq 0 \) and \( n \geq 2 \). Our proof extends to all generalized DCell connection rules for \( n\ge 3 \). Then, we propose an \( O(t_k) \) algorithm for finding a Hamiltonian path in \( DCell_{k} \), where \( t_k \) is the number of servers in \( DCell_{k} \). What’s more, we prove that \( DCell_{k} \) is \( (n+k-4) \)-fault Hamiltonian-connected and \( (n+k-3) \)-fault Hamiltonian. In addition, we show that a partial DCell is Hamiltonian connected if it conforms to a few practical restrictions.

Citation

  • Journal: The Computer Journal
  • Year: 2015
  • Volume: 58
  • Issue: 11
  • Pages: 2944–2955
  • Publisher: Oxford University Press (OUP)
  • DOI: 10.1093/comjnl/bxv019

BibTeX

@article{Wang_2015,
  title={{Hamiltonian Properties of DCell Networks}},
  volume={58},
  ISSN={1460-2067},
  DOI={10.1093/comjnl/bxv019},
  number={11},
  journal={The Computer Journal},
  publisher={Oxford University Press (OUP)},
  author={Wang, Xi and Erickson, Alejandro and Fan, Jianxi and Jia, Xiaohua},
  year={2015},
  pages={2944--2955}
}

Download the bib file

References

  • Ghemawat, S., Gobioff, H. & Leung, S.-T. The Google file system. Proceedings of the nineteenth ACM symposium on Operating systems principles 29–43 (2003) doi:10.1145/945445.945450 – 10.1145/945445.945450
  • Dean, J. & Ghemawat, S. MapReduce. Commun. ACM 51, 107–113 (2008) – 10.1145/1327452.1327492
  • Isard, M., Budiu, M., Yu, Y., Birrell, A. & Fetterly, D. Dryad. Proceedings of the 2nd ACM SIGOPS/EuroSys European Conference on Computer Systems 2007 (2007) doi:10.1145/1272996.1273005 – 10.1145/1272996.1273005
  • Al-Fares, M., Loukissas, A. & Vahdat, A. A scalable, commodity data center network architecture. Proceedings of the ACM SIGCOMM 2008 conference on Data communication 63–74 (2008) doi:10.1145/1402958.1402967 – 10.1145/1402958.1402967
  • Guo, C. et al. Dcell. Proceedings of the ACM SIGCOMM 2008 conference on Data communication 75–86 (2008) doi:10.1145/1402958.1402968 – 10.1145/1402958.1402968
  • Greenberg, A. et al. VL2. Proceedings of the ACM SIGCOMM 2009 conference on Data communication (2009) doi:10.1145/1592568.1592576 – 10.1145/1592568.1592576
  • Farrington, N. et al. Helios. Proceedings of the ACM SIGCOMM 2010 conference (2010) doi:10.1145/1851182.1851223 – 10.1145/1851182.1851223
  • Hamedazimi, N. et al. FireFly. SIGCOMM Comput. Commun. Rev. 44, 319–330 (2014) – 10.1145/2740070.2626328
  • Liu, Y. J., Gao, P. X., Wong, B. & Keshav, S. Quartz. SIGCOMM Comput. Commun. Rev. 44, 283–294 (2014) – 10.1145/2740070.2626332
  • Li, D. et al. FiConn: Using Backup Port for Server Interconnection in Data Centers. IEEE INFOCOM 2009 (2009) doi:10.1109/infcom.2009.5062153 – 10.1109/infcom.2009.5062153
  • Guo, C. et al. BCube. Proceedings of the ACM SIGCOMM 2009 conference on Data communication (2009) doi:10.1145/1592568.1592577 – 10.1145/1592568.1592577
  • Abu-Libdeh, H., Costa, P., Rowstron, A., O’Shea, G. & Donnelly, A. Symbiotic routing in future data centers. Proceedings of the ACM SIGCOMM 2010 conference 51–62 (2010) doi:10.1145/1851182.1851191 – 10.1145/1851182.1851191
  • Liao, Y., Yin, J., Yin, D. & Gao, L. DPillar: Dual-port server interconnection network for large scale data centers. Computer Networks 56, 2132–2147 (2012) – 10.1016/j.comnet.2012.02.016
  • Lin, D., Liu, Y., Hamdi, M. & Muppala, J. Hyper-BCube: A scalable data center network. 2012 IEEE International Conference on Communications (ICC) 2918–2923 (2012) doi:10.1109/icc.2012.6363759 – 10.1109/icc.2012.6363759
  • Xiaola Lin, McKinley, P. K. & Ni, L. M. Deadlock-free multicast wormhole routing in 2-D mesh multicomputers. IEEE Trans. Parallel Distrib. Syst. 5, 793–804 (1994) – 10.1109/71.298203
  • Wang, N.-C., Yen, C.-P. & Chu, C.-P. Multicast communication in wormhole-routed symmetric networks with hamiltonian cycle model. Journal of Systems Architecture 51, 165–183 (2005) – 10.1016/j.sysarc.2004.11.001
  • Johnson, D. S. The NP-completeness column: An ongoing gulde. Journal of Algorithms 3, 381–395 (1982) – 10.1016/0196-6774(82)90032-3
  • Fan, J. Hamilton-connectivity and cycle-embedding of the Möbius cubes. Information Processing Letters 82, 113–117 (2002) – 10.1016/s0020-0190(01)00256-3
  • Yang, X., Dong, Q., Yang, E. & Cao, J. Hamiltonian properties of twisted hypercube-like networks with more faulty elements. Theoretical Computer Science 412, 2409–2417 (2011) – 10.1016/j.tcs.2011.01.034
  • Wang, D. Hamiltonian Embedding in Crossed Cubes with Failed Links. IEEE Trans. Parallel Distrib. Syst. 23, 2117–2124 (2012) – 10.1109/tpds.2012.30
  • Xu, D., Fan, J., Jia, X., Zhang, S. & Wang, X. Hamiltonian properties of honeycomb meshes. Information Sciences 240, 184–190 (2013) – 10.1016/j.ins.2013.03.044
  • Kliegl, M. et al. Generalized DCell Structure for Load-Balanced Data Center Networks. 2010 INFOCOM IEEE Conference on Computer Communications Workshops 1–5 (2010) doi:10.1109/infcomw.2010.5466647 – 10.1109/infcomw.2010.5466647
  • Bondy, J. A. & Chvatal, V. A method in graph theory. Discrete Mathematics 15, 111–135 (1976) – 10.1016/0012-365x(76)90078-9
  • Fan, J. & Jia, X. Edge-pancyclicity and path-embeddability of bijective connection graphs. Information Sciences 178, 340–351 (2008) – 10.1016/j.ins.2007.08.012
  • Čada, R., Flandrin, E. & Li, H. Hamiltonicity and pancyclicity of cartesian products of graphs. Discrete Mathematics 309, 6337–6343 (2009) – 10.1016/j.disc.2008.11.024