Constructing Completely Independent Spanning Trees in Data Center Network Based on Augmented Cube

Guo Chen, Baolei Cheng, Dajin Wang

Research output: Contribution to journalArticlepeer-review

27 Scopus citations


A set of spanning trees T1,T2,., TkT1,T2,..,Tk in a network G are Completely Independent Spanning Trees (CISTs) if for any two nodes u and v in V(G) V(G), the paths between u and v in any two trees have no common edges and no common internal nodes. CISTs have important applications in data center networks, such as fault-tolerant multi-node broadcasting, fault-tolerant one-to-all broadcasting, reliable broadcasting, secure message distribution, and so on. The augmented cube AQn is a prominent variant of the well-known hypercube Qn, and having the important property of scalability, and both Qn and AQn have been proposed as the underlying structure for a data center network. The data center network based on AQn is denoted by AQDNn, and the logic graph of AQDNn is denoted by L-AQDNn. In this article, we study how to construct n-1 CISTs in L-AQDNn. The constructed n-1 CISTs are optimal in the sense that n-1 is the maximally allowed CISTs in L-AQDNn. The correctness of our construction algorithm is proved. It is the first time a direct relationship is established between the dimension of a hypercube-family network and the number of CISTs it can host.

Original languageEnglish
Article number9217977
Pages (from-to)665-673
Number of pages9
JournalIEEE Transactions on Parallel and Distributed Systems
Issue number3
StatePublished - 1 Mar 2021


  • Augmented cube
  • completely independent spanning trees
  • data center network
  • edge-disjoint hamiltonian paths
  • hamiltonian cycle


Dive into the research topics of 'Constructing Completely Independent Spanning Trees in Data Center Network Based on Augmented Cube'. Together they form a unique fingerprint.

Cite this