US5233606A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Arrangement for controlling shared-buffer-memory overflow in a multi-priority environment
Assignee: Nokia Bell Labs
•
Filing: 1991-08-02
•
Granted: 1993-08-03
•
Expires: 2011-08-02
Abstract
Abstract A shared-buffer-memory-based ATM switching module (1) used with ATM cells having a multiplicity of priorities has a plurality of queues for each output port (O-N), one for each cell priority, and handles buffer overflow in a manner fair to all output ports. It initially allows output-port queues to completely consume the buffer memory (12). Thereafter, when an additional incoming cell (on 7) is received for which there is no room in the buffer memory, the lengths of all of the queues of each output port are individually summed and compared to determine which port has the greatest number of buffered cells. A buffered ATM cell is discarded from the lowest-priority non-empty queue of that port. The incoming cell is then stored in the memory space vacated by the discarded cell. <IMAGE>
Inventors
- 👤 Mark A. Pashan
- 👤 Ronald A. Spanke
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-27 09:57
CPC Classifications
H; H03; H03K; H03K17/00; H04; H04Q; H04Q11/00; H04Q11/04; H04Q11/0428; H04Q11/0478; H04L; H04L12/00; H04L12/54; H04L12/56; H04L12/5601; H04L49/00; H04L49/10; H04L49/104; H04L49/105; H04L49/108; H04L49/15; H04L49/1553; H04L49/25; H04L49/253; H04L49/255; H04L2012/5638; H04L2012/5646; H04L2012/5651; H04L2012/5678; H04L2012/5681
Claims Analysis
Total Claims: 12
Claim 1
Independent Claim
161 words
A shared-buffer-memory-based packet-switching arrangement comprising: a plurality of output ports; a buffer memory defining a plurality of queues for each output port, each queue of an individual output port for storing packets destined for the individual output port and having a priority different from priorities of packets stored by other queues of the individual output port; means responsive to receipt of a packet having a priority and destined for an individual output port, for storing the received packet in the queue for storing packets of that priority for the individual output port; means for transmitting packets stored in the queues on corresponding output ports; and means responsive to receipt of a packet while storage space of the buffer memory is fully consumed by the queues, for deleting a stored packet from a non-empty queue storing lowest-priority packets stored for an output port that has the most packets stored in its queues, to vacate buffer-memory storage space for storing the received packet.
Claim 2
Dependent Claim
161 words
A shared-buffer-memory-based packet-switching arrangement comprising: a plurality of output ports; a buffer memory defining a plurality of queues for each output port, each queue of an individual output port for storing packets destined for the individual output port and having a priority different from priorities of packets stored by other queues of the individual output port; means responsive to receipt of a packet having a priority and destined for an individual output port, for storing the received packet in the queue for storing packets of that priority for the individual output port; means for transmitting packets stored in the queues on corresponding output ports; and means responsive to receipt of a packet while storage space of the buffer memory is fully consumed by the queues, for deleting a stored packet from a non-empty queue storing lowest-priority packets stored for an output port that has the most packets stored in its queues, to vacate buffer-memory storage space for storing the received packet.
Claim 3
Dependent Claim
41 words
The arrangement of claim 1 wherein the deleting means comprise: means for identifying an output port that has the most packets stored in its queues; and means for identifying a non-empty queue storing lowest-priority packets stored for the identified output port.
Claim 4
Dependent Claim
99 words
The arrangement of claim 1 wherein the deleting means comprise: a plurality of counters, a different one corresponding to each queue, for generating a count indicating a number of packets stored on the corresponding queue; means for summing the counts of the counters corresponding to all queues of individual output ports; means for comparing the sums to identify the output port having the most stored packets; and means for examining the counts of the counters corresponding to the queues of the identified output port to identify a non-empty queue storing the lowest-priority packets stored for the identified output port.
Claim 5
Dependent Claim
169 words
A control arrangement for a shared-buffer-memory-based packet-switching module having a plurality of output ports and a buffer memory defining a plurality of queues for each output port, each queue of an individual output port for storing packets destined for the individual output port and having a priority different from priorities of packets stored by other queues of the individual output port, the arrangement comprising: means responsive to receipt of a packet having a priority and destined for an individual output port, for storing the received packet in the queue for storing packets of that priority for the individual output port; means for transmitting packets stored in the queues on corresponding output ports; and means responsive to receipt of a packet while storage space of the buffer memory is fully consumed by the queues, for deleting a stored packet from a non-empty queue storing lowest-priority packets stored for an output port that has the most packets stored in its queues, to vacate buffer-memory storage space for storing the received packet.
Claim 6
Dependent Claim
169 words
A control arrangement for a shared-buffer-memory-based packet-switching module having a plurality of output ports and a buffer memory defining a plurality of queues for each output port, each queue of an individual output port for storing packets destined for the individual output port and having a priority different from priorities of packets stored by other queues of the individual output port, the arrangement comprising: means responsive to receipt of a packet having a priority and destined for an individual output port, for storing the received packet in the queue for storing packets of that priority for the individual output port; means for transmitting packets stored in the queues on corresponding output ports; and means responsive to receipt of a packet while storage space of the buffer memory is fully consumed by the queues, for deleting a stored packet from a non-empty queue storing lowest-priority packets stored for an output port that has the most packets stored in its queues, to vacate buffer-memory storage space for storing the received packet.
Claim 7
Dependent Claim
41 words
The arrangement of claim 4 wherein the deleting means comprise: means for identifying an output port that has the most packets stored in its queues; and means for identifying a non-empty queue storing lowest-priority packets stored for the identified output port.
Claim 8
Dependent Claim
99 words
The arrangement of claim 4 wherein the deleting means comprise: a plurality of counters, a different one corresponding to each queue, for generating a count indicating a number of packets stored on the corresponding queue; means for summing the counts of the counters corresponding to all queues of individual output ports; means for comparing the sums to identify the output port having the most stored packets; and means for examining the counts of the counters corresponding to the queues of the identified output port to identify a non-empty queue storing the lowest-priority packets stored for the identified output port.
Claim 9
Independent Claim
157 words
A method of controlling overflow of a shared-buffer-memory-based packet-switching module having a plurality of output ports and a buffer memory defining a plurality of queues for each output port, each queue of an individual output port for storing packets destined for the individual output port and having a priority different from priorities of packets stored by other queues of the individual output port, the method comprising the steps of: in response to receipt of a packet having a priority and destined for an individual output port while storage space of the buffer memory is fully consumed by the queues, deleting a stored packet from a non-empty queue storing lowest-priority packets stored for an output port that has the most packets stored in its queues; and in response to the deletion, storing the received packet in the queue for storing packets of that priority for the individual output port, in buffer-memory storage space vacated by the deleted packet.
Claim 10
Independent Claim
157 words
A method of controlling overflow of a shared-buffer-memory-based packet-switching module having a plurality of output ports and a buffer memory defining a plurality of queues for each output port, each queue of an individual output port for storing packets destined for the individual output port and having a priority different from priorities of packets stored by other queues of the individual output port, the method comprising the steps of: in response to receipt of a packet having a priority and destined for an individual output port while storage space of the buffer memory is fully consumed by the queues, deleting a stored packet from a non-empty queue storing lowest-priority packets stored for an output port that has the most packets stored in its queues; and in response to the deletion, storing the received packet in the queue for storing packets of that priority for the individual output port, in buffer-memory storage space vacated by the deleted packet.
Claim 11
Dependent Claim
41 words
The method of claim 7 wherein the step of deleting comprises the steps of: identifying an output port that has the most packets stored in its queues; and identifying a non-empty queue storing lowest-priority packets stored for the identified output port.
Claim 12
Dependent Claim
103 words
The method of claim 7 for a switching module further having a plurality of counters, a different one corresponding to each queue, for generating a count indicating a number of packets stored on the corresponding queue, wherein the step of deleting comprises the steps of: summing the counts of the counters corresponding to all queues of individual output ports; comparing the sums to identify the output port having the most stored packets; and examining the counts of the counters corresponding to the queues of the identified output port to identify a non-empty queue storing the lowest-priority packets stored for the identified output port.
References Cited (Backward Citations)
US4531204A
Cited
US4093823A
Cited
US4314367A
Cited
US4499576A
Cited
US4603416A
Cited
US4849968A
Cited
US4757529A
Cited
US5016248A
Cited
US5083269A
Cited
US5062106A
Cited
US4953157A
Cited
WO1991004624A1
Cited
US5048013A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1996-08-02 | 1997-02-01 | 1997-08-03 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2000-08-02 | 2001-02-01 | 2001-08-03 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2004-08-02 | 2005-02-01 | 2005-08-03 | $7700.00 | Window Closed / Lapsed |