Fault-Tolerant Routing of Generalized Hypercubes under 3-Component Connectivity
Chang Shu, Yan Wang, Jianxi Fan, Huanwen Zhang · 2021
The ability of a network to maintain its function in the face of outages caused by node failures is defined as fault tolerance and the component connectivity is a good indicator to measure the fault tolerance of network. The fault-tolerant routing algorithm based on component connectivity plays an important role in ensuring network reliability. The r-dimensional generalized hypercube G(mr,mr−1 ,…,m1) is an important topological structure, which has a small diameter, easy-to-construct connection mode and recursive structure. In this paper, for G(mr,mr−1 ,…,m1), firstly we study 3component connectivity and propose a fault-tolerant routing algorithm based on 3-component connectivity. We denote the 3-component connectivity of the generalized hypercube as cκ3(G) and prove cκ3(G) = 2κ(G) − 2, where κ(G) is the classic connectivity of the r-dimensional generalized hypercube. Then based on the 3-component connectivity, we propose an O(κ(G)3) fault-tolerant routing algorithm GHCCP, which can construct at least one fault-free path between any two distinct fault-free vertices.