System and method for implementing a clustered load balancer

• US 20020040402A1
• Filed: 09/26/2001
• Published: 04/04/2002
• Est. Priority Date: 09/28/2000
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Thubert, Pascal, Levy-Abegnoli, Eric
• Granted Patent: US 7,272,653 B2
• Time in Patent Office: Days
• US Class Current: 709/229
• CPC Class Codes: H04L 61/35 involving non-standard use of addresses for implementing network functionalities, e.g. coding subscription information within the address or functional addressing, i.e. assigning an address to a function
• 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/1019 Random or heuristic server selection
• CPC Class Codes: H04L 67/1023 based on a hash applied to IP addresses or costs

Abstract

A system and method of organizing a front-end load balancing function for implementing an Internet site so the transmission control protocol (TCP) connections, established between the front-end load balancing function and end-users, are spread over more than one individual load balancer (ILB). Each ILB consistently self-asserts a primary ILB owner for each one of the TCP connections. Hence, each ILB, for each delegated TCP connection can process each TCP connection on behalf of the load balancing function while handing off the other TCP connections to the corresponding ILB owners. Also, each ILB consistently self-asserts a backup ILB owner for each one of the TCP connections so the designated back up ILB owner takes over the processing of an ILB owned TCP connection should the ILB owner become incapable of processing the delegated TCP connection.

Claims

1. A method for enabling a front-end load balancing function to a cluster of servers functioning as an Internet site for serving end-users, said front-end load balancing function and said end-users establishing transmission control protocol (TCP) connections, said method comprising the steps of:

spreading said front-end load balancing function over more than one individual load balancer (ILB);

enabling each ILB to consistently self-assert, for said front-end load balancing function, an ILB owner for each one of said TCP connections;

processing an ILB-owned TCP connection on behalf of said load balancing function in said each ILB, for each one of said TCP connections owned by each said ILB; and

handing off an unassigned TCP connection to said ILB owner in each said ILB, for each one of said TCP connections not owned by each said ILB.

2. The method according to claim 1, wherein said enabling step further includes steps of:

consistently self-asserting, for said front-end load balancing function, a back up ILB owner for each one of said TCP connections; and

utilizing said back up ILB owner to process said ILB owned TCP connection should said ILB owner become incapable of processing said ILB owned TCP connection.

3. The method according to claim 2, wherein said enabling step, further includes steps of:

using a connection unique identifier for each one of said TCP connections;

using an ILB unique identifier for each said ILB;

computing a score for each said ILB;

obtaining a set of scores;

ranking said set of scores, said ranking step further includes;

designating said ILB having a best ranked score as said ILB owner;

designating said ILB having a second best ranked score as said back up ILB owner.

4. The method according to claim 3, wherein said method further includes a step of:

adding a connection unique identifier use step wherein said connection unique identifier is a twelve byte quadruplet including a TCP destination port, an IP destination address, a TCP source port, an IP source address.

5. The method according to claim 4, wherein said method further includes a step of:

using said ILB unique identifier wherein said ILB unique identifier is an IP address of said ILB.

6. The method according to claim 4, wherein said method further includes a step of:

using said ILB unique identifier wherein said ILB unique identifier is an index which is unique within said front-end load balancing function.

7. The method according to claim 3, wherein said ranking step further includes a step of:

ranking on the basis of the arithmetical values of said set of scores.

8. The method according to claim 3, wherein said designating steps further includes steps of:

selecting the largest arithmetical value of said set of scores as said best ranked score; and

selecting the second largest arithmetical value of said set of scores as said second best ranked score.

9. The method according to claim 3, wherein said step of computing a score further includes a step of:

calculating a cyclic redundancy check (CRC) code over said ILB unique identifier concatenated to said connection unique identifier.

10. The method according to claim 1, wherein said method further includes a step of:

designating a particular server, out of said cluster of servers due to process each said ILB owned TCP connection, with a lookup table of owned connections (LTOC) included in each said ILB.

11. The method according to claim 10 wherein said method further includes a step of:

including in each said LTOC, for each ILB owned TCP connection, said backup ILB owner.

