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

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.