Browse Prior Art Database

Fault Tolerant Routing Algorithm for a Hypercube

IP.com Disclosure Number: IPCOM000108310D
Original Publication Date: 1992-May-01
Included in the Prior Art Database: 2005-Mar-22
Document File: 3 page(s) / 120K

Publishing Venue

IBM

Related People

Finney, DW: AUTHOR

Abstract

A routing algorithm is described which utilizes the many alternative paths provided by the hypercube topology to reroute messages when a local fault is encountered in the normal path.

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

Fault Tolerant Routing Algorithm for a Hypercube

       A routing algorithm is described which utilizes the many
alternative paths provided by the hypercube topology to reroute
messages when a local fault is encountered in the normal path.

      For routing a message from source to destination port, the
hypercube topology offers a plurality of paths.  This routing
algorithm automatically routes messages via alternative paths when
local faults are detected.  For the majority of messages that would
normally have been routed via the faulty path, no additional latency
is added owing to the alternative routing.

      Each hypercube node contains a status register with one bit for
each output channel.  This bit is activated when a fault is detected
on the channel.  The status register may be set by hardware or
software.  This register is used by the routing algorithm to bypass
faulty channels.

      The output channel is selected by Exclusive ORing the
destination address with the node address, which yields the
destination vector, and then selecting the highest order bit that is
equal to "1" to be the output channel selection vector.  The status
register is used to mask the selection of faulty channels, so that
the highest order working channel is selected (Fig. 1).  As long as
at least one channel corresponding to the destination vector is
available, no additional latency will be added to the total message
path length (Fig. 2).

      If none of the working channels matches the destination vector,
then any working channel is selected and an error routing field in
the message is incremented by one.  If the value of the error routing
fie...