Fault-tolerant gamma interconnection networks by chaining

Abstract

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