An efficient algorithm to construct disjoint path covers of DCell networks

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review

33 Scopus Citations
View graph of relations

Author(s)

Related Research Unit(s)

Detail(s)

Original languageEnglish
Pages (from-to)197-210
Journal / PublicationTheoretical Computer Science
Volume609
Online published3 Oct 2015
Publication statusPublished - 4 Jan 2016

Abstract

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.

Research Area(s)

  • Data center network, DCell network, Disjoint path cover, Hamiltonian path

Citation Format(s)

An efficient algorithm to construct disjoint path covers of DCell networks. / Wang, Xi; Fan, Jianxi; Jia, Xiaohua; Lin, Cheng-Kuan.

In: Theoretical Computer Science, Vol. 609, 04.01.2016, p. 197-210.

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review