Abstract:
The fault-tolerance routing algorithms on generalized hypercube networks with the set of faulty links are studied. Let
G(
m,
r):
N=
mr (
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 + 4
m - 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.