Highly scalable least connections load balancing

• US 6,996,615 B1
• Filed: 12/11/2000
• Issued: 02/07/2006
• Est. Priority Date: 09/29/2000
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: McGuire, Jacob M.
• Primary Examiner(s): Dinh, Dung C.
• Assistant Examiner(s): STRANGE, AARON N
• Application Number:
  US09/734,450
• Time in Patent Office: 1,884 Days
• Field of Search: 718/105, 709224-226
• US Class Current: 709/226
• CPC Class Codes: G06F 2209/5016 Session
• CPC Class Codes: G06F 9/505 considering the load
• 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 69/16 Implementation or adaptation of Internet protocol [IP], of transmission control protocol [TCP] or of user datagram protocol [UDP]
• CPC Class Codes: H04L 69/163 In-band adaptation of TCP data exchange; In-band control procedures
• CPC Class Codes: H04L 69/164 Adaptation or special uses of UDP protocol

Abstract

A load balancing device according to an embodiment of the invention uses a predictor that comprises a plurality of Least Connections Control Blocks (LCCBs) that keeps track of the real servers with active connections. To speed up the search for the real server with the least number of active connections, an LCCB is kept for each metric. A metric is defined as the number of connections on a server divided by its weight (or capacity) of the server. This metric is kept as a quotient/remainder pair. The predictor sends out the real server address with the lowest metric whenever a new connection is required by the load balancing device.

Claims

1. A method for load balancing a plurality of servers, the method comprising:

providing a plurality of control blocks, each control block associated with a number of active connections a server is connected with, the control block configured to control at least one server with the associated number of connections in a server list;

determining a metric for each server by dividing the number of connections on the server by the capacity of the server wherein the metric is kept as a quotient/remainder pair;

storing the quotient/remainder pair in the control block;

incrementing the remainder by one for every connection added to the server;

decrementing the remainder by one for every connection removed from the server;

causing each control block to point to a server with a lowest value of the metric;

selecting the control block associated with the least number of connections; and

selecting the server pointed to by the control block.

2. The method as in claim 1, further comprising:

causing the control block with the server having an added/removed connection to transfer the server to an adjacent control block, wherein the adjacent control block is associated with the number of connections pertaining to the transferring server;

causing the control block to transfer the metric of the server to the adjacent control block; and

updating the pointer to point to the next server on the list of the control block.

3. The method as in claim 2, further comprising:

removing the control block if the control block does not have a server on the server list.

4. The method as in claim 2, further comprising:

causing the adjacent control block to receive the transferring server;

causing the adjacent control block to receive the metric of the transferring server; and

causing the adjacent control block to update and sort the server list.

5. The method as in claim 4, further comprising:

adding a control block if there is no control block associated with the number of connections of the transferring server.

6. A computer readable medium comprising:

instructions for execution on a processor for the practice of a method for load balancing a plurality of servers, the method having the following steps,

providing a plurality of control blocks, each control block associated with a number of active connections a server is connected with, the control block configured to control at least one server with the associated number of connections in a server list;

determining a metric for each server by dividing the number of connections on the server by the capacity of the server, wherein the metric is kept as a quotient/remainder pair;

storing the quotient/remainder pair in the control block;

incrementing the remainder by one for every connection added to the server;

decrementing the remainder by one for every connection removed from the server;

causing each control block to point to a server with a lowest value of the metric;

selecting the control block associated with the least number of connections; and

selecting the server pointed to by the control block.

7. The computer readable medium as in claim 6, further comprising instructions for:

causing the control block with the server having an added/removed connection to transfer the server to an adjacent control block, wherein the adjacent control block is associated with the number of connections pertaining to the transferring server;

causing the control block to transfer the metric of the server to the adjacent control block; and

updating the pointer to point to the next server on the list of the control block.

8. The computer readable medium as in claim 7, further comprising instructions for:

removing the control block if the control block does not have a server on the server list.

9. The computer readable medium as in claim 7, further comprising instructions for:

