Rate Control By Token Buckets

• US 20150036503A1
• Filed: 08/05/2013
• Published: 02/05/2015
• Est. Priority Date: 08/05/2013
• Status: Active Grant

• Current Assignee: GlobalFoundries, Inc.
• Original Assignee: International Business Machines Corporation
• Inventors: Kaplan, Marc A., Povzner, Anna S.
• Granted Patent: US 9,178,827 B2
• Time in Patent Office: Days
• US Class Current: 370/235.1
• CPC Class Codes: H04L 47/215 using token-bucket

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.

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, including updating a token bucket counter on demand and computing a time for granting the received request based on the updated token bucket 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.

2. The method of claim 1, further comprising computing a quantity of accumulated tokens as a function of token bucket parameters that include the rate at which tokens are accumulated, a burst size of the bucket, time of a last computation, and the quantity of tokens remaining since the last computation.

3. The method of claim 1, further comprising computing future time for servicing a request as a function of the required quantity of tokens, the quantity of accumulated tokens, rate at which tokens are accumulated, and time of a last computation.

4. The method of claim 1, further comprising an array of token buckets functioning as a unit that controls multiple sources of requests, each bucket representing a share of resource capacity.

5. The method of claim 4, further comprising capacity driven sharing of tokens in the array, including assigning an overflow size to each bucket in the array and sharing excess or unused capacity within the array, including each bucket in the array measuring available excess tokens, and for each bucket assigning a reserved burst size smaller than a burst size of the buckets and tokens above the reserved burst size available to other buckets in the array.

6. The method of claim 5, further comprising partitioning the array, and constraining sharing of tokens in an intra-partition basis.

7. The method of claim 4, further comprising overflowing unused tokens of the array into a catch basin, the basin representing short term unused capacity available for sharing with the array.

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, including an update of the counter on demand and computation of 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.

9. The computer program product of claim 8, further comprising program code to compute a quantity of accumulated tokens as a function of token bucket parameters that include the rate at which tokens are accumulated, a burst size of the bucket, time of a last computation, and the quantity of tokens remaining since the last computation.

10. The computer program product of claim 8, further comprising program code to compute future time for servicing the request as a function of the required quantity of tokens, the quantity of accumulated tokens, rate at which tokens are accumulated, and time of a last computation.

11. The computer program product of claim 8, further comprising program code to support an array of token buckets functioning as a unit that controls multiple sources of requests, each bucket representing a share of resource capacity.

12. The computer program product of claim 11, further comprising program code to support capacity driven sharing of tokens in the array, including assigning an overflow size to each bucket in the array and sharing excess or unused capacity within the array, including each bucket in the array measuring available excess tokens, and for each bucket assigning a reserved burst size smaller than a burst size of the buckets and tokens above the reserved burst size available to other buckets in the array.

13. The computer program product of claim 12, further comprising program code to partition the array, and constrain sharing of tokens in an intra-partition basis.

14. The computer program product of claim 11, further comprising program code to overflow unused tokens of the array into a catch basin, the basin representing short term unused capacity available for sharing with the array.

15. 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, including updating a token bucket counter on demand; and

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.

16. The method of claim 15, further comprising overflowing unused tokens within the unit into a shared bin, wherein tokens within the bin are available to each of the buckets in the unit to service the request.

17. The method of claim 16, wherein overflowing unused tokens includes each bucket in the unit measuring available excess tokens, and for each bucket assigning a reserved burst size smaller than a burst size of the buckets and tokens above the reserved burst size available to other buckets in the array.

18. The method of claim 15, further comprising computing a future time when the required quantity of tokens will be accumulated if the required quantity of tokens are unavailable in a bucket servicing the request and in the bin.