Load balancing between service component instances

• US 7,616,640 B1
• Filed: 01/06/2005
• Issued: 11/10/2009
• Est. Priority Date: 12/02/1998
• Status: Expired due to Fees

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Sitaraman, Aravind, Sthothra Bhasham, Sampath Kumar, Lou, Shuxian, Zhang, Shujin
• Primary Examiner(s): Pham; Chi H
• Assistant Examiner(s): Boakye; Alexander
• Application Number:
  US11/031,229
• Time in Patent Office: 1,769 Days
• Field of Search: 370/395.4, 370/412, 370/255, 370/338, 370/413, 370/229, 370/389, 370/401, 370/414, 370/402, 370/415, 370/259, 370/416, 370/524, 370/418, 370/231, 370/237, 370/468, 370/352, 370/395.1, 370/395.41, 709/713, 709/200, 709/201, 709/202, 709/100, 709/101, 709/102, 709/103
• US Class Current: 370/395.1
• CPC Class Codes: H04L 12/2872 Termination of subscriber connections
• CPC Class Codes: H04L 12/2889 Multiservice, e.g. MSAN
• CPC Class Codes: H04L 67/1001 for accessing one among a plurality of replicated servers

Abstract

Service requests, which are used to properly process a network access request received from a client, are processed by routing the service requests between at least two service component instances according to a load balancing algorithm. Load balancing includes: calculating a first ticket amount and a second ticket amount; assigning the first ticket amount to a first instance and the second ticket amount to a second instance; using a selection scheme to select an instance having a ticket amount greater than a threshold amount to process a service request; decrementing the ticket amount corresponding to the instance selected; and scheduling the instance selected to receive a service request. The present invention may further include distinguishing between operable and inoperable instances, providing ticket amounts that are not based on performance ratings to inoperable instances, and providing ticket amounts that are based on performance ratings to operable instances.

Claims

1. A method of load balancing the processing of service requests between at least two service component instances, the method being performed by a processor in an electronic environment, the method comprising:

associating a first ticket amount with a first instance and a second ticket amount with a second instance, using a load balancer;

scheduling the first instance to receive a service request and decrementing the first ticket amount, if the first ticket amount is greater than a threshold amount and the first instance is selectable from the at least two service components instances under a predetermined scheme, or if the first instance is the only instance within the at least two instances having a ticket amount greater than the threshold amount; and

scheduling the second instance to receive the service request and decrementing the second ticket amount, if the second ticket amount is greater than the threshold amount and the second instance is selectable from the at least two service components instances under a predetermined scheme, or if the second instance is the only instance within the at least two instances having a ticket amount greater than the threshold amount.

2. The method of claim 1, further comprising:

calculating a first performance rating and a second performance rating; and

calculating the first ticket amount using the first performance rating and the second ticket amount using the second performance rating.

3. The method of claim 2, wherein calculating the performance rating is performed if a maintenance interval occurs.

4. The method of claim 2, wherein the calculating the first performance rating includes:

calculating a round trip time grade;

calculating a timed-out grade; and

averaging the round trip time grade and the timed-out grade.

5. The method of claim 2, wherein calculating the first ticket amount using the first performance rating includes:

selecting an initial ticket amount; and

setting the first ticket amount equal to the initial ticket amount multiplied by the first performance rating divided by the average performance rating of the at least two instances.

6. The method of claim 2, wherein calculating the second ticket amount using the second performance rating includes:

selecting an initial ticket amount; and

setting the second ticket amount equal to the initial ticket amount multiplied by the second performance rating divided by the average performance rating of the at least two instances.

7. The method of claim 2, wherein the calculating the first performance rating includes:

selecting a total number of tickets which may be allocated between or among the at least two instances;

calculating a first average round-trip value for the first instance and a second average round-trip value for the second instance;

dividing the first average round-trip value by the sum of the first and second round-trip values so as to obtain a first result; and

multiplying the total number of tickets by the first result.

8. The method of claim 1, further comprising:

calculating a third performance rating;

calculating a third ticket amount using the third performance rating;

associating the third ticket amount with a third instance; and

scheduling the third instance to receive a service request, if the third ticket amount is greater than the threshold amount and the third instance is selectable from the at least two service components instances under a predetermined scheme, or if the third instance is the only instance within the at least two instances having a ticket amount greater than the threshold amount.

9. An apparatus for load balancing the processing of service requests between at least two service component instances, the apparatus comprising:

means for associating a first ticket amount with a first instance and a second ticket amount with a second instance;

means for scheduling the first instance to receive a service request and means for decrementing the first ticket amount, if the first ticket amount is greater than a threshold amount and the first instance is selectable from the at least two service components instances under a predetermined scheme, or if the first instance is the only instance within the at least two instances having a ticket amount greater than the threshold amount; and

means for scheduling the second instance to receive the service request and means for decrementing the second ticket amount, if the second ticket amount is greater than the threshold amount and the second instance is selectable from the at least two service components instances under a predetermined scheme, or if the second instance is the only instance within the at least two instances having a ticket amount greater than the threshold amount.

10. The apparatus of claim 9, further comprising:

means for calculating a first performance rating and a second performance rating; and

means for calculating the first ticket amount using the first performance rating and the second ticket amount using the second performance rating.

11. The apparatus of claim 10, wherein the means for calculating the first and second performance rating is performed if a maintenance interval occurs.

12. The apparatus of claim 10, wherein the means for calculating the first performance rating includes:

means for calculating a round trip time grade;

means for calculating a timed-out grade; and

means for averaging the round trip time grade and the timed-out grade.

