Dynamic load balancer for multiple network servers

• US 6,601,084 B1
• Filed: 12/19/1997
• Issued: 07/29/2003
• Est. Priority Date: 12/19/1997
• Status: Expired due to Term

• Current Assignee: Citrix Systems, Inc. (Cloud Software Group)
• Original Assignee: Avaya Technology Corporation Miami Lakes FLA US
• Inventors: Matthews, Abraham R., Bhaskaran, Sajit
• Primary Examiner(s): Oberley, Alvin
• Assistant Examiner(s): BULLOCK JR, LEWIS ALEXANDER
• Application Number:
  US08/992,038
• Time in Patent Office: 2,048 Days
• Field of Search: 709/105, 709/223-226, 709/229
• US Class Current: 718/105
• 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 67/01 Protocols
• CPC Class Codes: H04L 67/1001 for accessing one among a plurality of replicated servers
• CPC Class Codes: H04L 67/10015 Access to distributed or replicated servers, e.g. using brokers
• CPC Class Codes: H04L 67/1006 with static server selection, e.g. the same server being selected for a specific client
• 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/1023 based on a hash applied to IP addresses or costs
• CPC Class Codes: H04L 67/1034 Reaction to server failures by a load balancer
• CPC Class Codes: H04L 9/40 Network security protocols

Abstract

The present invention provides methods and systems for balancing the load on a plurality of servers using a load balancing algorithm which continuously examines the loads on the plurality of servers and makes adjustments in the loads accordingly. Among the factors considered in the load balancing are the power of each server relative to other servers, the load on each server relative to the other servers, and a “credit” for each server based on their power and load.

Claims

1. A method for assigning a plurality of data requests among a plurality of servers, said method comprising:

determining a load on each of said plurality of servers, wherein said load on each of said plurality of servers is computed relative to a power rating of each of said plurality of servers;

assigning each of said data requests to a bucket of a first plurality of buckets, wherein said first plurality of buckets outnumber said plurality of servers; and

assigning each bucket of said plurality of buckets containing a data request to a server of said plurality of servers in response to said load on each of said plurality of servers;

wherein each of said data requests includes a source address and wherein each of said data requests is assigned to a bucket based on said source address.

2. The method of claim 1, wherein

said first plurality of buckets contain B buckets;

each of said buckets in said first plurality of buckets is uniquely numbered from zero to B−

1; and

a data request of said plurality of data requests is assigned to bucket number said source address of said data request modulo B.

3. The method of claim 1, wherein said assigning each bucket of said plurality of buckets containing a data request to a server of said plurality of servers further comprises:

detecting a first not-assigned bucket having at least one of said data requests; and

assigning said first not-assigned bucket to an underloaded server.

4. The method of claim 3, wherein said underloaded server is the most underloaded server.

5. The method of claim 1, wherein assigning each bucket of said plurality of buckets containing a data request to a server of said plurality of servers further comprises:

detecting a first not-assigned bucket having at least one of said data requests;

calculating a credit for each of said servers; and

assigning said first not-assigned bucket to a server having a largest said credit.

6. The method of claim 5, further comprising detecting a skewed load on said plurality of servers.

7. A method for assigning a plurality of data requests among a plurality of servers, said method comprising:

determining a load on each of said plurality of servers, wherein said load on each of said plurality of servers is computed relative to a power rating of each of said plurality of servers;

assigning each of said data requests to a bucket of a first plurality of buckets, wherein said first plurality of buckets outnumber said plurality of servers;

assigning each bucket of said plurality of buckets containing a data request to a server of said plurality of servers in response to said load on each of said plurality of servers, including

detecting a first not-assigned bucket having at least one of said data requests,

calculating a credit for each of said servers, and

assigning said first not-assigned bucket to a server having a largest said credit;

detecting a skewed load on said plurality of servers;

selecting a second bucket from said plurality of buckets, wherein said second bucket is in a low granularity mode; and

