Browse Prior Art Database

Ram-Based Packet Switch With Overflow Buffers

IP.com Disclosure Number: IPCOM000099452D
Original Publication Date: 1990-Jan-01
Included in the Prior Art Database: 2005-Mar-14
Document File: 3 page(s) / 141K

Publishing Venue

IBM

Related People

Chang, PC: AUTHOR [+2]

Abstract

This disclosure presents an output queuing packet switch which contains a RAM buffer at each cross point of a crossbar switch. An overflow buffer associated with each input link reduces the packet loss rate while maintaining the packet sequence on outgoing links.

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

Ram-Based Packet Switch With Overflow Buffers

       This disclosure presents an output queuing packet switch
which contains a RAM buffer at each cross point of a crossbar switch.
 An overflow buffer associated with each input link reduces the
packet loss rate while maintaining the packet sequence on outgoing
links.

      Memory switches are widely used in packet switching. One of the
reasons is that a memory switch provides both the switching and
buffering functions.  Traditionally, the design of memory switches is
based on a single memory mapping.  Namely, the whole memory is used
as a single unit and only one read or write operation can be
performed at a time.  Multiple input/output links are
time-division-multiplexed to a single input/output port of the
memory.  The switching capacity is limited by the memory access speed
which results in a severe bottleneck for high-speed communications.

      A bus matrix switch has been developed in which a first-in,
first-out (FIFO) is placed at each cross point of a crossbar switch
[1].  This architecture overcomes the memory bandwidth limitation
described above because each FIFO operates independently.  The packet
loss rate of such a switch could be improved by using an overflow
buffering scheme in which an overflow buffer is provided for each
input link.  For a given input, when the FIFO connected to the
designated output is full, the incoming packet is stored in the
overflow buffer.  The output links read out packets from either the
normal buffers or the overflow buffers.  As there is only one
overflow buffer per input port, this buffer receives packets headed
to different output ports. The order in which these packets must be
read out only depends on the availability of their output port and is
typically different from the order in which they have been received.
This requires that the overflow buffers has a random access
capability.  FIFOs such as those used in (1) cannot satisfy this
requirement and overflow buffers can therefore not be easily
implemented in such a system.  The switch described in this
disclosure overcomes this problem.

      This disclosure presents a packet switch which uses RAM buffers
to replace the FIFOs used in (1).  An additional overflow buffer
shared by all output links is also provided for each input link. Each
incoming packet is stored in the buffer located at the cross point
(intersection of its input row and its destination column) of the
input and designated output links if the buffer is not full.
Otherwise, this packet is stored in the overflow buffer.  Each output
link has the capability to read packets from any buffer in its column
as well as from any overflow buffer.  Overflow buffers are also
implemented using RAMs which provide the required random access
capability.

      The block diagram of the M-by-N packet switch is shown in the
figure.  It consists of several parts: memory switch fabric, write-
pointer control, r...