13. The apparatus of claim 10, wherein the means for calculating the first ticket amount using the first performance rating includes:

means for selecting an initial ticket amount; and

means for setting the first ticket amount equal to initial ticket amount multiplied by the first performance rating divided by an average performance rating of the at least two instances.

14. The apparatus of claim 10, wherein the means for calculating the second ticket amount using the second performance rating includes:

means for selecting an initial ticket amount; and

means for setting the second ticket amount equal to the initial ticket amount multiplied by the second performance rating divided by an average performance rating of the at least two instances.

15. The apparatus of claim 10, wherein the means for calculating the first performance rating includes:

means for selecting a total number of tickets which may be allocated between or among the at least two instances;

means for calculating a first average round-trip value for the first instance and a second average round-trip value for the second instance;

means for dividing the first average round-trip value by the sum of the first and second round-trip values so as to obtain a first result; and

means for multiplying the total number of tickets by the first result.

16. The apparatus of claim 9, further comprising:

means for calculating a third performance rating;

means for calculating a third ticket amount using the third performance rating;

means for associating the third ticket amount with a third instance; and

means for scheduling the third instance to receive a service request, if the third ticket amount is greater than the threshold amount and the third instance is selectable from the at least two service components instances under a predetermined scheme, or if the third instances is the only instance within the at least two instances having a ticket amount greater than the threshold amount.

17. A program storage device readable by a machine, tangibly embodying a program of instructions executable by the machine to perform a method of load balancing the processing of service requests between at least two service component instances, the method comprising:

associating a first ticket amount with a first instance and a second ticket amount with a second instance;

scheduling the first instance to receive a service request and decrementing the first ticket amount, if the first ticket amount is greater than a threshold amount and the first instance is selectable from the at least two service components instances under a predetermined scheme, or if the first instance is the only instance within the at least two instances having a ticket amount greater than the threshold amount;

scheduling the second instance to receive the service request and decrementing the second ticket amount, if the ticket amount is greater than the threshold amount and the second instance is selectable from the at least two service components instances under a predetermined scheme, or if the second instance is the only instance within the at least two instances having a ticket amount greater than the threshold amount.

18. A method of load balancing the processing of service requests between the at least two instances, including a first instance and a second instance, the method being performed by a processor in an electronic environment, the method comprising:

tracking at least one parameter;

calculating, using a performance rating calculator, for the first and second instance within the at least two instances, including a first performance rating for a first instance and a second performance rating for a second instance, and by assigning a first ticket amount to the first instance and a second ticket amount to the second instance, the first ticket amount and the second ticket amount based on the first performance rating and the second performance rating, respectively; and

scheduling an instance, responsive to the first and second performance ratings, which has a ticket amount greater than the selected threshold, from the at least two instances to receive a service request, and by decrementing the ticket amount.

19. The method of claim 18, wherein the calculating further comprises calculating the performance rating for the each instance when any one of the each instance fails to perform a selected number of services within a given period.

20. The method of claim 18, wherein the scheduling an instance further comprises performing the scheduling in a predetermined scheme.

21. A program storage device readable by a machine, tangibly embodying a program of instructions executable by the machine to perform a method of load balancing the processing of service requests between at least two instances, including a first instance and a second instance, the method comprising:

tracking at least one parameter;

calculating a performance rating for the first and second instance within the at least two instances, including a first performance rating for a first instance and a second performance rating for a second instance, and by assigning a first ticket amount to the first instance and a second ticket amount to the second instance, the first ticket amount and the second ticket amount based on the first performance rating and the second performance rating, respectively; and

scheduling an instance, responsive to the first and second performance ratings, which has a ticket amount greater than the selected threshold, from the at least two instances to receive a service request, and by decrementing the ticket amount.

22. A load balancer for load balancing the processing of service requests between at least two instances, including a first instance and a second instance, the apparatus comprising:

a parameter tracker for tracking at least one parameter;

a performance rating calculator responsive to the at least one parameter;

by calculating a performance rating for each instance within the at least two instances, including a first performance rating for a first instance and a second performance rating for a second instance, and

by assigning a first ticket amount to the first instance and a second ticket amount to the second instance, the first ticket amount and the second ticket amount based on the first performance rating and the second performance rating, respectively; and

a traffic manager responsive to the first and second performance ratings by scheduling an instance in a predetermined manner, which has a ticket amount greater than the selected threshold, from the at least two instances to receive a service request, and by decrementing the ticket amount.

23. The apparatus of claim 22, wherein the performance rating calculator calculates the performance rating for the each instance when any one of the each instance fails to perform a selected number of services within a given period.

24. The system of claim 22, further including a third instance.

25. A communications system having a network access point for processing network access requests, the system comprising:

a first instance responsive to at least one service request;

a second instance responsive to at least one service request;

a first network access point coupled to the first instance and the second instance, the first network access point having;

a parameter tracker for tracking at least one parameter;

a performance rating calculator responsive to the at least one parameter;

by calculating a performance rating for each instance within the at least two instances, including a first performance rating for the first instance and a second performance rating for a second instance, and

by assigning a first ticket amount to the first instance and a second ticket amount to the second instance, the first ticket amount and the second ticket amount based on the first performance rating and the second performance rating, respectively; and

a traffic manager responsive to the first and second performance ratings by scheduling an instance in a predetermined manner, which has a ticket amount greater than the selected threshold, from the at least two instances to receive a service request and by decrementing a ticket amount associated with the instance.

26. The system of claim 25, wherein the performance rating calculator calculates when any one of the each instance fails to perform a selected number of services within a given period.

27. The system of claim 25, further including a second network access point.