Computer system and method for load balancing with selective control

• US 6,119,143 A
• Filed: 05/22/1997
• Issued: 09/12/2000
• Est. Priority Date: 05/22/1997
• Status: Expired due to Term

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Yu, Philip Shi-Lung, Wolf, Joel Leonard, Dias, Daniel Manuel
• Primary Examiner(s): Dinh, Dung C.
• Assistant Examiner(s): Le, Hieu C.
• Application Number:
  US08/862,047
• Time in Patent Office: 1,209 Days
• Field of Search: 395/200.31, 395/200.32, 395/200.33, 395/200.56, 395/200.75, 395/200.79, 395/200.78, 395/800.29, 395/800.3, 709/246, 709/245, 709/249, 709/105, 709/201, 709/202, 709/203
• US Class Current: 709/201
• CPC Class Codes: G06F 2209/5019 Workload prediction
• CPC Class Codes: G06F 2209/5022 Workload threshold
• CPC Class Codes: G06F 9/505 considering the load
• CPC Class Codes: G06F 9/5083 Techniques for rebalancing the load in a distributed system
• CPC Class Codes: H04L 61/4511 using domain name system [DNS]
• CPC Class Codes: H04L 67/1001 for accessing one among a plurality of replicated servers
• CPC Class Codes: H04L 67/1008 based on parameters of servers, e.g. available memory or workload monitoring of computer activity G06F11/30
• CPC Class Codes: H04L 67/1017 based on a round robin mechanism

Abstract

A computerized method for load balancing in a geographically distributed or clustered system is disclosed. An arbiter assigns clients to nodes. The arbiter partitions clients into groups based on their request load. Each group is dynamically scheduled among nodes, thus avoiding high load groups from being allocated to the same node and overloading the system. If one of the nodes becomes overload, an alarm is generated, so that fewer or no new clients are allocated to the overloaded node.

Claims

1. In a multi-node server environment wherein client requests can be satisfied by routing a client request to any server, and wherein clients are divided into groups, and wherein client groups periodically send requests to an arbitrator, a computerized method employed by the arbitrator for assigning a server to service some or all of the requests from a client group, comprising the steps of:

estimating a load, associated with the requests from client groups to an assigned server node;

partitioning client groups into tiers, in response to said step of estimating a load; and

for each tier, separately scheduling the client groups to the assigned server node.

2. The method of claim 1 wherein each of the multi-node servers are web servers at geographically distributed sites, wherein the arbitrator comprises an extended domain name server (DNS), and wherein the client group consists of the set of clients behind a common gateway or SOCKS server, the method comprising the steps of:

said estimating step including estimating the hidden load behind each gateway;

said partitioning step including assigning gateways to the tiers; and

said scheduling step comprising mapping name requests to IP addresses using a separate round robin method for each tier.

3. The method of claim 2, wherein said estimating step comprises the step of estimating the hidden load behind the gateway as a ratio of a total number of page requests from the gateway to web server sites, to a number of name server requests from the gateway.

4. The method of claim 2, wherein a different round robin order is used for each tier.

5. The method of claim 2 wherein said partitioning step comprises partitioning the gateways into two tiers wherein a first tier includes gateways having more than a mean hidden load, and a second tier includes remaining gateways.

6. The method of claim 5, further comprising the step of recursively splitting at least one of the tiers are according to the mean load within that tier.

7. The method of claim 4 wherein the round robin order for each tier is pseudo-random.

8. The method of claim 2 wherein the round robin order for different tiers is staggered, with different sites as starting points.

9. The method of claim 8 wherein a load threshold is used, further comprising the steps of:

detecting if the load at a site exceeds the threshold; and

reducing the weight of one or more of the tiers for the site exceeding the threshold.

10. The method of claim 9, further comprising the step of:

said reducing step including reducing the weight to zero for the site exceeding the threshold;

detecting if the load at a site having zero weight has fallen below a second threshold; and

increasing the weight of the site detected to have fallen below the second threshold.

11. The method of claim 1 wherein, in said scheduling step further comprises the step of assigning each tier using a round-robin assignment.