The hypercube serves as a high-performance interconnection network employed in various fields, including data center networks, network-on-chips, and wireless sensor networks. As the number of processing elements rapidly increases, these application fields are facing significant challenges in preserving communication efficiency with robust fault-tolerant mechanisms. Paths and cycles are two effective and popular tools for improving the communication efficiency of large-scale networks. Fault-tolerant path/cycle embedding is recognized as a solution to maintain communication efficiency and fault tolerance simultaneously. In this paper, we aim to enhance the fault-tolerant path/cycle embedding capability of hypercube networks by an emerging fault model, namely thePartitionedEdgeFault (PEF) model. Under this model, we put forward four distinct fault-tolerant path/cycle embedding algorithms that can handle large-scale faulty edges. Moreover, by proving the upper bound of these algorithms’ fault tolerance, we derive the optimal fault-tolerant Hamiltonian laceability and bipancyclicity of hypercubes under the PEF model. Furthermore, we conduct both theoretical and experimental analyses to show our algorithms’ outstanding fault-tolerant capability compared to the state-of-the-art. To validate the practical applicability of our theoretical results, we also develop a deadlock-free routing strategy leveraging the proposed embedding algorithm and compare its performance with benchmark routing algorithms.

Data center networks (DCNs) are the essential backbone connecting servers, storage, and networking devices, enabling vast data processing and seamless transmission. Among these competing platforms, BCube stands out due to its exceptional scalability and fault tolerance. For a graphGas the underlying topology of a network, the neighbor connectivity (resp. edge-neighbor connectivity) refers to the minimum number of vertices (resp. edges) that the removal of their closed neighborhoods (which is called subversion) results in becoming disconnected, complete, or empty (resp. trivial). These two connectivities provide more precise evaluations of network reliability and fault tolerance. In this paper, we explore these two specific connectivities of BCube and conduct a series of experiments to evaluate the effects of subversion across various scales. Specifically, we compare the experimental outcomes of random failures with those of cascade failures at varying failure rates. Additionally, we conduct a comparative analysis of the average path length (APL) of BCube and other networks, including thek-aryn-cube and DCell, in residual networks after subversion. These experiments enhance our understanding of the complexities of neighbor connectivity and subversion behaviors within BCube, demonstrating its superior fault tolerance.

BCube stands as a renowned server-centric data center network (DCN), boasting numerous advantages, such as low diameter, high aggregate throughput, and abundant parallel paths. As DCNs expand rapidly, followed by the daily increasing likelihood of failures, fault tolerance has become an impor tant issue in DCNs. Hamiltonian paths constitute a pivotal network topology for parallel and distributed computing, suitable for designing deadlock-free routing algorithms, fault-tolerant routing algorithms, and congestion avoidance. The partitioned edge fault (PEF) model is a recently proposed fault model that exploits the properties of networks to achieve fault tolerance with an exponential scale. In this paper, we explore the existence of Hamiltonian paths in BCube under the PEF model. Since one switch failure will result in multiple faulty links, we also extend the conclusions related to Hamiltonian paths to analyze the fault tolerance of BCube under the PEF model when switch failures occur. Moreover, we provide algorithms to embed a Hamiltonian path between arbitrary two distinct servers into BCube under the PEF model. Experimental analysis and comparisons demonstrate that our approach exhibits exponential enhancements over the other known results, and BCube DCNs possess remarkable fault tolerance in response to both link and switch failures under the PEF model. As a by-product, we obtain a deadlock-free routing based on the constructed Hamiltonian path and assess the routing performance compared to the benchmark routing algorithms.

With the surge of bandwidth demand for cloud applications and the exponential growth of data, data center networks (DCNs) are expanding rapidly, followed by the daily increasing likelihood of failures. Such failures, whether due to device or link issues, are inevitable and often lead to packet loss, transmission delays, and even system downtime. Thus, it is crucial to assess the fault-tolerant capabilities of data center networks using appropriate reliability metrics when failures occur. BCube is a well-known server-centric data center network with many advantages, such as rich low-diameter paths, high throughput, and excellent expandability. Not only do the recently proposed matroidal connectivity and conditional matroidal connectivity have reasonable fault assumptions that align well with the structural characteristics of data center networks, but they also significantly enhance the fault tolerance performance of DCNs. This paper determines the matroidal connectivity and conditional matroidal connectivity of BCube, which is the first study to apply the two reliability metrics in DCNs. Then, we extend the conclusions about (conditional) matroidal connectivity to analyze the fault tolerance of BCube in the occurrence of switch failures. In addition, we develop an efficient algorithm to identify the structural features of minimum faulty edge sets, where the cardinality of these edge sets corresponds to the conditional matroidal connectivity of BCube. Finally, we experimentally evaluate the effects of both link and switch failures on BCube’s performance under the matroidal restriction. The experimental analyses reveal that BCube DCNs exhibit high fault tolerance under matroidal constraints, with the ability to withstand both link and switch failures.

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.

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.