8 October 2020 in IEEE Transactions on Parallel and Distributed Systems
A set of spanning trees $T_1,T_2,\cdots,T_k$ in a network G are Completely Independent Spanning Trees (CISTs) if for any two nodes u and $v$ in $V(G)$ , the paths between u and v in any two trees have no common edges and no common internal nodes. CISTs have important applications in data center networks, such as fault-tolerant multi-node broadcasting, fault-tolerant one-to-all broadcasting, reliable broadcasting, secure message distribution, and so on. The augmented cube $AQ_n$ is a prominent variant of the well-known hypercube $Q_n$ , and having the important property of scalability, and both $Q_n$ and $AQ_n$ have been proposed as the underlying structure for a data center network. The data center network based on $AQ_n$ is denoted by $AQDN_n$ , and the logic graph of $AQDN_n$ is denoted by $L\text{-}AQDN_n$ . In this paper, we study how to construct $n-1$ CISTs in $L\text{-}AQDN_n$ . The constructed $n-1$ CISTs are optimal in the sense that $n-1$ is the maximally allowed CISTs in $L\text{-}AQDN_n$ . The correctness of our construction algorithm is proved. It is the first time a direct relationship is established between the dimension of a hypercube-family network and the number of CISTs it can host.
17 July 2023 in ACM Computing Surveys
The problem of constructing independent spanning trees (ISTs) dates back to as early as the late 1980s. Given a network G of a certain topology, the question is whether we can, as well as how to, construct a set of ISTs in G . ISTs have proven to be of great importance in many network tasks. The past decade has seen a particularly remarkable increase in the literature on ISTs, manifesting a significant growth of interest. ISTs can be classified into edge-independent spanning trees (edge-ISTs), node-independent spanning trees (node-ISTs), and completely independent spanning trees (CISTs). For a network G , node-ISTs (edge-ISTs) rooted at u are a set of spanning trees rooted at u in G such that there are no common internal nodes (edges) between u and any other node among the paths in these spanning trees. If every node in a set of node-ISTs can act as a root node, the set of trees is called CISTs . This survey aims at bringing together important works on ISTs that have been reported in the literature. It provides a historical perspective of how the field has evolved, and can serve as an integrated useful resource of references for future research on ISTs.
13 September 2019 in IEEE Transactions on Parallel and Distributed Systems
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.
30 January 2013 in The Journal of Supercomputing
30 September 2020 in Journal of Computer Science and Technology
13 June 2024 in IEEE/ACM Transactions on Networking
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).