TY - JOUR
T1 - An efficient algorithm to construct disjoint path covers of DCell networks
AU - Wang, Xi
AU - Fan, Jianxi
AU - Jia, Xiaohua
AU - Lin, Cheng-Kuan
PY - 2016/1/4
Y1 - 2016/1/4
N2 - 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, Dk,n, has been proposed for one of the most important data center networks as a server centric data center network structure. Dk,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,n is one-to-one r-disjoint path coverable for any integer 1≤r≤n+k-1, except for D1,2. Moreover, we propose an O(tk) algorithm for finding a one-to-one r-disjoint path cover in Dk,n for any integer 1≤r≤n+k-1, where tk is the number of servers in Dk,n.
AB - 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, Dk,n, has been proposed for one of the most important data center networks as a server centric data center network structure. Dk,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,n is one-to-one r-disjoint path coverable for any integer 1≤r≤n+k-1, except for D1,2. Moreover, we propose an O(tk) algorithm for finding a one-to-one r-disjoint path cover in Dk,n for any integer 1≤r≤n+k-1, where tk is the number of servers in Dk,n.
KW - Data center network
KW - DCell network
KW - Disjoint path cover
KW - Hamiltonian path
UR - http://www.scopus.com/inward/record.url?scp=84951909205&partnerID=8YFLogxK
UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-84951909205&origin=recordpage
U2 - 10.1016/j.tcs.2015.09.022
DO - 10.1016/j.tcs.2015.09.022
M3 - 21_Publication in refereed journal
VL - 609
SP - 197
EP - 210
JO - Theoretical Computer Science
JF - Theoretical Computer Science
SN - 0304-3975
ER -