A set of $k$ spanning trees in a graph $G$ are called completely independent spanning trees (CISTs for short) if the paths joining every pair of vertices $x$ and $y$ in any two trees have neither vertex nor edge in common, except for $x$ and $y$ . The existence of multiple CISTs in the underlying graph of a network has applications in fault-tolerant broadcasting and secure message distribution. In this paper, we investigate the construction of CISTs in a server-centric data center network called BCube connected crossbars (BCCC), which can provide good network performance using inexpensive commodity off-the-shelf switches and commodity servers with only two network interface card (NIC) ports. The significant advantages of BCCC are its good expandability, lower communication latency, and higher robustness in component failure. Based on the structure of compound graphs of BCCC, we provide efficient algorithms to construct $\lceil \frac{n}{4}\rceil$ CISTs in the logical graph of BCCC, denoted by $L$ - $BCCC(n,k)$ , for $n\geqslant 5$ . As a by-product, we obtain a fault-tolerant routing that takes the constructed CISTs as its routing table. We then evaluate the performance of the fault-tolerant routing through simulation results.

A set of k (≥ 2) spanning trees in the underlying graph of a network topology is called completely independent spanning trees, (CISTs for short), if they are pairwise edge-disjoint and inner-node-disjoint. Particularly, if k=2, the two CISTs are called a dual-CIST. However, it has been proved that determining if there exists a dual-CIST in a graph is an NP-hard problem. Kwong et al. [IEEE/ACM Transactions Networking 19(5) 1543-1556, 2011] defined that a routing is protected, if there is an alternate with loop-free forwarding, when a single link or node failure occurs. Shortly afterward, Tapolcai [Optim. Lett. 7(4) 723-730, 2013] showed that a network possessing a dual-CIST suffices to establish a protection routing. It is well-known that Cayley graphs have a large number of desirable properties of interconnection networks. Although many results of constructing dual-CISTs on interconnection networks have been proposed in the literature, so far, the work has not been dealt with on Cayley graphs due to that their expansions are in exponential scalability. In this paper, we try to make a breakthrough of this work on some famous subclasses of Cayley graphs, including alternating group networks, bubble-sort network, and star networks. We first propose tree searching algorithms for helping the construction of dual-CISTs on low-dimensional networks. Then, by inductive construction, we show that dual-CISTs on high-dimensional networks can also be constructed agreeably. As a result, we can configure protection routings by using the constructed dual-CISTs. In addition, we complement some analysis with a simulation study of the proposed construction to evaluate the corresponding performance.

Dense Gaussian networks (DGNs) are suitable topology candidates for network-on-chip (NoC) architectures because they provide favorable network properties such as symmetry, regularity, lower diameter, and shorter average hop distance. In particular, DGNs can accommodate more nodes in the same chip area compared with other grid-like structures. A set of spanning trees in the underlying graph of a network is called completely independent spanning trees (CISTs for short) if, for each pair of vertices $x$ and $y$ in the graph, the paths joining $x$ and $y$ in any two spanning trees have neither vertex nor edge in common, except for $x$ and $y$ . Although the problem of determining whether a graph admits a dual-CIST (i.e., two CISTs) is NP-complete, the existence of multiple CISTs in a network has applications in fault-tolerant routing and secure message distribution. A recent result showed that a network possessing a dual-CIST suffices to configure a protection routing. A protection routing is a multi-path routing scheme for integrating route discovery and route maintenance mechanisms such that there is a loop-free alternate path for packet forwarding when a single link or node failure occurs. Accordingly, this paper develops linear-time algorithms for constructing a dual-CIST in DGNs. Furthermore, we provide simulation results to evaluate the performance of the efficiency of protection routing in DGNs.