Connectivity and Routing Algorithm of the Data Center Network HSDC

AbstractIn order to satisfy the rapidly increasing demand for data volume, large data center networks (DCNs) have been proposed. In 2019, Zhang et al. proposed a new highly scalable DCN architecture named HSDC, which can achieve greater incremental scalability. In this paper, we give the definition of the logical graph of HSDC, named \(H_n\), which can be treated as a compound graph of hypercube and complete graph of the same dimension. First, we prove that the connectivity and tightly super connectivity of \(H_n\) are both n. Then, we give an O(n) routing algorithm to find a shortest path between any two distinct nodes in \(H_n\), and prove the correctness of this algorithm. In fact, we also prove that the distance constructed by this algorithm is no more than \(2d+1\) if \(d