US5224099A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Circuitry and method for fair queuing and servicing cell traffic using hopcounts and traffic classes
Assignee: Cisco Technology Inc
•
Filing: 1991-05-17
•
Granted: 1993-06-29
•
Expires: 2011-05-17
Abstract
Abstract A method of fair queuing and servicing cell traffic in a telecommunication node which interfaces with a telecommunication system including a multiplicity of nodes is described. The steps include placing cells of traffic are placed in a queue according to a hopcount associated with each cell of bursty traffic, the hopcount being representative of the number of nodes traversed by the associated cell. Cells of traffic within the queue are serviced according to their associated hopcount. The hopcount associated with each cell of traffic is incremented as each cell of traffic is serviced. Circuitry providing fair queuing and servicing of cell traffic in a telecommunication node which interfaces with a telecommunication system including a multiplicity of nodes is also described.
Inventors
- 👤 Charles M. Corbalis
- 👤 Lionel A. Bustini
- 👤 Patrick D. Daley
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-26 14:14
CPC Classifications
H; H04; H04L; H04L47/00; H04L47/10; H04L47/28; H04L12/00; H04L12/64; H04L12/6418; H04L47/24; H04L47/2425; H04L47/2433; H04L47/43; H04Q; H04Q11/00; H04Q11/04; H04Q11/0428; H04Q11/0478; H04L12/54; H04L12/56; H04L12/5601; H04L2012/5614; H04L2012/5618; H04L2012/5619; H04L2012/5638; H04L2012/5646; H04L2012/5649; H04L2012/5651; H04L2012/5671; H04L2012/5678; H04L2012/5679; H04L2012/5681; H04L2012/6481
Claims Analysis
Total Claims: 23
Claim 1
Independent Claim
128 words
A method of fair queuing and servicing cell traffic in a telecommunication node for interfacing with a telecommunication system including a multiplicity of nodes, said method comprising: a. classifying a subset of cell traffic as bursty traffic; b. placing cells of said bursty traffic in a queue according to a hopcount associated with each cell of bursty traffic, said hopcount being representative of a number of nodes traversed by the associated cell of bursty traffic; c. servicing cells of bursty traffic within said queue according to said associated hopcount, cells of bursty traffic with a greater hopcount being serviced before cells of bursty traffic with a lower hopcount; and d. incrementing said hopcount associated with each cell of bursty traffic when each cell of bursty traffic is serviced.
Claim 2
Independent Claim
128 words
A method of fair queuing and servicing cell traffic in a telecommunication node for interfacing with a telecommunication system including a multiplicity of nodes, said method comprising: a. classifying a subset of cell traffic as bursty traffic; b. placing cells of said bursty traffic in a queue according to a hopcount associated with each cell of bursty traffic, said hopcount being representative of a number of nodes traversed by the associated cell of bursty traffic; c. servicing cells of bursty traffic within said queue according to said associated hopcount, cells of bursty traffic with a greater hopcount being serviced before cells of bursty traffic with a lower hopcount; and d. incrementing said hopcount associated with each cell of bursty traffic when each cell of bursty traffic is serviced.
Claim 3
Dependent Claim
20 words
The method of queuing and servicing cell traffic of claim 1 wherein said bursty traffic comprises point to point traffic.
Claim 4
Dependent Claim
18 words
The method of queuing and servicing cell traffic of claim 1 wherein said bursty traffic comprises multicast data.
Claim 5
Independent Claim
315 words
A method of queuing and servicing packet traffic in a telecommunication node for interfacing with a telecommunication system including a multiplicity of nodes, said method comprising: a. classifying traffic an non-bursty traffic and bursty traffic, b. allocating a first minimum bandwidth to said non-bursty traffic and a second minimum bandwidth to said bursty traffic; c. accruing transmission credit for said non-bursty traffic according to said first minimum bandwidth and for said bursty traffic according to said second minimum bandwidth; d. placing packets of said non-bursty traffic in a first queue; e. placing packets of said bursty traffic in a second queue according to a hopcount associated with each packet of bursty traffic, said hopcount being representative of a number of nodes transverse by the associated packet of bursty traffic; f. generating a first flag whenever a packet is in said first queue and a second flag whenever a packet is in said second queue; g. servicing packets within said first queue when said first flag is present and transmission credit has accrued for said non-bursty traffic; h. servicing packets within said second queue next when said second flag is present and transmission credit has accrued for said bursty traffic, packets of bursty traffic with a greater hopcount being serviced before packets of bursty traffic with a lower hopcount; i. servicing packets within said first queue next if no transmission credit has accrued for either said non-bursty traffic or said bursty traffic and said first flag is present; j. servicing packets within said second queue next if no transmission credit has accrued for either said non-bursty traffic or said bursty traffic and said second flag is present, packets of bursty traffic with a grater hopcount being serviced before packets of bursty traffic with a lower hopcount; and k. incrementing said hopcount associated with each packet of bursty traffic when each packet of bursty traffic is serviced.
Claim 6
Independent Claim
315 words
A method of queuing and servicing packet traffic in a telecommunication node for interfacing with a telecommunication system including a multiplicity of nodes, said method comprising: a. classifying traffic an non-bursty traffic and bursty traffic, b. allocating a first minimum bandwidth to said non-bursty traffic and a second minimum bandwidth to said bursty traffic; c. accruing transmission credit for said non-bursty traffic according to said first minimum bandwidth and for said bursty traffic according to said second minimum bandwidth; d. placing packets of said non-bursty traffic in a first queue; e. placing packets of said bursty traffic in a second queue according to a hopcount associated with each packet of bursty traffic, said hopcount being representative of a number of nodes transverse by the associated packet of bursty traffic; f. generating a first flag whenever a packet is in said first queue and a second flag whenever a packet is in said second queue; g. servicing packets within said first queue when said first flag is present and transmission credit has accrued for said non-bursty traffic; h. servicing packets within said second queue next when said second flag is present and transmission credit has accrued for said bursty traffic, packets of bursty traffic with a greater hopcount being serviced before packets of bursty traffic with a lower hopcount; i. servicing packets within said first queue next if no transmission credit has accrued for either said non-bursty traffic or said bursty traffic and said first flag is present; j. servicing packets within said second queue next if no transmission credit has accrued for either said non-bursty traffic or said bursty traffic and said second flag is present, packets of bursty traffic with a grater hopcount being serviced before packets of bursty traffic with a lower hopcount; and k. incrementing said hopcount associated with each packet of bursty traffic when each packet of bursty traffic is serviced.
Claim 7
Dependent Claim
21 words
The method of queuing and servicing packet traffic of claim 4 wherein said bursty traffic comprises bursty point to point traffic.
Claim 8
Dependent Claim
18 words
The method of queuing and servicing packet traffic of claim 4 wherein said bursty traffic comprises multicast data.
Claim 9
Independent Claim
165 words
A method of queuing and servicing packet traffic in a telecommunication node for interfacing with a telecommunication system including a multiplicity of nodes, said method comprising: a. classifying a subset of packet traffic as bursty traffic; b. placing packets of said bursty traffic in a queue having a multiplicity of subqueues, said packets being placed in said subqueues according to a hopcount associated with each packet of bursty traffic, said hopcount being representative of a number of nodes traversed by the associated packet of bursty traffic, each subqueue having a different servicing priority; c. moving a packet of bursty traffic from a one subqueue to another subqueue having a higher servicing priority than said one subqueue after said packet of bursty traffic has remained in said one subqueue for a time T; d. servicing packets of bursty traffic within said queue according to subqueue priority; and e. incrementing said hopcount associated with each packet of bursty traffic when each packet of bursty traffic is serviced.
Claim 10
Independent Claim
165 words
A method of queuing and servicing packet traffic in a telecommunication node for interfacing with a telecommunication system including a multiplicity of nodes, said method comprising: a. classifying a subset of packet traffic as bursty traffic; b. placing packets of said bursty traffic in a queue having a multiplicity of subqueues, said packets being placed in said subqueues according to a hopcount associated with each packet of bursty traffic, said hopcount being representative of a number of nodes traversed by the associated packet of bursty traffic, each subqueue having a different servicing priority; c. moving a packet of bursty traffic from a one subqueue to another subqueue having a higher servicing priority than said one subqueue after said packet of bursty traffic has remained in said one subqueue for a time T; d. servicing packets of bursty traffic within said queue according to subqueue priority; and e. incrementing said hopcount associated with each packet of bursty traffic when each packet of bursty traffic is serviced.
Claim 11
Dependent Claim
21 words
The method of queuing and servicing packet traffic of claim 7 wherein said bursty traffic comprises bursty point to point traffic.
Claim 12
Dependent Claim
18 words
The method of queueing and servicing packet traffic of claim 7 wherein said bursty traffic comprises multicast data.
Claim 13
Independent Claim
383 words
A method of queuing and servicing packet traffic in a telecommunication node for interfacing with a telecommunication system including a multiplicity of nodes, said method comprising: a. classifying traffic as non-bursty traffic and bursty traffic, b. allocating a first minimum bandwidth to said non-bursty traffic and a second minimum bandwidth to said bursty traffic; c. accruing transmission credit for said non-bursty traffic according to said first minimum bandwidth and for said traffic according to said second minimum bandwidth; d. placing packets of said non-bursty traffic in a first queue; e. placing packets of said bursty traffic in a second queue having a multiplicity of subqueues, said packets being placed in said subqueues according to a hopcount associated with each packet of bursty traffic, said hopcount being representative of a number of nodes traversed by the associated packet of bursty traffic, a subqueue associated with a greater hopcount having a higher servicing priority than a subqueue associated with a lesser hopcount; f. moving a packet of bursty traffic from a one subqueue to another subqueue having a higher servicing priority than said one subqueue after said packet of bursty traffic has remained in said one subqueue for a time T; g. generating a first flag whenever a packet is in said first queue and a second flag whenever a packet is in said second queue; h. servicing packets within said first queue when said first flag is present and transmission credit has accrued for said non-bursty traffic; i. servicing packets within said second queue next if said second flag is present and transmission credit has accrued for said bursty traffic, said packets within said second queue being serviced by subqueue according to the servicing priority of the subqueue; j. servicing packets within said first queue next if no transmission credit has accrued for either said non-bursty traffic or said bursty traffic and said first flag is present; k. servicing packets within said second queue next if no transmission credit has accrued for either said non-bursty traffic or said bursty traffic and said second flag is present, said packets within said second queue being serviced by subqueue according to the servicing priority of the subqueue; and i. incrementing said hopcount associated with each packet of bursty traffic when each packet of bursty traffic is serviced.
Claim 14
Independent Claim
383 words
A method of queuing and servicing packet traffic in a telecommunication node for interfacing with a telecommunication system including a multiplicity of nodes, said method comprising: a. classifying traffic as non-bursty traffic and bursty traffic, b. allocating a first minimum bandwidth to said non-bursty traffic and a second minimum bandwidth to said bursty traffic; c. accruing transmission credit for said non-bursty traffic according to said first minimum bandwidth and for said traffic according to said second minimum bandwidth; d. placing packets of said non-bursty traffic in a first queue; e. placing packets of said bursty traffic in a second queue having a multiplicity of subqueues, said packets being placed in said subqueues according to a hopcount associated with each packet of bursty traffic, said hopcount being representative of a number of nodes traversed by the associated packet of bursty traffic, a subqueue associated with a greater hopcount having a higher servicing priority than a subqueue associated with a lesser hopcount; f. moving a packet of bursty traffic from a one subqueue to another subqueue having a higher servicing priority than said one subqueue after said packet of bursty traffic has remained in said one subqueue for a time T; g. generating a first flag whenever a packet is in said first queue and a second flag whenever a packet is in said second queue; h. servicing packets within said first queue when said first flag is present and transmission credit has accrued for said non-bursty traffic; i. servicing packets within said second queue next if said second flag is present and transmission credit has accrued for said bursty traffic, said packets within said second queue being serviced by subqueue according to the servicing priority of the subqueue; j. servicing packets within said first queue next if no transmission credit has accrued for either said non-bursty traffic or said bursty traffic and said first flag is present; k. servicing packets within said second queue next if no transmission credit has accrued for either said non-bursty traffic or said bursty traffic and said second flag is present, said packets within said second queue being serviced by subqueue according to the servicing priority of the subqueue; and i. incrementing said hopcount associated with each packet of bursty traffic when each packet of bursty traffic is serviced.
Claim 15
Dependent Claim
21 words
The method of queuing and servicing packet traffic of claim 10 wherein said bursty traffic comprises bursty point to point traffic.
Claim 16
Dependent Claim
18 words
The method of queuing and servicing packet traffic of claim 10 wherein said bursty traffic comprises multicast data.
Claim 17
Dependent Claim
408 words
Circuitry for queuing and servicing packet traffic in a telecommunication node for interfacing with a telecommunication system including a multiplicity of nodes, said circuitry comprising: a. circuitry for classifying traffic as non-bursty traffic and bursty traffic, b. circuitry for allocating a first minimum bandwidth to said non-bursty traffic and a second minimum band width to said bursty traffic; c. circuitry for accruing transmission credit for said non-bursty traffic according to said first minimum bandwidth and for said bursty traffic according to said second minimum bandwidth; d. circuitry for placing packets of said non-bursty traffic in a first queue; e. circuitry for placing packets of said bursty traffic in a second queue having a multiplicity of subqueues, said packets being placed in said subqueues according to a hopcount associated with each packet of bursty traffic, said hopcount being representative of a number of nodes traversed by the associated packet of bursty traffic, a subqueue associated with a greater hopcount having a greater servicing priority than a subqueue associated with a lesser hopcount; f. circuitry for moving a packet of non-bursty traffic from a one subqueue to another subqueue having a higher servicing priority than said one subqueue after said packet of bursty traffic has remained in said one subqueue for a time T; g. circuitry for generating a first flag whenever a packet is in said first queue and a second flag whenever a packet is in said second queue; h. circuitry for servicing packets within said first queue when said first flag is present and transmission credit has accrued for said non-bursty traffic; i. circuitry for servicing packets within said second queue next it said second flag is present and transmission credit has accrued for said bursty traffic, said packets within said second queue being serviced by subqueue according to the servicing priority of the subqueue; j. circuitry for servicing packets within said first queue next if no transmission credit has accrued for either said non-bursty traffic or said bursty traffic and said first flag is present; k. circuitry for servicing packets within said second queue next if not transmission credit has accrued for either said non-bursty traffic or said bursty traffic and said second flag is present, said packets within said second queue being serviced by subqueue according to the servicing priority of the subqueue; and i. circuitry for increasing said hopcount associated with each packet of bursty traffic when each packet of bursty traffic is serviced.
Claim 18
Dependent Claim
408 words
Circuitry for queuing and servicing packet traffic in a telecommunication node for interfacing with a telecommunication system including a multiplicity of nodes, said circuitry comprising: a. circuitry for classifying traffic as non-bursty traffic and bursty traffic, b. circuitry for allocating a first minimum bandwidth to said non-bursty traffic and a second minimum band width to said bursty traffic; c. circuitry for accruing transmission credit for said non-bursty traffic according to said first minimum bandwidth and for said bursty traffic according to said second minimum bandwidth; d. circuitry for placing packets of said non-bursty traffic in a first queue; e. circuitry for placing packets of said bursty traffic in a second queue having a multiplicity of subqueues, said packets being placed in said subqueues according to a hopcount associated with each packet of bursty traffic, said hopcount being representative of a number of nodes traversed by the associated packet of bursty traffic, a subqueue associated with a greater hopcount having a greater servicing priority than a subqueue associated with a lesser hopcount; f. circuitry for moving a packet of non-bursty traffic from a one subqueue to another subqueue having a higher servicing priority than said one subqueue after said packet of bursty traffic has remained in said one subqueue for a time T; g. circuitry for generating a first flag whenever a packet is in said first queue and a second flag whenever a packet is in said second queue; h. circuitry for servicing packets within said first queue when said first flag is present and transmission credit has accrued for said non-bursty traffic; i. circuitry for servicing packets within said second queue next it said second flag is present and transmission credit has accrued for said bursty traffic, said packets within said second queue being serviced by subqueue according to the servicing priority of the subqueue; j. circuitry for servicing packets within said first queue next if no transmission credit has accrued for either said non-bursty traffic or said bursty traffic and said first flag is present; k. circuitry for servicing packets within said second queue next if not transmission credit has accrued for either said non-bursty traffic or said bursty traffic and said second flag is present, said packets within said second queue being serviced by subqueue according to the servicing priority of the subqueue; and i. circuitry for increasing said hopcount associated with each packet of bursty traffic when each packet of bursty traffic is serviced.
Claim 19
Independent Claim
196 words
A method of fair queuing and servicing cell traffic in a telecommunication node for interfacing with a telecommunication system including a multiplicity of nodes, said method comprising: a. classifying one subset of cell traffic as a first type of bursty traffic and another subset of cell traffic as a second type of bursty traffic. b. placing cells of said first type of bursty traffic in a first queue according to a hopcount associated with each cell of said first type of bursty traffic, said hopcount being representative of a number of nodes traversed by the associated cell of said first type of bursty traffic; c. placing cells of said second type of bursty traffic in a second queue according to a hopcount associated with each cell of said said type of bursty traffic, said hopcount being representative of a number of nodes traversed by the associated cell of said second type of bursty traffic; d. servicing cells of bursty traffic within said first queue and said second queue according to said associated hopcount; and e. incrementing said hopcount associated with each cell of each type of bursty traffic when each cell of bursty traffic is serviced.
Claim 20
Independent Claim
196 words
A method of fair queuing and servicing cell traffic in a telecommunication node for interfacing with a telecommunication system including a multiplicity of nodes, said method comprising: a. classifying one subset of cell traffic as a first type of bursty traffic and another subset of cell traffic as a second type of bursty traffic. b. placing cells of said first type of bursty traffic in a first queue according to a hopcount associated with each cell of said first type of bursty traffic, said hopcount being representative of a number of nodes traversed by the associated cell of said first type of bursty traffic; c. placing cells of said second type of bursty traffic in a second queue according to a hopcount associated with each cell of said said type of bursty traffic, said hopcount being representative of a number of nodes traversed by the associated cell of said second type of bursty traffic; d. servicing cells of bursty traffic within said first queue and said second queue according to said associated hopcount; and e. incrementing said hopcount associated with each cell of each type of bursty traffic when each cell of bursty traffic is serviced.
Claim 21
Dependent Claim
28 words
The method of claim 14 wherein said first type of bursty traffic comprises bursty point to point traffic and said second type of bursty traffic comprises multicast traffic.
Claim 22
Independent Claim
106 words
A method of fair queuing and servicing cell traffic in a telecommunication node for interfacing with a telecommunication system including a multiplicity of nodes, said method comprising: a. placing cells of cell traffic in a queue according to a hopcount associated with each cell of traffic, said hopcount being representative of a number of nodes traversed by the associated cell of traffic; b. servicing cell of traffic within said queue according to said associated hopcount, cells with a greater hopcount being serviced before cells with a lower hopcount; and c. incrementing said hopcount associated with each cell of traffic when each cell of traffic is serviced.
Claim 23
Independent Claim
106 words
A method of fair queuing and servicing cell traffic in a telecommunication node for interfacing with a telecommunication system including a multiplicity of nodes, said method comprising: a. placing cells of cell traffic in a queue according to a hopcount associated with each cell of traffic, said hopcount being representative of a number of nodes traversed by the associated cell of traffic; b. servicing cell of traffic within said queue according to said associated hopcount, cells with a greater hopcount being serviced before cells with a lower hopcount; and c. incrementing said hopcount associated with each cell of traffic when each cell of traffic is serviced.
References Cited (Backward Citations)
US4491945A
Cited
US4494230A
Cited
US4506358A
Cited
US4771425A
Cited
US4819228A
Cited
US4903261A
Cited
US4644533A
Cited
US4757529A
Cited
US4819230A
Cited
US4939718A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1996-06-28 | 1996-12-28 | 1997-06-29 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2000-06-28 | 2000-12-28 | 2001-06-29 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2004-06-28 | 2004-12-28 | 2005-06-29 | $7700.00 | Window Closed / Lapsed |