Given a simple undirected graph$G$, a set of spanning trees for$G$are completely independent spanning trees (CISTs for short), where for any two vertices$x, y \in V(G)$, the paths connecting$x$and$y$on these trees have no common vertices and edges except$x$and$y$. In this paper, we provide an approach to construct three CISTs in three$n$-dimensional folded hypercube-variant networks, including enhanced hypercubes ($n=5$), folded crossed cubes ($n=5$) and complete Josephus cubes ($n=4$). For higher-dimensional networks, we propose a recursive algorithm that generates three CISTs with diameters of order$2 n+c$for some constant$c$. Finally, we simulate numerous node pairs using the three constructed CISTs to configure protection routes, test random node failures, and employ the transmission failure rate (TFR) to evaluate the effectiveness of CIST-based protection routing, demonstrating strong fault tolerance under various failure scenarios.

A network can contain numerous spanning trees. If two spanning trees T i , T j do not share any common edges, T i and T j are said to be pairwisely edge-disjoint. For spanning trees T 1 , T 2 ,…, T m , if every two of them are pairwisely edge-disjoint, they are called completely edge-independent spanning trees (CEISTs for short). CEISTs can facilitate many network functionalities, and constructing CEISTs as maximally allowed as possible in a given network is a worthy undertaking. In this paper, we establish the maximal number of CEISTs in the locally twisted cube network, and propose an algorithm to construct ⌊ n 2 ⌋ CEISTs in LTQ n , the n -dimensional locally twisted cube. The proposed algorithm has been actually implemented, and we present the outputs. Network broadcasting in the LTQ n was simulated using ⌊ n 2 ⌋ CEISTs, and the performance compared with broadcasting using a single tree.

It is widely known that parallel and distributed systems are crucial technologies and platforms necessary to support supercomputing and cloud computing. The network architecture forms the foundational support for the stable operation of these systems, directly influencing their reliability, scalability, and robustness. As the network scale expands, the probability of processor/server and communication link failures increases. Therefore, it is imminent to consider how to build up the fault tolerance and reliability of the network. The circulant-based recursive networks (CRNs) are a novel type of network with several desirable properties such as regularity, recursiveness, vertex (edge) transitivity and so on. CRNs contain not only interconnection networks hypercubes and$k$-ary$n$-cubes, but also data center network BCube, as well as some future networks. Connectivity and diagnosability of networks have garnered significant attention, as they suffice for analyzing and measuring networks' fault tolerance. This article focuses primarily on conditional connectivity and diagnosability under the good neighbor fault pattern. In this work, we explore the conditional connectivity and diagnosability (built on$g$-good neighbor fault pattern) of the$f$-dimensional$r$-order CRN under the PMC model and MM* model, respectively. These values are nearly$g$times greater than the traditional connectivity and diagnosability of CRNs, respectively, implying that they can further improve fault tolerance of CRNs. Furthermore, it is worth noting that the results can be effectively utilized in BCube and other future networks given that they are both subclasses of CRNs.

With the increasing network scale, hardware faults are inevitable. Therefore, research on network reliability under the condition of hardware failure is an important subject. In this article, we investigate$h$-extra connectivity,$h$-extra diagnosability under the PMC and MM$^{*}$models, and$t/m$-diagnosability under the PMC model of recursive networks based on complete graphs (RNCGs) that include not only interconnection network Dragonfly but also data center networks—DCell, generalized DCell, and other unknown networks. In addition, we propose the fault-tolerant routing (F-TR) algorithm, FTPath, which constructs a F-TR in the largest component when the number of faulty nodes is less than the$h$-extra connectivity. Moreover, we evaluate the performance of RNCGs. First, we compare the fault-tolerant performance of RNCGs through experiments. The results show that the average path length constructed by the FTPath algorithm is close to that of the breadth-first search algorithm, and shorter than that of the depth-first search algorithm. Second, we evaluate the performance of this network for different parameters:$h$-extra connectivity, diagnosability under different strategies. The results show that the network has good fault tolerance and fault diagnosis capabilities.

Abstract Fault-tolerant performance of a network is the prerequisite and guarantee for the normal operation of a network, which is often characterized by connectivity. Let $H$ denote a connected subgraph of $G$ and $H^{*}$ denote the union of the set of all connected subgraphs of $H$ and the set of the trivial graph. Super $H$-connectivity (resp. super $H^{*}$-connectivity) satisfies the conditions of both super connectivity and $H$-structure connectivity (resp. $H$-substructure connectivity). These two kinds of new connectivity provide a new metric to measure the fault-tolerance of the network, that is, the super structure fault-tolerance. The generalized hypercube $G(m_{r}, m_{r-1},..., m_{1})$ is a universal topology of interconnection networks that contains other commonly used topologies and it has been applied in many data center networks because of its excellent qualities. In this paper, we research the super structure fault-tolerance of $G(m_{r}, m_{r-1},..., m_{1})$ by studying super $H$-connectivity $\kappa ^{\prime}(G|H)$ and super $H^{*}$-connectivity $\kappa ^{\prime}(G|H^{*})$ for $H\in \{K_{1,M},\ C_{3},\ C_{4},\ K_{4}\}$.

