Fault-Tolerant Routing for Multistage Interconnection Networks
Original Publication Date: 1989-Mar-01
Included in the Prior Art Database: 2005-Jan-27
The presence of fault-producing elements in message routing in a multiprocessor data handling system employing a multistage interconnection network can be tolerated by using two passes that first route the message to an incorrect intermediate destination which then forwards the message to the correct destination. This technique avoids the necessity of extra stages or redundant switching elements. In the figure, a portion of a multistage network is shown with full-access capability between any two of sixteen connected processors, each with an associated memory element and designated PME. The network consists of log2N stages of switching elements, each having two imputs and two outputs to connect N input ports to N output ports. In the figure, only four stages 1-4 of n stages are shown with 0-7 switching elements in each stage.