%0 Journal Article
%T Hamiltonian Properties of DCell Networks
%A Xi Wang
%A Alejandro Erickson
%A Jianxi Fan
%A Xiaohua Jia
%J Computer Science
%D 2015
%I arXiv
%R 10.1093/comjnl/bxv019
%X 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.
%U http://arxiv.org/abs/1510.02689v1