Patent ID: 7813276

Claim:
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, 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, said cluster member having a workload shared across said plurality of cluster members and configured for running common applications and used to provide key databases, file sharing, business applications and consumer services; a first set of computer-executable instructions for controlling the admission of client requests sent to that cluster member, 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.