Hamiltonian Properties of DCell Networks
Xi Wang, Alejandro Erickson, Jianxi Fan, Xiaohua Jia · The Computer Journal · 2015
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}$|. Furthermore, 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.