Connectivity and Routing Algorithm of the Data Center Network HSDC

Part 8: NetworkInternational audienceIn 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$$Hn, 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$$Hn are both n. Then, we give an O(n) routing algorithm to find a shortest path between any two distinct nodes in $$H_n$$Hn, 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$$2d+1 if $$d<n$$d