System and method for managing requests for pooled resources during non-contention

• US 8,676,621 B1
• Filed: 09/28/2011
• Issued: 03/18/2014
• Est. Priority Date: 09/28/2011
• Status: Expired due to Fees

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Helfrich, Brian, Nunnerley, David
• Primary Examiner(s): Hammond, III, Thomas M
• Application Number:
  US13/247,846
• Time in Patent Office: 902 Days
• Field of Search: 705 35- 45
• US Class Current: 705/7.12
• CPC Class Codes: G06Q 10/0631 Resource planning, allocation, distributing or scheduling for enterprises or organisations
• CPC Class Codes: G06Q 10/10 Office automation; Time management

Abstract

A computer system that provides pooled computing resources to clients may receive requests for resources, each of which includes a bid amount. While the supply of resources exceeds the demand, the system may adaptively determine a theoretical bid threshold for the resource pool that represents the predicted value of the lowest bid amount for which corresponding requests will be granted when demand for the resources exceeds supply. The determination may be dependent on a distribution of the bid amounts included in the requests for resources. The system may adaptively determine the lowest bid amount for which corresponding ones of the requests will be granted during non-contention dependent on changes in demand for the resources, the total capacity of the resource pool, and the theoretical bid threshold value, and may grant requests that include higher bid amounts. The use of some resources may be terminated in response to changes in demand.

Claims

1. A method, comprising:

performing by a computer that provides access to pooled computing resources to clients;

receiving a plurality of requests for use of at least some of computing resources in a computing resource pool while supply of the computing resources exceeds demand for the computing resources, wherein each request comprises a respective bid amount;

determining a value of a theoretical bid threshold for the computing resources in the computing resource pool, wherein the theoretical bid threshold value represents a predicted value of the lowest bid amount for which corresponding requests for the computing resources will be granted when demand for the computing resources exceeds supply for the computing resources, and wherein said determining the value of the theoretical bid threshold is dependent on the bid amounts included in the plurality of requests;

repeatedly determining, based at least in part on the number of computing resources requested in the plurality of requests, the number of computing resources available in the computing resource pool, and the theoretical bid threshold, a value of a current non-contention bid threshold for the computing resource pool, wherein the current non-contention bid threshold value represents the lowest bid amount for which corresponding ones of the plurality of requests will be granted when supply for the computing resources exceeds demand for the computing resources, and wherein the current non-contention bid threshold value is less than the theoretical bid threshold value and greater than a predetermined minimum bid threshold value for the computing resources;

identifying one or more of the plurality of requests for which the respective bid amount is not less than the determined value of the current non-contention bid threshold; and

based at least in part upon the respective bid amounts of the identified one or more of the plurality of requests, granting access to the computing resources for the identified one or more of the plurality of requests.

2. The method of claim 1, further comprising:

terminating the use of one or more resources of the resource pool previously granted in response to a request for resources for which the value of the included bid amount was less than the current non-contention bid threshold value.

3. The method of claim 1, wherein said determining the value of the theoretical bid threshold comprises:

modeling the distribution of at least a portion of the bid amounts included in the plurality of requests; and

calculating the value of the theoretical bid threshold dependent on the distribution.

4. The method of claim 1, further comprising:

receiving one or more additional requests for resources in the resource pool while supply of the resources exceeds demand for the resources, wherein each additional request comprises a respective bid amount; and

modifying the value of the current non-contention bid threshold for the resource pool, wherein said modifying comprises;

determining a modified value of the theoretical bid threshold for the resource pool dependent on the bid amounts included in the one or more additional requests; and

determining a modified value of the current non-contention bid threshold dependent on the modified value of the theoretical bid threshold.

5. A system, comprising:

one or more processors; and

a memory coupled to the one or more processors and storing program instructions that when executed by the one or more processors cause the one or more processors to perform;

receiving a plurality of requests for use of at least some computing resources in a computing resource pool while supply of the computing resources exceeds demand for the computing resources, wherein each request comprises a respective bid amount;

determining a value of a theoretical bid threshold for the computing resources in the computing resource pool, wherein the theoretical bid threshold value represents a predicted value of the lowest bid amount for which corresponding requests for the computing resources will be granted when demand for the computing resources exceeds supply for the computing resources, and wherein said determining the value of the theoretical bid threshold is dependent on the bid amounts included in the plurality of requests;

repeatedly determining, based at least in part on the number of computing resources requested in the plurality of requests, the number of computing resources available in the computing resource pool, and the theoretical bid threshold, a value of a current non-contention bid threshold for the computing resource pool, wherein the current non-contention bid threshold value represents the lowest bid amount for which corresponding ones of the plurality of requests will be granted when supply for the computing resources exceeds demand for the computing resources, and wherein the current non-contention bid threshold value is less than the theoretical bid threshold value and greater than a predetermined minimum bid threshold value for the computing resources;

