Fault-tolerant gamma interconnection network without backtracking

Abstract

A no-backtracking gamma interconnection network (NBGIN) is a modified gamma interconnection network (GIN) that can tolerate one switch or link fault without backward packet transmission. Basically, this can be achieved by providing two alternative paths at all intermediate nodes during the progression of routing through carefully designed algorithm. In this work, a destination 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 link 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 processes 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 with the routing tag. (C) 2001 Elsevier Science Inc. All rights reserved.