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.

With the rapid development of cloud computing, many large-scale data centers are being built to provide increasingly popular online application services. This leads to the proposal of data center networks (DCNs) supporting millions of servers with high-network capacity by using only commodity switches. The k-dimensional DCell with n-port switches and $tk,n$ servers, $Dk,n$, has been proposed as a model for a large-scale DCN with a server-centric structure. In this paper, we study the diagnosability and the g-good-neighbor conditional diagnosability of $Dk,n$. We prove that: (i) $Dk,n$ is $(n+k−1)$-diagnosable under the precise diagnosis strategy and $(2k+n−2)/(2k+n−2)$- diagnosable under the pessimistic diagnosis strategy; (ii) the g-good-neighbor conditional diagnosabilities of $Dk,n$ under the PMC model and the MM^* model are both $(g+1)k+n−1$ (resp. $(n+k−g)tg−n+1,n−1)$ with $0≤g≤n−1$ (resp. $n≤g≤n+k−2$), which is almost $(g+1)$ (resp. $tg−n+1,n$) times of the traditional diagnosability. These results provide a quantitative evaluation for a large-scale DCN’s reliability and availability.

Connectivity is a classic measure for reliability of a multiprocessor system in the case of processor failures. Extra connectivity and component connectivity are two important indicators of the reliability of a multiprocessor system in presence of failing processors. The $h$-extra connectivity $\kappa _{h}(G)$ of a graph $G$ is the minimum number of nodes whose removal will disconnect $G$, and every remaining component has at least $h+1$ nodes. Moreover, the $h$-component connectivity $c\kappa _{h}(G)$ of $G$ is the minimum number of nodes whose deletion results in a graph with at least $h$ components. However, the extra connectivity and component connectivity of many well-known networks have been independently investigated. In this paper, we determine the relationship between extra connectivity and component connectivity of general networks. As applications, the extra connectivity and component connectivity are explored for some well-known networks, including complete cubic networks, hierarchical cubic networks, generalized exchanged hypercubes, dual-cube-like networks, Cayley graphs generated by transposition trees and hierarchical hypercubes as well.

The scale of data center networks (DCNs) has grown rapidly with the increasing popularity of cloud computing, data explosion, and the dramatic drop in setup costs. Thus, inevitable component failures (including switches and servers) will become more frequent. A DCN requires maintaining regular and reliable operation and providing efficient routing algorithms for transmitting data between servers. Particularly, fault-tolerant routing is necessary. Recently, constructing completely independent spanning trees (CISTs) on DCNs has received much attention as a dual-CIST (i.e., two CISTs) suffices to configure protection routing, which is a fault-tolerant routing. Moreover, the protection routing can additionally realize a secure mechanism if it is configured by more CISTs. BCube is a server-centric DCN with many advantages, and many variations were deformed from BCube with application requirements, such as RCube and RRect. In this paper, we provide a unified framework called BCube-based DCN (BDCN) that integrates the representation of the logic graphs of DCNs mentioned above, facilitating consistent algorithms' design. Then, we develop efficient algorithms to construct multiple CISTs on BDCN under the consideration of switch failures. Note that this is the first study that constructs multiple CISTs in DCNs with switch failures. Finally, using standard metrics, such as average path length (APL) and transmission failure rate (TFR), we evaluate the performance of the fault-tolerant routing through experiments.

The recently proposed RCube network is a cube-based server-centric data center network (DCN), including two types of heterogeneous servers, called core servers and edge servers. Remarkably, it takes the latter as backup servers to deal with server failures and thus achieve high availability. This paper first points out that RCube is suitable as a candidate topology of DCNs for edge computing. Three transmission types are among core and edge servers based on the demand for applications’ computation and instant response. We then employ protection routing to analyze the transmission failure of RCube DCNs. Unlike traditional protection routing, which only tolerates a single link or node failure, we use the multi-protection routing scheme to improve fault-tolerance capability. To configure a protection routing in a network, according to Tapolcai’s suggestion, we need to construct two completely independent spanning trees (CISTs), which are edge-disjoint and inner-vertex-disjoint spanning trees. It is well-known that the problem of determining whether there exists a dual-CIST (i.e., two CISTs) in a network is NP-complete. A logic graph of RCube, denoted by $L$ - $RCube(n,m,k)$ , is a network with a recursive structure. Each basic building element consists of $n$ core servers and $m$ edge servers, where the order $k$ is the number of recursions applied in the structure. In this paper, we provide algorithms to construct $\min \{n,\lfloor (n+m)/2\rfloor \}$ CISTs in $L$ - $RCube(n,m,k)$ for $n+m\geqslant 4$ and $n>1$ . From a combination of the multiple CISTs, we can configure the desired multi-protection routing. In our simulation, we configure up to 10 protection routings for RCube DCNs. As far as we know, in past research, there were at most three protection routings developed in other network structures. Finally, we summarize some crucial analysis viewpoints about the transmission efficiency of DCNs with heterogeneous edge-core servers from the simulation results.