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
Document File: 3 page(s) / 71K

Publishing Venue

IBM

Related People

Rathi, BD: AUTHOR [+2]

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.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 52% of the total text.

Page 1 of 3

Fault-Tolerant Routing for Multistage Interconnection Networks

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. Each network port is identified by an n-digit address. Messages to be transmitted have headers that include routing tags of n-bits that represent the destination ports, such as d1, d2, d3...dn, when each bit is one stage. For example, stage i looks at bit i and routes the message to the top output of the switch for a 0 and the bottom for a 1. An illustration is given in the figure with a connection from output port 4 to output port 5 via binary routing of 0101. The header also contains a source address for request- acknowledgement handshake protocol. When a switching element or connecting link fails, the fault is noted by the preceding switching element and is avoided by transmission of the message to an intermediate destination, then to the correct destination. This is done by changing the bits in the routing tag after the last successful stage in the first pass. For the succeeding stages, corresponding source address bits are used as the routing bits to the intermediate destination. In the second pass, the message is routed to the correct destination by using the original tag. Implementation requires a reroute bit, circuits to read or set the reroute bit...