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

Abstract

A set of spanning trees T <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">1</sub> ; T <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sub> ;. .. ; Tk in a network G are Completely Independent Spanning Trees (CISTs) if for any two nodes u and v in 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.