Browse Prior Art Database

Fault Tolerant Routing Schemes on Multistage Interconnection Networks

IP.com Disclosure Number: IPCOM000110746D
Original Publication Date: 1992-Dec-01
Included in the Prior Art Database: 2005-Mar-25
Document File: 2 page(s) / 103K

Publishing Venue

IBM

Related People

Bruck, J: AUTHOR [+8]

Abstract

Disclosed is a unified technique for tolerating switch faults in a multistage interconnection network, each pair of processors. We bidirectional multistage interconnection network where an operational switch chip can route a packet incoming on any of its input ports to any of its output ports.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 52% of the total text.

Fault Tolerant Routing Schemes on Multistage Interconnection Networks

       Disclosed is a unified technique for tolerating switch
faults in a multistage interconnection network, each pair of
processors.  We bidirectional multistage interconnection network
where an operational switch chip can route a packet incoming on any
of its input ports to any of its output ports.

      The disclosed technique for tolerating faults in such
multistage interconnection networks consists of three stages.  First,
it identifies and locates switch faults.  Second, it identifies a set
of processors that can continue to operate despite the faulty
switches.  And third, it computes routes that do not contain faulty
switches between the remaining processors.
Stage 1: Locating Faults

      In the first stage, the network duplicates communication
operations and constantly checks for disagreements which would
indicate faults.
Stage 2: Disabling Processors
Omega Networks

      In an Omega network [1], there is a unique path between each
source-destination processor pair.  Therefore, every switch fault
prevents certain pairs of processors from communicating.  Let N be
the number of processors and B be the radix of each switch.  If a
switch in stage i is faulty, either a set of Bi source processors or
a set of N/Bi-1 destination processors can be disabled.  It is,
therefore, best to disable the set of source processors when the
faulty switch lies in the first half of the network and to disable
the set of destination processors when it lies in the second half.

      When there are f>1 faulty switches, the situation is more
complicated.  Each faulty switch in stage i either disables Bi source
processors or N/Bi-1 destination processors.  However, it is possible
for the set of source or destination processors disabled by one
faulty switch to overlap with those disabled by another faulty
switch.  It is impossible to minimize the number of processors
disabled by one faulty switch without considering the others.  In
practice, when f is small, it is possible to determine the smallest
set of processors to disable by examining all the 2f combinations of
sets of processors.  When f is large, a simple heuristic would be to
disable the set of source processors corresponding to each switch
fault in the first half of the network and to disable the set of
destination processors corresponding to each switch fault in the
second half of the network.
Extra-Stage Omega Networks

      An Omega network with one extra stage consists of an Omega
netw...