US6130878A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and apparatus for rate-based scheduling using a relative error approach
Assignee: Hewlett Packard Enterprise Development LP
•
Filing: 1995-12-27
•
Granted: 2000-10-10
•
Expires: 2015-12-27
Abstract
Abstract This disclosure presents a novel scheme for rate-based scheduling. In particular, this approach can be applicable to scheduling flows in computer networks such as ATM. It can also be used to provide weighted fair service in scheduling computer jobs. Unlike many of the methods commonly used for rate scheduling in network adapters, the present method allows to provide strict rate guarantees to all flows. A distinguishing feature of the present method is that it operates in the frequency domain, rather than in time domain.
Inventors
- 👤 Anna Charny
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-06 12:07
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/5629; H04L2012/5631; H04L2012/5632; H04L2012/5638; H04L2012/5646; H04L2012/5651; H04L2012/5678; H04L2012/5679
Claims Analysis
Total Claims: 12
Claim 1
Independent Claim
156 words
A method of rate-based scheduling of a plurality of data flows in a shared resource in a computer system, each of the data flows containing data cells, comprising the steps of: for each of the data flows in the plurality, providing, to a scheduler, an error term and a working frequency, the working frequency being an assigned rate of data flow relative to a total available bandwidth of the shared resource; scheduling, by the scheduler, each of the data flows on a per cell basis such that for each data flow the error term is substantially equal to the provided error term and each of the data flows achieves a long term average data now rate that is substantially equal to respective data flow's assigned rate of data flow said scheduler using the provided working frequency to define the error term per cell of the respective data flow, instead of using rate of the data flow.
Claim 2
Independent Claim
156 words
A method of rate-based scheduling of a plurality of data flows in a shared resource in a computer system, each of the data flows containing data cells, comprising the steps of: for each of the data flows in the plurality, providing, to a scheduler, an error term and a working frequency, the working frequency being an assigned rate of data flow relative to a total available bandwidth of the shared resource; scheduling, by the scheduler, each of the data flows on a per cell basis such that for each data flow the error term is substantially equal to the provided error term and each of the data flows achieves a long term average data now rate that is substantially equal to respective data flow's assigned rate of data flow said scheduler using the provided working frequency to define the error term per cell of the respective data flow, instead of using rate of the data flow.
Claim 3
Dependent Claim
137 words
The method of rate-based scheduling of data flows in the shared resource in the computer system according to claim 1 wherein the step of providing comprises the steps of: setting a value of a link cell slot to zero; setting a value of a virtual flow rate equal to the difference between the value of the available bandwidth in the shared resource and a value of a sum of the assigned rates of all the data flows; setting the assigned rate of data flow relative to the available bandwidth of the shared resource for each of the data flows to a quotient of the assigned rate of flow of each data flow and the total available bandwidth; and setting the error term for each data flow rate at link cell slot 0 to the value of zero.
Claim 4
Dependent Claim
204 words
The method of rate-based scheduling of data flows in the shared resource in the computer system according to claim 1 wherein the step of scheduling comprises the steps of: selecting a data flow dependent on the data flow's error term; determining whether the data flow and a cell of the data flow are available; sending a null cell if the step of determining determines that said data flow and said cell of the data flow are unavailable; transmitting said cell if the step of determining determines that said data flow and said cell of the data flow are available; incrementing a link cell slot; setting the error term for said data flow at said link cell slot equal to the error term for the data flow at the link cell slot plus the assigned rate of data flow relative to the available bandwidth minus 1; and for each of the data flows not equal to the data flow, the error term for each of the data flows at the link cell slot is set equal to each of the data flows' error term at the link cell slot plus each of the data flows' assigned rate of data flow relative to the available bandwidth.
Claim 5
Independent Claim
227 words
A method of rate-based scheduling of data flows in a shared resource in a computer system, each of the data flows containing data cells, comprising the steps of: providing an error term and an assigned rate of data flow relative to the available bandwidth of the shared resource for each of the data flows; scheduling each of the data flows such that each of the data flows' error term is substantially equal to the provided error term on a per data cell basis and each of the data flow achieves a long term average data flow that is substantially equal to each of the data flows' assigned rate of data flow; wherein said providing step comprises the steps of: setting a value of a link cell slot to zero; Setting a value of a virtual flow rate equal to the difference between the value of the available bandwidth in the shared resource and a value of a sum of the assigned rates of all the data flows; setting the assigned rate of data flow relative to the available bandwidth of the shared resource for each of the data flows to a quotient of the assigned rate of flow of each data flow and the total available bandwidth; and setting the error term for each data flow rate at link cell slot 0 to the value of zero.
Claim 6
Independent Claim
227 words
A method of rate-based scheduling of data flows in a shared resource in a computer system, each of the data flows containing data cells, comprising the steps of: providing an error term and an assigned rate of data flow relative to the available bandwidth of the shared resource for each of the data flows; scheduling each of the data flows such that each of the data flows' error term is substantially equal to the provided error term on a per data cell basis and each of the data flow achieves a long term average data flow that is substantially equal to each of the data flows' assigned rate of data flow; wherein said providing step comprises the steps of: setting a value of a link cell slot to zero; Setting a value of a virtual flow rate equal to the difference between the value of the available bandwidth in the shared resource and a value of a sum of the assigned rates of all the data flows; setting the assigned rate of data flow relative to the available bandwidth of the shared resource for each of the data flows to a quotient of the assigned rate of flow of each data flow and the total available bandwidth; and setting the error term for each data flow rate at link cell slot 0 to the value of zero.
Claim 7
Independent Claim
294 words
A method of rate-based scheduling of data flows in a shared resource in a computer system, each of the data flows containing data cells, comprising the steps of: providing an error term and an assigned rate of data flow relative to the available bandwidth of the shared resource for each of the data flows; scheduling each of the data flows such that each of the data flows' error term is substantially equal to the provided error term on a per data cell basis and each of the data flow achieves a long term average data flow that is substantially equal to each of the data flows' assigned rate of data flow; wherein said providing step comprises the steps of: selecting a data flow dependent on the data flow's error term; determining whether the data flow and a cell of the data flow are available; sending a null cell if the step of determining determines that said data flow and said cell of the data flow are unavailable; transmitting said cell if the step of determining determines that said data flow and said cell of the data flow are available; incrementing a link cell slot; setting the error term for said data flow at said link cell slot equal to the error term for the data flow at the link cell slot plus the assigned rate of data flow relative to the available bandwidth minus 1; and for each of the data flows not equal to the data flow, the error term for each of the data flows at the link cell slot is set equal to each of the data flows' error term at the link cell slot plus each of the data flows' assigned rate of data flow relative to the available bandwidth.
Claim 8
Independent Claim
294 words
A method of rate-based scheduling of data flows in a shared resource in a computer system, each of the data flows containing data cells, comprising the steps of: providing an error term and an assigned rate of data flow relative to the available bandwidth of the shared resource for each of the data flows; scheduling each of the data flows such that each of the data flows' error term is substantially equal to the provided error term on a per data cell basis and each of the data flow achieves a long term average data flow that is substantially equal to each of the data flows' assigned rate of data flow; wherein said providing step comprises the steps of: selecting a data flow dependent on the data flow's error term; determining whether the data flow and a cell of the data flow are available; sending a null cell if the step of determining determines that said data flow and said cell of the data flow are unavailable; transmitting said cell if the step of determining determines that said data flow and said cell of the data flow are available; incrementing a link cell slot; setting the error term for said data flow at said link cell slot equal to the error term for the data flow at the link cell slot plus the assigned rate of data flow relative to the available bandwidth minus 1; and for each of the data flows not equal to the data flow, the error term for each of the data flows at the link cell slot is set equal to each of the data flows' error term at the link cell slot plus each of the data flows' assigned rate of data flow relative to the available bandwidth.
Claim 9
Independent Claim
145 words
A method of rate-based scheduling of a plurality of data flows in a shared resource in a computer system, each of the data flows containing data cells, comprising the steps of: for each of the data flows in the plurality, storing, in a scheduler, a respective error term equal to a relative error in transmission time between an actual scheduling time and an ideal scheduling time accumulated by the data flow at the beginning of a link cell slot and an assigned rate of flow relative to a total available bandwidth of the shared resource; and scheduling, by the scheduler, on a per cell basis each of the data flows as a function of the data flow's error term such that each of the data flows achieves a long term average flow rate that is substantially equal to that data flow's assigned rate of flow.
Claim 10
Independent Claim
145 words
A method of rate-based scheduling of a plurality of data flows in a shared resource in a computer system, each of the data flows containing data cells, comprising the steps of: for each of the data flows in the plurality, storing, in a scheduler, a respective error term equal to a relative error in transmission time between an actual scheduling time and an ideal scheduling time accumulated by the data flow at the beginning of a link cell slot and an assigned rate of flow relative to a total available bandwidth of the shared resource; and scheduling, by the scheduler, on a per cell basis each of the data flows as a function of the data flow's error term such that each of the data flows achieves a long term average flow rate that is substantially equal to that data flow's assigned rate of flow.
Claim 11
Dependent Claim
138 words
The method of rate-based scheduling of data flows in the shared resource in the computer system according to claim 6 wherein the step of providing comprises the steps of: setting a value of the link cell slot to zero; setting a value of a virtual flow rate equal to a difference between a value of available bandwidth in the shared resource and a value of a sum of the assigned rates of flow of all of the data flows; setting the assigned rate of flow relative to the total available bandwidth of the shared resource for each of the data flows to a quotient of the assigned rate of flow of each data flow and the total available bandwidth; and setting the error term for each data flow at link cell slot zero to the value of zero.
Claim 12
Dependent Claim
204 words
The method of rate-based scheduling of data flows in the shared resource in the computer system according to claim 6 wherein the step of scheduling comprises the steps of: selecting a data flow dependent on the data flow's error term; determining whether the data flow and a cell of the data flow are available; sending a null cell if the step of determining determines that said data flow and said cell of the data flow are unavailable; transmitting said cell if the step of determining determines that said data flow and said cell of the data flow are available; incrementing said link cell slot; setting the error term for said data flow at said link cell slot equal to the error term for the data flow at the link cell slot plus the assigned rate of data flow relative to the available bandwidth minus 1; and for each of the data flows not equal to the data flow, the error term for each of the data flows at the link cell slot is set equal to each of the data flows' error term at the link cell slot plus each of the data flows' assigned rate of data flow relative to the available bandwidth.
References Cited (Backward Citations)
US4807116A
Cited
US5301333A
Cited
US5367678A
Cited
US5528513A
Cited
US5506969A
Cited
JPH07221768A
Cited
EP0669777A1
Cited
US5577035A
Cited
US5392280A
Cited
US5434860A
Cited
US5555244A
Cited
US5566163A
Cited
US5619502A
Cited
US5602830A
Cited
US5533020A
Cited
US5533009A
Cited
JPH09130398A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2003-10-10 | 2004-04-10 | 2004-10-10 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2007-10-10 | 2008-04-10 | 2008-10-10 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2011-10-10 | 2012-04-10 | 2012-10-10 | $7700.00 | Window Closed / Lapsed |