Method for Distributed Traffic Shaping across a Cluster

• US 20080008095A1
• Filed: 07/10/2006
• Published: 01/10/2008
• Est. Priority Date: 07/10/2006
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Gilfix, Michael A.
• Granted Patent: US 7,760,641 B2
• Time in Patent Office: Days
• US Class Current: 370/235
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/19 at layers above the network layer network arrangements for networked applications for scheduling or organising the servicing of application requests H04L67/60
• CPC Class Codes: H04L 47/215 using token-bucket
• 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/1014 based on the content of a request
• CPC Class Codes: H04L 67/1023 based on a hash applied to IP addresses or costs
• CPC Class Codes: H04L 67/1034 Reaction to server failures by a load balancer
• CPC Class Codes: H04L 67/14 Session management for real-time applications in data packet communications networks H04L65/1066
• CPC Class Codes: H04L 67/63 Routing a service request depending on the request content or context

Abstract

A network is provided herein comprising a plurality of network resources, and at least one network cluster having a plurality of cluster members. Each member of the cluster may be configured for utilizing one or more of the network resources and for tracking usage thereof. For example, each member of the cluster may include one or more token buckets for tracking that member'"'"'s usage of the network resources. At least one member of the cluster (i.e., a “reservation coordinator”) may include a first set of computer-executable instructions for receiving network traffic destined for a particular network resource at a first rate (i.e., a maximum average sustained rate). In addition, the reservation coordinator may include a second set of computer-executable instructions for distributing the first rate among at least a subset of the cluster members. In some cases, each member of the cluster may include a third set of computer-executable instructions for changing how the first rate is distributed among members of the subset. For example, the third set of computer-executable instructions may include instructions for attempting to reserve a substantially larger or smaller portion of the first rate.

Claims

1. A method for controlling the distribution of network traffic sent to a network cluster having a plurality of cluster members, the method comprising:

receiving network traffic destined for a particular network resource at a first rate, the network traffic comprising a plurality of client requests, each having a weight assigned thereto; and

distributing the first rate among a subset of the cluster members, wherein each cluster member within the subset maintains a token bucket for the particular network resource, and wherein the amount of rate distributed to each cluster member within the subset corresponds to a regeneration rate for a respective token bucket.

2. The method as recited in claim 1, further comprising distributing burst among the subset of cluster members.

3. The method as recited in claim 2, wherein a sum of the rates distributed to each cluster member within the subset equals the first rate, and wherein a sum of the burst distributed to each cluster member within the subset equals a total burst output for the network cluster.

4. The method as recited in claim 3, wherein a substantially equal amount of rate and burst is distributed to each cluster member within the subset.

5. The method as recited in claim 3, wherein the amount of rate and the amount of burst distributed to one or more cluster members within the subset differs from the amount of rate and the amount of burst distributed to other cluster members within the subset.

6. The method as recited in claim 3, wherein the total burst output divided by the largest amount of burst distributed to any of the cluster members within the subset is greater than or equal to the largest weight assigned to the plurality of client requests.

7. The method as recited in claim 3, further comprising redistributing the total burst output among active members of the subset, if one or more cluster members of the subset fails or is taken off-line.

8. The method as recited in claim 1, further comprising:

directing one of the client requests to one of the cluster members in the subset; and

accessing a local token bucket stored within the one cluster member for tracking usage of the particular network resource, wherein the local token bucket contains a current number of tokens and is configured for accepting additional tokens at a second rate equal to the regeneration rate assigned to the local token bucket.

9. The method as recited in claim 8, further comprising consuming a number of tokens from the local token bucket, the number being equal to the weight assigned to the one client request, if the current number of tokens contained within the local token bucket is greater than or equal to the weight assigned to the one client request.

10. The method as recited in claim 9, further comprising attempting to increase the regeneration rate assigned to the local token bucket regardless of whether or not tokens were consumed from the local token bucket.

11. The method as recited in claim 10, wherein the step of attempting comprises:

sending a reservation request to an estimation algorithm configured for determining when to satisfy a reservation request; and

receiving a reservation amount from the estimation algorithm, wherein the reservation amount is based on whether or not the one client request was received in a burst of network traffic.

12. The method as recited in claim 11, wherein if the one client request was not received in a burst of network traffic, the step of receiving comprises:

receiving a zero reservation amount from the estimation algorithm, if the reservation request is sent within a designated silence period; and

receiving a non-zero reservation amount from the estimation algorithm, if the reservation request is sent after the designated silence period ends.

13. The method as recited in claim 12, wherein if the one client request was received in a burst of network traffic, the step of receiving comprises:

determining a current rate consumption trend for all network traffic received by the one cluster member for the particular network resource during a current time period;

receiving a zero reservation amount from the estimation algorithm, if;

(a) the reservation request is sent within a designated silence period, or (b) the current rate consumption trend for the one cluster member is decreasing or steady and the amount of rate distributed to the one cluster member is greater than zero; and

receiving a non-zero reservation amount from the estimation algorithm, if the reservation request is sent after the designated silence period ends.

14. The method as recited in claim 13, wherein upon receiving a non-zero reservation amount from the estimation algorithm, the step of attempting further comprises:

sending the reservation request to a reservation algorithm configured for determining whether or not sufficient rate capacity remains within the cluster to satisfy the reservation request;

receiving a zero reservation amount from the reservation algorithm, if insufficient rate capacity remains within the cluster to satisfy the reservation request; and

receiving a non-zero reservation amount from the reservation algorithm, if sufficient rate capacity remains within the cluster to satisfy the reservation request.

15. The method as recited in claim 14, wherein upon receiving a non-zero reservation amount from the reservation algorithm, the method further comprises increasing the amount of rate distributed to the one cluster member by adding the non-zero reservation amount to the regeneration rate for the local token bucket.

16. A network comprising:

a plurality of network resources; and

a network cluster having a plurality of cluster members, each individually configured for utilizing one or more of the network resources and for tracking usage thereof.

17. The network as recited in claim 16, wherein each member of the cluster comprises a separate database containing one or more token buckets for tracking that member'"'"'s usage of one or more network resources.

18. The network as recited in claim 17, wherein at least one member of the cluster comprises:

a first set of computer-executable instructions configured for receiving network traffic destined for a particular network resource at a first rate, the network traffic comprising a plurality of client requests; and

a second set of computer-executable instructions configured for distributing the first rate among a subset of cluster members, wherein each member within the subset maintains a local token bucket for the particular network resource, and wherein

the amount of rate distributed to each member within the subset corresponds to a regeneration rate for a respective local token bucket.

19. The network as recited in claim 18, wherein the second set of computer-executable instructions are further configured for distributing burst among active members of the subset.

20. The network as recited in claim 18, wherein each member of the cluster comprises a third set of computer-executable instructions for changing how the first rate is distributed among the members of the subset.

21. The network as recited in claim 20, wherein the third set of computer-executable instructions comprise:

a fourth set of computer-executable instructions for attempting to reserve a larger portion of the first rate; and

a fifth set of computer-executable instructions for attempting to reserve a smaller portion of the first rate.

22. The network as recited in claim 21, wherein the fourth set of computer-executable instructions are executed by only one member of the subset at any given time.

23. The network as recited in claim 21, wherein the fifth set of computer-executable instructions are executed by all members of the subset at once.