Load balancing method and system based on estimated elongation rates

• US 6,986,139 B1
• Filed: 10/06/2000
• Issued: 01/10/2006
• Est. Priority Date: 10/06/1999
• Status: Expired due to Fees

• Current Assignee: NEC Corporation
• Original Assignee: NEC Corporation
• Inventors: Kubo, Hidehito
• Primary Examiner(s): An, Meng-Al T.
• Assistant Examiner(s): Opie, George L
• Application Number:
  US09/680,517
• Time in Patent Office: 1,922 Days
• Field of Search: 718/105, 709/223
• US Class Current: 718/105
• CPC Class Codes: G06F 2209/5019 Workload prediction
• CPC Class Codes: G06F 9/505 considering the load

Abstract

A dynamic load balancing method allowing a transaction processing load is balanced among computers by using estimated elongation rates is disclosed. In a system composed of a plurality of computers for processing transaction processing requests originating from a plurality of terminals, elongation rates of processing time for respective ones of the computers are estimated, where an elongation rate is a ratio of a processing time required for processing a transaction to a net processing time which is a sum of CPU time and an input/output time for processing the transaction. After calculating load indexes of respective ones of the computers based on the estimated elongation rates, a destination computer is selected from the computers based on the load indexes, wherein the destination computer having a minimum one among the load indexes.

Claims

1. A load balancing method in a system comprising a plurality of computers for processing transaction processing requests originating from a plurality of terminals, comprising steps of:

a) estimating load states of respective ones of the plurality of computers;

b) determining estimated elongation rates of processing time for respective ones of the plurality of computers based on the estimated load states, the estimated elongation rates being estimates of a ratio of job processing response time, including queuing time, to total processing time;

c) calculating load indexes of respective ones of the plurality of computers based on the estimated elongation rates; and

d) determining load distribution among the plurality of computers based on the load indexes;

wherein the step (a) comprises the steps of;

a.1) measuring load data of each of the plurality of computers at constant intervals; and

a.2) estimating a load state of each of the plurality of computers based on the load data;

wherein,

in the step (a), a current number of in-process transactions in each of the plurality of computers is measured in response to start and termination of transaction processing at each of the plurality of computers,

in the step (b), an estimated elongation rate of processing time for each of the plurality of computers is determined based on the estimated current load state and the current number of in-process transactions in the computer; and

wherein the step (b) comprises the steps of;

b.1) correcting the estimated load states using current numbers of in-process transactions for respective ones of the plurality of computers to produce corrected estimated load states; and

b.2) determining said estimated elongation rates of processing time for respective ones of the plurality of computers based on the corrected estimated current load states.

2. The load balancing method according to claim 1, wherein the steps (a) through (d) are sequentially performed when a transaction processing request has been received from a terminal,

wherein, in the step (d), one of the plurality of computers is selected based on the load indexes as an execution computer processing the transaction processing request.

3. The load balancing method according to claim 1, wherein, in the step (a.1), a number of in-process transactions and a number of job processing processes staying in a CPU system of the computer are measured as the load data measured at constant intervals.

4. The load balancing method according to claim 1, wherein, in the step (a.1), a number of in-process transactions and a CPU utilization of the computer are measured as the load data measured at constant intervals.

5. The load balancing method according to claim 1, wherein, in the step (c), an estimated elongation rate is used as a load index of each of the plurality of computers.

6. The load balancing method according to claim 1, wherein, in the step (c), an estimated elongation rate is one of a before-scheduling estimated elongation rate and an after-scheduling estimated elongation rate,

wherein the before-scheduling estimated elongation rate is an estimated elongation rate calculated from a corresponding estimated load state before the transaction processing request is allocated to respective ones of the plurality of computers, and

the after-scheduling estimated elongation rate is an estimated elongation rate calculated from a corresponding estimated load state after the transaction processing request is allocated to respective ones of the plurality of computers.

7. The load balancing method according to claim 6, wherein the step (c) comprises the steps of:

c.1) multiplying the estimated elongation rate of each of the plurality of computers by a current number of in-process transactions in the computer to produce a total estimated elongation rate of the computer; and

c.2) determining the total estimated elongation rate as a load index of the computer.

8. The load balancing method according to claim 6, wherein the step (c) comprises the steps of:

c.1) multiplying the estimated elongation rate of each of the plurality of computers by a current number of in-process transactions in the computer to produce a total estimated elongation rate of the computer;

c.2) calculating a total estimated elongation rate difference between an after-scheduling total estimated elongation rate and a before-scheduling total estimated elongation rate of each of the plurality of computers; and

c.3) determining the total estimated elongation rate difference as a load index of the computer.

