TY - JOUR
T1 - Hamiltonian Properties of DCell Networks
AU - Wang, Xi
AU - Erickson, Alejandro
AU - Fan, Jianxi
AU - Jia, Xiaohua
PY - 2014/8/11
Y1 - 2014/8/11
N2 - 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.
AB - 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.
KW - algorithm
KW - data center networks
KW - DCell
KW - fault tolerance
KW - Hamiltonian
KW - Hamiltonian connectivity
KW - partial DCell
UR - http://www.scopus.com/inward/record.url?scp=84947791747&partnerID=8YFLogxK
UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-84947791747&origin=recordpage
U2 - 10.1093/comjnl/bxv019
DO - 10.1093/comjnl/bxv019
M3 - 21_Publication in refereed journal
VL - 58
SP - 2944
EP - 2955
JO - Computer Journal
JF - Computer Journal
SN - 0010-4620
IS - 11
ER -