US5844890A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Communications cell scheduler and scheduling method for providing proportional use of network bandwith
Assignee: International Business Machines Corp
•
Filing: 1997-03-25
•
Granted: 1998-12-01
•
Expires: 2017-03-25
Abstract
Abstract A method and apparatus are provided for scheduling the transmission of cells of a plurality of data streams in a communications network. A best effort scheduler is provided for scheduling the transmission of cells of a plurality of data streams in a communications network. The best effort scheduler includes a best effort operational mode and can include more than one timing wheel. When the best effort scheduler includes more than one timing wheel, then the priority of the best effort timing wheel is lower than the priority of the other timing wheel or wheels. Data of each data stream is enqueued to a corresponding data cell queue. A target next transmission time for each data cell queue is calculated utilizing predetermined logical channel descriptor parameters. A lower priority or a higher priority timing wheel is selected and a timing wheel time slot is calculated based on an identified target transmission time for each active data cell queue. An active indication is set for the identified timing wheel time slot and an entry is stored to point to the corresponding data cell queue for the identified timing wheel time slot. The relative rates between data streams are maintained, while the absolute rates of the data streams are increased or decreased in the low priority wheel. Scheduling opportunities can be defined utilizing a predefined pseudo data cell queue. Then the calculation of the target transmission time for each data cell queue includes the predefined pseudo data cell queue, and the identified target transmission time for the predefined pseudo data cell queue defines scheduling opportunities of multiple timing wheel time slots.
Inventors
- 👤 Gary Scott Delp
- 👤 Philip Lynn Leichty
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-25 01:07
CPC Classifications
H; H04; H04L; H04L12/00; H04L12/54; H04L12/56; H04L12/5601; H04L12/5602; H04L12/28; H04L2012/5638; H04L2012/5646; H04L2012/5651; H04L2012/5678; H04L2012/5679
Claims Analysis
Total Claims: 25
Claim 1
Independent Claim
240 words
A method for scheduling the transmission of cells of a plurality of data streams in a communications network comprising the steps of: enqueuing data of each data stream to a corresponding data cell queue; calculating a target transmission time for each said data cell queue utilizing predetermined logical scheduling rate parameters of each data stream; including the steps of maintaining peak transmission rate and sustainable transmission rate connection parameters in terms of timing wheel time slot intervals and utilizing a calculation algorithm represented by: New timestamp=MAX(old timestamp+sustained interval, current time-burst limit); responsive to each said calculated next target transmission time, calculating a timing wheel time slot in a timing wheel, setting an active indication for said identified timing wheel time slot and storing an entry to point to said corresponding data cell queue for said identified timing wheel time slot; selecting a next data cell queue for transmission by checking for said active indication in a current timing wheel time slot of said timing wheel; responsive to identifying said active indication, processing a first data cell queue for transmission and rescheduling said data cell queue; moving to a next timing wheel time slot by checking for an active indication in a current frame of active indicators corresponding to timing wheel time slots of said timing wheel; and responsive to identifying said active indication in said current frame, moving to a first active timing wheel time slot in said current frame.
Claim 2
Independent Claim
240 words
A method for scheduling the transmission of cells of a plurality of data streams in a communications network comprising the steps of: enqueuing data of each data stream to a corresponding data cell queue; calculating a target transmission time for each said data cell queue utilizing predetermined logical scheduling rate parameters of each data stream; including the steps of maintaining peak transmission rate and sustainable transmission rate connection parameters in terms of timing wheel time slot intervals and utilizing a calculation algorithm represented by: New timestamp=MAX(old timestamp+sustained interval, current time-burst limit); responsive to each said calculated next target transmission time, calculating a timing wheel time slot in a timing wheel, setting an active indication for said identified timing wheel time slot and storing an entry to point to said corresponding data cell queue for said identified timing wheel time slot; selecting a next data cell queue for transmission by checking for said active indication in a current timing wheel time slot of said timing wheel; responsive to identifying said active indication, processing a first data cell queue for transmission and rescheduling said data cell queue; moving to a next timing wheel time slot by checking for an active indication in a current frame of active indicators corresponding to timing wheel time slots of said timing wheel; and responsive to identifying said active indication in said current frame, moving to a first active timing wheel time slot in said current frame.
Claim 3
Dependent Claim
93 words
A method for scheduling the transmission of cells of a plurality of data streams in a communications network as recited in claim 1 further include the step of defining scheduling opportunities utilizing a predefined pseudo data cell queue; and wherein said step of calculating said target transmission time for each said data cell queue utilizing predetermined logical scheduling rate parameters of each data stream includes said predefined pseudo data cell queue, and said identified target transmission time for said predefined pseudo data cell queue defining scheduling opportunities of multiple timing wheel time slots.
Claim 4
Dependent Claim
44 words
A method for scheduling the transmission of cells of a plurality of data streams in a communications network as recited in claim 1 includes the step of: responsive to an absence of said active indication in said current frame, and reading a next frame.
Claim 5
Dependent Claim
89 words
A method for scheduling the transmission of cells of a plurality of data streams in a communications network as recited in claim 1 wherein the step of moving to said next timing wheel time slot by checking for said active indication in said current frame of timing time slots of said timing wheel includes the steps of identifying a next available time slot having said entry for said corresponding data cell queue within a block of timing wheel time slots, and moving to said identified next available time slot.
Claim 6
Dependent Claim
50 words
A method for scheduling the transmission of cells of a plurality of data streams in a communications network as recited in claim 1 wherein the step of calculating said time slot in said timing wheel includes utilizing a calculation algorithm represented by: New time slot=MAX(timestamp+sustained interval, current time+peak interval). 6.
Claim 7
Dependent Claim
52 words
A method for scheduling the transmission of cells of a plurality of data streams in a communications network as recited in claim 5 wherein the step of processing lower priority timing wheel entries includes the step of moving an entry from said lower priority timing wheel to said higher priority timing wheel.
Claim 8
Dependent Claim
81 words
A method for scheduling the transmission of cells of a plurality of data streams in a communications network as recited in claim 3 further includes the steps of selecting a higher priority timing wheel or a lower priority timing wheel for each said calculated next target transmission time for each said data cell queue, and wherein the step of responsive to said absence of said active indication in said current frame, includes the step of processing lower priority timing wheel entries.
Claim 9
Dependent Claim
51 words
A method for scheduling the transmission of cells of a plurality of data streams in a communications network as recited in claim 7 wherein the step of processing lower priority timing wheel entries includes the step of checking for completion of first wheel processing of a portion of said current frame.
Claim 10
Dependent Claim
57 words
A method for scheduling the transmission of cells of a plurality of data streams in a communications network as recited in claim 7 wherein the step of processing lower priority timing wheel entries includes the step of moving an entry from said lower priority timing wheel to a new time slot of said lower priority timing wheel.
Claim 11
Dependent Claim
56 words
A method for scheduling the transmission of cells of a plurality of data streams in a communications network as recited in claim 7 wherein the step of processing lower priority timing wheel entries includes the step of moving a portion of said current frame of said higher priority time wheel from the past to the future.
Claim 12
Dependent Claim
52 words
A method for scheduling the transmission of cells of a plurality of data streams in a communications network as recited in claim 7 wherein the step of processing lower priority timing wheel entries includes the step of moving a portion of said lower priority timing wheel from the past to the future.
Claim 13
Dependent Claim
267 words
Apparatus for scheduling the transmission of cells of a plurality of data streams in a communications network comprising: means for enqueuing data of each data stream to a corresponding data cell queue; means for calculating a target transmission time for each said data cell queue utilizing predetermined logical scheduling rate parameters of each data stream; said target transmission time calculating means including means for maintaining peak transmission rate and sustainable transmission rate connection parameters in terms of timing wheel time slot intervals and means for utilizing a calculation algorithm represented by: New timestamp=MAX(old timestamp+sustained interval, current time-burst limit); means responsive to each said calculated next target transmission time, means for calculating a timing wheel time slot in a timing wheel, means for setting an active indication for said identified timing wheel time slot and means for storing an entry to point to said corresponding data cell queue for said identified timing wheel time slot; means for selecting a next data cell queue for transmission including means for checking for said active indication in a current timing wheel time slot of said first timing wheel; means, responsive to identifying said active indication, for processing a first data cell queue for transmission and rescheduling said data cell queue; means for moving to a next timing wheel time slot including means for checking for an active indication in a current frame of active indications corresponding to timing wheel time slots of said timing wheel; and means, responsive to identifying said active indication in said current frame, for moving to a first active timing wheel time slot in said current frame.
Claim 14
Dependent Claim
267 words
Apparatus for scheduling the transmission of cells of a plurality of data streams in a communications network comprising: means for enqueuing data of each data stream to a corresponding data cell queue; means for calculating a target transmission time for each said data cell queue utilizing predetermined logical scheduling rate parameters of each data stream; said target transmission time calculating means including means for maintaining peak transmission rate and sustainable transmission rate connection parameters in terms of timing wheel time slot intervals and means for utilizing a calculation algorithm represented by: New timestamp=MAX(old timestamp+sustained interval, current time-burst limit); means responsive to each said calculated next target transmission time, means for calculating a timing wheel time slot in a timing wheel, means for setting an active indication for said identified timing wheel time slot and means for storing an entry to point to said corresponding data cell queue for said identified timing wheel time slot; means for selecting a next data cell queue for transmission including means for checking for said active indication in a current timing wheel time slot of said first timing wheel; means, responsive to identifying said active indication, for processing a first data cell queue for transmission and rescheduling said data cell queue; means for moving to a next timing wheel time slot including means for checking for an active indication in a current frame of active indications corresponding to timing wheel time slots of said timing wheel; and means, responsive to identifying said active indication in said current frame, for moving to a first active timing wheel time slot in said current frame.
Claim 15
Dependent Claim
91 words
Apparatus for scheduling the transmission of cells of a plurality of data streams in a communications network as recited in claim 12 further includes means for defining scheduling opportunities utilizing a predefined pseudo data cell queue; and wherein said means for calculating said target transmission time for each said data cell queue utilizing predetermined logical scheduling rate parameters of each data stream includes said predefined pseudo data cell queue, and said identified target transmission time for said predefined pseudo data cell queue defining scheduling opportunities of multiple timing wheel time slots.
Claim 16
Dependent Claim
42 words
Apparatus for scheduling the transmission of cells of a plurality of data streams in a communications network as recited in claim 12 further includes means, responsive to an absence of said active indication in said current frame, for reading a next frame.
Claim 17
Dependent Claim
96 words
Apparatus for scheduling the transmission of cells of a plurality of data streams in a communications network as recited in claim 14 further includes means for selecting a higher priority timing wheel or a lower priority timing wheel for each said calculated next target transmission time for each said data cell queue, and wherein said means, responsive to an absence of said active indication in said current frame, further includes means for processing lower priority timing wheel entries including means for moving an entry from said lower priority timing wheel to said higher priority timing wheel.
Claim 18
Dependent Claim
50 words
Apparatus for scheduling the transmission of cells of a plurality of data streams in a communications network as recited in claim 15 wherein said means for processing lower priority timing wheel entries include means for checking for completion of higher priority wheel processing of a portion of said current frame.
Claim 19
Dependent Claim
302 words
A computer program product for use in a data communications network having a cell scheduler for scheduling the transmission of cells of a plurality of data streams in said communications network, the computer program product comprising: a record medium; means, recorded on said recording medium, for storing a corresponding data cell queue for each of the plurality of data streams; means, recorded on said recording medium, for storing predetermined logical channel control parameter values for each data cell queue; means, recorded on said recording medium, for calculating a next target transmission time for each data cell queue; said target transmission time calculating means including means for maintaining peak transmission rate and sustainable transmission rate connection parameters in terms of timing wheel time slot intervals and means for utilizing a calculation algorithm represented by: New timestamp=MAX(old timestamp+sustained interval, current time-burst limit); means, recorded on said recording medium, for calculating a timing wheel time slot in a timing wheel, for setting an active indication for said identified timing wheel time slot, and for storing an entry to point to said corresponding data cell queue for said identified timing wheel time slot; means, recorded on said recording medium, for selecting a next data cell queue for transmission including means for checking for said active indication in a current timing wheel time slot of said timing wheel; means, responsive to identifying said active indication, for processing a first data cell queue for transmission and rescheduling said data cell queue; means for moving to a next timing wheel time slot including means for checking for an active indication in a current frame of timing wheel time slots of said timing wheel; and means, responsive to identifying said active indication in said current frame, for moving to a first active timing wheel time slot in said current frame.
Claim 20
Dependent Claim
302 words
A computer program product for use in a data communications network having a cell scheduler for scheduling the transmission of cells of a plurality of data streams in said communications network, the computer program product comprising: a record medium; means, recorded on said recording medium, for storing a corresponding data cell queue for each of the plurality of data streams; means, recorded on said recording medium, for storing predetermined logical channel control parameter values for each data cell queue; means, recorded on said recording medium, for calculating a next target transmission time for each data cell queue; said target transmission time calculating means including means for maintaining peak transmission rate and sustainable transmission rate connection parameters in terms of timing wheel time slot intervals and means for utilizing a calculation algorithm represented by: New timestamp=MAX(old timestamp+sustained interval, current time-burst limit); means, recorded on said recording medium, for calculating a timing wheel time slot in a timing wheel, for setting an active indication for said identified timing wheel time slot, and for storing an entry to point to said corresponding data cell queue for said identified timing wheel time slot; means, recorded on said recording medium, for selecting a next data cell queue for transmission including means for checking for said active indication in a current timing wheel time slot of said timing wheel; means, responsive to identifying said active indication, for processing a first data cell queue for transmission and rescheduling said data cell queue; means for moving to a next timing wheel time slot including means for checking for an active indication in a current frame of timing wheel time slots of said timing wheel; and means, responsive to identifying said active indication in said current frame, for moving to a first active timing wheel time slot in said current frame.
Claim 21
Dependent Claim
101 words
A computer program product for use in a data communications network having a cell scheduler for scheduling the transmission of cells of a plurality of data streams as recited in claim 17 further includes means, recorded on said recording medium, for defining scheduling opportunities utilizing a predefined pseudo data cell queue; and wherein said means, recorded on said recording medium, for calculating said target transmission time for each said data cell queue includes said predefined pseudo data cell queue, and said identified target transmission time for said predefined pseudo data cell queue defining scheduling opportunities of multiple timing wheel time slots.
Claim 22
Dependent Claim
69 words
A computer program product for use in a data communications network having a cell scheduler for scheduling the transmission of cells of a plurality of data streams as recited in claim 17 wherein said means, recorded on said recording medium, for selecting said next data cell queue for transmission further includes means, responsive to an absence of said active indication in said current frame, for reading a next frame.
Claim 23
Dependent Claim
106 words
A computer program product for use in a data communications network having a cell scheduler for scheduling the transmission of cells of a plurality of data streams as recited in claim 19 further includes means for selecting a higher priority timing wheel or a lower priority timing wheel for each said calculated next target transmission time for each said data cell queue, and wherein said means, responsive to an absence of said active indication in said current frame, further includes means for processing lower priority timing wheel entries including means for moving an entry from said lower priority timing wheel to said higher priority timing wheel.
Claim 24
Dependent Claim
286 words
A best effort scheduler for scheduling the transmission of cells of a plurality of data streams in a communications network comprising: memory means for storing a corresponding data cell queue for each of the plurality of data streams; means for storing predetermined logical channel control parameter values for each data cell queue, means for calculating a target transmission time for each said data cell queue utilizing predetermined logical scheduling rate parameters of each data stream; said target transmission time calculating means including means for maintaining peak transmission rate and sustainable transmission rate connection parameters in terms of timing wheel time slot intervals and means for utilizing a calculation algorithm represented by: New timestamp=MAX(old timestamp+sustained interval, current time-burst limit); means responsive to each said calculated next target transmission time, for calculating a timing wheel time slot in a timing wheel, means for setting an active indication for said identified timing wheel time slot and means for storing an entry to point to said corresponding data cell queue for said identified timing wheel time slot; means for selecting a next data cell queue for transmission including means for checking for said active indication in a current timing wheel time slot of said first timing wheel; means, responsive to identifying said active indication, for processing a first data cell queue for transmission and rescheduling said data cell queue; means for moving to a next timing wheel time slot including means for checking for an active indication in a current frame of active indications corresponding to timing wheel time slots of said timing wheel; and means, responsive to identifying said active indication in said current frame, for moving to a first active timing wheel time slot in said current frame.
Claim 25
Dependent Claim
286 words
A best effort scheduler for scheduling the transmission of cells of a plurality of data streams in a communications network comprising: memory means for storing a corresponding data cell queue for each of the plurality of data streams; means for storing predetermined logical channel control parameter values for each data cell queue, means for calculating a target transmission time for each said data cell queue utilizing predetermined logical scheduling rate parameters of each data stream; said target transmission time calculating means including means for maintaining peak transmission rate and sustainable transmission rate connection parameters in terms of timing wheel time slot intervals and means for utilizing a calculation algorithm represented by: New timestamp=MAX(old timestamp+sustained interval, current time-burst limit); means responsive to each said calculated next target transmission time, for calculating a timing wheel time slot in a timing wheel, means for setting an active indication for said identified timing wheel time slot and means for storing an entry to point to said corresponding data cell queue for said identified timing wheel time slot; means for selecting a next data cell queue for transmission including means for checking for said active indication in a current timing wheel time slot of said first timing wheel; means, responsive to identifying said active indication, for processing a first data cell queue for transmission and rescheduling said data cell queue; means for moving to a next timing wheel time slot including means for checking for an active indication in a current frame of active indications corresponding to timing wheel time slots of said timing wheel; and means, responsive to identifying said active indication in said current frame, for moving to a first active timing wheel time slot in said current frame.
References Cited (Backward Citations)
US4839831A
Cited
US5274768A
Cited
US5381407A
Cited
US5359592A
Cited
US5694548A
Cited
US5579312A
Cited
US5533020A
Cited
US5629928A
Cited
US5533021A
Cited
US5537408A
Cited
US5533009A
Cited
US5625625A
Cited
US5610921A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2001-11-30 | 2002-06-01 | 2002-12-01 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2005-11-30 | 2006-06-01 | 2006-12-01 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2009-11-30 | 2010-06-01 | 2010-12-01 | $7700.00 | Window Closed / Lapsed |