9. A load balancing system comprising:

a plurality of terminals, each of said plurality of terminals being adapted to originate a transaction processing request;

a plurality of computers, each of said plurality of computers being adapted to process a plurality of transaction processing requests originating from a plurality of terminals in parallel;

a load estimator for estimating load states of respective ones of the plurality of computers;

a load data memory for storing the estimated load states; and

an execution computer selector for selecting one of the plurality of computers as an execution computer to be put in charge of processing a transaction processing request based on load indexes of respective ones of the plurality of computers, wherein the load indexes are calculated from estimated elongation rates of processing time for respective ones of the plurality of computers, wherein the estimated elongation rates are determined based on the estimated load states and are estimates of a ratio of job processing response time, including queuing time, to total processing time;

wherein the load estimator measures load data of each of the plurality of computers at constant intervals and estimates a load state of each of the plurality of computers based on the load data;

wherein the load estimator measures a current number of in-process transactions in each of the plurality of computers in response to start and termination of transaction processing at each of the plurality of computers;

wherein the execution computer selector determines an estimated elongation rate of processing time for each of the plurality of computers based on the estimated current load state and the current number of in-process transactions in the computer; and

wherein the execution computer selector corrects the estimated load states using the current numbers of in-process transactions for respective ones of the plurality of computers to produce corrected estimated load states, and determines estimated elongation rates of processing time for respective ones of the plurality of computers based on the corrected estimated current load states.

10. The load balancing system according to claim 9, wherein the execution computer selector is started up when a transaction processing request has been received from a terminal and then selects one of the plurality of computers based on the load indexes as an execution computer processing the transaction processing request.

11. The load balancing system according to claim 9, wherein the load estimator measures a number of in-process transactions and a number of job processing processes staying in a CPU system of the computer as the load data measured at constant intervals.

12. The load balancing system according to claim 9, wherein the load estimator measures a number of in-process transactions and a CPU utilization of the computer as the load data measured at constant intervals.

13. The load balancing system according to claim 9, wherein the execution computer selector uses an estimated elongation rate as a load index of each of the plurality of computers.

14. The load balancing system according to claim 9, wherein an estimated elongation rate is one of a before-scheduling estimated elongation rate and an after-scheduling estimated elongation rate,

wherein the before-scheduling estimated elongation rate is an estimated elongation rate calculated from a corresponding estimated load state before the transaction processing request is allocated to respective ones of the plurality of computers, and

the after-scheduling estimated elongation rate is an estimated elongation rate calculated from a corresponding estimated load state after the transaction processing request is allocated to respective ones of the plurality of computers.

15. The load balancing system according to claim 14, wherein the execution computer selector multiplies the estimated elongation rate of each of the plurality of computers by a current number of in-process transactions in the computer to produce a total estimated elongation rate of the computer, and determines the total estimated elongation rate as a load index of the computer.

16. The load balancing system according to claim 14, wherein the execution computer selector multiplies the estimated elongation rate of each of the plurality of computers by a current number of in-process transactions in the computer to produce a total estimated elongation rate of the computer, calculates a total estimated elongation rate difference between an after-scheduling total estimated elongation rate and a before-scheduling total estimated elongation rate of each of the plurality of computers, and determines the total estimated elongation rate difference as a load index of the computer.

17. The load balancing system according to claim 9, further comprising:

a control node connected between the terminals and the plurality of computers, wherein the control node includes the load estimator, the load data memory, and the execution computer selector.

18. The load balancing system according to claim 9, further comprising:

a switching device connecting the plurality of computers to each other,

wherein each of the plurality of computers includes the load estimator, the load data memory, and the execution computer selector, wherein an estimated load state estimated at a computer is transferred to all other computers through the switching device so that the load state memory of each of the plurality of computers stores same load state data.

19. The load balancing system according to claim 9, further comprising:

a switching device connecting the plurality of computers to each other, the switching device including the load data memory which is shared among the plurality of computers,

wherein each of the plurality of computers includes the load estimator and the execution computer selector, wherein an estimated load state estimated at a computer is transferred to the switching device to be stored in the load state memory.

20. A load balancing system according to claim 9, wherein the execution computer selector selects a computer to which the execution computer selector belongs when the load index of the computer is smaller than a value obtained by multiplying a minimum load index among the plurality of computers by a predetermined factor greater than 1.

21. A load balancing system comprising:

a plurality of terminals, each of said plurality of terminals being adapted to originate a transaction processing request;

a plurality of computers, each of said plurality of computers being adapted to process a plurality of transaction processing requests originating from a plurality of terminals in parallel;

