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.

The generalized hypercube (GH) is one key interconnection network with excellent topological properties. It not only contains many other interconnection topologies, but also can be used to construct some data center networks, such as HyperX, BCube, FBFLY, and SWCube. However, the construction cost of GH is high since there are too many links in it. Therefore, in this paper, we propose a novel low cost interconnection architecture called the exchanged generalized hypercube (EGH). We study the properties of EGH, such as the number of edges, the degree of vertices, connectivity, diameter, and diagnosability. Then, we give a routing algorithm to find the shortest path between any two distinct vertices of EGH. Furthermore, we design an algorithm to give disjoint paths between any two distinct vertices of EGH. In addition, we propose two local diagnosis algorithms in EGH under PMC model and MM model, respectively. Simulation results demonstrate that even if the proportion of faulty vertices in EGH is up to 25%, the probability that these two diagnosis algorithms can successfully judge the status of vertices is more than 90%. The analysis shows that the construction cost of EGH is much less than GH.

An efficient diagnosis is very important for a multiprocessor system. The ability to identify all the faulty devices in a multiprocessor system is known as diagnosability. In the comparison model, the diagnosis is performed by sending two identical signals from a processor to a pair of distinct neighbors, and then comparing their responses. Sengupta and Dahbura proposed a polynomial-time algorithm with time complexity O(N⁵) to diagnose a system with a total number N of processors under the comparison model. Recently, some concepts, such as the conditional diagnosability and the local diagnosability, are concerned with the measure which is able to better reflect fault patterns in real systems. In this paper, we propose a specific structure, the balanced wind-bell-tree, and give an algorithm to determine the fault status of each processor for conditional local diagnosis under the comparison model. According to our results, a specific t-connected network with the balanced wind-bell-tree structure is conditionally (2t-1)°-diagnosable, and the time complexity to diagnose all the faulty processors is O(N(logN)²) with our algorithm, where N is the total number of the processors in the network.

The $k$ -ary $n$ -cube $Q_{n}^{k}$ is one of the most popular interconnection networks engaged as the underlying topology of data center networks, on-chip networks, and parallel and distributed systems. Due to the increasing probability of faulty edges in large-scale networks and extensive applications of the Hamiltonian path, it becomes more and more critical to investigate the fault tolerability of interconnection networks when embedding the Hamiltonian path. However, since the existing edge fault models in the current literature only focus on the entire status of faulty edges while ignoring the important information in the edge dimensions, their fault tolerability is narrowed to a minimal scope. This paper first proposes the concept of the partitioned fault model to achieve an exponential scale of fault tolerance. Based on this model, we put forward two novel indicators for the bipartite networks (including $Q^{k}_{n}$ with even $k$ ), named partition-edge fault-tolerant Hamiltonian laceability and partition-edge fault-tolerant hyper-Hamiltonian laceability. Then, we exploit these metrics to explore the existence of Hamiltonian paths and unpaired 2-disjoint path cover in $k$ -ary $n$ -cubes with large-scale faulty edges. Moreover, we prove that all these results are optimal in the sense that the number of edge faults tolerated has attended to the best upper bound. Our approach is the first time that can still embed a Hamiltonian path and an unpaired 2-disjoint path cover into the $k$ -ary $n$ -cube even if the faulty edges grow exponentially.