12. The method according claim 1, wherein said method further includes a step of:

including a cache of all least recently used associations formed, within said front-end load balancing function , between each one of said TCP connections with an individual server out of said cluster of servers, in each of said ILB.

13. The method according to claim 3, upon receiving a TCP synchronous idle character (SYN) Packet in a receiving ILB, wherein said method further includes steps of:

computing said set of scores;

determining said ILB owner and said back up ILB owner;

checking if said receiving ILB is said ILB owner;

selecting an individual server to process a new TCP connection, in response to determining that said receiving ILB is said ILB owner;

forwarding said TCP SYN packet to said individual server;

broadcasting a control packet within said front-end load balancing function informing of a new formed association between said new TCP connection, said individual server and said back up ILB owner in all ILBs receiving said broadcast control packet;

optionally caching said new formed association;

testing if said broadcast receiving ILB is selected said backup ILB owner;

moving forward directly to said completing step, in response to determining that said broadcast receiving ILB is not selected said backup ILB owner;

storing in said LTOC of said broadcast receiving ILB that, for said new TCP connection, said broadcast receiving ILB is said back up ILB owner, in response to determining that said broadcast receiving ILB is selected said backup ILB owner;

forwarding said TCP SYN packet to said ILB owner, in response to determining that said receiving ILB is not said ILB owner;

forwarding said TCP SYN packet to said individual server;

broadcasting a control packet within said front-end load balancing function informing of a new formed association between said new TCP connection, said individual server and said back up ILB owner;

in all ILBs receiving said broadcast control packet;

optionally caching said new formed association;

testing if said broadcast receiving ILB is selected said backup ILB owner;

moving forward directly to said completing step, in response to determining that said broadcast receiving ILB is not selected said backup ILB owner; and

storing in said LTOC of said broadcast receiving ILB that, for said new TCP connection, said broadcast receiving ILB is said back up ILB owner, in response to determining that said broadcast receiving ILB is selected said backup ILB owner.

14. The method according to claim 3, upon receiving a transmission control protocol (TCP) Packet other than a synchronous idle character (SYN), in said receiving individual load balancer (ILB), said method further comprising the steps of:

computing said set of scores;

determining said ILB owner and said back up ILB owner;

checking if said receiving ILB is said ILB owner or said back up ILB owner of a previously established TCP connection;

retrieving in said LTOC of said receiving ILB a corresponding entry for said previously established TCP connection, in response to said receiving ILB is said ILB owner or said backup ILB owner of a previously established TCP connection;

forwarding said TCP packet to said individual server according to said LTOC corresponding entry;

testing if said TCP packet is a FIN or RST packet;

moving forward directly to said completing step, in response to determining that said TCP packet is not a FIN or RST packet;

broadcasting an end of connection control packet within said front-end load balancing function informing all ILBs that said previously established TCP connection has terminated thus, that each said cache and said LTOC of said back up ILB owner and/or said ILB owner must be updated accordingly, in response to determining that said TCP packet is a FIN or RST packet;

looking up said cache of said receiving ILB for an entry corresponding to said previously established TCP connection, in response to determining that said receiving ILB is not said ILB owner nor said back up ILB owner of a previously established TCP connection;

forwarding said TCP packet to said individual server according to said LTOC corresponding entry, in response to finding an entry corresponding to said previously established TCP connection;

testing if said TCP packet is a FIN or RST packet;

moving forward directly to said completing step, in response to determining that said TCP packet is not a FIN or RST packet;

broadcasting an end of connection control packet within said front-end load balancing function informing all ILBs that said previously established TCP connection has terminated thus, that each said cache and said LTOC of said back up ILB owner and/or said ILB owner must be updated accordingly, in response to determining that said TCP packet is a FIN or RST packet; and

forwarding said TCP packet to said ILB owner, in response to not finding an entry corresponding to said previously established TCP connection.

15. The method according to claim 14, wherein said method further comprising the step of:

forwarding to said ILB owner said received packet other than a SYN when receiving ILB has no cache, in response to determining that said receiving ILB is not said ILB owner nor said backup ILB owner of a previously established TCP connection.

