Load balancing between service component instances

• US 6,442,165 B1
• Filed: 12/02/1998
• Issued: 08/27/2002
• Est. Priority Date: 12/02/1998
• Status: Expired due to Term

• 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): Vincent, David
• Assistant Examiner(s): Boakye, Alexander O.
• Application Number:
  US09/205,004
• Time in Patent Office: 1,364 Days
• Field of Search: 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/395.4, 370/237, 370/395.41, 370/412, 370/468, 370/230, 370/352, 370/395.21, 709/713, 709/200, 709/201, 709/202, 709/100, 709/101, 709/102, 709/103, 709/105
• US Class Current: 370/395.4
• CPC Class Codes: G06F 9/505 considering the load

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 comprising:

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

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

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

2. The method of claim 1, further comprising:

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

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

3. The method of claim 2, wherein calculating said first and second performance rating is performed if a maintenance interval occurs.

4. The method of claim 2, wherein calculating said first and second performance rating is performed if a maintenance interval occurs and when at least one timed-out service request occurs.

5. The method of claim 2, wherein said step of calculating said first performance rating includes the steps of:

calculating a round trip time grade;

calculating a timed-out grade; and

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

6. The method of claim 5, wherein said step of calculating said round trip time grade includes the steps of:

finding an average round trip time by;

using a history of at least one performance parameter;

setting said round trip time grade equal to 100 if said average round trip time is less than 500 milliseconds;

setting said round trip time grade equal to 0 if said average round trip time is greater than 10,000 milliseconds; and

setting said round trip time grade equal to (10,000−

said average round trip time) divided by 95.

7. The method of claim 5, wherein calculating said timed-out grade includes:

setting said timed-out grade equal to 100 if a history of said timed-out grade includes no timed-out service requests;

setting said timed-out grade equal to 0 if the number of timed-out grade in said history are greater than half the total number of service requests made; and

setting said timed-out grade equal to (1−

(the number of timed-out service requests divided by half the total number of service requests made))*100.

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

selecting an initial ticket amount; and

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

9. The method of claim 2, wherein said step of calculating said second ticket amount using said second performance rating includes:

selecting an initial ticket amount; and

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

10. The method of claim 2, wherein said step of calculating said first performance rating includes the steps of:

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 said first instance and a second average round-trip value for said second instance;

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

multiplying said total number of tickets by said first result.

11. The method of claim 1, further including keeping a history of at least one performance parameter for said first instance and said second instance, respectively.

12. The method of claim 11, wherein said at least one performance parameter includes a round-trip time parameter which is defined as a time period beginning from the time a service request is sent to a selected instance until the time a reply to said service request is received from said selected instance.

13. The method of claim 11, wherein said at least one performance parameter includes a reply-request ratio parameter which is defined by a number of replies to service requests performed by said selected instance divided by a number of service requests sent to said selected instance.

14. The method of claim 11, wherein said at least one performance parameter includes a time-out parameter which is defined by a number service requests which are sent to said selected instance and which are not replied to by said selected instance with a selected time-out period.

15. The method of claim 1, further comprising:

calculating a third performance rating;

calculating a third ticket amount using said third performance rating;

associating said third ticket amount with a third instance; and

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

16. 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 said 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 said first instance and a second ticket amount to said second instance, said first ticket amount and said second ticket amount based on said first performance rating and said second performance rating, respectively; and

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

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

18. The apparatus of claim 16, wherein said traffic manager schedules said service requests in a round-robin manner.

19. The system of claim 16, further including a third instance.

20. 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 said first instance and said second instance, said first network access point having;

a parameter tracker for tracking at least one parameter;

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

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

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

22. The system of claim 20, wherein said traffic manager schedules said service requests in a round-robin manner.

23. The system of claim 20, further including a second network access point.

24. A method of load balancing the processing of service requests between at least two service component instances, the method comprising:

designating as operable a first instance and a second instance;

distributing service requests to said first instance and said second instance;

distributing service requests to said first instance and said second instance using a load-balancing distribution scheme after the expiration of a maintenance interval and if at least one timed-out packet was generated during said maintenance interval, said load-balancing distribution scheme including;

calculating a first performance rating and a second performance rating;

calculating a first ticket amount using said first performance rating and assigning said first ticket amount to said first instance, if said first instance is operable;

calculating a second ticket amount using said second performance rating and assigning said second ticket amount to said second instance, if said second instance is operable;

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

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

25. The method of claim 24, further including selecting a detection threshold for said first instance and said second instance.

26. The method of claim 25, further including:

tracking a first number of consecutive timed-out service requests that occur for said first instance;

tracking a second number of consecutive timed-out service requests that occur for said second instance;

designating said first instance inoperable and assigning a first ticket amount having a value one increment above said threshold amount, if said first number of consecutive timed-out service requests exceeds said detection threshold; and

designating said second instance inoperable and assigning a second ticket amount having a value one increment above said threshold amount, if said second number of consecutive timed-out service requests exceeds said detection threshold.

27. The method of claim 26, further including designating said first instance operable, calculating said first ticket amount using said first performance rating, and assigning said first ticket amount to said first instance, if said first instance replies to a service request.

28. The method of claim 26, further including designating said second instance operable, calculating said second ticket amount using said second performance rating, and assigning said second ticket amount to said second instance, if said second instance replies to a service request.

29. The method of claim 24, wherein said at least one timed-out packet is associated with said first instance.

30. The method of claim 24, wherein said at least one timed-out packet is associated with said second instance.

31. A method of load balancing the processing of service requests between at least two service component instances which have an initial ticket amount that is greater than a threshold amount, the method comprising:

scheduling service requests to each instance having a ticket amount greater than the threshold amount;

decrementing a ticket amount corresponding to one of said each instance each time said each instance is scheduled to receive a service request;

resetting said ticket amount of said each instance to the initial ticket amount each time a selected number of said each instance have a ticket amount that is equal to or less than the threshold ticket amount; and

resetting said ticket amount of said each instance to a corresponding calculated ticket amount each time a selected interrupt expires.

32. The method of claim 31, further including:

calculating a performance rating for each instance; and

calculating said calculated ticket amount using said performance rating that corresponds to said each instance.

33. The method of claim 31, further including resetting said ticket amount of said each instance to said calculated ticket amount each time said selected number of said each instance have a ticket amount that is equal to or less than the threshold ticket amount.