Method for Distributed Hierarchical Admission Control across a Cluster

• US 20080008090A1
• 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,813,276 B2
• Time in Patent Office: Days
• US Class Current: 370/230
• CPC Class Codes: H04L 47/15 in relation to multipoint traffic arrangements for broadcast or multicast in data networks H04L12/18
• CPC Class Codes: H04L 47/70 Admission control; Resource allocation
• CPC Class Codes: H04L 47/745 Reaction in network
• CPC Class Codes: H04L 47/762 triggered by the network
• CPC Class Codes: H04L 47/782 Hierarchical allocation of resources, e.g. involving a hierarchy of local and centralised entities
• CPC Class Codes: H04L 47/83 based on usage prediction

Abstract

A network cluster is provided herein having a plurality of cluster members. In order to control the admission of client requests sent to the cluster, one member of the cluster is elected “reservation coordinator.” The reservation coordinator runs a reservation algorithm for controlling the distribution of rate capacity across members of the cluster. For example, each member of the cluster may reserve some amount of rate from the coordinator to allow for passing of client requests. To ensure that each member is provided with the appropriate rate capacity, each member of the cluster runs an estimation algorithm to determine whether or not additional rate capacity should be reserved from the reservation coordinator, or released back into the cluster for redistribution. The estimation algorithm is run in real-time and allows the admission control algorithm to adapt to changes in rate distribution.

Claims

1. A network cluster comprising a plurality of cluster members, wherein each member of the cluster comprises:

a first database containing a hierarchical tree structure for tracking a current rate consumption of that cluster member; and

a first set of computer-executable instructions for controlling the admission of client requests sent to that cluster member.

2. The network cluster as recited in claim 1, wherein the hierarchical tree structure stored within the first database comprises a plurality of levels, a plurality of nodes, and at least one branch, wherein a single one of the nodes is a root node occupying a highest level of the tree structure, wherein a given branch connects a parent node in a given level to a child node in a level directly below the given level, and wherein each node of the tree structure comprises a bucket configured for accepting tokens up to a maximum rate limit, which is specified for that bucket as a maximum number of tokens added per time period.

3. The network cluster as recited in claim 2, wherein the first set of computer-executable instructions comprise:

a second set of computer-executable instructions for receiving a client request for a service or operation provided by one of the cluster members, the client request having a weight assigned thereto;

a third set of computer-executable instructions for accessing the tree structure stored within the first database of the cluster member receiving the client request;

a fourth set of computer-executable instructions for traversing the tree structure to get a chain of buckets descending from the root node to a child node corresponding to the requested service or operation;

a fifth set of computer-executable instructions for admitting the client request, if a number of tokens equal to the weight of the client request can be added to each bucket within the chain of buckets without exceeding the maximum rate limit specified for any bucket in the chain; and

a sixth set of computer-executable instructions for attempting to reserve additional rate capacity to satisfy the client request, if adding the number of tokens causes any bucket within the chain of buckets to exceed its maximum rate limit for that time period.

4. The network cluster as recited in claim 3, wherein the sixth set of computer-executable instructions comprise:

a seventh set of computer-executable instructions for sending a reservation request to ask for the additional rate capacity;

an eighth set of computer-executable instructions for updating the tree structure with a non-zero reservation amount if;

(a) the reservation request is not sent within a designated silence period, and (b) sufficient rate capacity remains within the cluster to satisfy the reservation request; and

a ninth set of computer-executable instructions for traversing the updated tree structure to get a new chain of buckets descending from the root node to the child node corresponding to the requested service or operation.

5. The method as recited in claim 4, wherein following the ninth set of computer-executable instructions, the first set of computer-executable instructions further comprises:

a tenth set of computer-executable instructions for admitting the client request, if the number of tokens can be added to each bucket within the new chain of buckets without exceeding the maximum rate specified for any bucket in the chain; and

