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, Dk,n, has been proposed for one of the most important data center networks as a server centric data center network...

Full description

Saved in:
Bibliographic Details
Published in:Theoretical computer science 2016-01, Vol.609, p.197-210
Main Authors: Wang, Xi, Fan, Jianxi, Jia, Xiaohua, Lin, Cheng-Kuan
Format: Article
Language:English
Subjects:
Algorithms
Data center network
Data centers
DCell network
Disjoint path cover
Hamiltonian path
Integers
Networks
Servers
Servers (computers)
Switches
Switching theory
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0304-3975
1879-2294
DOI:10.1016/j.tcs.2015.09.022