16. The method according to claim 1, wherein said method further comprising the step of:

broadcasting ID messages regularly from each said ILB in order to keep all other said ILBs aware of their respective status while each said ILB actively participating, at any given instant, in said front-end load balancing function.

17. The method according to claim 16, wherein upon listening for the reception of said ID messages, in said receiving ILB said method further comprising the steps of:

checking if a new ILB has joined said front-end load balancing function, in response to receiving a new ID message;

continuing ID message monitoring, in response to determining that said new ILB has not joined said front-end load balancing function;

re-computing scores including said new ILB, in response to determining that said new ILB has joined said front-end load balancing function for each one of said TCP connections currently handled by said receiving ILB as said ILB owner or as said backup owner;

updating a transfer table, said updating step said transfer table further comprising;

adding said ILB owned TCP connection in said transfer table as now owned by said new ILB, in response to determining if said new ILB is elected to become said ILB owner and said receiving ILB is elected to become said back up ILB owner;

changing, in said LTOC of said receiving ILB, state of current TCP connection;

adding said ILB owned TCP connection in said transfer table as now backup owned by said new ILB, in response to determining if said receiving ILB remains to be said ILB owner and said new ILB is elected to become said back up ILB owner;

adding said ILB owned TCP connection in said transfer table as now back up owned by said new ILB, in response to determining said new ILB is elected to become said back up ILB owner and said receiving ILB is no longer said ILB owner or said back up ILB owner;

deleting, in said LTOC of said receiving ILB, current TCP connection; and

transferring said transfer table to said new ILB.

18. The method according to claim 17, wherein upon listening for the reception of said ID messages, in said receiving ILB, said method further comprising the steps of:

checking if a former ILB has left said front-end load balancing function, in response to receiving a new ID message;

continuing ID message monitoring, in response to determining if a former ILB has not left said front-end load balancing function;

flushing said cache of said receiving ILB of all entries corresponding to said former ILB, in response to determining if a former ILD has left said front-end load balancing function;

updating said transfer table, for each one of said TCP connections currently handled by said receiving ILB as said ILB owner or as said back up ILB owner, said step of updating said transfer table further comprising the step of;

re-computing a new back up ILB owner among remaining ILBs, in response to determining said receiving ILB is said ILB owner and said former ILB was said backup ILB owner;

adding in said transfer table said new back up ILB owner;

changing, in said LTOC of said receiving ILB, state of current TCP connection so as said receiving ILB becomes a new ILB owner, in response to determining said receiving ILB is said back up ILB owner and said former ILB was said ILB owner;

re-computing a new back up ILB owner;

adding in said transfer table said new ILB owner and said new back up ILB owner;

transferring said transfer table to all remaining ILBs.

19. A system for enabling a front-end load balancing function to a cluster of servers together implementing an Internet site for serving end-users, said front-end load balancing function and said end-users establishing TCP connections, said system comprising:

means for spreading said front-end load balancing function over more than one individual load balancer (ILB);

means for enabling each ILB to consistently self-assert, for said front-end load balancing function, an ILB owner for each one of said TCP connections;

means for processing an ILB-owned TCP connection in behalf of said load balancing function in said each ILB, for each one of said TCP connections owned by said each ILB; and

means for handing off an ILB not owned TCP connection to said ILB owner in each said ILB, for each one of said TCP connections not owned by said each ILB.

20. A computer-readable medium comprising instructions for enabling a front-end load balancing function to a cluster of servers together implementing an Internet site for serving end-users, said front-end load balancing function and said end-users establishing TCP connections, said instruction means comprising:

instruction means for spreading said front-end load balancing function over more than one individual load balancer (ILB);

instruction means for enabling each ILB to consistently self-assert, for said front-end load balancing function, an ILB owner for each one of said TCP connections;

instruction means for processing an ILB-owned TCP connection in behalf of said load balancing function in said each ILB, for each one of said TCP connections owned by said each ILB; and

instruction means for handing off an ILB not owned TCP connection to said ILB owner in each said ILB, for each one of said TCP connections not owned by said each ILB.