Load balancing based on queue length, in a network of processor stations

• US 6,128,642 A
• Filed: 07/22/1997
• Issued: 10/03/2000
• Est. Priority Date: 07/22/1997
• Status: Expired due to Term

• Current Assignee: AT&T Corporation (AT&T, Inc.)
• Original Assignee: AT&T Corporation (AT&T, Inc.)
• Inventors: Ramakrishnan, Kadangode K., Doraswamy, Naganand
• Primary Examiner(s): Matar, Ahmad F.
• Assistant Examiner(s): Barot, Bharat
• Application Number:
  US08/898,074
• Time in Patent Office: 1,169 Days
• Field of Search: 709/102, 709/105, 709/200-203, 709/217-219, 709/223-228, 709/238, 709/314
• US Class Current: 709/201
• CPC Class Codes: G06F 2209/5022 Workload threshold
• CPC Class Codes: G06F 9/505 considering the load

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.

Claims

1. 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.

2. 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).

3. 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.

4. 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.

5. 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.

6. 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.

7. The method of claim 6, wherein said receiving step (d) is periodically repeated with updated queue length over the announcement interval.

8. 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.

9. 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.

10. The method of claim 1, wherein the at least job is selected in step (a) using hysteresis.

11. 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.

12. 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.

13. 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.

14. 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.

15. 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.

16. 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.