Dynamic queue length thresholds in a shared memory ATM switch
First Claim
1. A packet communications system comprising:
- a packet processing circuit for processing packets as incoming and outgoing packets, for receiving an incoming packet on an input port and for transmitting an outgoing packet on an output port, with the packets belonging to at least one space priority class and to at least one scheduling class;
a memory for storing the processed packets in queues; and
a processor using control logic and configured for controlling the packet processing circuit to process the packets and for allocating memory among the queues by computing an availability value based on the occupancy of the memory, by computing a control parameter as a function of the availability value, by computing the lengths of the queues, and by controlling admittance of each incoming packet to its queue based on the length of the queue being less than the control parameter.
5 Assignments
0 Petitions
Accused Products
Abstract
A dynamic threshold system and method is disclosed for allocating memory among different output queues in a shared-memory ATM switch. The maximum permissible length for any individual queue at any instant of time is a function of the unused buffering in the switch. The dynamic threshold system and method deliberately reserves a small amount of buffer space, not allocating it to any currently active output queue, but attempts to equally share the remaining buffer space among the currently active output queues. The dynamic threshold system and method improve fairness and switch efficiency by guaranteeing access to the buffer space for all output queues, and by preventing any single output queue from monopolizing the memory at the expense of the others. The dynamic threshold system and method adapt to uncertain or changing load conditions. The packet losses that occur with dynamic thresholds tend to be clustered at a few offending queues, which is desirable in ATM systems, since it results in fewer messages being disturbed at higher protocol layers and, hence, fewer message retransmissions. The dynamic threshold system and method are also extendable to handle traffic with multiple space priorities.
-
Citations
38 Claims
-
1. A packet communications system comprising:
-
a packet processing circuit for processing packets as incoming and outgoing packets, for receiving an incoming packet on an input port and for transmitting an outgoing packet on an output port, with the packets belonging to at least one space priority class and to at least one scheduling class; a memory for storing the processed packets in queues; and a processor using control logic and configured for controlling the packet processing circuit to process the packets and for allocating memory among the queues by computing an availability value based on the occupancy of the memory, by computing a control parameter as a function of the availability value, by computing the lengths of the queues, and by controlling admittance of each incoming packet to its queue based on the length of the queue being less than the control parameter. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23)
-
-
24. A method for allocating memory space among queues in a packet communications system, the queues including packets of at least one space priority class and of at least one scheduling class, the method comprising the steps of:
-
maintaining counts of the lengths of the queues; maintaining an availability value associated with the occupancy of the memory, and a control parameter that is a function of the availability value; processing an incoming packet including at least one of the steps of admitting the incoming packet to its queue and rejecting the incoming packet according to the condition of the length of the queue being less than the control parameter. - View Dependent Claims (25, 26, 27, 28, 29, 30, 31, 32, 33, 34)
-
-
35. A packet communications module comprising:
-
a packet processing circuit for processing packets as incoming and outgoing packets to receive an incoming packet on an input port and to transmit an outgoing packet on an output port; a memory for storing the processed packets in an output port queue associated with the output port; a processor using stored programs and configured for controlling the packet processing circuit to process the packets, for computing availability values based on the total occupancy of the memory, for computing control parameters as functions of the availability values, for computing an output port queue length, and for controlling admittance of packets to the output port queue based on the output port queue lengths being less than corresponding control parameters to allocate memory space in the memory for admitted packets.
-
-
36. A system for allocating memory space in an asynchronous transfer mode (ATM) switch for switching ATM packets, the system comprising:
-
the ATM switch for processing ATM packets as incoming and outgoing ATM packets to receive incoming ATM packets on a plurality of input ports and to transmit outgoing ATM packets on a plurality of output ports; a memory for storing the processed ATM packets in an output port queue; a processor having associated memory and using stored programs and configured for controlling the ATM switch to process the ATM packets, for computing availability values based on the total occupancy of the memory, for computing control parameters as functions of the availability values, for computing an output port queue length, and for controlling admittance of ATM packets to the output port queue based on the output port queue lengths being less than corresponding control parameters to allocate memory space in the memory for admitted ATM packets.
-
-
37. A method for allocating memory space in a shared memory of an asynchronous transfer mode (ATM) switch, the method comprising the steps of:
-
receiving an packet; determining a control parameter as a function of an occupancy value of the shared memory; and storing the packet in a queue in the memory based on a queue length of the queue being less than the control parameter.
-
-
38. A method for allocating memory space among a plurality of output queues in a shared memory of an asynchronous transfer mode (ATM) switch module, the method comprising the steps of:
-
determining a first count from an occupancy of the shared memory; receiving an ATM packet from an input port; determining a priority setting of the received packet; determining a first queue length of the first queue corresponding to the priority setting; storing the ATM packet in the shared memory responsive to the condition of the first queue length being less than a predetermined multiple of the first count.
-
Specification