Load balancing according to an iterative greatest common divisor approach to weight normalization

• US 7,761,546 B2
• Filed: 04/25/2005
• Issued: 07/20/2010
• Est. Priority Date: 04/25/2005
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: McAfee, Gary O.
• Primary Examiner(s): Vaughn, Jr.; William C
• Assistant Examiner(s): PEREZ TORO, CARLOS RAFAEL
• Application Number:
  US11/113,793
• Publication Number:
  US 20060242298A1
• Time in Patent Office: 1,912 Days
• Field of Search: 709223-226, 370/254, 711/150
• US Class Current: 709/223
• CPC Class Codes: H04L 67/1001 for accessing one among a plurality of replicated servers
• CPC Class Codes: H04L 67/1023 based on a hash applied to IP addresses or costs
• CPC Class Codes: H04L 67/1029 using data related to the state of servers by a load balancer
• CPC Class Codes: H04L 67/1031 Controlling of the operation of servers by a load balancer, e.g. adding or removing servers that serve requests

Abstract

A method, system and apparatus for load balancing workloads in a cluster according to an iterative greatest common divisor approach to weight normalization. A load balancing method can include computing a greatest common divisor for a set of current normalized values for raw weights corresponding to endpoints in a cluster. Each of the current normalized values can be reduced by a factor proportionate to the greatest common divisor. The reduction can produce new normalized values for the raw weights corresponding to the endpoints in the cluster. The computing and reducing steps can be repeated for the new normalized values until the new normalized values are sufficiently low. Finally, workloads can be assigned to the endpoints in the cluster according to the new normalized values which are sufficiently low.

Claims

1. A load balancing method comprising the steps of:

computing a greatest common divisor for a set of current normalized values for raw weights corresponding to endpoints in a cluster, wherein a weight represents a proportion of workload corresponding to an endpoint;

reducing each of said current normalized values by a factor proportionate to said greatest common divisor, said reduction producing new normalized values for said raw weights corresponding to said endpoints in said cluster;

repeating said computing and reducing steps for said new normalized values until said new normalized values are low enough to result in distribution of current workload among the endpoints according to said new normalized values;

responsive to said greatest common denominator not exceeding unity, determining if said reduction produces an odd value;

further responsive to said reduction producing an odd value, correcting said odd value to an even value in a direction opposite to a direction of a previous correction; and

,

assigning workloads to said endpoints in said cluster according to said new normalized values.

2. The method of claim 1, wherein said correcting step comprises the steps of:

consulting a cache to identify a direction of a previous correction; and

,

changing said odd value to an even value in a direction opposite to said direct of said previous correction.

3. The method of claim 1, wherein said repeating step comprises the step of responsive to said greatest common divisor exceeding unity, repeating said computing and reducing steps for said new normalized values.

4. A computer system, comprising:

a memory;

at least one processor connected to the memory; and

a load balancer executing on the at least one processor, wherein

the memory includes;

a set of raw weights assigned to corresponding endpoints in a communicatively coupled cluster, wherein a weight represents a proportion of workload corresponding to an endpoint;

a set of initially established normalized values for said raw weights;

a plurality of cached directions of corrections for corresponding ones of said normalized values;

the processor includes;

weight normalization logic configured to

iteratively reduce said initially established normalized values by a greatest common divisor for said normalized values until said new normalized values are low enough to result in distribution of current workload among the endpoints according to said new normalized values, and

correct odd values of individual reduced ones of said normalized values in a direction which is opposite to a cached direction for said individual reduced ones of said normalized values; and

workload assignment logic configured to assign workloads to said endpoints in said cluster according to said normalized values.

5. A machine readable storage having stored thereon a computer program for load balancing endpoints in a server cluster, the computer program comprising a routine set of instructions which when executed by a machine causes the machine to perform the steps of:

computing a greatest common divisor for a set of current normalized values for raw weights corresponding to the endpoints in a cluster, wherein a weight represents a proportion of workload corresponding to an endpoint;

reducing each of said current normalized values by a factor proportionate to said greatest common divisor, said reduction producing new normalized values for said raw weights corresponding to said endpoints in said cluster;

repeating said computing and reducing steps for said new normalized values until said new normalized values are low enough to result in distribution of current workload among the endpoints according to said new normalized values;

responsive to said greatest common denominator not exceeding unity, determining if said reduction produces an odd value;

further responsive to said reduction producing an odd value, correcting said odd value to an even value in a direction opposite to a direction of a previous correction; and

,

assigning workloads to said endpoints in said cluster according to said new normalized values.

6. The machine readable storage of claim 5, wherein said correcting step comprises the steps of:

consulting a cache to identify a direction of a previous correction; and

,

changing said odd value to an even value in a direction opposite to said direct of said previous correction.

7. The machine readable storage of claim 5, wherein said repeating step comprises the step of responsive to said greatest common divisor exceeding unity, repeating said computing and reducing steps for said new normalized values.