Browse Prior Art Database

Adaptive Routing Schemes on Multistage Interconnection Networks

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

Publishing Venue

IBM

Related People

Bruck, J: AUTHOR [+8]

Abstract

Disclosed are four schemes for using adaptiveness in a static multistage interconnection network. We consider a bidirectional multistage interconnection network where the switch chip can route a packet incoming on any of its input ports to any of its output ports. Packets are routed using virtual cut-through, and blocked packets are stored in the switch in which congestion occurs. Each switch contains a small buffer associated with each input and output, as well as a large central queue. Packets may either pass directly from an input buffer to an output buffer, or they can go from an input buffer to the central queue and then to an output buffer. Successive flits of a packet may be stored in buffers at several consecutive switches on the packet's path. Scheme 1: Switch Adaptive Routing

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

Adaptive Routing Schemes on Multistage Interconnection Networks

       Disclosed are four schemes for using adaptiveness in a
static multistage interconnection network.  We consider a
bidirectional multistage interconnection network where the switch
chip can route a packet incoming on any of its input ports to any of
its output ports.  Packets are routed using virtual cut-through, and
blocked packets are stored in the switch in which congestion occurs.
Each switch contains a small buffer associated with each input and
output, as well as a large central queue.  Packets may either pass
directly from an input buffer to an output buffer, or they can go
from an input buffer to the central queue and then to an output
buffer.  Successive flits of a packet may be stored in buffers at
several consecutive switches on the packet's path.
Scheme 1: Switch Adaptive Routing

      This scheme uses redundant-path encodings where several output
ports of a switch have the same number.  A binary flit may be used to
select an output of a switch, where half the outputs are labeled with
0 and half the outputs are labeled with 1.  An incoming packet is
sent through the first available port having the correct label, and a
fair arbitration scheme is used when several such ports are
available.  The network topology is chosen so that all routes
associated with the same header lead to the same destination.  Work
[1,2] has shown that such a simple adaptive scheme can lead to
extremely good congestion tolerance, when used with a well-designed
network topology.
Scheme 2: Time Stamps

      This scheme adds time stamps to packets in order to detect
network congestion.  When processor i sends a packet to processor j,
processor i adds a time stamp t indicating when the packet was sent.
When processor j receives the packet, it checks to see if the current
time is past t + w, where w is a pre-selected threshold.  If the time
is past t + w, processor j sends a detour packet to processor i
indicating that the path that it used is suffering from congestion.
When processor i receives the detour packet, it picks a new random
route for processor j.

      Several issues related to this scheme are as follows.  First,
the threshold w must be set carefully for the scheme to be both
adaptive and efficient.  Second, the scheme, as described, does not
distinguish between destination congestion and intermediate
congestion that should be handled differently.  Third, the fact that
detour packets take some time to re...