US5541912A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Dynamic queue length thresholds in a shared memory ATM switch
Assignee: AT&T Inc
•
Filing: 1994-10-04
•
Granted: 1996-07-30
•
Expires: 2014-10-04
Abstract
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.
Inventors
- 👤 Abhijit K. Choudhury
- 👤 Ellen L. Hahne
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-30 23:37
CPC Classifications
H; H04; H04L; H04L12/00; H04L12/54; H04L12/56; H04L12/5601; H04L49/00; H04L49/10; H04L49/104; H04L49/105; H04L49/108; H04L2012/5638; H04L2012/5646; H04L2012/5651; H04L2012/5678; H04L2012/5681; H04L2012/5682
Claims Analysis
Total Claims: 44
Claim 1
Independent Claim
143 words
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.
Claim 2
Dependent Claim
143 words
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.
Claim 3
Dependent Claim
17 words
The packet communications system of claim 1 wherein the packet processing circuit processes packets of variable lengths.
Claim 4
Dependent Claim
17 words
The packet communications systems of claim 1 wherein the packet processing circuit processes packets of fixed lengths.
Claim 5
Dependent Claim
16 words
The packet communications system of claim 1 wherein the packets are asynchronous transfer mode (ATM) cells.
Claim 6
Dependent Claim
33 words
The packet communications system of claim 1 wherein the packet processing circuit is connected to a plurality of input ports; and the processor controls the packet processing circuit to perform packet multiplexing functions.
Claim 7
Dependent Claim
33 words
The packet communications system of claim 1 wherein the packet processing circuit is connected to a plurality of output ports; and the processor controls the packet processing circuit to perform packet demultiplexing functions.
Claim 8
Dependent Claim
38 words
The packet communications system of claim 1 wherein the packet processing circuit is connected to a plurality of input ports and a plurality of output ports; and the processor controls the packet processing circuit to perform switching functions.
Claim 9
Dependent Claim
26 words
The packet communications system of claim 1 wherein the queue of the incoming packet includes packets destined for the same output port as the incoming packet.
Claim 10
Dependent Claim
36 words
The packet communications system of claim 1 wherein the queue of the incoming packet includes packets destined for the same output port as the incoming packet and having the same priority class as the incoming packet.
Claim 11
Dependent Claim
58 words
The packet communications system of claim 1 wherein the queue of the incoming packet includes packets destined for the same output port as the incoming packet and having one of the same space priority class as in the incoming packet and a space priority class with a higher priority according to a predetermined order than the incoming packet.
Claim 12
Dependent Claim
36 words
The packet communications system of claim 1 wherein the queue of the incoming packet includes packets destined for the same output port as the incoming packet and having the same scheduling class as the incoming packet.
Claim 13
Dependent Claim
27 words
The packet communications system of claim 1 wherein the queue of the incoming packet includes packets that arrived over the same input port as the incoming packet.
Claim 14
Dependent Claim
40 words
The packet communications system of claim 1 wherein the processor uses the control parameter as a threshold, and the processor denies the incoming packet admission to its queue if the length of the queue equals or exceeds the control parameter.
Claim 15
Dependent Claim
25 words
The packet communications system of claim 13 wherein the processor includes a comparator for determining whether the queue length equals or exceeds the control parameter.
Claim 16
Dependent Claim
36 words
The packet communications system of claim 1 wherein the processor computes the control parameter to be at least one of the availability value, a multiple of the availability value, and a fraction of the availability value.
Claim 17
Dependent Claim
23 words
The packet communications system of claim 15 wherein the particular multiple and fraction used depends on the space priority of the incoming packet.
Claim 18
Dependent Claim
22 words
The packet communications system of claim 15 wherein the multiple and fraction is a positive and negative integer power of 2, respectively.
Claim 19
Dependent Claim
27 words
The packet communications system of claim 17 wherein the processor includes a shift register for determining the product of the power of 2 and the availability value.
Claim 20
Dependent Claim
30 words
The packet communications system of claim 1 wherein the processor computes the availability value as the difference between a measure of effective buffer capacity and a measure of memory occupancy.
Claim 21
Dependent Claim
23 words
The packet communications system of claim 19 wherein the measure of effective buffer capacity depends on the space priority of the incoming packet.
Claim 22
Dependent Claim
22 words
The packet communications system of claim 19 wherein the measure of memory occupancy depends on the space priority of the incoming packet.
Claim 23
Dependent Claim
31 words
The packet communications system of claim 21 wherein the measure of memory occupancy is the number of packets in the memory with the same space priority class as the incoming packet.
Claim 24
Dependent Claim
53 words
The packet communications system of claim 21 wherein the measure of memory occupancy is the number of packets in the memory with at least one of the same space priority class as the incoming packet and a space priority class with a higher priority according to a predetermined order than the incoming packet.
Claim 25
Independent Claim
108 words
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.
Claim 26
Independent Claim
108 words
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.
Claim 27
Dependent Claim
21 words
The method of claim 24 wherein the step of processing includes processing asynchronous transfer mode (ATM) cells as the incoming packets.
Claim 28
Dependent Claim
25 words
The method of claim 24 including the step of associating the queue of the incoming packet with the space priority class of the incoming packet.
Claim 29
Dependent Claim
24 words
The method of claim 24 including the step of associating the queue of the incoming packet with the scheduling class of the incoming packet.
Claim 30
Dependent Claim
30 words
The method of claim 24 including the step of updating the length count of any queue immediately whenever the step of processing admits or removes a packet from the queue.
Claim 31
Dependent Claim
27 words
The method of claim 24 wherein the step of maintaining an availability value includes the step of maintaining an amount of unused memory as the availability value.
Claim 32
Dependent Claim
35 words
The method of claim 24 including the step of setting the control parameter equal to at least one of the availability value, a fraction of the availability value, and a multiple of the availability value.
Claim 33
Dependent Claim
22 words
The method of claim 24 including the step of associating the control parameter with the space priority class of the incoming packet.
Claim 34
Dependent Claim
42 words
The method of claim 24 wherein the step of admitting uses the control parameter as a threshold on the queue length of the incoming packet, and the step of rejecting is performed if the queue length equals or exceeds the control parameter.
Claim 35
Dependent Claim
31 words
The method of claim 24 including the step of updating the availability value and the control parameter immediately whenever the step of processing admits or removes a packet from the memory.
Claim 36
Dependent Claim
90 words
The method of claim 24 wherein the steps of admitting and rejecting the incoming packet includes the steps of: receiving the incoming packet; determining the space priority class of the incoming packet; determining the scheduling class of the incoming packet; determining the queue that the packet would join; determining the length of the queue; determining the control parameter; making an admission decision whether or not to admit the incoming packet to its queue; and storing the incoming packet in its queue in the memory if the admission decision is favorable.
Claim 37
Dependent Claim
133 words
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.
Claim 38
Dependent Claim
133 words
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.
Claim 39
Independent Claim
155 words
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.
Claim 40
Independent Claim
155 words
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.
Claim 41
Independent Claim
65 words
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.
Claim 42
Independent Claim
65 words
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.
Claim 43
Independent Claim
98 words
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.
Claim 44
Independent Claim
98 words
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.
References Cited (Backward Citations)
US5193090A
Cited
US5072443A
Cited
US5014265A
Cited
US5163046A
Cited
US5272697A
Cited
US5136584A
Cited
US5115430A
Cited
US5280470A
Cited
US5128937A
Cited
US5278969A
Cited
US5233606A
Cited
US5285441A
Cited
US5278828A
Cited
US5289303A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1999-07-30 | 2000-01-29 | 2000-07-30 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2003-07-30 | 2004-01-29 | 2004-07-30 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2007-07-30 | 2008-01-29 | 2008-07-30 | $7700.00 | Window Closed / Lapsed |