Browse Prior Art Database

Packet Resequencing Algorithm with Priority Support

IP.com Disclosure Number: IPCOM000106646D
Original Publication Date: 1993-Dec-01
Included in the Prior Art Database: 2005-Mar-21
Document File: 4 page(s) / 113K

Publishing Venue

IBM

Related People

Batz, RM: AUTHOR [+6]

Abstract

An intelligent packet resequencing algorithm is disclosed for packets with different priorities in a router architecture that uses multiple processors to process different packet headers in parallel. Priority support is provided to accomodate multimedia traffic.

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

Packet Resequencing Algorithm with Priority Support

      An intelligent packet resequencing algorithm is disclosed for
packets with different priorities in a router architecture that uses
multiple processors to process different packet headers in parallel.
Priority support is provided to accomodate multimedia traffic.

      In an environment where multiple processors are used to process
different packet headers in parallel, the original packet arrival
sequence may not be maintained after header processing, due to the
variance in header processing delays.  Although most routing
protocols in heterogeneous protocol stacks, such as TCP/IP, DECnet,
APPLETALK, etc., allow the end stations to reorder packets, the
resequencing function at the end stations will require large buffers
and will adversely affect the end-to-end packet latency.

      The algorithm disclosed efficiently reorders the packets so
that they can leave the router in the same sequence as they arrived
in the described environment.  The algorithm also supports different
packet priorities in order to enable demanding applications such as
multimedia.  In multimedia applications, where strigent bounds exist
for the jitter incurred at intermediate nodes, i.e. bridges and
routers, assigning higher priority to multimedia traffic within such
nodes effectively reduces its delay or jitter.

      Fig. 1 shows the configuration of a router architecture
employing multiple processors to process packet headers in parallel.
The Medium Interface Units (MIUs) receive/transmit packets from/to
the attached network links.  The packets are stored in the Shared
Memory shown and processed by one of the multiple header processors
(P1 to Pn).  The processors synchronize through the shared memory to
maintain a consistent routing table.  The Interconnection Network is
used to interconnect the processors, the shared memory, and the MIUs.
This logical configuration can be implemented in various ways; e.g.,
the interconnection network can be a single bus, multiple busses, or
a crossbar switch, and the shared memory can be implemented in a
distributed or centralized fashion, etc.

      Resequencing ensures that packets of any given priority are
transmitted to the destination MIU in the same order as they are
received from the source MIU.  Incoming packets are appended to an
input queue and outgoing packets are dequeued from output queues.
The disclosed algorithm achieves resequencing by enqueueing packets
of a given priority in an output queue in the same order as they are
received at the input queue.  The algorithm operates for an arbitrary
number o...