TOKEN-BASED PRICING POLICIES FOR BURST-MODE OPERATIONS

• US 20140379506A1
• Filed: 06/25/2013
• Published: 12/25/2014
• Est. Priority Date: 06/25/2013
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: MARSHALL, STUART HENRY SEELYE, XIAO, WEI, SWIFT, BJORN PATRICK, MUNISWAMY-REDDY, KIRAN-KUMAR, FILIPE, MIGUEL MASCARENHAS, LU, YIJUN, STEFANI, STEFANO, HAMILTON, JAMES R.
• Granted Patent: US 10,764,185 B2
• Time in Patent Office: Days
• US Class Current: 705/26.1
• CPC Class Codes: G06F 9/5005 to service a request
• CPC Class Codes: G06Q 30/0283 Price estimation or determination
• CPC Class Codes: H04L 47/12 Avoiding congestion; Recovering from congestion
• CPC Class Codes: H04L 47/215 using token-bucket

Abstract

Methods and apparatus for token-based pricing policies for burst-mode operations are disclosed. A pricing policy to be applied to token population changes at a token bucket used for admission control during burst-mode operations at a work target is determined. Over a time period, changes to the token population of that bucket are recorded. A billing amount to be charged to a client is determined, based on the recorded changes in token population and an associated pricing amount indicated in the pricing policy.

Claims

1. A system, comprising:

one or more computing devices configured to;

instantiate one or more token buckets associated with workload management at a work target, wherein the work target is configured to operate in a plurality of modes of operation with respective sets of admission control parameters for accepting work requests for execution, and wherein a decision to accept a work request is made based at least in part on a token population of at least one bucket of the one or more token buckets;

determine a token pricing policy to be applied to a particular token bucket of the one or more token buckets, wherein the token pricing policy indicates (a) one or more applicability criteria for the token pricing policy, including an identification of at least a burst mode of operation of the plurality of modes of operation during which the token pricing policy is to be applied, and (b) a pricing amount, to be charged to a client, for a change to a token population of the particular token bucket;

record, over a time period, one or more changes to the token population of the particular token bucket, wherein the one or more changes occur during a burst mode of operation of the work target in which the one or more applicability criteria are met; and

generate a billing amount to be charged to the client based at least in part on the one or more changes recorded over the time period.

2. The system as recited in claim 1, wherein the one or more token buckets comprise a normal-mode bucket whose token population is used to determine a mode of operation of the work target, and one or more burst-mode buckets whose token population is used to determine whether to accept a work request during the burst mode of operation, wherein particular token bucket comprises a burst-mode bucket of the one or more burst-mode buckets.

3. The system as recited in claim 2, wherein the one or more burst-mode buckets comprise a local-burst-limit bucket whose token population is indicative of the available throughput capacity at the work target, and a shared-resource capacity bucket whose token population is indicative of available throughput capacity at a resource shared by a plurality of work targets, wherein the particular bucket comprises the shared-capacity bucket, and wherein a particular applicability criterion of the one or more applicability criteria indicates that the pricing policy is to apply in response to a determination that the token population of the local-burst-limit bucket is no greater than a specified threshold.

4. The system as recited in claim 1, wherein the change to the token population of the particular token bucket comprises a reduction in the token population as a result of one or more tokens being consumed to accept a received work request for execution.

5. The system as recited in claim 1, wherein the change to the token population of the particular token bucket comprises a reduction in the token population as a result of one or more tokens being transferred to a different bucket in response to a token sale operation implemented using a token marketplace.

6. A method, comprising:

performing, by one or more computing devices,

instantiating one or more token buckets associated with workload management at a work target, wherein a decision to accept a work request directed to the work target is made based at least in part on a token population of at least one bucket of the one or more token buckets;

determining a token pricing policy to be applied to a particular token bucket of the one or more token buckets during a burst mode of operation of the work target, wherein the token pricing policy indicates a pricing amount to be charged to a client for a change to a token population of the particular token bucket;

recording, over a time period, one or more changes to the token population of the particular token bucket, wherein the one or more changes are implemented during the burst mode of operation; and

generating a billing amount to be charged to the client based at least in part on the one or more changes recorded over the time period.

7. The method as recited in claim 6, wherein the one or more token buckets comprise a normal-mode bucket whose token population is used to determine a mode of operation of the work target, and one or more burst-mode buckets whose token population is used to determine whether to accept a work request during the burst mode of operation, wherein particular token bucket comprises a burst-mode bucket of the one or more burst-mode buckets.

