Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

Wavefront Routing

IP.com Disclosure Number: IPCOM000105960D
Original Publication Date: 1993-Sep-01
Included in the Prior Art Database: 2005-Mar-20
Document File: 2 page(s) / 94K

Publishing Venue

IBM

Related People

Freitas, R: AUTHOR [+3]

Abstract

Disclosed is a technique for routing messages over an interconnection network in a multiprocessor system. The proposed technique implements a number of routing techniques such as flooding, fixed-path routing and multi-path routing through a single technique. The proposed technique is independent of the topology of the network.

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

Wavefront Routing

      Disclosed is a technique for routing messages over an
interconnection network in a multiprocessor system.  The proposed
technique implements a number of routing techniques such as flooding,
fixed-path routing and multi-path routing through a single technique.
The proposed technique is independent of the topology of the network.

      The proposed method combines flooding and variable header
strategies into one scheme.  The proposed scheme has the advantages
of both these schemes.

      In wavefront routing, a unit of the routing header specifies
how a switch should be set up for each hop in the network.  The size
of the unit depends on the size of the network switch and any special
routing functions that may need to be provided.  Each node along a
path form the source to the destination uses up one unit of routing
header in setting up its switch.  Specifically, each unit in routing
header contains information about which output ports at that switch
should be used in sending the message to the destination.  Along with
this routing header, each message contains the intended destination
of this message.  Each node, along a path from the source to the
destination, checks to see if it is the intended destination.  If it
is, it receives the message and does not forward the message any
further.  If it is not the intended destination, it consumes the next
unit of routing header to determine the directions along which it
should transmit the message.  Wavefront routing header to determine
the directions along which it should transmit the message.  Wavefront
routing doesn't require that all the specified output ports be
available for the message to be forwarded at a node.  A node forwards
the message along all the available output ports that are specified
in the routing header.  Unlike the traditional variable header
strategies, wavefront routing allows multiple output ports to be
specified in the routing header.  If the routing header is completely
consumed and the message does not arrive at the destination, the
message is dropped and the path setup to reach the current node is
torn down.  The path is torn down backwards as far as all the output
paths for this message at a switch have been unsuccessful.  This
method of specifying the termination condition is a powerful feature
of wavefront routing.  It implies that if the diameter of the network
is known, without knowing the relative location of a destination, a
mes...