US5757771A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Queue management to serve variable and constant bit rate traffic at multiple quality of service levels in a ATM switch
Assignee: Yurie Systems Inc
•
Filing: 1995-11-14
•
Granted: 1998-05-26
•
Expires: 2015-11-14
Abstract
Abstract A buffer management system and method for use in an ATM switch that allows for data processing of variable bit rate (VBR) and constant bit rate (CBR) traffic using a common buffer memory. The buffer memory is broken down into data sub-queues, each of which is assigned an output and purge priority. ATM cells are allocated to a particular data sub-queue by matching the desired quality-of-service of the cells with the output and purge characteristics of each sub-queue. The system and method dynamically sizes the data sub-queues so as to be equal to the number of ATM cells in the data sub-queue. In addition, age and size ratio thresholds may be assigned to each data sub-queue to better distribute available bandwidth among the sub-queues, and to ensure that cells are not excessively delayed.
Inventors
- 👤 Kwok-Leung Li
- 👤 Yung-Lung Ho
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-04 12:50
CPC Classifications
H; H04; H04L; H04L49/00; H04L49/30; H04L49/3081; H04Q; H04Q11/00; H04Q11/04; H04Q11/0428; H04Q11/0478; H04L12/00; H04L12/54; H04L12/56; H04L12/5601; H04L2012/5638; H04L2012/5646; H04L2012/5651; H04L2012/5678; H04L2012/5679; H04L2012/5681
Claims Analysis
Total Claims: 36
Claim 1
Independent Claim
219 words
A method of processing a plurality of digital data packets that are received from at least one data input port, temporarily stored in a buffer memory, and intended for transmission through at least one data output port comprising the steps of: receiving said digital data packets from said at least one data input port; dividing said buffer memory for storing said digital data packets into a plurality of data sub-queues, each of said data sub-queues having a length that is dynamically determined in response to the receipt of said digital data packets by said data sub-queues and each of said data sub-queues having an assigned output ranking and purge ranking; assigning an accumulation ratio for each of said plurality of data sub-queues; calculating an accumulation ratio threshold for each of said plurality of data sub-queues equal to the product of said accumulation ratio for each of said plurality of data sub-queues and the total number of digital data packets stored in said buffer memory; storing each of said digital data packets in a selected one of said data sub-queues; and transmitting each of said digital data packets from said plurality of data sub-queues to said at least one output port in accordance with said accumulation ratio threshold and said output ranking of each of said plurality of data sub-queues.
Claim 2
Independent Claim
219 words
A method of processing a plurality of digital data packets that are received from at least one data input port, temporarily stored in a buffer memory, and intended for transmission through at least one data output port comprising the steps of: receiving said digital data packets from said at least one data input port; dividing said buffer memory for storing said digital data packets into a plurality of data sub-queues, each of said data sub-queues having a length that is dynamically determined in response to the receipt of said digital data packets by said data sub-queues and each of said data sub-queues having an assigned output ranking and purge ranking; assigning an accumulation ratio for each of said plurality of data sub-queues; calculating an accumulation ratio threshold for each of said plurality of data sub-queues equal to the product of said accumulation ratio for each of said plurality of data sub-queues and the total number of digital data packets stored in said buffer memory; storing each of said digital data packets in a selected one of said data sub-queues; and transmitting each of said digital data packets from said plurality of data sub-queues to said at least one output port in accordance with said accumulation ratio threshold and said output ranking of each of said plurality of data sub-queues.
Claim 3
Dependent Claim
16 words
The method of claim 1 wherein each of said digital data packets is an ATM cell.
Claim 4
Dependent Claim
32 words
The method of claim 1 wherein at least one of said plurality of data sub-queues is given a higher output ranking than at least one other of said plurality of data sub-queues.
Claim 5
Dependent Claim
29 words
The method of claim 3 wherein each of said plurality of data sub-queues has an output ranking unique from said output ranking of each of said other data sub-queues.
Claim 6
Dependent Claim
33 words
The method of claim 4 further comprising the step of purging said digital data packets from said plurality of data sub-queues in accordance with said purge ranking of each of said data sub-queues.
Claim 7
Dependent Claim
32 words
The method of claim 5 wherein at least one of said plurality of data sub-queues is given a higher purge ranking than at least one other of said plurality of data sub-queues.
Claim 8
Dependent Claim
29 words
The method of claim 6 wherein each of said plurality of data sub-queues has a purge ranking unique from said purge ranking of each of said other data sub-queues.
Claim 9
Dependent Claim
58 words
The method of claim 3 further comprising the step of: shortening the length of said data sub-queue from which said digital data packet was purged after said purging, whereby said shortening allows said data sub-queue from which said digital data packet was transmitted to equal the total length of said digital data packets remaining in said data sub-queue.
Claim 10
Dependent Claim
18 words
The method of claim 1 wherein said at least one data input port receives constant bit rate traffic.
Claim 11
Dependent Claim
18 words
The method of claim 1 wherein said at least one data input ports receives variable bit rate traffic.
Claim 12
Dependent Claim
26 words
The method of claim 1 wherein said at least one data input ports receives a combination of constant bit rate traffic and variable bit rate traffic.
Claim 13
Dependent Claim
62 words
The method of claim 1 further comprising the step of: shortening said length of each of said plurality of data sub-queue from which said digital data packet was transmitted after said transmitting, whereby said shortening allows said data sub-queue from which said digital data packet was transmitted to equal the total length of said digital data packets remaining in said data sub-queue.
Claim 14
Independent Claim
246 words
A method of processing a plurality of digital data packets that are received from at least one data input port, temporarily stored in a buffer memory, and intended for transmission through at least one data output port comprising the steps of: receiving said digital data packets from said at least one data input port; dividing said buffer memory for storing said digital data packets into a plurality of data sub-queues, each of said data sub-queues having a length that is dynamically determined in response to the receipt of said digital data packets by said data sub-queues and each of said data sub-queues having an assigned output ranking and purge ranking, an assigned delay threshold representing a minimum bandwidth for each of said plurality of data sub-queues, and a dispatch-essential flag and an age counter; storing each of said digital data packets in a selected one of said data sub-queues; incrementing said age counter for each of said plurality of data sub-queues when a digital data packet is dispatched from another of said plurality of data sub-queues; setting said dispatch-essential flag for each of said plurality of data sub-queues when said age counter for said each of said plurality of data sub-queues exceeds said delay threshold for said each of said plurality of data sub-queues; and outputting said digital data packets from each of said plurality of data sub-queues in accordance with said dispatch-essential flag and said output ranking of each of said plurality of data sub-queues.
Claim 15
Independent Claim
246 words
A method of processing a plurality of digital data packets that are received from at least one data input port, temporarily stored in a buffer memory, and intended for transmission through at least one data output port comprising the steps of: receiving said digital data packets from said at least one data input port; dividing said buffer memory for storing said digital data packets into a plurality of data sub-queues, each of said data sub-queues having a length that is dynamically determined in response to the receipt of said digital data packets by said data sub-queues and each of said data sub-queues having an assigned output ranking and purge ranking, an assigned delay threshold representing a minimum bandwidth for each of said plurality of data sub-queues, and a dispatch-essential flag and an age counter; storing each of said digital data packets in a selected one of said data sub-queues; incrementing said age counter for each of said plurality of data sub-queues when a digital data packet is dispatched from another of said plurality of data sub-queues; setting said dispatch-essential flag for each of said plurality of data sub-queues when said age counter for said each of said plurality of data sub-queues exceeds said delay threshold for said each of said plurality of data sub-queues; and outputting said digital data packets from each of said plurality of data sub-queues in accordance with said dispatch-essential flag and said output ranking of each of said plurality of data sub-queues.
Claim 16
Dependent Claim
33 words
The method of claim 13 wherein each of said plurality of data sub-queues has an dispatch counter representing a minimum number of digital data packets to be transmitted before clearing said dispatch-essential flag.
Claim 17
Dependent Claim
45 words
The method of claim 14 further comprising the step of decrementing said corresponding dispatch counter for each of said plurality of data sub-queues when a digital data packet is transmitted from each of said plurality of data sub-queues to said at least one output port.
Claim 18
Dependent Claim
38 words
The method of claim 15 further comprising the step of clearing said dispatch-essential flag for each of said plurality of data sub-queues when said dispatch counter indicates that said minimum number of digital data packets have been transmitted.
Claim 19
Dependent Claim
32 words
The method of claim 13 further comprising the step of clearing said dispatch-essential flag for each of said plurality of data sub-queues when each of said plurality of data sub-queues is empty.
Claim 20
Independent Claim
232 words
A method of processing a plurality of digital data packets that are received from at least one data input port, temporarily stored in a buffer memory, and intended for transmission through at least one data output port comprising the steps of: receiving said digital data packets form said at least one data input port; dividing said buffer memory for storing said digital data packets into a plurality of data sub-queues, each of said data sub-queues having a length that is dynamically determined in response to the receipt of said digital data packets by said data sub-queues and each of said data sub-queues having an assigned output ranking and an assigned delay threshold, and a dispatch-essential flag and an age counter; storing each of said digital data packets in a selected one of said data sub-queues; incrementing said age counter for each of said plurality of data sub-queues when a digital data packet is dispatched from another of said plurality of data sub-queues; setting said dispatch-essential flag for each of said plurality of data sub-queues when said age counter for said each of said plurality of data sub-queues exceeds said delay threshold for said each of said plurality of data sub-queues; and outputting said digital data packets from each of said plurality of data sub-queues in accordance with said delay threshold and said output ranking of each of said plurality of data sub-queues.
Claim 21
Independent Claim
232 words
A method of processing a plurality of digital data packets that are received from at least one data input port, temporarily stored in a buffer memory, and intended for transmission through at least one data output port comprising the steps of: receiving said digital data packets form said at least one data input port; dividing said buffer memory for storing said digital data packets into a plurality of data sub-queues, each of said data sub-queues having a length that is dynamically determined in response to the receipt of said digital data packets by said data sub-queues and each of said data sub-queues having an assigned output ranking and an assigned delay threshold, and a dispatch-essential flag and an age counter; storing each of said digital data packets in a selected one of said data sub-queues; incrementing said age counter for each of said plurality of data sub-queues when a digital data packet is dispatched from another of said plurality of data sub-queues; setting said dispatch-essential flag for each of said plurality of data sub-queues when said age counter for said each of said plurality of data sub-queues exceeds said delay threshold for said each of said plurality of data sub-queues; and outputting said digital data packets from each of said plurality of data sub-queues in accordance with said delay threshold and said output ranking of each of said plurality of data sub-queues.
Claim 22
Dependent Claim
33 words
The method of claim 18 wherein each of said plurality of data sub-queues has an dispatch counter representing a minimum number of digital data packets to be transmitted before clearing said dispatch-essential flag.
Claim 23
Dependent Claim
45 words
The method of claim 19 further comprising the step of decrementing said corresponding dispatch counter for each of said plurality of data sub-queues when a digital data packet is transmitted from each of said plurality of data sub-queues to said at least one output port.
Claim 24
Dependent Claim
38 words
The method of claim 20 further comprising the step of clearing said dispatch-essential flag for each of said plurality of data sub-queues when said dispatch counter indicates that said minimum number of digital data packets have been transmitted.
Claim 25
Independent Claim
209 words
A method of processing a plurality of digital data packets that are received from at least one data input port, temporarily stored in a buffer memory, and intended for transmission through at least one data output port comprising the steps of: receiving said digital data packets form said at least one data input port; dividing said buffer memory for storing said digital data packets into a plurality of data sub-queues, each of said data sub-queues having a length that is dynamically determined in response to the receipt of said digital data packets by said data sub-queues and each of said data sub-queues having an assigned output ranking and an assigned accumulation ratio; storing each of said digital data packets in a selected one of said data sub-queues calculating an accumulation ratio threshold for each of said plurality of data sub-queues equal to the product of said accumulation ratio for each of said plurality of data sub-queues and the total number of digital data packets stored in said buffer memory; and transmitting each of said digital data packets from said plurality of data sub-queues to said at least one output port in accordance with said accumulation ratio threshold and said output ranking of each of said plurality of data sub-queues.
Claim 26
Independent Claim
209 words
A method of processing a plurality of digital data packets that are received from at least one data input port, temporarily stored in a buffer memory, and intended for transmission through at least one data output port comprising the steps of: receiving said digital data packets form said at least one data input port; dividing said buffer memory for storing said digital data packets into a plurality of data sub-queues, each of said data sub-queues having a length that is dynamically determined in response to the receipt of said digital data packets by said data sub-queues and each of said data sub-queues having an assigned output ranking and an assigned accumulation ratio; storing each of said digital data packets in a selected one of said data sub-queues calculating an accumulation ratio threshold for each of said plurality of data sub-queues equal to the product of said accumulation ratio for each of said plurality of data sub-queues and the total number of digital data packets stored in said buffer memory; and transmitting each of said digital data packets from said plurality of data sub-queues to said at least one output port in accordance with said accumulation ratio threshold and said output ranking of each of said plurality of data sub-queues.
Claim 27
Independent Claim
140 words
An apparatus for processing a plurality of digital data packets that are received from at least one data input port, temporarily stored in a buffer memory, and intended for transmission through at least one data output port comprising the steps of: input means for receiving said digital data packets from said at least one data input port; processing means connected with said input means for dividing said buffer memory into a plurality of data sub-queues each having a length that is dynamically determined in response to the receipt of said digital data packets by said data sub-queues and each of said data sub-queues having an assigned output ranking and purge ranking, and an assigned delay threshold and accumulation ratio, said processing means further operating to store each of said digital data packets in a selected one of said data sub-queues.
Claim 28
Independent Claim
140 words
An apparatus for processing a plurality of digital data packets that are received from at least one data input port, temporarily stored in a buffer memory, and intended for transmission through at least one data output port comprising the steps of: input means for receiving said digital data packets from said at least one data input port; processing means connected with said input means for dividing said buffer memory into a plurality of data sub-queues each having a length that is dynamically determined in response to the receipt of said digital data packets by said data sub-queues and each of said data sub-queues having an assigned output ranking and purge ranking, and an assigned delay threshold and accumulation ratio, said processing means further operating to store each of said digital data packets in a selected one of said data sub-queues.
Claim 29
Dependent Claim
47 words
The apparatus of claim 23 further comprising output means connected with said processing means for transmitting each of said digital data packets from said plurality of data sub-queues to said at least one output port in accordance with said output ranking of each of said data sub-queues.
Claim 30
Dependent Claim
35 words
The apparatus of claim 24 wherein said processing means further operates to purge said digital data packets from said plurality of data sub-queues in accordance with said purge ranking of each of said data sub-queues.
Claim 31
Dependent Claim
70 words
The apparatus of claim 23 wherein said processing means further operates to shorten said length of each of said plurality of data sub-queue from which said digital data packet was transmitted after said output means transmits said digital data packets, whereby said shortening allows said data sub-queue from which said digital data packet was transmitted to equal the total length of said digital data packets remaining in said data sub-queue.
Claim 32
Independent Claim
246 words
A method of processing a plurality of digital data packets that are received from at least one data input port, temporarily stored in a buffer memory, and intended for transmission through at least one data output port comprising the steps of: receiving said digital data packets from said at least one data input port; dividing said buffer memory for storing said digital data packets into a plurality of data sub-queues, each of said data sub-queues having a length that is dynamically determined in response to the receipt of said digital data packets by said data sub-queues and each of said data sub-queues having an assigned output ranking and purge ranking, an assigned delay threshold representing a minimum bandwidth for each of said plurality of data sub-queues, and a dispatch-essential flag; storing each of said digital data packets in a selected one of said data sub-queues; determining a delay time indicative of the time lapsed since the digital data packet at the head of each of said plurality of data sub-queues was stored in said data sub-queue; setting said dispatch-essential flag for each of said plurality of data sub-queues when said delay time for said each of said plurality of data sub-queues exceeds said delay threshold for said each of said plurality of data sub-queues; and outputting said digital data packets from each of said plurality of data sub-queues in accordance with said dispatch-essential flag and said output ranking of each of said plurality of data sub-queues.
Claim 33
Independent Claim
246 words
A method of processing a plurality of digital data packets that are received from at least one data input port, temporarily stored in a buffer memory, and intended for transmission through at least one data output port comprising the steps of: receiving said digital data packets from said at least one data input port; dividing said buffer memory for storing said digital data packets into a plurality of data sub-queues, each of said data sub-queues having a length that is dynamically determined in response to the receipt of said digital data packets by said data sub-queues and each of said data sub-queues having an assigned output ranking and purge ranking, an assigned delay threshold representing a minimum bandwidth for each of said plurality of data sub-queues, and a dispatch-essential flag; storing each of said digital data packets in a selected one of said data sub-queues; determining a delay time indicative of the time lapsed since the digital data packet at the head of each of said plurality of data sub-queues was stored in said data sub-queue; setting said dispatch-essential flag for each of said plurality of data sub-queues when said delay time for said each of said plurality of data sub-queues exceeds said delay threshold for said each of said plurality of data sub-queues; and outputting said digital data packets from each of said plurality of data sub-queues in accordance with said dispatch-essential flag and said output ranking of each of said plurality of data sub-queues.
Claim 34
Dependent Claim
28 words
The method of claim 27 wherein the next digital data packet is transmitted from the head of the highest output ranking data sub-queue with its dispatch-essential flag set.
Claim 35
Independent Claim
259 words
An apparatus for processing a plurality of digital data packets that are received from at least one data input port, temporarily stored in a buffer memory, and intended for transmission through at least one data output port comprising the steps of: input means for receiving said digital data packets from said at least one data input port; processing means connected with said input means for dividing said buffer memory into a plurality of data sub-queues each having a length that is dynamically determined in response to the receipt of said digital data packets by said data sub-queues and each of said data sub-queues having an assigned output ranking and purge ranking, an assigned delay threshold representing a minimum bandwidth for each of said plurality of data sub-queues, a dispatch-essential flag; and an accumulation ratio, said processing means further operating to store each of said digital data packets in a selected one of said data sub-queues; determining a delay time indicative of the time lapsed since the digital data packet at the head of each of said plurality of data sub-queues was stored in said data sub-queue; setting said dispatch-essential flag for each of said plurality of data sub-queues when said delay time for said each of said plurality of data sub-queues exceeds said delay threshold for said each of said plurality of data sub-queues; and outputting said digital data packets from each of said plurality of data sub-queues in accordance with said dispatch-essential flag, said accumulation ratio, and said output ranking of each of said plurality of data sub-queues.
Claim 36
Independent Claim
259 words
An apparatus for processing a plurality of digital data packets that are received from at least one data input port, temporarily stored in a buffer memory, and intended for transmission through at least one data output port comprising the steps of: input means for receiving said digital data packets from said at least one data input port; processing means connected with said input means for dividing said buffer memory into a plurality of data sub-queues each having a length that is dynamically determined in response to the receipt of said digital data packets by said data sub-queues and each of said data sub-queues having an assigned output ranking and purge ranking, an assigned delay threshold representing a minimum bandwidth for each of said plurality of data sub-queues, a dispatch-essential flag; and an accumulation ratio, said processing means further operating to store each of said digital data packets in a selected one of said data sub-queues; determining a delay time indicative of the time lapsed since the digital data packet at the head of each of said plurality of data sub-queues was stored in said data sub-queue; setting said dispatch-essential flag for each of said plurality of data sub-queues when said delay time for said each of said plurality of data sub-queues exceeds said delay threshold for said each of said plurality of data sub-queues; and outputting said digital data packets from each of said plurality of data sub-queues in accordance with said dispatch-essential flag, said accumulation ratio, and said output ranking of each of said plurality of data sub-queues.
References Cited (Backward Citations)
US5083269A
Cited
WO1991004624A1
Cited
US5475680A
Cited
US5150358A
Cited
US5303078A
Cited
US5365519A
Cited
US5233606A
Cited
US5278828A
Cited
US5463620A
Cited
US5555265A
Cited
US5541912A
Cited
US5521916A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2001-05-25 | 2001-11-24 | 2002-05-26 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2005-05-25 | 2005-11-24 | 2006-05-26 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2009-05-25 | 2009-11-24 | 2010-05-26 | $7700.00 | Window Closed / Lapsed |