Browse Prior Art Database

Adaptive Packet-Switched Routing in a Multiprocessor Network with Automatic Message Reassembly

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

Publishing Venue

IBM

Related People

Narasimha Reddy, AL: AUTHOR

Abstract

Disclosed is a technique for routing messages in a packet-switched multiprocessor network that guarantees ordered delivery of packets of a message while allowing adaptive routing of messages.

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

Adaptive Packet-Switched Routing in a Multiprocessor Network with Automatic Message Reassembly

      Disclosed is a technique for routing messages in a
packet-switched multiprocessor network that guarantees ordered
delivery of packets of a message while allowing adaptive routing of
messages.

      A technique is described for guaranteeing ordered delivery of
packets in a packet-switched multiprocessor network even when
adaptive routing is used in the network.  Every message is assumed to
be broken up into a number of fixed length packets.  If the message
is a single packet, there is no problem of reassembly.  Hence,
consider a message that is longer than one packet.  A message
consists of a start packet, an end packet and optionally some
intermediate packets.  The start packet signals the beginning of a
message and is used for establishing a path between the source and
the destination.  The end packet signals that the message transfer is
complete and is used for terminating the established path between the
source and the destination.  The path is established in a cut-through
fashion and hence does not pay the round-trip penalties associated
with circuit switching.

      Each node contains an "Established Path Table' (EPT) in its
switch.  This table is indexed by the source address of each packet.
Each entry in this table contains two fields, "direction", and
"valid".  The direction field indicates the direction along which a
message arriving from a particular source should be routed.  The
valid field in each entry indicates if that entry is valid or not.
Each node that sees the start packet of a message updates its entry
(indexed by the source address given in the start packet) and marks
it valid.  The direction field is determined by the routing function
implemented in the switch.  The packet is routed using a cut-through
mechanism through the switch to the neighboring node.  Hence, the
nodes along the path established so far between the source and the
destination will have their EPT entries marked correctly and further
along, the entries will be invalid as the start packet makes its way
to the destination.  When the start packet reaches the destination,
all the nodes along the path taken by the start packet between the
source and destination will have valid entries in the EPT.

      The packets following the...