Method and apparatus for load balancing within a computer system

• US 7,606,916 B1
• Filed: 11/10/2003
• Issued: 10/20/2009
• Est. Priority Date: 11/10/2003
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Potter, Darran, Clymer, Andrew
• Primary Examiner(s): Vaughn, Jr.; William C
• Assistant Examiner(s): Richardson; Thomas
• Application Number:
  US10/705,158
• Time in Patent Office: 2,171 Days
• Field of Search: 709223-226, 709/229
• US Class Current: 709/229
• CPC Class Codes: G06F 9/505 considering the load

Abstract

A method and apparatus for load balancing within a computer system makes use of client MAC addresses, reduced modulo N, to direct client requests to a particular server within a server farm. The method is particularly applicable to load balancing applied to AAA servers. In the preferred embodiments, the method can handle failovers and fail-back with few or no aborted authentications.

Claims

1. A method of load-balancing within a computer system, comprising:

(a) receiving a message representative of a request for computer resources from a supplicant, said message including a unique supplicant identifier;

(b) extracting the supplicant identifier from said message;

associating the supplicant with one of a plurality of available resources in dependence upon the supplicant identifier;

storing said association on a load balancing server that is coupled to and logically interposed between the supplicant and the available resources;

on receipt of a further message including message information from said supplicant, using said association to direct said message information, as originally received, toward said one resource; and

recording supplicant identifiers as messages are received, and storing each said respective identifier in an identifier look-up table against the respective resource with which it has been associated; and

maintaining a function look-up table, the table storing an identifier of each available resource for each possible output of a mapping function based on the supplicant identifier, and in which,

if no entry currently exists in the identifier look-up table on receipt of a message from a supplicant, making the association in dependence upon the function look-up table, and

writing a new entry to the identifier look-up table;

wherein the method is performed by one or more computing devices.

2. A method according to claim 1 in which the supplicant identifier is representative of a media access control (MAC) address.

3. A method according to claim 1, including the step of applying an access policy to the message, and associating the supplicant with the said one of the available resources if the policy so permits.

4. A method according to claim 1 including relaying said further message toward said one resource.

5. A method according to claim 1 in which the message or further message is a Remote Access Dial In User Service (“

RADIUS”

) packet.

6. A method according to claim 1 in which the message or further message uses the Extensible Authentication Protocol (EAP).

7. A method according to claim 1 in which the mapping function comprises calculating the value of at least a part of the supplicant identifier using a modulo N operation, where N is a positive integer greater than or equal to the number of resources available.

8. A method according to claim 1 in which, on receipt of the further message, a check is first made in the identifier look-up table and the further message is passed on to the already-associated resource if an entry currently exists in said table for the supplicant identifier within said message.

9. A method according to any one of claims 1 or 8 in which, on receipt of a completion message confirming that the resource is no longer required, the corresponding entry in the identifier look-up table is removed or marked as expired.

10. A method according to claim 1 in which said message is representative of an authentication request, and the association step includes associating the remote supplicant with one of a plurality of authentication servers.

11. A method according to claim 10 in which, on completion by the said one of the available resources of an authentication procedure, and on receipt of a completion message confirming completion, the corresponding entry in the identifier look-up table is removed or marked as expired.

12. A method according to claim 10 including maintaining a central store of session-state information, for all available resources, in a global session-state server (GSSS).

13. A method according to claim 1 including maintaining a central store of session-state information, for all available resources, in a global session-state server (GSSS);

the central store being updated on completion of an authentication procedure by one of said authentication servers.

14. A method according to claim 12 or claim 13 in which an authentication server requiring session-state information that it does not itself possess obtains said information from said Global Session-State Server (GSSS).

15. The method of claim 1, further comprising:

configuring the supplicant devices to point to the load balancing server instead of a destination server.

16. The method of claim 1, further comprising:

the load-balancing server selecting a single authentication server from among a set of identically configured authentication servers.

17. The method of claim 1, further comprising:

configuring the size of the identifier look-up table in proportion to the number of servers being managed.

18. The method of claim 1, further comprising:

