Rate control by token buckets
First Claim
Patent Images
1. A method comprising:
- maintaining a rate control mechanism for a source of requests, the rate control mechanism including a token bucket represented by a counter;
the bucket accumulating tokens at a given rate until the counter reaches a token bucket burst size;
in response to receiving a request, the request associated with a unit of work rate per measure of time, computing a quantity of accumulated tokens as a function of token bucket parameters, wherein the token bucket parameters include the rate at which tokens are accumulated, a burst size of the bucket, time of a last computation, and a quantity of tokens remaining since the last computation;
updating the counter on demand, and computing a time for granting the received request based on the updated counter; and
servicing the request if the required quantity of tokens are accumulated, and computing a future time when the required quantity of tokens will be accumulated if the required quantity of tokens are unavailable.
6 Assignments
0 Petitions
Accused Products
Abstract
Aspects of the invention are provided for rate control and management of service requests. A token bucket is employed in conjunction with a capacity sharing scheme to manage processing of service requests. Each token represents the capacity reserved for a particular source of requests. Excess tokens may be shed, with the excess tokens representing available excess capacity. Similarly, a projected time at which the service request(s) may be released may be computed in the event the bucket does not contain the required quantity of tokens to process the request.
8 Citations
18 Claims
-
1. A method comprising:
-
maintaining a rate control mechanism for a source of requests, the rate control mechanism including a token bucket represented by a counter; the bucket accumulating tokens at a given rate until the counter reaches a token bucket burst size; in response to receiving a request, the request associated with a unit of work rate per measure of time, computing a quantity of accumulated tokens as a function of token bucket parameters, wherein the token bucket parameters include the rate at which tokens are accumulated, a burst size of the bucket, time of a last computation, and a quantity of tokens remaining since the last computation; updating the counter on demand, and computing a time for granting the received request based on the updated counter; and servicing the request if the required quantity of tokens are accumulated, and computing a future time when the required quantity of tokens will be accumulated if the required quantity of tokens are unavailable. - View Dependent Claims (2, 3, 4, 5, 6, 7)
-
-
8. A computer program product for managing rate control of requests, the computer program product comprising a computer readable storage device having program code embodied therewith, the program code executable by a processor to:
-
maintain a rate control mechanism for a source of requests, the rate control mechanism including a token bucket represented by a counter; the bucket to accumulate tokens at a given rate until the counter reaches a token bucket burst size; in response to receiving a request, the request associated with a unit of work rate per measure of time, compute a quantity of accumulated tokens as a function of token bucket parameters, wherein the token bucket parameters include the rate at which tokens are accumulated, a burst size of the bucket, time of a last computation, and a quantity of tokens remaining since the last computation; update the counter on demand, and compute a time to grant the received request based on the updated counter; and service the request if the required quantity of tokens are accumulated, and compute a future time when the required quantity of tokens will be accumulated if the required quantity of tokens are unavailable. - View Dependent Claims (9, 10, 11, 12, 13)
-
-
14. A method comprising:
-
maintaining a rate control mechanism for a source of requests, the rate control mechanism including two or more token buckets functioning as a unit for managing multiple sources of requests, each bucket representing a share of resource capacity; each of the buckets accumulating tokens at a given rate; in response to receiving a request, computing a quantity of accumulated tokens as a function of token bucket parameters, wherein the token bucket parameters include the rate at which tokens are accumulated in each bucket, a burst size of each bucket, time of a last computation, and a quantity of tokens remaining in each bucket since the last computation; updating a token bucket counter on demand; servicing a request if the required quantity of tokens are accumulated; and computing availability of excess tokens within the unit if the required quantity of tokens are unavailable, including sharing excess or unused capacity within the unit. - View Dependent Claims (15, 16, 17, 18)
-
Specification