a load estimator for estimating load states of respective ones of the plurality of computers;

a load data memory for storing the estimated load states; and

an execution computer selector for selecting one of the plurality of computers as an execution computer to be nut in charge of processing a transaction processing request based on load indexes of respective ones of the plurality of computers, wherein the load indexes are calculated from estimated elongation rates of processing time for respective ones of the plurality of computers, wherein the estimated elongation rates are determined based on the estimated load states and are estimates of a ratio of job processing response time, including queuing time, to total processing time;

wherein the load estimator measures load data of each of the plurality of computers at constant intervals and estimates a load state of each of the plurality of computers based on the load data;

wherein the load estimator measures a current number of in-process transactions in each of the plurality of computers in response to start and termination of transaction processing at each of the plurality of computers;

wherein the execution computer selector determines an estimated elongation rate of processing time for each of the plurality of computers based on the estimated current load state and the current number of in-process transactions in the computer;

wherein the load estimator measures load data of each of the plurality of computers at constant intervals to produce a sequence of load data, and estimates a current load state of each of the plurality of computers based on the sequence of load data; and

wherein the execution computer selector corrects the estimated load states using the current numbers of in-process transactions for respective ones of the plurality of computers to produce corrected estimated load states, and determines estimated elongation rates of processing time for respective ones of the plurality of computers based on the corrected estimated current load states.

22. A load balancing system comprising;

a plurality of terminals, each of said plurality of terminals being adapted to originate a transaction processing request;

a plurality of computers, each of said plurality of computers being adapted to process a plurality of transaction processing requests originating from a plurality of terminals in parallel;

a load estimator for estimating load states of respective ones of the plurality of computers;

a load data memory for storing the estimated load states;

an execution computer selector for selecting one of the plurality of computers as an execution computer to be put in charge of processing a transaction processing request based on load indexes of respective ones of the plurality of computers, wherein the load indexes are calculated from estimated elongation rates of processing time for respective ones of the plurality of computers, wherein the estimated elongation rates are determined based on the estimated load states and are estimates of a ratio of job processing response time, including queuing time, to total processing time; and

a switching device connecting the plurality of computers to each other,

wherein each of the plurality of computers includes the load estimator, the load data memory, and the execution computer selector, wherein an estimated load state estimated at a computer is transferred to all other computers through the switching device so that the load state memory of each of the plurality of computers stores same load state data; and

wherein the execution computer selector selects a computer to which the execution computer selector belongs when the load index of the computer is smaller than a value obtained by multiplying a minimum load index among the plurality of computers by a predetermined factor greater than 1.

23. A load balancing system comprising:

a plurality of terminals, each of which originates said plurality of terminals being adapted to originate a transaction processing request;

a plurality of computers, each of which processes said plurality of computers being adapted to process a plurality of transaction processing requests originating from a plurality of terminals in parallel;

a load estimator for estimating load states of respective ones of the plurality of computers;

a load data memory for storing the estimated load states; and

an execution computer selector for selecting one of the plurality of computers as an execution computer to be put in charge of processing a transaction processing request based on load indexes of respective ones of the plurality of computers, wherein the load indexes are calculated from estimated elongation rates of processing time for respective ones of the plurality of computers, wherein the estimated elongation rates are determined based on the estimated load states;

the system further comprising;

an interim control node connected between the plurality of terminals and the plurality of computers, wherein the interim control node includes an interim execution computer selector for selecting one of the plurality of computers according to a predetermined rule; and

a switching device connecting the plurality of computers to each other,

wherein each of the plurality of computers includes the load estimator, the load data memory, and the execution computer selector, wherein an estimated load state estimated at a computer is transferred to all other computers through the switching device so that the load state memory of each of the plurality of computers stores same load state data, and

wherein the execution computer selector selects a computer to which the execution computer selector belongs when the load index of the computer is smaller than a value obtained by multiplying a minimum load index among the plurality of computers by a predetermined factor greater than 1.

24. A load balancing method in a system comprising a plurality of computers for processing transaction processing requests originating from a plurality of terminals, comprising steps of:

a) estimating load states of respective ones of the plurality of computers;

b) determining estimated elongation rates of processing time for respective ones of the plurality of computers based on the estimated load states;

c) calculating load indexes of respective ones of the plurality of computers based on the estimated elongation rates; and

d) determining load distribution among the plurality of computers based on the load indexes,

wherein the estimated elongation rate E is a ratio of a processing time required for a job processing process to a net processing time, wherein the estimated elongation rate E is obtained by the following equation;

E=X/(X−

P·

P), when P<

N, =N+1.0, when P□

N,

where X=N·