the function look-up table maintaining a record of expired servers; and

the identifier look-up table maintaining a record of dead servers.

19. The method of claim 1, further comprising:

the load balancing server transmitting the message without any changes.

20. The method of claim 1, further comprising:

the load balancing server transmitting the message to an intermediate Extensible Authentication Protocol (EAP) device that knows how to route the message back to the originating supplicant.

21. A computer readable volatile or non-volatile medium storing a sequence of instructions which, when executed on a processor, cause said processor to carry out the steps of:

(a) receiving a message representative of a request for computer resources from a supplicant, said message including a unique supplicant identifier;

(b) extracting the supplicant identifier from the message;

(c) associating the supplicant with one of a plurality of available resources in dependence upon a function of the supplicant identifier;

(d) recording supplicant identifiers as messages are received, and storing each said respective identifier in an identifier look-up table against the respective resource with which it has been associated;

(e) storing said association on a load balancing server that is coupled to and logically interposed between the supplicant and the available resources;

(f) on receipt of a further message including message information from said supplicant, using said association to direct said message, as originally received, information toward said one resource;

(g) maintaining a function look-up table, the function look-up table storing an identifier of each available resource for with each possible output of a mapping function based on the supplicant identifier, and in which, if no entry currently exists in the identifier look-up table on receipt of a message from a supplicant, making the association in dependence upon the function look-up table, and writing a new entry to the identifier look-up table.

22. An apparatus for load-balancing within a computer system, said apparatus comprising:

one or more processors;

(a) means for receiving a message representative of a request for computer resources from a supplicant, said message including a unique supplicant identifier;

(b) means for extracting the supplicant identifier from the message;

(c) means for associating the supplicant with one of a plurality of available resources in dependence upon a function of the supplicant identifier;

(d) means for recording supplicant identifiers as messages are received, and storing each said respective identifier in an identifier look-up table against the respective resource with which it has been associated;

(e) means for storing said association on a load balancing server that is coupled to and logically interposed between the supplicant and the available resources;

(f) means for using said association, on receipt of a further message including message information from said supplicant, to direct said message information, as originally received, toward said one resource; and

(g) means for maintaining a function look-up table, the function look-up table storing an identifier of each available resource for each possible output of a mapping function based on the supplicant identifier, and in which,

if no entry currently exists in the identifier look-up table on receipt of a message from a supplicant, making the association in dependence upon the function look-up table, and

writing a new entry to the identifier look-up table.

23. An apparatus for load-balancing within a computer system, said apparatus comprising:

(a) a network interface for receiving a message representative of a request for computer resources from a supplicant, said message including a unique supplicant identifier;

(b) a processor carrying a stored sequence of instructions which, when executed, cause said processor to carry out the steps of;

(i) extracting the supplicant identifier from the message;

(ii) associating the supplicant with one of a plurality of available resources in dependence upon a function of the supplicant identifier;

(iii) recording supplicant identifiers as messages are received, and storing each said respective identifier in an identifier look-up table against the respective resource with which it has been associated

(iv) storing said association on a load balancing server that is coupled to and logically interposed between the supplicant and the available resources;

(v) maintaining a function look-up table, the table storing an identifier of each available resource for each possible output of a mapping function based on the supplicant identifier, and in which,

if no entry currently exists in the identifier look-up table on receipt of a message from a supplicant, making the association in dependence upon the function look-up table, and

writing a new entry to the identifier look-up table; and

(c) a switching system for switching which, on receipt of a further message including message information from said supplicant, uses said association to direct said message information, as originally received, toward said one resource.

24. The apparatus of claim 23, further comprising instructions which when executed cause, in response to sending a message from a supplicant to a resource and failing to receive a response from the resource within a specified time after a specified number of attempts, marking the corresponding resource as inactive in the function look-up table, and selecting a new resource selection index.

25. The apparatus of claim 24, further comprising instructions which when executed cause periodically sending a message from a supplicant to an inactive resource, receiving a response from the inactive resource, and marking the corresponding resource as active in the function look-up table.