Hamiltonian Properties of the Data Center Network HSDC with Faulty Elements

The data center network HSDC is a superior candidate for building large-scale data centers, and strikes a good balance among diameter, bisection width, incremental scalability and other important characteristics in contrast to the state-of-the-art data center network architectures. The Hamiltonian property is an important indicator to measure the reliability of a network. In this paper, we study the Hamiltonian properties of HSDC's logic graph H-n. Firstly, we prove that H-n is Hamiltonian-connected for n >= 3. Secondly, we propose an O(NlogN) algorithm for finding a Hamiltonian path between any two distinct nodes in H-n, where N is the number of nodes in H-n. Furthermore, we consider the Hamiltonian properties of H-n with faulty elements, and prove that H-n is (n - 3)-fault-tolerant Hamiltonian-connected and (n - 2) -fault-tolerant Hamiltonian for n >= 3.