Abstract According to Menger’s theorem, connectivity and edge connectivity are closely related to node-disjoint paths and edge-disjoint paths, respectively. Node- and edge-disjoint paths can keep the effective transmission of information and confidentiality. Therefore, node-disjoint paths and edge-disjoint paths are two important parameters to measure the reliability of a network. For a faulty node (resp. edge) set $S\subset V$ (resp. $S\subset E$), a connected graph $G=(V,E)$ is $S$-strongly Menger-node-connected (resp. Menger-edge-connected) if any two distinct nodes $x$ and $y$ in $G-S$ are connected by $\min \{\deg _{G-S}(x),\deg _{G-S}(y)\}$ internally node-disjoint (resp. edge-disjoint) paths in $G-S$, where $\deg _{G-S}(x)$ and $\deg _{G-S}(y)$ are the degrees of $x$ and $y$ in $G-S$, respectively. And most of the previous studies are based on networks that are triangle-free. In this paper, we consider the strongly Menger (edge) connectedness of a class of $r$-dimensional recursive networks RNCG $G_{r}$ with triangles. Moreover, we show that $G_{r}$ is $(rl-l-1)$-strongly Menger-node-connected. And then we show that $G_{r}$ is $[k+(r-1)l-2]$-strongly Menger-edge-connected of order 1 and $[2k+2(r-1)l-6]$-strongly Menger-edge-connected of order 2. Since the class of $r$-dimensional recursive networks RNCG $G_{r}$ includes not only data center networks DCell and generalized DCell but also interconnection network dragonfly, etc., all the results are appropriate for these networks.

Networks of large scales are an essential component in supercomputing systems as well as in data centers. As the network scale increases, the probability of processor/server failures also inevitably increases. It is therefore a worthwhile undertaking to make efforts reducing, as much as possible, the effect of faulty processors/servers to the entire network. This paper introduces a new class of network architectures, called circulant-based recursive networks (CRNs), and investigates CRN’s diameter, connectivity, and in particular, the fault diagnosability under the two diagnostic models−the PMC and the comparison diagnostic models. CRNs are a generalization of some well-known interconnection networks−hypercube, k-ary n-cube network and the data center network BCube, as well as some other less-known networks. In addition to obtaining its diagnosability properties, the paper also presents a one-to-one (unicast) path construction algorithm named SPath. Based on SPath, we further propose an algorithm FTPath for CRNs finding a fault-tolerant path between any two vertices, provided that the number of faulty vertices is no more than its connectivity minus one. Three parameters−average distance, message density, and cost−are used to assess CRNs’ performance. Experimental comparisons are conducted, and the results indicate that the average path length obtained by the algorithm SPath (resp., FTPath) is shorter than that of the Depth-First Search algorithm (DFS) and is on a par with the Breath-First Search algorithm (BFS).

Abstract The data center network HSDC is a superior candidate for building large-scale data centers, and strikes a good balance among diameter, bisection width, incremental scalability and other important characteristics in contrast to the state-of-the-art data center network architectures. The Hamiltonian property is an important indicator to measure the reliability of a network. In this paper, we study the Hamiltonian properties of HSDC’s logic graph $H_n$. Firstly, we prove that $H_n$ is Hamiltonian-connected for $n\geq 3$. Secondly, we propose an $O(NlogN)$ algorithm for finding a Hamiltonian path between any two distinct nodes in $H_n$, where $N$ is the number of nodes in $H_n$. Furthermore, we consider the Hamiltonian properties of $H_n$ with faulty elements, and prove that $H_n$ is $(n-3)$-fault-tolerant Hamiltonian-connected and $(n-2)$-fault-tolerant Hamiltonian for $n\geq 3$.

Abstract As a kind of conditional connectivity, component connectivity is an improvement of traditional connectivity, which is conducive to enhance the reliability of the network. To be specific, the $r$-component connectivity of a network $G$, written as $c\kappa _{r}(G)$, is defined as the minimum number of all node cuts whose removal causes the remaining network to have at least $r$ components. Component diagnosability, as another measure of network reliability, is usually related to the number of components in the remaining network. The $r$-component diagnosability, written as $ct_{r}(G)$, is defined as the maximum number of faulty sets such that at least $r$ components in the surviving network and all faulty nodes can be diagnosed. This paper mainly explores the relationship between component connectivity and component diagnosability of some regular networks. Once knowing the component connectivity of such a network, with the help of this relationship, we can easily obtain the component diagnosability of the network. Furthermore, we apply this relationship to some famous regular networks to obtain their component diagnosabilities under the PMC model.

Abstract Connectivity is a significant metric to assess the fault tolerance of a network. For a faulty vertex set $H$, the $h$-extra connectivity is defined under the assumption that every component of the network removing $H$ has at least $h+1$ fault-free vertices. Compared to the traditional connectivity, which is defined under the assumption that the network removing $H$ is disconnected or trivial, the $h$-extra connectivity can better reflect the true fault tolerance of the network. The $BCube$ is an important server-centric data center network; it has good fault tolerance and scalability. In this paper, our research focuses on the logical structure of $BCube$, named $BC_{n,k}$, which is actually a specific type of generalized hypercubes. We prove that the 3-extra connectivity of $BC_{n,k}$ is $4(k+1)(n-1)-4n$ for $k\geq 4$ and $n\geq 4$.

Independent spanning trees (ISTs) play an important role in secure message distribution, bandwidth as well as fault-tolerant broadcasting. Thus the construction of ISTs on many classes of graphs has been investigated. The n-dimensional folded crossed cube FCQnis a strengthened variation of the n-dimensional crossed cube CQn, which is obtained from CQnby adding edges between any pair of vertices with furthest Hamming distance. In this paper, we study the existence and parallel construction of ISTs on FCQn. We first present the definition of Flag-Mapping and propose an algorithm to obtain the Flag-Mapping of each vertex on n +1 spanning trees of FCQn. Then based on the outputs of above algorithm, we propose a fully parallelized algorithm with the time complexity O(n) by using N processors to construct n +1 ISTs on FCQn, where n ≥ 1 and N =2n, and present the corresponding simulation experiments to verify its validity.