Patent US6128642A successfully refreshed from Google Patents.
US6128642A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Load balancing based on queue length, in a network of processor stations
Assignee: AT&T Inc
•
Filing: 1997-07-22
•
Granted: 2000-10-03
•
Expires: 2017-07-22
Abstract
Abstract A method for distributing a job load from a local processor station to at least one processor station within a plurality of processor stations connected by a multiaccess channel. A job is selected for remote execution from the local processor so that the average load value of the local processor station is reduced to the average load value of the processor station having the lowest average load value from a subset of processor stations. The average load value can be, for example, average utilization or average queue length.
Inventors
- 👤 Naganand Doraswamy
- 👤 Kadangode K. Ramakrishnan
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-30 19:52
CPC Classifications
G; G06; G06F; G06F9/00; G06F9/06; G06F9/46; G06F9/50; G06F9/5005; G06F9/5027; G06F9/505; G06F2209/00; G06F2209/50; G06F2209/5022
Claims Analysis
Total Claims: 19
Claim 1
Independent Claim
178 words
A method for distributing a job load from a local processor station to at least one processor station within a plurality of processor stations connected by a communications channel, comprising: (a) selecting at least one job for remote execution from the local processor station so that a load value of the local processor station is reduced to a target load value corresponding to an average load value of other processor stations in the plurality of processor stations; and (b) distributing the at least one job selected in step (a) to at least one processor station in the plurality of processor stations that has an average load value less than the load value of the local processor station by a threshold, the load value of the local processor station corresponding to an instantaneous queue length of the local processor station, the instantaneous queue length indicating the number of jobs awaiting processing at the local processor station, each average load value of other processor stations corresponding to a queue length for each respective processor station averaged over an announcement interval.
Claim 2
Independent Claim
178 words
A method for distributing a job load from a local processor station to at least one processor station within a plurality of processor stations connected by a communications channel, comprising: (a) selecting at least one job for remote execution from the local processor station so that a load value of the local processor station is reduced to a target load value corresponding to an average load value of other processor stations in the plurality of processor stations; and (b) distributing the at least one job selected in step (a) to at least one processor station in the plurality of processor stations that has an average load value less than the load value of the local processor station by a threshold, the load value of the local processor station corresponding to an instantaneous queue length of the local processor station, the instantaneous queue length indicating the number of jobs awaiting processing at the local processor station, each average load value of other processor stations corresponding to a queue length for each respective processor station averaged over an announcement interval.
Claim 3
Dependent Claim
68 words
The method of claim 1, further comprising: (c) selecting, from the plurality of processor stations, a subset of processor stations each having the average load value less than the load value for the local processor station by a threshold; wherein said distributing step (b) distributes the at least one job selected in step (a) among the processor stations in the subset of processor stations selected in step (c).
Claim 4
Dependent Claim
89 words
The method of claim 2, wherein a number of jobs selected for remote execution in step (a) is substantially equal to: ##EQU3## where: τ is an execution time needed to off-load the jobs to the subset of processor stations, y is an average servicing time per job executed over the announcement interval, p t is a processing time needed to decide whether to execute the jobs either locally or remotely, and o t is a fixed overhead time for transmitting one job to one processor station in the subset.
Claim 5
Dependent Claim
43 words
The method of claim 3, wherein the execution time, τ, is substantially equal to: ##EQU4## where: W is the announcement interval, N is the number of jobs that have been executed in a current announcement interval, and U is a target queue length.
Claim 6
Dependent Claim
48 words
The method of claim 2, wherein the at least one job is selected in step (a) so that the instantaneous queue length of the local processor station is reduced to substantially the average queue length of the processor station in the subset having the lowest average queue length.
Claim 7
Dependent Claim
36 words
The method of claim 2, further comprising: (d) receiving, over the communications channel, a multicast packet indicating the queue length of each remaining processor station in the plurality of processor stations, averaged over the announcement interval.
Claim 8
Dependent Claim
21 words
The method of claim 6, wherein said receiving step (d) is periodically repeated with updated queue length over the announcement interval.
Claim 9
Dependent Claim
32 words
The method of claim 2, wherein the at least one job is distributed in said step (b) to at least one target processor station within the subset of processor stations by random.
Claim 10
Dependent Claim
33 words
The method of claim 2, wherein the at least one job is distributed in said step (b) to at least one target processor station within the subset of processor stations by round robin.
Claim 11
Dependent Claim
17 words
The method of claim 1, wherein the at least job is selected in step (a) using hysteresis.
Claim 12
Dependent Claim
62 words
The method of claim 10, wherein the at least one job is selected in step (a) only when: (i) the number of packets associated with the at least one job is less than a high-level mark, and (ii) when the high-level mark was previously exceeded, the number of packets associated with the at least one job is less than a low-level mark.
Claim 13
Dependent Claim
30 words
The method of claim 2, further comprising: (d) sending, over the communications channel, a multicast packet indicating the queue length of the local processor station, averaged over the announcement interval.
Claim 14
Independent Claim
154 words
A system for balancing a job load within a network of processor stations, comprising: a communications channel; and a plurality of processor stations each being connected to said communications channel, each processor station having a processor, a computer-readable memory, an input port including a queue to be coupled to an input device, an output port to be coupled to an output device and a network port to be coupled to the communications channel; a local processor station selecting at least one job for remote execution so that an instantaneous queue length of the local processor station is reduced to an average queue length of other processor stations in the plurality of processor stations, the local processor station distributing the at least one job to at least one processor station in the plurality of processor stations that has an average load value less than the load value of the local processor station by a threshold.
Claim 15
Independent Claim
154 words
A system for balancing a job load within a network of processor stations, comprising: a communications channel; and a plurality of processor stations each being connected to said communications channel, each processor station having a processor, a computer-readable memory, an input port including a queue to be coupled to an input device, an output port to be coupled to an output device and a network port to be coupled to the communications channel; a local processor station selecting at least one job for remote execution so that an instantaneous queue length of the local processor station is reduced to an average queue length of other processor stations in the plurality of processor stations, the local processor station distributing the at least one job to at least one processor station in the plurality of processor stations that has an average load value less than the load value of the local processor station by a threshold.
Claim 16
Dependent Claim
64 words
The method of claim 13, wherein: the local processor selecting from said plurality of processor stations a subset of processor stations each having the average queue length less than the instantaneous queue length of the local processor station by a threshold, and the local processor distributing the at least one job among to at least one processor station in the subset of processor stations.
Claim 17
Independent Claim
167 words
An apparatus for distributing a job load from a local processor station to at least one processor station within a plurality of processor stations connected by a communications channel, comprising: means for selecting at least one job for remote execution from the local processor so that a load value of the local processor station is reduced to a target load value corresponding to an average load value of other processor stations in the plurality of processor stations, and means for distributing the at least one job among the processor stations that has an average load value less than the load value of the local processor station by a threshold, the load value of the local processor station corresponding to an instantaneous queue length of the local processor station, the instantaneous queue length indicating the number of jobs awaiting processing at the local processor station, each average load value of other processor stations corresponding to a queue length for each respective processor station averaged over an announcement interval.
Claim 18
Independent Claim
167 words
An apparatus for distributing a job load from a local processor station to at least one processor station within a plurality of processor stations connected by a communications channel, comprising: means for selecting at least one job for remote execution from the local processor so that a load value of the local processor station is reduced to a target load value corresponding to an average load value of other processor stations in the plurality of processor stations, and means for distributing the at least one job among the processor stations that has an average load value less than the load value of the local processor station by a threshold, the load value of the local processor station corresponding to an instantaneous queue length of the local processor station, the instantaneous queue length indicating the number of jobs awaiting processing at the local processor station, each average load value of other processor stations corresponding to a queue length for each respective processor station averaged over an announcement interval.
Claim 19
Dependent Claim
61 words
The apparatus of claim 15 further comprising: means for selecting, from the plurality of processor stations, a subset of processor stations each having the average load value less than the load value of the local processor station by a threshold; said distributing means distributes the at least one job to at least one processor station in the subset of processor stations.
References Cited (Backward Citations)
US5539883A
Cited
US5548724A
Cited
US5655120A
Cited
US5592672A
Cited
US5774668A
Cited
US5867706A
Cited
US5872972A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2003-10-03 | 2004-04-03 | 2004-10-03 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2007-10-03 | 2008-04-03 | 2008-10-03 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2011-10-03 | 2012-04-03 | 2012-10-03 | $7700.00 | Window Closed / Lapsed |