8. The method as recited in claim 7, wherein the one or more burst-mode buckets comprise a local-burst-limit bucket whose token population is indicative of the throughput capacity at the work target, and a shared-resource capacity bucket whose token population is indicative of available throughput capacity at a resource shared by a plurality of work targets, wherein the particular bucket comprises the shared-capacity bucket, and wherein, in accordance with the pricing policy, the method further comprises performing, by the one or more computing devices:

in response to determining that the token population of the local-burst-limit bucket meets a threshold criterion, applying the pricing policy to a particular change of token population of the shared-resource capacity bucket.

9. The method as recited in claim 6, wherein the change to the token population of the particular token bucket comprises a reduction in the token population as a result of one or more tokens being consumed to accept a received work request for execution.

10. The method as recited in claim 6, wherein the change to the token population of the particular token bucket comprises a reduction in the token population as a result of one or more tokens being transferred to a different bucket in response to a token sale operation implemented using a token marketplace.

11. The method as recited in claim 10, further comprising performing, by the one or more computing devices:

implementing one or more programmatic interfaces enabling a particular client to indicate, via the token marketplace, that tokens of the particular token bucket are available for transfer to another token bucket.

12. The method as recited in claim 11, wherein the token pricing policy indicates that an amount to be charged for a transfer of a token to a different bucket from the particular bucket is to be determined based at least in part on one or more auction bids received for the transfer.

13. The method as recited in claim 6, further comprising performing, by the one or more computing devices:

implementing one or more programmatic interfaces enabling a client to select a token pricing policy from among a plurality of token pricing policies.

14. The method as recited in claim 6, wherein the pricing policy indicates a client-specified budget limit, further comprising performing, by the one or more computing devices:

determining to implement a change to the population of the particular token bucket based at least in part on the client-specified budget limit.

15. The method as recited in claim 6, wherein the work target comprises a first partition of a storage object, wherein the storage object includes at least the first partition and a second partition, wherein a particular change of the one or more changes to the token population of the particular bucket is a result of a transfer of a token from the particular bucket to a different bucket used for workload management of the second partition.

16. A non-transitory computer-accessible storage medium storing program instructions that when executed on one or more processors:

determine a token pricing policy to be applied to a particular token bucket of one or more token buckets used for admission control decisions at a work target, wherein the token pricing policy is to be applied during a burst mode of operation of the work target, and wherein the token pricing policy indicates a pricing amount to be charged to a client for a change to a token population of the particular token bucket;

record, over a time period, one or more changes to the token population of the particular token bucket during the burst mode of operation; and

generate a billing amount to be charged to the client based at least in part on the one or more changes recorded over the time period.

17. The non-transitory computer-accessible storage medium as recited in claim 16, wherein the one or more token buckets comprise a normal-mode bucket whose token population is used to determine whether to accept a work request during a normal mode of operation of the work target, and one or more burst-mode buckets whose token population is used to determine whether to accept a work request during the burst mode of operation, wherein the particular token bucket comprises a burst-mode bucket of the one or more burst-mode buckets, and wherein the instructions when executed on the one or more processors:

determine a different token pricing policy to be applied to token population changes of the normal-mode bucket.

18. The non-transitory computer-accessible storage medium as recited in claim 17, wherein the one or more burst-mode buckets comprise a local-burst-limit bucket whose token population is indicative of available throughput capacity at the work target, and a shared-resource capacity bucket whose token population is indicative of available throughput capacity at a resource shared by a plurality of work targets, wherein the particular bucket comprises the shared-capacity bucket, and wherein, in accordance with the pricing policy, the instructions when executed on the one or more processors:

in response to a determination that the token population of the local-burst-limit bucket meets a threshold criterion, apply the pricing policy to a particular change of token population of the shared-resource capacity bucket.

19. The non-transitory computer-accessible storage medium as recited in claim 16, wherein the change to the token population of the particular token bucket comprises a reduction in the token population as a result of one or more tokens being transferred to a different bucket in response to a token sale operation implemented using a token marketplace.

20. The non-transitory computer-accessible storage medium as recited in claim 16, wherein the particular bucket is configured with a token refill rate and a maximum token population limit, wherein the pricing policy comprises an indication of a different amount to be charged to the client for a change to at least one of:

(a) the token refill rate, or (b) the maximum token population limit.