An efficient algorithm to construct disjoint path covers of DCell networks

Data center networks have been becoming more and more important with the development of cloud computing. For any two integers k≥0 and n≥2, the k-dimensional DCell with n-port switches, D_k,n, has been proposed for one of the most important data center networks as a server centric data center network structure. D_k,n can support millions of servers with outstanding network capacity and provide good fault tolerance by only using commodity switches. A disjoint path cover has significant applications in data center networks. In this paper, we prove that D_k,n is one-to-one r-disjoint path coverable for any integer 1≤r≤n+k-1, except for D_1,2. Moreover, we propose an O(t_k) algorithm for finding a one-to-one r-disjoint path cover in D_k,n for any integer 1≤r≤n+k-1, where t_k is the number of servers in D_k,n.