Hamiltonian Properties of DCell Networks

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review

25 Scopus Citations
View graph of relations

Author(s)

Related Research Unit(s)

Detail(s)

Original languageEnglish
Pages (from-to)2944-2955
Journal / PublicationComputer Journal
Volume58
Issue number11
Publication statusPublished - 11 Aug 2014

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 ≥ 0 and n ≥ 2. Our proof extends to all Generalized DCell connection rules for n ≥ 3. Then, we propose an O(tk) algorithm for finding a Hamiltonian path in DCellk, where tk is the number of servers in DCellk. Furthermore, we prove that DCellk 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.

Research Area(s)

  • algorithm, data center networks, DCell, fault tolerance, Hamiltonian, Hamiltonian connectivity, partial DCell

Citation Format(s)

Hamiltonian Properties of DCell Networks. / Wang, Xi; Erickson, Alejandro; Fan, Jianxi; Jia, Xiaohua.

In: Computer Journal, Vol. 58, No. 11, 11.08.2014, p. 2944-2955.

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review