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

摘要

A set of spanning trees T1; T2;...; Tk in a network G are Completely Independent Spanning Trees (CISTs) if for any two nodes u and v in V oGTHORN, 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.