Hamiltonian Properties of DCell Networks

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(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.