(P+1), N is the number of in-process transactions in a computer and P is the number of transaction processes in a CPU system of the computer.

25. A load balancing method in a system comprising a plurality of computers for processing transaction processing requests originating from a plurality of terminals, comprising steps of:

a) estimating load states of respective ones of the plurality of computers;

b) determining estimated elongation rates of processing time for respective ones of the plurality of computers based on the estimated load states;

c) calculating load indexes of respective ones of the plurality of computers based on the estimated elongation rates; and

d) determining load distribution among the plurality of computers based on the load indexes,

wherein the estimated elongation rate E is obtained by the following equation;

E=N(1−

R)/(N(1−

R)−

R·

R)

where N is a number of in-process transactions in a computer and R is a CPU utilization.

26. A load balancing method in a system comprising an interim load balancing device connecting a plurality of terminals and a plurality of execution computers, comprising steps of:

at the interim load balancing device,

a) setting a predetermined distribution scheme;

b) when receiving a transaction processing request from a terminal, selecting an interim destination execution computer from the plurality of execution computers according to the predetermined distribution scheme;

c) sending the transaction processing request to the interim destination execution computer;

at each of the execution computers,

d) estimating a load state of the execution computer based on load data measured at regular intervals including a number of in-process transactions and one of a CPU utilization and a number of job processing processes staying in a CPU system of the execution computer;

e) storing the load state of the execution computer and a load state received from another execution computer in a load state memory;

f) transferring the load state of the execution computer to all other execution computers;

g) when receiving the transaction processing request from the interim load balancing device, determining estimated elongation rates of processing time for respective ones of the plurality of execution computers based on the load states stored in the load state memory;

h) calculating load indexes of respective ones of the plurality of execution computers from the estimated elongation rates;

said method further comprising the steps of;

i) determining based on the load indexes whether the transaction processing request should be processed by the interim destination execution computer or transferred to another execution computer;

j) when it is determined that the transaction processing request should be transferred to another execution computer, determining in said interim destination execution computer, a final destination computer among the plurality of execution computers based on the load indexes to transfer it to the final destination computer; and

k) when it is determined in said interim destination execution computer, that the transaction processing request should be processed by the interim destination execution computer, processing the transaction processing request in said interim destination execution computer.

27. A load balancing method according to claim 26, wherein, in the step (a), the predetermined distribution scheme is a static distribution method such that the plurality of terminals are previously divided into a plurality of groups and said interim destination execution computer is determined depending on which one of the plurality of groups a request originating terminal belongs to.

28. A load balancing method according to claim 26, wherein, in the step (a), the predetermined distribution scheme is a static round distribution method such that the plurality of execution computers are sequentially and repeatedly selected as an interim destination execution computer in the arrival order.

29. A load balancing method according to claim 26, wherein the step (a) comprises the steps of:

a.1) receiving load data from each of the plurality of execution computers at regular intervals, the load data including a number of in-process transactions and one of a CPU utilization and a number of job processing processes staying in a CPU system of the execution computer;

a.2) determining the predetermined distribution scheme based on the load data so that a transaction processing load is balanced among the plurality of execution computers.

30. A computer readable recording medium for storing computer executable software comprising

a first computer program for instructing a first computer of an interim load balancing device to distribute transaction processing requests originating from a plurality of terminals to a plurality of execution computers;

and

a second computer program for instructing each of the plurality of execution computers to balance a transaction processing load among the plurality of execution computers,

wherein the first computer program comprises the steps of;

a) setting a predetermined distribution scheme;

b) when receiving a transaction processing request from a terminal, determining an interim execution computer according to the predetermined distribution scheme; and

c) sending the transaction processing request to the interim execution computer,

wherein the second computer program comprises the steps of;

d) estimating a load state of the execution computer based on load data measured at regular intervals including a number of in-process transactions and one of a CPU utilization and a number of job processing processes staying in a CPU system of the execution computer;

e) storing the load state of the execution computer and a load state received from another execution computer in a load state memory;

f) transferring the load state of the execution computer to all other execution computers;

g) when receiving the transaction processing request from the interim load balancing device, determining estimated elongation rates of processing time for respective ones of the plurality of execution computers based on the load states stored in the load state memory;

h) calculating load indexes of respective ones of the plurality of execution computers from the estimated elongation rates;

i) determining based on the load indexes whether the transaction processing request should be processed by the execution computer or transferred to another execution computer;

j) when it is determined that the transaction processing request should be transferred to another execution computer, determining a final destination computer among the plurality of execution computers based on the load indexes to transfer it to the final destination computer; and

k) when it is determined that the transaction processing request should be processed by the execution computer, processing the transaction processing request.