Browse Prior Art Database

Fault-Tolerant Routing for Multistage Interconnection Networks

IP.com Disclosure Number: IPCOM000034583D
Original Publication Date: 1989-Mar-01
Included in the Prior Art Database: 2005-Jan-27

Publishing Venue

IBM

Related People

Authors:
Rathi, BD Varma, A [+details]

Abstract

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.