A no-backtracking gamma interconnection network (NBGIN) is a modified gamma
interconnection network (GIN) that can tolerate one switch or link fault w
ithout backward packet transmission. Basically, this can be achieved by pro
viding two alternative paths at all intermediate nodes during the progressi
on of routing through carefully designed algorithm. In this work, a destina
tion tag routing named as NB function is designed. With this NB function, a
packet can find an alternate path as soon as it encounters a switch or lin
k fault in NBGIN. The major advantage of NBGIN over gamma-induced networks
is that there is no rerouting penalty under a fault. In addition, NBGIN pro
cesses the characteristics of one-fault tolerance, destination tag routing,
and dynamic rerouting. Furthermore, the routing and rerouting path can be
simply determined by the destination tag only instead of being computed wit
h the routing tag. (C) 2001 Elsevier Science Inc. All rights reserved.