Research on Fault-Tolerance Routing Algorithms on Generalized Hypercube Networks

The fault-tolerance routing algorithms on generalized hypercube networks with the set of faulty links are studied. Let G(m, r): N= m^r (m ≥ 2, r ≥ 1), be a generalized hypercube networks with the set of faulty links F, |F| denotes the number of elements in F and the graph G(m, r) - F is connected. S and D are two nodes, between which the Hamming distance is H(S, D) = h. Then, there are conclusions as following:(1) If |F| < d, there is a fault-free path P(S, D), such that |P(S, D)| ≤h+2; (2) If d≤ |F| <m(d-m+ 1), there is a fault-free path P(S, D), such that |P(S, D)| ≤ h + 4m - 2. where, | P(S, D) | is the length of Path P(S, D) and d is the degree of G(m, r). Path P(S, D) is fault-free means that there is no faulty links on it. The corresponding routing algorithms are proposed in this paper.