A Class of Redundant Path Multistage Interconnection Networks

Abstract

A general class of fault-tolerant multistage interconnection networks is presented, wherein fault-tolerance is achieved by providing multiple disjoint paths between every input and output. These networks are derived from the Omega networks and as such retain all the connection properties of the parent networks in the absence of faults. An R-path network in this class can tolerate (R-1) arbitrary faults in the intermediate stages of the network at a cost that is far less than providing R copies of the original network. Different techniques for constructing such networks are presented and relevant properties and control algorithms are investigated.