Resource allocation system

• US 8,650,298 B2
• Filed: 12/03/2010
• Issued: 02/11/2014
• Est. Priority Date: 12/04/2009
• Status: Active Grant

• Current Assignee: Creme Software Limited
• Original Assignee: Creme Software Limited
• Inventors: Daly, Edmond James, McNamara, Cronan, Ronan, David
• Primary Examiner(s): Shah, Chirag
• Assistant Examiner(s): PANCHOLI, RINA C
• Application Number:
  US12/959,848
• Publication Number:
  US 20110138055A1
• Time in Patent Office: 1,166 Days
• Field of Search: None
• US Class Current: 709/226
• CPC Class Codes: G06F 2209/5019 Workload prediction
• CPC Class Codes: G06F 9/505 considering the load

Abstract

The present application provides a scalable system for managing requests for compute resources using a cloud computing architecture. The system estimates the total processing time of each computation in advance and monitors the progress of each computation to provide a more accurate estimate of remaining processing time. In this way, a determination may be made as each new computation request is received as to whether an additional resource is required or whether an existing resource would be suitable.

Claims

1. A system for managing computing resources obtained from a cloud computing environment, the system being configured to allocate one or more computational requests received from one or more users to one or more computing resources of the cloud, the system comprising:

an interface configured to receive the computational requests from the one or more users;

an estimator configured to estimate a time required to perform the received computational request if allocated to a computing resource of the cloud; and

a feedback module receiving feedback data from existing resources of the cloud as to their availability, wherein;

an existing computing resource of the cloud is a computing resource of the cloud which has been obtained for an incurred cost for a predetermined time from the cloud and to which a computational request has been assigned, the feedback data including an estimate of a time remaining for each computing resource of the cloud to complete the computational request currently assigned to them,

prior to allocation of a received computational request, the system is configured to obtain an acceptable wait time for the received computational request and determine whether the received computational request will have to wait longer than the obtained acceptable wait time before being allocated to a resource of the cloud based on the feedback from the existing resources of the cloud of how long a computation request will have to wait for an existing resource of the cloud to become available to execute the received computational request,

the system is further configured to obtain at least one further resource from the cloud based on a positive determination,

the system is further configured to allocate the received computational request to the existing resources of the cloud based on a negative determination, and

the system is further configured, based on a determination that less than a predetermined time is remaining, to shut down the existing resource of the cloud before the existing resource enters a following billing cycle.

2. The system according to claim 1, wherein the system is configured to allocate resources by placing the received computational request in a queue until an existing resource assigned in the cloud computing environment to the system becomes available.

3. The system according to claim 1, further comprising a database, the database being configured to store the estimates received from resources by the feedback module.

4. The system according to claim 3, wherein the database is configured to also store information regarding the availability of computing resources to the system.

5. The system according to claim 3, wherein the system is further configured to store the determined estimate as the computational request is allocated to a computing resource.

6. The system according to claim 5, wherein data for individual computing resources is updated based on the feedback data received from the feedback module.

7. The system according to claim 1, wherein the estimator is configured to determine the estimate using at least two partial estimates which are aggregated together.

8. The system according to claim 7, wherein the feedback module receives feedback data on each of the partial estimates.

9. The system according to claim 7, wherein one of the partial estimates comprises an initialization estimate, the initialization estimate providing an estimate of the time required to initialize the computing resource to perform the allocated request.

10. The system according to claim 7, wherein one of the partial estimates comprises a finalization estimate, the finalization estimate providing an estimate of the time required, after a computing resource has completed a task, to store resultant data.

11. The system according to claim 7, wherein one of the partial estimates comprises an iteration estimate, wherein the partial estimate for the iteration estimate is calculated by determining a number of iterations required to complete the request and a time required to complete each iteration.

12. The system according to claim 1, wherein the estimator is configured to determine the estimate of the time required to perform the computational request by reference to times taken to complete previous computational requests.

13. The system according to claim 12, wherein the determination of the estimate determines the estimate based on values of identified parameters of the calculation and where the estimate extrapolates the estimate from the values of parameters and the time taken for previous computational requests.

14. A system comprising:

a processor and memory in a cloud computer environment;

an interface in the cloud computer environment configured to receive a plurality of computational requests from a server outside the cloud;

a plurality of existing computing resource instances in the cloud computing environment that have each been obtained for an incurred cost for a predetermined time from the cloud and to which each has been assigned a current computational request, wherein each instance is configured by the server outside the cloud, each instance being configured to perform that instance'"'"'s current computational request comprising calculations received from the server, wherein each instance is configured to calculate an estimate of the time remaining for performance of that instance'"'"'s current computational request;

a first feedback module for providing the calculated estimates to the server;

wherein each instance of the cloud computing environment is configurable to perform an additional computational request comprising additional calculations received from the server after that instance has completed that instance'"'"'s current computational request, and

wherein the system is further configured, based on a determination that less than a predetermined time is remaining, to terminate the existing computing resource instance of the cloud before the existing computing resource instance enters a following billing cycle.

15. The system according to claim 14, wherein each instance is configured to provide the calculated estimates to the server by updating a database associated with the server.

16. The system according to claim 15, wherein each instance is configured when inactive to periodically check the database for an unallocated task.

17. The system according to claim 16, wherein each instance has a predetermined lifetime corresponding to the minimum request-able time for an instance from the cloud and wherein the instance is configured, if there is no unallocated task, to return itself to the cloud when it is within a predetermined time of its lifetime.

18. The system according to claim 17, wherein the lifetime of an instance recommences if it is performing a task at the end of its lifetime.

19. A system comprising:

an instance in a cloud computing environment, where the instance is configured by a server outside the cloud, the instance being configured to perform a task comprising calculations received from the server, wherein the instance is configured to calculate an estimate of the time remaining for performance of the task; and

a first feedback module for providing the calculated estimates to the server, wherein the instance is configured to calculate the estimate as a series of partial estimates, the system further comprising;

an allocator that allocates one or more computational requests received from one or more users to one or more computing resources of the cloud that include the task in the instance;

an interface configured to receive the computational requests from the one or more users;

an estimator configured to estimate the time required to perform the received computational request if allocated to a computing resource; and

a second feedback module receiving feedback data from existing resources of the cloud as to their availability, wherein;

an existing computing resource of the cloud is a computing resource of the cloud which has been obtained for an incurred cost for a predetermined time from the cloud and to which a computational request has been assigned, the feedback data including an estimate of the time remaining for each computing resource of the cloud to complete the computational request currently assigned to them, the estimate including the calculated partial estimates from the first feedback module in the instance,

prior to allocation of a received computational request, the system is configured to obtain an acceptable wait time for the received computational request and determine whether the received computational request will have to wait longer than the obtained acceptable wait time before being allocated to a resource of the cloud based on the feedback from the existing resources of the cloud of how long a computation request will have to wait for an existing resource of the cloud to become available to execute the received computational request,

the system is further configured to obtain at least one further resource from the cloud based on a positive determination,

the system is further configured to allocate the received computational request to the existing resource of the cloud based on a negative determination, and

the system is further configured, based on a determination that less than a predetermined time is remaining, to shut down the existing resource of the cloud before the existing resource enters a following billing cycle.

20. The system according to claim 19, wherein the calculation comprises at least one iterative calculation and the estimate includes an iterative estimate based on a number of iterations performed in a primary loop of said at least one iterative calculation.

21. The system according to claim 19, wherein at least one iterative calculation comprises at least one sub-loop for performing an iterative calculation within each iteration of a primary loop.

22. The system according to claim 20, wherein the iterative estimate is updated as iterations are completed.