Fault-tolerant gamma interconnection network without backtracking

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.