Browse Prior Art Database

First-In First-Out Queuing in Single Stage Switching Networks Built from Multiple Identical Packet Switching Modules

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

Publishing Venue

IBM

Related People

Heusler, L: AUTHOR

Abstract

In single stage switching built from multiple identical switching modules a logical output queue actually consists of several paralleled queues located in different modules. In the following, a scheme to combine these queues is prepared such that they behave as one queue with First-In First-Out (FIFO) characteristic.

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

First-In First-Out Queuing in Single Stage Switching Networks Built from Multiple Identical Packet Switching Modules

      In single stage switching built from multiple identical
switching modules a logical output queue actually consists of several
paralleled queues located in different modules.  In the following, a
scheme to combine these queues is prepared such that they behave as
one queue with First-In First-Out (FIFO) characteristic.

      Depending on the application a wide range of switch
interconnection sizes may be required and therefore the capability
for modular growth is an important feature of any switch module
design.  The architecture of the considered NxN packet switching
module consists of a non-blocking self routing network combined with
output queuing.  Fig. 1 shows a possible configuration for a 2Nx2N
based on four NxN switching modules.

      Paralleled inputs are distinguished by using an address filter
which allows only packets with a valid chip address to be routed to
one of the module outputs and at paralleled outputs control logic
ensures that only one port is active at a time.  Similar, any SxS
single stage switch fabric can be built from (S/N) sup 2 switching
modules.  The method to arrange modules in such a structure is not
subject of this paper.

      The above networks behave like a single stage network because
each output can be reached from all inputs by passing through a
single module.  However, it should be noted that the logical queue
belonging to a switch output actually consists of several paralleled
queues located in separate modules and in the following a description
of how to link these separate physical queues such that they exhibit
a single queue FIFO characteristic.

      The problem we try to solve can best be described by focusing
on the enable sequence of two separate physical queues serving one
output of a two times single stage port expanded switch fabric.  A
straight forward activation scheme of the dotted ports would search
all queues in a round robin fashion and based on their empty status
grant a single packet transmission before proceeding to the next
queue.  Albeit such a scheme typically results in a good link
utilization it cannot guarantee "fair" link access for all traffic
patterns.  This is shown in Fig. 2 where contending packets from
different origins a, b, and c arrive in a fixed repetitive sequence.
Depending on whether they are routed through a single or two separate
queues a different output pattern results and by comparing the
average queuing delay it can be seen that in the second case packets
from a are favored at the expense of packets f...