converting said second bucket from said low granularity mode to a high granularity mode.

8. The method of claim 7 wherein:

converting comprises

creating a plurality of child buckets; and

assigning data requests destined for said second bucket to one of said plurality of child buckets.

9. The method of claim 8 wherein:

assigning each bucket of said plurality of buckets comprises

assigning a not-assigned child bucket of the plurality of child buckets to a server having a largest said credit.

10. A load balancer for balancing the load due to a plurality of data requests on a plurality of servers, said load balancer comprising:

a plurality of buckets;

a bucket selector configured to assign each of said data requests to a bucket in said plurality of buckets;

a load estimator or configured to compute a load on each of said plurality of servers, wherein said load on each of said plurality of servers is computed relative to a power rating of each of said plurality of servers; and

a server selector configured to dynamically assign any unassigned bucket containing a data request to a server in said plurality of servers in response of the estimated load on each of said plurality of servers, wherein

each of said data requests contains a source address; and

said bucket selector determines which bucket to assign a specific data request based on said source address of said specific data request.

11. The load balancer of claim 10, wherein said plurality of buckets outnumbers said plurality of servers.

12. The load balancer of claim 10 wherein said server selector assigns an unassigned bucket containing a data request to an underloaded server.

13. The load balancer of claim 12, wherein said underloaded server is a most underloaded server.

14. The load balancer of claim 10, further comprising a credit calculator coupled to said load estimator and configured to calculate a credit for each of said servers to form a plurality of credits.

15. The load balancer of claim 10, wherein said server selector assigns an unassigned bucket containing a data request to a server having a large credit.

16. The load balancer of claim 15, wherein said server selector assigns an unassigned bucket containing a data request to a server having the largest credit.

17. A load balancer for balancing the load due to a plurality of data requests on a plurality of servers, said load balancer comprising:

memory defining a plurality of buckets, wherein said plurality of buckets outnumber said plurality of servers;

a bucket selector configured to assign each of said data requests to a bucket in said plurality of buckets;

a load estimator configured to compute a load on each of said plurality of servers by calculating a credit for each of said servers, wherein said load on each of said plurality of servers is computed relative to a power rating of each of said plurality of servers, and to detect a skewed load on said plurality of servers;

a server selector configured to dynamically assign any unassigned bucket containing a data request to a server in said plurality of servers in response to the estimated load on each of said plurality of servers by detecting a first not-assigned bucket having at least one of said data requests and assigning said first not-assigned bucket to a server having a largest said credit; and

a bucket granularizer configured to select a second bucket from said plurality of buckets which second bucket is in a low granularity mode and to convert said first bucket from said low granularity mode to a high granularity mode, in response to a detection of a skewed load.

18. The load balancer of claim 17 wherein:

the bucket granularizer is configured to convert said first bucket by creating a plurality of child buckets; and

the bucket selector is configured to assign data requests destined for said second bucket to one of said plurality of child buckets.

19. The load balancer of claim 18 wherein:

the server selector is configured to assign a not-assigned child bucket of the plurality of child buckets to a server having a largest said credit.

20. A method of assigning a plurality of data requests among a plurality of servers, said method comprising:

determining a weight of each server as a ratio of a power rating of the server and a sum of the power ratings of all of the servers;

determining a weighted load of each server as a ratio of a load of the server and the weight of the server;

determining a load normalizer as a minimum one of absolute values of the weighted loads of the servers;

determining a credit of each server as a difference between the weight of the server and a ratio of the weighted load of the server and the load normalizer;

assigning each of said data requests to a bucket of a plurality of buckets; and

assigning buckets of said plurality of buckets containing a data request to servers of said plurality of servers that have greatest said credits.

21. The method of claim 20 wherein:

assigning buckets comprises

assigning one of the buckets containing a data request to a server of said plurality of servers that has a greatest said credit;

redetermining said credit of said server to which said one of the buckets was assigned; and