identifying one or more of the plurality of requests for which the respective bid amount is not less than the determined value of the current non-contention bid threshold; and

based at least in part upon the respective bid amounts of the identified one or more of the plurality of requests, granting access to the computing resources for the identified one or more of the plurality of requests.

6. The system of claim 5, wherein said determining the value of the current non-contention bid threshold is further dependent on the respective bid amounts in the plurality of requests.

7. The system of claim 5, wherein when executed by the one or more processors, the program instructions further cause the one or more processors to perform:

terminating the use of one or more resources of the resource pool previously granted in response to a request for resources for which the value of the included bid amount was less than the current non-contention bid threshold value.

8. The system of claim 5, wherein said determining the value of the theoretical bid threshold comprises:

modeling the distribution of at least a portion of the bid amounts included in the plurality of requests; and

calculating the value of the theoretical bid threshold dependent on the distribution.

9. The system of claim 8, wherein the portion of the bid amounts included in the plurality of requests are modeled as a Poisson distribution.

10. The system of claim 5, wherein when executed by the one or more processors, the program instructions further cause the one or more processors to perform:

receiving one or more additional requests for use of at least some computing resources in the computing resource pool while supply of the computing resources exceeds demand for the computing resources, wherein each additional request comprises a respective bid amount; and

modifying the value of the current non-contention bid threshold for the computing resource pool, wherein said modifying comprises;

determining a modified value of the theoretical bid threshold for the computing resource pool dependent on the bid amounts included in the one or more additional requests; and

determining a modified value of the current non-contention bid threshold dependent on the modified value of the theoretical bid threshold.

11. A non-transitory, computer-readable storage medium storing program instructions that when executed on one or more computers cause the one or more computers to perform:

receiving a plurality of requests for use of at least some computing resources in a computing resource pool while supply of the computing resources exceeds demand for the computing resources, wherein each request comprises a respective bid amount;

determining a value of a theoretical bid threshold for the computing resources in the computing resource pool, wherein the theoretical bid threshold value represents a predicted value of the lowest bid amount for which corresponding requests for the computing resources will be granted when demand for the computing resources exceeds supply for the computing resources, and wherein said determining the value of the theoretical bid threshold is dependent on the bid amounts included in the plurality of requests;

repeatedly determining, based at least in part on the number of computing resources requested in the plurality of requests, the number of computing resources available in the computing resource pool, and the theoretical bid threshold, a value of a current non-contention bid threshold for the computing resource pool, wherein the current non-contention bid threshold value represents the lowest bid amount for which corresponding ones of the plurality of requests will be granted when supply for the computing resources exceeds demand for the computing resources, and wherein the current non-contention bid threshold value is less than the theoretical bid threshold value and greater than a predetermined minimum bid threshold value for the computing resources;

identifying one or more of the plurality of requests for which the respective bid amount is not less than the determined value of the current non-contention bid threshold; and

based at least in part upon the respective bid amounts of the identified one or more of the plurality of requests, granting access to the computing resources for the identified one or more of the plurality of requests.

12. The storage medium of claim 11, wherein when executed on the one or more computers, the program instructions further cause the one or more computers to perform:

terminating the use of one or more resources of the resource pool previously granted in response to a request for resources for which the value of the included bid amount was less than the current non-contention bid threshold value.

13. The storage medium of claim 11, wherein said determining the value of the theoretical bid threshold comprises:

modeling the distribution of at least a portion of the bid amounts included in the plurality of requests; and

calculating the value of the theoretical bid threshold dependent on the distribution.

14. The storage medium of claim 11, wherein when executed on the one or more computers, the program instructions further cause the one or more computers to perform:

receiving one or more additional requests for use of at least some computing resources in the computing resource pool while supply of the computing resources exceeds demand for the computing resources, wherein each additional request comprises a respective bid amount; and

modifying the value of the current non-contention bid threshold for the computing resource pool, wherein said modifying comprises;

determining a modified value of the theoretical bid threshold for the computing resource pool dependent on the bid amounts included in the one or more additional requests; and

determining a modified value of the current non-contention bid threshold dependent on the modified value of the theoretical bid threshold.

15. The storage medium of claim 14, wherein when executed on the one or more computers, the program instructions further cause the one or more computers to perform, in response to said modifying, granting one of the additional requests or terminating the use of one or more resources of the resource pool previously granted in response to a request for resources.