Browse Prior Art Database

Randomized Routing Schemes on Multistage Interconnection Networks

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

Publishing Venue

IBM

Related People

Bruck, J: AUTHOR [+8]

Abstract

Disclosed are three schemes for using randomization in routing algorithms on a multistage interconnection network.

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

Randomized Routing Schemes on Multistage Interconnection Networks

       Disclosed are three schemes for using randomization in
routing algorithms on a multistage interconnection network.

      We consider a 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.  Packets are routed
using virtual out-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.

      The three schemes use routing tables, which means that each
processor i contains an array of N entries, where entry j specifies
information for routing from processor i to processor j.
Scheme 1: Static Random Routes

      In this scheme, each processor has one fixed routing table.  A
processor's routing table consists of N entries, with the j entry
containing the header for routing to processor j.  Several free bits
in each entry are set randomly and independently when the routing
table is initialized.  These free bits select one out of multiple
possible routes between processors i and j.

      Advantages of this scheme include: simple programmability,
little overhead, and its being non-overtaking.  On the other hand,
the single randomization of this scheme increases the chance that
communication will perform poorly throughout specific applications.
Furthermore, this scheme sends successive packets from a single
source to a single destination on the same route, which may compound
congestion that already occurred in the network.  We use the term
temporal correlation to refer to the tendency of a routing scheme to
use the same route for successive packets between a
source-destination pair.
Scheme 2: Dynamic Random Routes

      This scheme uses one routing table per processor, which is
initialized as in the...