causing the adjacent control block to receive the transferring server;

causing the adjacent control block to receive the metric of the transferring server; and

causing the adjacent control block to update and sort the server list.

10. The computer readable medium as in claim 9, further comprising instructions for:

adding a control block if there is no control block associated with the number of connections of the transferring server.

11. A load balancing apparatus comprising:

a plurality of control blocks, each control block associated with a number of active connections a server is connected with, the control block configured to control at least one server with the associated number of connections;

a metric of the server, kept as a quotient/remainder pair, wherein the remainder is incremented by one for every connection added to the server, and the remainder is decremented by one for every connection removed from the server;

a memory to store the quotient/remainder pair;

a pointer in each control block that points to a server with a lowest value of the metric; and

a selection circuit that selects the control block associated with the least number of connections and further selects the server pointed to by the control block.

12. The load balancing apparatus as in claim 11, further comprising:

the control block configured to transfer the server having an added/removed connection to an adjacent control block, wherein the adjacent control block is associated with the number of connections pertaining to the transferring server;

the control block further configured to transfer the metric of the server to the adjacent control block; and

the control block configured to update the pointer to point to the next server on the list of the control block.

13. The load balancing apparatus as in claim 12 further comprises:

the control block is de-activated if the control block does not have a server on the server list.

14. The load balancing apparatus as in claim 12, further comprises:

the adjacent control block configured to receive the transferring server; and

the adjacent control block further configured to receive the metric of the transferring server, wherein the adjacent control block updates and sorts the server list.

15. The load balancing apparatus as in claim 14, further comprises:

a control block that is activated to receive the transferring server if there is no control block associated with the number of connections of the transferring server and the control block is associated with the number of connections of the transferring server.

16. An apparatus for load balancing a plurality of servers, the apparatus comprising:

means for providing a plurality of control blocks, each control block associated with a number of active connections a server is connected with, the control block configured to control at least one server with the associated number of connections in a server list;

means for determining a metric for each server by dividing the number of connections on the server by the capacity of the server, wherein the metric is kept as a quotient/remainder pair;

means for storing the quotient/remainder pair in the control block;

means for incrementing the remainder by one for every connection added to the server;

means for decrementing the remainder by one for every connection removed from the server;

means for causing each control block to point to a server with a lowest value of the metric;

means for selecting the control block associated with the least number of connections; and

means for selecting the server pointed to by the control block.

17. A method for load balancing a plurality of servers, the method comprising:

associating each of the plurality of servers with one of one or more control blocks, each control block representing a number of connections of the associated servers;

determining a metric for each associated server by dividing the number of connections on the server by an assigned weight of the server, wherein the metric is kept as a quotient/remainder pair;

storing the quotient/remainder pair in the control block;

incrementing the remainder by one for every connection added to the server;

decrementing the remainder by one for every connection removed from the server;

pointing, within each control block, to a server with a lowest value of the metric;

selecting the control block associated with the least number of connections; and

selecting the server pointed to by the control block.

18. The method as in claim 17, wherein the assigned weight represents a server'"'"'s capacity to handle connections.

19. A system for load balancing a plurality of servers, the system comprising:

one or more clients to send client requests; and

a virtual server to receive and process the client requests, the virtual server having,

A) a plurality of real servers, and

B) a load balancing apparatus to receive the client requests and load balance the client requests among the plurality of real servers, the load balancing apparatus further having,

i) one or more control blocks, each of the plurality of real servers associated with one of one or more control blocks, each control block representing a number of connections of the associated servers,

ii) a metric for each associated server, kept as a quotient/remainder pair, wherein the remainder is incremented by one for every connection added to the server and the remainder is decremented by one for every connection removed from the server,

iii) a memory to store the quotient/remainder pair,

iv) a pointer within each control block that points to a server with a lowest value of the metric, and

v) a selection circuit that selects the control block associated with the least number of connections and further selects the server pointed to by the control block.