Hybrid scheme for queuing in a shared memory ATM switch buffer

Details Hybrid scheme for queuing in a shared memory ATM switch buffer Hybrid scheme for queuing in a shared memory ATM switch buffer

1998-05-15

2001-11-20

Patel, Ajit (Department: 2662)

Multiplex communications

Pathfinding or routing

Switching a message which includes an address header

C370S412000

Reexamination Certificate

active

06320861

ABSTRACT:

FIELD OF THE INVENTION
The present invention is related to sending unicast and multicast ATM cells over an ATM network. More specifically, the present invention is related to sending unicast and multicast cells over an ATM network using distinct techniques for unicast cells and for multicast cells.
BACKGROUND OF THE INVENTION
As ATM cells traverse an ATM switch from an input port to an output port, they are stored temporarily in buffers at various stages of the switch. There are several types of buffers. One type of buffer is a shared memory buffer. In a shared memory buffer, cells are assigned to queues which correspond to output ports of the stage of the switch, and these queues share the same physical memory. One of the challenges in designing a shared memory buffer is buffer and queue management.
Buffer management consists of allocating space in the shared memory for the queues as they grow and reclaiming space in the memory as the queues shrink. Queue management consists of tracking the cells that are in the queue by tracking the addresses of those cells within the shared memory in lists. As cells are added to the queue, addresses are added to the list and as cells are read from the queue, they are removed. Buffer and queue management are closely related.
Current shared memory buffer and queue management techniques vary in the way they maintain queues in physical memory and in the way they handle unicast and multicast cells. These two types of cells differ in that a unicast cell is destined for only one output port of the buffer and a multicast cell can be destined for several output ports. One management strategy consists of dividing the shared memory into small blocks and organizing the queues as FIFOs (first-in first-out) containing linked lists of memory blocks. Each cell is stored in only one queue and the queues are tracked by means of block pointers. Typically, there is one unicast queue for each output port and one multicast queue which serves all of the output ports. This scheme is memory efficient but presents problems for multicast. Since a multicast cell is stored in a single multicast queue, a sophisticated scheduling algorithm is needed in order to choose between the multicast queue and several unicast queues as cells are read from the buffer and sent to the output ports of the switch stage since the cells in the multicast queue go to several output ports. Another problem with this strategy is head-of-the-line blocking within the multicast queue.
A second management strategy consists of organizing the queues as FIFOs (first-in first-out) that hold shared memory addresses of cells. It should be noted that adjacent cells in the FIFO can be stored in memory addresses that are not necessarily adjacent. One FIFO exists for each output port, and both unicast and multicast cells are stored in it. A copy of the multicast cell is placed in the FIFO of each destination in the multicast. This scheme has the advantage of requiring a simpler scheduling algorithm and not suffering from head-of-the-line blocking but requires very large memories for the address FIFOs.
The present invention describes a hybrid buffer and queue management scheme in which queues consisting of unicast ATM cells are organized as linked-lists of memory blocks and queues consisting of multicast ATM cells are organized as address lists. This scheme has the advantage of being very memory efficient for unicast queue management, uses a shared memory for both unicast and multicast cells, and requires a simple scheduling algorithm for reading cells from the buffer.
SUMMARY OF THE INVENTION
The present invention pertains to a switch for an ATM communication system. The ATM communication system has an ATM network on which ATM cells travel, source nodes connected to the ATM network which produce ATM cells and send them onto the ATM network, and destination nodes connected to the ATM network which receive ATM cells from the ATM network. The switch comprises input ports through which cells are received from the ATM network. The switch comprises output ports through which cells are transmitted to the ATM network. The switch comprises a switching mechanism connected to the input ports and output ports which transfer cells from the input ports to output ports. The switching mechanism has a unicast sending mechanism for sending unicast cells to an output port and has a multicast sending mechanism for sending multicast cells to a desired output port. The multicast sending mechanism is separate and different from the unicast sending mechanism.
The present invention pertains to a method for sending ATM cells over an ATM network. The method comprises the steps of receiving a first ATM unicast cell at a switch connected to the ATM network from the ATM network. Then there is the step of routing the first unicast cell out a first output port of the switch to the ATM network with a unicast sending mechanism. Next there is the step of receiving an ATM multicast cell at the switch from the ATM network. Then there is the step of routing the multicast cell out the first output port to the ATM network with a multicast sending mechanism. The multicast sending mechanism is separate and different from the unicast sending mechanism.


REFERENCES:
patent: 5392280 (1995-02-01), Zheng
patent: 5577035 (1996-11-01), Hayter et al.
patent: 5608726 (1997-03-01), Virgile
patent: 5689506 (1997-11-01), Chiussi et al.
patent: 5784003 (1998-07-01), Dahlgren
patent: 5898687 (1999-04-01), Harriman et al.
patent: 5982775 (1999-11-01), Brunner et al.
patent: 6101187 (2000-08-01), Cukier et al.

Affiliated with

Also associated with

Rating

Hybrid scheme for queuing in a shared memory ATM switch buffer does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Hybrid scheme for queuing in a shared memory ATM switch buffer, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Hybrid scheme for queuing in a shared memory ATM switch buffer will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2574866