an eleventh set of computer-executable instructions for rejecting the client request, if adding the number of tokens causes any bucket within the new chain of buckets to exceed its maximum rate for that time period.

6. A method for controlling the admission of client requests sent to a cluster having a plurality of cluster members, the method comprising:

receiving a client request for a service or operation provided by one of the cluster members, the client request having a weight assigned thereto;

accessing a tree structure stored within the one cluster member, the tree structure comprising a plurality of levels, a plurality of nodes, and at least one branch, wherein a single one of the nodes is a root node occupying a highest level of the tree structure, wherein a given branch connects a parent node in a given level to a child node in a level directly below the given level, and wherein each node of the tree structure comprises a bucket configured for accepting tokens up to a maximum rate limit, which is specified for that bucket as a maximum number of tokens added per time period;

traversing the tree structure to get a chain of buckets descending from the root node to a child node corresponding to the requested service or operation; and

admitting the client request, if a number of tokens equal to the weight of the client request can be added to each bucket within the chain of buckets without exceeding the maximum rate limit specified for any bucket in the chain.

7. The method as recited in claim 6, further comprising attempting to reserve additional rate capacity to satisfy the client request, if adding the number of tokens causes any bucket within the chain of buckets to exceed its maximum rate for that time period.

8. The method as recited in claim 7, wherein the step of attempting to reserve additional rate capacity comprises:

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

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.

9. The method as recited in claim 8, wherein the estimation algorithm is run by the cluster member that received the client request.

10. The method as recited in claim 8, further comprising rejecting the client request upon receiving a zero reservation amount from the estimation algorithm.

11. The method as recited in claim 8, wherein upon receiving a non-zero reservation amount from the estimation algorithm, the step of attempting to reserve additional rate capacity 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.

12. The method as recited in claim 11, wherein the reservation algorithm is run by one of the plurality of cluster members elected to become reservation coordinator.

13. The method as recited in claim 11, further comprising rejecting the client request upon receiving a zero reservation amount from the reservation algorithm.

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

updating the tree structure of the one cluster member with the non-zero reservation amount received from the reservation algorithm; and

traversing the updated tree structure to get a new chain of buckets descending from the root node to the child node corresponding to the requested service or operation.

15. The method as recited in claim 14, wherein upon traversing the updated tree structure, the method further comprises:

admitting the client request, if the number of tokens can be added to each bucket within the new chain of buckets without exceeding the maximum rate specified for any bucket in the chain;

or

rejecting the client request, if adding the number of tokens causes any bucket within the new chain of buckets to exceed its maximum rate for that time period.

16. A method for releasing rate capacity from one member of a cluster comprising a plurality of cluster members, the method comprising:

receiving one or more client requests, each having a weight assigned thereto, over the course of a current time period;

calculating an average rate for the current time period by summing the weights of the client requests received during the current time period and dividing the sum by the current time period;

determining a current rate consumption trend by comparing the average rate calculated for the current time period to an average rate calculated for a previous time period; and

releasing rate capacity from one member of the cluster based on the current rate consumption trend and a current reservation amount allocated to that cluster member.

17. The method as recited in claim 16, wherein the current rate consumption trend is determined to be:

increasing, if the average rate for the current time period is higher than the average rate for the previous time period;

steady, if the average rate for the current time period is equal to the average rate for the previous time period;

or

decreasing, if the average rate for the current time period is lower than the average rate for the previous time period.

18. The method as recited in claim 17, wherein rate capacity is released from the one member of the cluster if:

(a) the current rate consumption trend is determined to be steady or decreasing, and (b) the one member of the cluster has more reserved rate than it is currently using.

19. The method as recited in claim 18, wherein the one member of the cluster is determined to have more reserved rate than it is currently using if a difference between the current reservation amount and the average rate for the current time period is greater than a predetermined amount.

20. The method as recited in claim 17, wherein rate capacity is not released from the one member of the cluster if:

(a) the current rate consumption trend is determined to be increasing, or (b) the current reservation amount is zero.