US6041059A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Time-wheel ATM cell scheduling
Assignee: RPX Corp
•
Filing: 1997-04-25
•
Granted: 2000-03-21
•
Expires: 2017-04-25
Abstract
Abstract A method is provided for the implementation of a time-wheel ATM cell scheduler with very large number of queues that can precisely pace any assigned bandwidth described in [i,m] terms (i cells in m cell-times), as long as m/i>=[number of queues]. The method requires only a small, bounded amount of work per physical connection independent of the number of VCs.
Inventors
- 👤 Alexander Joffe
- 👤 Ari Birger
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-30 21:29
CPC Classifications
H; H04; H04L; H04L12/00; H04L12/54; H04L12/56; H04L12/5601; H04L12/5602; H04Q; H04Q11/00; H04Q11/04; H04Q11/0428; H04Q11/0478; H04L2012/5678; H04L2012/5679
Claims Analysis
Total Claims: 15
Claim 1
Independent Claim
269 words
A method of operating a cell scheduler for asynchronous time mode transfer of virtual channel entries at predetermined cell transmission time intervals, the cell scheduler comprising a plurality of queues of a first type, at least one queue of a second type, and means for transferring virtual channel entries among the first and the second queue, the method comprising at each interval: iteratively selecting one of the queues of the first type; if the selected queue has at least one entry, transferring all entries of the first type from the selected queue to a queue of the second type; if the queue of the second type has at least one entry, transmitting an entry at a head of the queue of the second type, the entry at the head of the queue of the second type having a step; if a period of time elapsed since the entry at the head of the queue of the second type was last transmitted is less than the step of the entry at the head of the queue of the second type, appending said entry at the head of the queue of the second type to a tail of one of the queues of the first type; and if a period of time elapsed since the entry at the head of the queue of the second type was last transmitted is not less than the step of the entry at the head of the queue of the second type, appending the entry at the head of the queue of the second type to a tail of the queue of the second type.
Claim 2
Independent Claim
269 words
A method of operating a cell scheduler for asynchronous time mode transfer of virtual channel entries at predetermined cell transmission time intervals, the cell scheduler comprising a plurality of queues of a first type, at least one queue of a second type, and means for transferring virtual channel entries among the first and the second queue, the method comprising at each interval: iteratively selecting one of the queues of the first type; if the selected queue has at least one entry, transferring all entries of the first type from the selected queue to a queue of the second type; if the queue of the second type has at least one entry, transmitting an entry at a head of the queue of the second type, the entry at the head of the queue of the second type having a step; if a period of time elapsed since the entry at the head of the queue of the second type was last transmitted is less than the step of the entry at the head of the queue of the second type, appending said entry at the head of the queue of the second type to a tail of one of the queues of the first type; and if a period of time elapsed since the entry at the head of the queue of the second type was last transmitted is not less than the step of the entry at the head of the queue of the second type, appending the entry at the head of the queue of the second type to a tail of the queue of the second type.
Claim 3
Dependent Claim
47 words
The method of claim 1, wherein transmitting the entry at the head of the queue of the second type is determined by: adding a step size to an accumulated value; extracting an integer part of the accumulated value; and subtracting the integer part from the accumulated value.
Claim 4
Dependent Claim
51 words
The method of claim 1, wherein the period of time elaped since the entry at the head of the queue of the second type was last transmitted is determined by: subtracting a timestamp value of the entry at the head of the queue of the second type from a current time.
Claim 5
Dependent Claim
28 words
The method of claim 1, further comprising: updating the current time; and adding the step to a timestamp value if the time elapsed is greater than the step.
Claim 6
Dependent Claim
271 words
A cell scheduler to be used in asynchronous time mode transfer of virtual channel entries, the scheduler comprising: a plurality of queues of a first type; at least one queue of a second type; and means for transferring virtual channel entries to and from each of said queues of a first type and a queue of a second type; wherein one of the queues of the first type is selected; if the selected queue has at least one entry, all entries of the first type are transferred from the slected queue to a queue of the second type; if the queue of the second type has at least one enty, an entry at a head of the queue of the second type is transmitted, the entry at the head of the queue of the second type having a step; if a period of time elapsed since the entry at the head of the queue of the second type was last transmitted is less than the step of the entry at the head of the queue of the second type, said entry at the head of the queue of the second type is appended to a tail of one of the queues of the first type; and if a period of time elapsed since the entry at the head of the queue of the second type was last transmitted is not less than the step of the entry at the head of the queue of the second type, the entry at the head of the queue of the second type is appended to a tail of the queue of the second type.
Claim 7
Dependent Claim
271 words
A cell scheduler to be used in asynchronous time mode transfer of virtual channel entries, the scheduler comprising: a plurality of queues of a first type; at least one queue of a second type; and means for transferring virtual channel entries to and from each of said queues of a first type and a queue of a second type; wherein one of the queues of the first type is selected; if the selected queue has at least one entry, all entries of the first type are transferred from the slected queue to a queue of the second type; if the queue of the second type has at least one enty, an entry at a head of the queue of the second type is transmitted, the entry at the head of the queue of the second type having a step; if a period of time elapsed since the entry at the head of the queue of the second type was last transmitted is less than the step of the entry at the head of the queue of the second type, said entry at the head of the queue of the second type is appended to a tail of one of the queues of the first type; and if a period of time elapsed since the entry at the head of the queue of the second type was last transmitted is not less than the step of the entry at the head of the queue of the second type, the entry at the head of the queue of the second type is appended to a tail of the queue of the second type.
Claim 8
Dependent Claim
13 words
The system of claim 5, further comprising one or more Virtual Channels (VC).
Claim 9
Dependent Claim
17 words
The system of claim 5, wherein each of the queues further comprises zero or more VC entries.
Claim 10
Dependent Claim
21 words
The system of claim 6, wherein each of the VCs further comprises: a step value; an accumulated result; and a timestamp.
Claim 11
Dependent Claim
308 words
A scheduling system to be used in asynchronous time mode transfer of virtual channel entries, the system comprising first and second cell schedulers, the first cell scheduler having a first priority and the second cell scheduler having a second priority, lower than the first priority, wherein the first and the second cell schedulers further comprise: a plurality of queues of a first type; at least one queue of a second type; and means for transferring virtual channel entries to and from each of said queues of a first type and a queue of a second type; wherein one of the queues of the first type is selected; if the selected queue has at least one entry, all entries of the first type are transferred from the selected queue to a queue of the second type; if the queue of the second type has at least one entry, an entry at a head of the queue of the second type is transmitted, the entry at the head of the queue of the second type having a step; if a period of time elapsed since the entry at the head of the queue of the second type was last transmitted is less than the step of the entry at the head of the queue of the second type, said entry at the head of the queue of the second type is appended to a tail of one of the queues of the first type; and if a period of time elapsed since the entry at the head of the queue of the second type was last transmitted is not less than the step of the entry at the head of the queue of the second type, the entry at the head of the queue of the second type is appended to a tail of the queue of the second type.
Claim 12
Dependent Claim
308 words
A scheduling system to be used in asynchronous time mode transfer of virtual channel entries, the system comprising first and second cell schedulers, the first cell scheduler having a first priority and the second cell scheduler having a second priority, lower than the first priority, wherein the first and the second cell schedulers further comprise: a plurality of queues of a first type; at least one queue of a second type; and means for transferring virtual channel entries to and from each of said queues of a first type and a queue of a second type; wherein one of the queues of the first type is selected; if the selected queue has at least one entry, all entries of the first type are transferred from the selected queue to a queue of the second type; if the queue of the second type has at least one entry, an entry at a head of the queue of the second type is transmitted, the entry at the head of the queue of the second type having a step; if a period of time elapsed since the entry at the head of the queue of the second type was last transmitted is less than the step of the entry at the head of the queue of the second type, said entry at the head of the queue of the second type is appended to a tail of one of the queues of the first type; and if a period of time elapsed since the entry at the head of the queue of the second type was last transmitted is not less than the step of the entry at the head of the queue of the second type, the entry at the head of the queue of the second type is appended to a tail of the queue of the second type.
Claim 13
Dependent Claim
306 words
A scheduling system to be used in asynchronous time mode transfer of virtual channel entries, the system comprising first and second cell schedulers, wherein an output line of the first cell scheduler is coupled to an input line of the second cell scheduler and the first and the second cell schedulers further comprise: a plurality of queues of a first type; at least one queue of a second type; and means for transferring virtual channel entries to and from each of said queues of a first type and a queue of a second type; wherein one of the queues of the first type is selected; if the selected queue has at least one entry, all entries of the first type are transferred from the selected queue to a queue of the second type; if the queue of the second type has at least one entry, an entry at a head of the queue of the second type is transmitted, the entry at the head of the queue of the second type having a step; if a period of time elapsed since the entry at the head of the queue of the second type was last transmitted is less than the step of the entry at the head of the queue of the second type, said entry at the head of the queue of the second type is appended to a tail of one of the queues of the first type; and if a period of time elapsed since the entry at the head of the queue of the second type was last transmitted is not less than the step of the entry at the head of the queue of the second type, the entry at the head of the queue of the second type is appended to a tail of the queue of the second type.
Claim 14
Dependent Claim
306 words
A scheduling system to be used in asynchronous time mode transfer of virtual channel entries, the system comprising first and second cell schedulers, wherein an output line of the first cell scheduler is coupled to an input line of the second cell scheduler and the first and the second cell schedulers further comprise: a plurality of queues of a first type; at least one queue of a second type; and means for transferring virtual channel entries to and from each of said queues of a first type and a queue of a second type; wherein one of the queues of the first type is selected; if the selected queue has at least one entry, all entries of the first type are transferred from the selected queue to a queue of the second type; if the queue of the second type has at least one entry, an entry at a head of the queue of the second type is transmitted, the entry at the head of the queue of the second type having a step; if a period of time elapsed since the entry at the head of the queue of the second type was last transmitted is less than the step of the entry at the head of the queue of the second type, said entry at the head of the queue of the second type is appended to a tail of one of the queues of the first type; and if a period of time elapsed since the entry at the head of the queue of the second type was last transmitted is not less than the step of the entry at the head of the queue of the second type, the entry at the head of the queue of the second type is appended to a tail of the queue of the second type.
Claim 15
Dependent Claim
46 words
The system of claim 9, wherein each of the cell schedulers further comprises a plurality of virtual channel entries, and a virtual channel entry scheduled for immediate transmission on the first scheduler is transmitted before a virtual channel entry scheduled for transmission on the second scheduler.
References Cited (Backward Citations)
US2686844A
Cited
US4885744A
Cited
US5062106A
Cited
US5136584A
Cited
US5231633A
Cited
US5233606A
Cited
US5311509A
Cited
US5337308A
Cited
US5555264A
Cited
US5521923A
Cited
US5457687A
Cited
US5719853A
Cited
WO1995020282A1
Cited
US5555265A
Cited
US5577035A
Cited
US5592476A
Cited
WO1995032570A1
Cited
US5633867A
Cited
US5557611A
Cited
EP0700186A1
Cited
US5528588A
Cited
US5633859A
Cited
US5704047A
Cited
US5541912A
Cited
US5533020A
Cited
US5517495A
Cited
US5629928A
Cited
US5561663A
Cited
US5583863A
Cited
US5533009A
Cited
US5715250A
Cited
US5809024A
Cited
US5748629A
Cited
US5751951A
Cited
US5771234A
Cited
US5689508A
Cited
US5765032A
Cited
US5926458A
Cited
US5850399A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2003-03-21 | 2003-09-20 | 2004-03-21 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2007-03-21 | 2007-09-20 | 2008-03-21 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2011-03-21 | 2011-09-20 | 2012-03-21 | $7700.00 | Window Closed / Lapsed |