assigning another one of the buckets containing a data request to a server that currently has a greatest said credit.

22. The method of claim 21 wherein:

said determinings and said redetermining are effected via integer arithmetic.

23. The method of claim 20 further comprising:

determining a flow weight as a minimum one of absolute values of the credits of the servers;

determining a flow adjustment of each server as a ratio of the flow weight and the weight of the server;

wherein

assigning buckets comprises

assigning one of the buckets containing a data request to a server of said plurality of servers that has a greatest said credit;

reducing the credit of said server to which said one of the buckets was assigned by the flow adjustment of said server; and

assigning another one of the buckets containing a data request to a server that currently has a greatest said credit.

24. The method of claim 23 wherein:

determining a weight comprises scaling said weight by a weight scale;

determining a weighted load comprises scaling said weighted load by a load scale; and

determining a flow adjustment comprises scaling said flow adjustment by the load scale.

25. The method of claim 23 wherein:

said determining and said reducing are effected via integer arithmetic.

26. The method of claim 20 wherein:

determining a weight comprises scaling said weight by a weight scale; and

determining a weighted load comprises scaling said weighted load by a load scale.

27. The method of claim 20 wherein:

said determinings are effected via integer arithmetic.

28. The method of claim 20 wherein:

a load of a server comprises a plurality of ones of;

a number of data requests received by the server, a number of data packets received by the server, a number of bytes received by the server, a number of data packets sent by the server, and a number of bytes sent by the server.

29. A load balancer for balancing the load due to a plurality of data requests on a plurality of servers, said load balancer comprising:

a plurality of buckets;

a bucket selector configured to assign each of said data requests to a bucket of said plurality of buckets;

a credit calculator configured to determine a weight of each server as a ratio of a power rating of the server and a sum of the power ratings of all of the servers, to determine a weighted load of each server as a ratio of a load of the server and the weight of the server, to determine a load normalizer as minimum one of absolute values of the weighted loads of the servers, and to determine a credit of each server as a difference between the weight of the server and a ratio of the weighted load of the server and the load normalizer; and

a server selector configured to assign buckets of said plurality of buckets containing a data request to servers of said plurality of servers that have greatest said credits.

30. The load balancer of claim 29 wherein:

the credit calculator is configured to redetermine said credit of a server to which one of the buckets was assigned; and

the server selector is configured to assign said one of the buckets containing a data request to a server of said plurality of servers that has a greatest said credit, and to assign another one of the buckets containing a data request to a server that currently has a greatest said credit.

31. The load balancer of claim 30 wherein:

the credit calculator is an integer arithmetic calculator.

32. The load balancer of claim 29 wherein:

the credit calculator is further configured to determine a flow weight as a minimum one of absolute values of the credits of the servers, to determine a flow adjustment of each server as a ratio of the flow weight and the weight of the server, and to reduce the credit of a server to which one of the buckets was assigned by the flow adjustment of said server; and

the server selector is configured to assign said one of the buckets containing a data request to a server of said plurality of servers that has a greatest said credit, and to assign another one of the buckets containing a data request to a server that currently has a greatest said credit.

33. The load balancer of claim 32 wherein:

the credit calculator is configured to scale said weight of each server by a weight scale and to scale said weighted load of each server and the flow adjustment by a load scale.

34. The load balancer of claim 32 wherein:

the credit calculator is an integer arithmetic calculator.

35. The load balancer of claim 29 wherein:

the credit calculator is configured to scale said weight of each server by a weight scale and to scale said weighted load of each server by a load scale.

36. The load balancer of claim 29 wherein:

the credit calculator is an integer arithmetic calculator.

37. The load balancer of claim 29 wherein:

a load of a server comprises a plurality of ones of;

a number of data requests received by the server, a number of data packets received by the server, a number of bytes received by the server,

a number of data packets sent by the server, and a number of bytes sent by the server.