US5996019A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Network link access scheduling using a plurality of prioritized lists containing queue identifiers
Assignee: Ascom Intermediate AG
•
Filing: 1996-07-18
•
Granted: 1999-11-30
•
Expires: 2016-07-18
Abstract
Abstract Methods and apparatus for scheduling cell transmission over a network link by a switch. The switch includes a plurality of queues associated with each link. Lists of queues are maintained for each link. In one embodiment, each link is associated with more than one type of list (with the list type corresponding to a scheduling category) and more than one prioritized list of each type (with the priority of the list corresponding to a quality of service). The scheduling lists are accessed to permit cell transmission from a queue contained therein in a predetermined sequence as a function of scheduling category, priority within a particular scheduling category and whether the bandwidth requirement for the particular scheduling category has been met. With this arrangement, maximum permissible delay requirements for each scheduling category are met.
Inventors
- 👤 Stephen A. Hauser
- 👤 Richard G. Bubenik
- 👤 Stephen A. Caldara
- 👤 Michael E. Gaddis
- 👤 Thomas A. Manning
- 👤 James M. Meredith
- 👤 Raymond L. Strouble
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-30 12:11
CPC Classifications
H; H04; H04L; H04L47/00; H04L47/10; H04L47/18; G; G06; G06F; G06F15/00; G06F15/16; G06F15/163; G06F15/173; G06F15/17356; G06F15/17368; G06F15/17375; H04L12/00; H04L12/28; H04L12/46; H04L12/4604; H04L12/4608; H04L12/54; H04L12/56; H04L12/5601; H04L12/5602; H04L12/64; H04L12/6402; H04L41/00; H04L41/08; H04L41/0896; H04L47/11; H04L47/15; H04L47/16; H04L47/26; H04L47/266; H04L47/29; H04L47/30; H04L47/50; H04L47/52; H04L47/521; H04L47/522; H04L47/525; H04L47/56; H04L47/62; H04L47/621; H04L47/6215; H04L47/622; H04L47/6225; H04L47/625; H04L47/627; H04L47/70; H04L47/72; H04L47/722; H04L47/74; H04L47/743; H04L47/745; H04L47/76; H04L47/762; H04L47/78; H04L47/782; H04L47/80; H04L47/805; H04L47/82; H04L47/822; H04L49/00; H04L49/10; H04L49/101; H04L49/103; H04L49/104; H04L49/105; H04L49/106; H04L49/107; H04L49/108; H04L49/15; H04L49/1515; H04L49/153; H04L49/1553; H04L49/1576; H04L49/20; H04L49/201; H04L49/203; H04L49/205; H04L49/25; H04L49/253; H04L49/254; H04L49/255; H04L49/256; H04L49/30; H04L49/3009; H04L49/3081; H04L49/309; H04L49/45; H04L49/455; H04L49/50; H04L49/501; H04L49/503; H04L49/505; H04L49/506; H04L49/55; H04L49/552; H04L49/90; H04L49/901; H04L49/9047; H04L49/9063; H04L49/9078; H04L69/00; H04L69/30; H04L69/32; H04L69/322; H04L69/324; H04Q; H04Q11/00; H04Q11/04; H04Q11/0428; H04Q11/0478; H04W; H04W28/00; H04W28/02; H04W28/10; H04W28/14; H04J; H04J3/00; H04J3/02; H04J3/06; H04J3/0635; H04J3/0682; H04J3/0685; H04L2012/5614; H04L2012/5616; H04L2012/5625; H04L2012/5627; H04L2012/5628; H04L2012/5629; H04L2012/5631; H04L2012/5632; H04L2012/5634; H04L2012/5635; H04L2012/5638; H04L2012/564; H04L2012/5642; H04L2012/5643; H04L2012/5646; H04L2012/5647; H04L2012/5648; H04L2012/5649; H04L2012/565; H04L2012/5651; H04L2012/5652; H04L2012/5672; H04L2012/5678; H04L2012/5679; H04L2012/5681; H04L2012/5682; H04L2012/5683; H04L2012/5684; H04L2012/5685; H04L41/0897; H04L41/40; H04L49/508; H04L49/555; H04L7/00; H04L7/04; H04L7/041; H04L7/046; Y; Y10; Y10S; Y10S370/00; Y10S370/901; Y10S370/902; Y10S370/903; Y10S370/905
Claims Analysis
Total Claims: 24
Claim 1
Independent Claim
171 words
A communications switch comprising: an input port operative to receive cells over an input link, each of said cells being associated with a respective scheduling category; an output port operative to transmit said cells from said switch over an output link, said output port comprising a plurality of queues associated with said output link, wherein each of said plurality of queues is adapted for enqueuing cells associated with at least one scheduling category; a switch fabric coupled between said input port and said output port; a memory comprising a plurality of lists, each of said lists associated with a respective scheduling category and adapted for listing ones of said plurality of queues; and a controller coupled to said memory and operative to schedule said lists in order to provide the queues listed in said lists with access to said output link, wherein said lists are scheduled based on the scheduling category associated with each of said lists and whether a bandwidth requirement associated with the respective scheduling category has been met.
Claim 2
Dependent Claim
171 words
A communications switch comprising: an input port operative to receive cells over an input link, each of said cells being associated with a respective scheduling category; an output port operative to transmit said cells from said switch over an output link, said output port comprising a plurality of queues associated with said output link, wherein each of said plurality of queues is adapted for enqueuing cells associated with at least one scheduling category; a switch fabric coupled between said input port and said output port; a memory comprising a plurality of lists, each of said lists associated with a respective scheduling category and adapted for listing ones of said plurality of queues; and a controller coupled to said memory and operative to schedule said lists in order to provide the queues listed in said lists with access to said output link, wherein said lists are scheduled based on the scheduling category associated with each of said lists and whether a bandwidth requirement associated with the respective scheduling category has been met.
Claim 3
Dependent Claim
30 words
The switch recited in claim 1 wherein said memory further comprises a bandwidth measurement table for storing entries indicating the scheduling category associated with cells transmitted during a predetermined interval.
Claim 4
Dependent Claim
44 words
The switch recited in claim 2 further comprising a counter for counting the number of entries in said bandwidth table for each scheduling category, wherein said counter is operative to determine whether said bandwidth requirement associated with a respective scheduling category has been met.
Claim 5
Independent Claim
86 words
A method of resolving contention between plural queues having associated therewith cells for transmission over a link, the method comprising the steps of: associating each of said queues with at least one of a plurality of scheduling lists having a respective one of a plurality of scheduling categories associated therewith; measuring the bandwidth provided to each of said plurality of scheduling categories over a predetermined interval; and selecting one of said plurality of scheduling lists based on the measured bandwidth provided to the respective scheduling category.
Claim 6
Independent Claim
86 words
A method of resolving contention between plural queues having associated therewith cells for transmission over a link, the method comprising the steps of: associating each of said queues with at least one of a plurality of scheduling lists having a respective one of a plurality of scheduling categories associated therewith; measuring the bandwidth provided to each of said plurality of scheduling categories over a predetermined interval; and selecting one of said plurality of scheduling lists based on the measured bandwidth provided to the respective scheduling category.
Claim 7
Dependent Claim
62 words
The method recited in claim 4 wherein said bandwidth measuring step comprises the steps of: storing a bandwidth measurement table comprising entries, each indicative of the one of said plurality of scheduling categories associated with a prior cell transmission; and maintaining a count of the number of entries, in said bandwidth measurement tables associated with each of said plurality of scheduling categories.
Claim 8
Dependent Claim
32 words
The method recited in claim 4 wherein said list selecting step further comprises the step of selecting one of said plural scheduling lists based on the scheduling category associated with said list.
Claim 9
Dependent Claim
48 words
The switch recited in claim 1 wherein at least one of said plurality of lists has a priority associated therewith within the respective scheduling category and wherein said plurality of lists are additionally scheduled based on said priority of said lists within the respective scheduling category, if any.
Claim 10
Dependent Claim
41 words
The switch recited in claim 1 wherein each of said plurality of lists comprises an entry having a first field for identifying one of said plurality of queues and a second field for pointing to another entry within the respective list.
Claim 11
Dependent Claim
45 words
The switch recited in claim 1 wherein each of said plurality of queues comprises a queue descriptor for identifying the at least one scheduling category associated with cells enqueued in said queue, a priority within said at least one scheduling category and said output link.
Claim 12
Dependent Claim
50 words
The switch recited in claim 9 wherein said queue descriptor further comprises a cell counts associated with said at least one scheduling category associated with cells engueued in said queues for storing a count of the number of cells in said queue associated with said at least one scheduling category.
Claim 13
Independent Claim
80 words
A method of resolving contention between a plurality of queues for access to a link, the method comprising the steps of: maintaining a plurality of lists associated with said link, each of said lists comprised of at least one entry for identifying one of said plurality of queues; and selecting one of said plurality of lists for providing link access to an identified one of said plurality of queues in accordance with a predetermined sequence of said plurality of lists.
Claim 14
Independent Claim
80 words
A method of resolving contention between a plurality of queues for access to a link, the method comprising the steps of: maintaining a plurality of lists associated with said link, each of said lists comprised of at least one entry for identifying one of said plurality of queues; and selecting one of said plurality of lists for providing link access to an identified one of said plurality of queues in accordance with a predetermined sequence of said plurality of lists.
Claim 15
Dependent Claim
49 words
The method recited in claim 11 wherein each of said plurality of lists has a scheduling category and priority within the respective scheduling category associated therewith and wherein said one of said plurality of lists is selected in accordance with said scheduling category and priority associated with said list.
Claim 16
Dependent Claim
41 words
The method recited in claim 12 wherein said one of said plurality of lists is selected in accordance with said predetermined sequence of said plurality of lists and whether a bandwidth requirement associated with the respective scheduling category has been met.
Claim 17
Dependent Claim
77 words
The method recited in claim 11 wherein said list maintaining step comprises the step of adding an entry to one of said plurality of lists when a cell is enqueued on said one of said plurality of queues if said one of said plurality of queues is not already identified in an entry in said one of said plurality of lists and said cell has the same scheduling category as said one of said plurality of lists.
Claim 18
Dependent Claim
64 words
The method recited in claim 11 wherein said list maintaining step comprises the step of deleting an entry from one of said plurality of lists when a cell is dequeued from said one of said plurality of queues if said one of said plurality of queues does not contain any cells having the same scheduling category as said one of said plurality of lists.
Claim 19
Dependent Claim
99 words
A switch coupled to a link, said switch comprising: a plurality of queues adapted for enqueuing cells for transmission over said link; a plurality of lists associated with said link, each of said plurality of lists adapted for maintaining at least one entry identifying one of said plurality of queues; and a controller for selecting one of said plurality of lists for providing link access to said one of said plurality of queues identified in an entry therein, wherein said one of said plurality of lists is selected in accordance with a predetermined sequence of said plurality of lists.
Claim 20
Dependent Claim
99 words
A switch coupled to a link, said switch comprising: a plurality of queues adapted for enqueuing cells for transmission over said link; a plurality of lists associated with said link, each of said plurality of lists adapted for maintaining at least one entry identifying one of said plurality of queues; and a controller for selecting one of said plurality of lists for providing link access to said one of said plurality of queues identified in an entry therein, wherein said one of said plurality of lists is selected in accordance with a predetermined sequence of said plurality of lists.
Claim 21
Dependent Claim
31 words
The switch recited in claim 16 wherein each of said plurality of lists has one of a plurality of scheduling categories and a priority within the respective scheduling category associated therewith.
Claim 22
Dependent Claim
25 words
The switch recited in claim 17 wherein said predetermined sequence is based on said scheduling category and said priority associated with said plurality of lists.
Claim 23
Dependent Claim
30 words
The switch recited in claim 17 further comprising a bandwidth measurement table for storing an average bandwidth provided to each of a plurality of scheduling categories over a predetermined interval.
Claim 24
Dependent Claim
29 words
The switch recited in claim 19 wherein said predetermined sequence is based on the average bandwidth provided to each of said plurality of scheduling categories over said predetermined interval.
References Cited (Backward Citations)
US3804991A
Cited
US3974343A
Cited
US4069399A
Cited
US4603382A
Cited
US4849968A
Cited
US4727537A
Cited
US4737953A
Cited
US4715030A
Cited
US4821034A
Cited
US4993018A
Cited
US4920531A
Cited
US4878216A
Cited
US4797881A
Cited
US4837761A
Cited
US5084871A
Cited
US5335325A
Cited
US5282201A
Cited
US4893307A
Cited
US5021949A
Cited
US4870641A
Cited
US4893302A
Cited
US4894824A
Cited
US4958341A
Cited
US4899333A
Cited
US4872159A
Cited
US4872160A
Cited
US4979100A
Cited
US5377327A
Cited
US5146560A
Cited
US4956839A
Cited
US5198808A
Cited
US4922503A
Cited
US5060228A
Cited
US5157657A
Cited
US5090011A
Cited
US5083269A
Cited
US4897841A
Cited
US5199027A
Cited
US4947390A
Cited
US4933938A
Cited
US5132966A
Cited
US4953157A
Cited
US5119372A
Cited
US5179558A
Cited
US5093912A
Cited
US5422879A
Cited
US5130982A
Cited
US5067123A
Cited
US5119369A
Cited
US5070498A
Cited
US5090024A
Cited
US5193151A
Cited
US5197067A
Cited
US5084867A
Cited
US5191652A
Cited
US5163046A
Cited
US5130975A
Cited
US5185743A
Cited
US5272697A
Cited
US5379418A
Cited
US5544170A
Cited
US5309431A
Cited
US5553068A
Cited
US5239539A
Cited
US5151897A
Cited
US5258979A
Cited
US5146474A
Cited
US5029164A
Cited
US5303232A
Cited
US5253248A
Cited
US5341376A
Cited
US5115429A
Cited
US5301190A
Cited
US5335222A
Cited
US5333131A
Cited
US5253247A
Cited
US5274641A
Cited
US5150358A
Cited
US5128932A
Cited
US5267232A
Cited
US5420988A
Cited
US5283788A
Cited
US5163045A
Cited
US5414703A
Cited
US5394396A
Cited
US5271010A
Cited
US5255266A
Cited
US5497369A
Cited
US5268897A
Cited
US5301193A
Cited
US5280470A
Cited
US5285446A
Cited
US5375117A
Cited
US5333134A
Cited
US5287349A
Cited
US5341373A
Cited
US5590132A
Cited
US5479402A
Cited
US5339310A
Cited
US5487063A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2002-11-29 | 2003-05-31 | 2003-11-30 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2006-11-29 | 2007-05-31 | 2007-11-30 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2010-11-29 | 2011-05-31 | 2011-11-30 | $7700.00 | Window Closed / Lapsed |