Fault-tolerant gamma interconnection networks by chaining

The authors propose two single-fault-tolerant gamma interconnection network s. The first is a partially chained gamma interconnection network (PCGIN) w ith two disjoint paths between any source-destination pair. A PCGIN has the characteristics of one fault tolerance and destination tag routing, but ba cktracking may be necessary when a fault occurs. To eliminate the backtrack ing penalties of a PCGIN, a fully chained gamma interconnection network (FC GIN); that can at least tolerate one link or switch fault at each stage wit hout backtracking, is also proposed FCGIN has the advantages of destination tag routing, lower hardware costs than a PCGIN, low fault penalty, and str ong reroutability.