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≥0k≥0 and n≥2n≥2, the k-dimensional DCell with n  -port switches, Dk,nDk,n, has been proposed for one of the most important data center networks as a server centric data center network structure. Dk,nDk,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 Dk,nDk,n is one-to-one r  -disjoint path coverable for any integer 1≤r≤n+k−11≤r≤n+k−1, except for D1,2D1,2. Moreover, we propose an O(tk)O(tk) algorithm for finding a one-to-one r  -disjoint path cover in Dk,nDk,n for any integer 1≤r≤n+k−11≤r≤n+k−1, where tktk is the number of servers in Dk,nDk,n.