Statistical packing of resource requirements in data centers

• US 8,656,404 B2
• Filed: 10/16/2008
• Issued: 02/18/2014
• Est. Priority Date: 10/16/2008
• Status: Expired due to Fees

• Current Assignee: Palo Alto Research Center, Inc. (Xerox Holdings Corp.)
• Original Assignee: Palo Alto Research Center, Inc. (Xerox Holdings Corp.)
• Inventors: Greene, Daniel H., Chu, Maurice, Hindi, Haitham, Preas, Bryan T., Parekh, Nitin
• Primary Examiner(s): LI, AIMEE J
• Application Number:
  US12/253,111
• Publication Number:
  US 20100100877A1
• Time in Patent Office: 1,951 Days
• Field of Search: 718/102, 718/104
• US Class Current: 718/104
• CPC Class Codes: G06F 2209/5019 Workload prediction
• CPC Class Codes: G06F 9/45533 Hypervisors; Virtual machine monitors
• CPC Class Codes: G06F 9/5011 the resources being hardware resources other than CPUs, Servers and Terminals
• CPC Class Codes: Y02D 10/00 Energy efficient computing, e.g. low power processors, power management or thermal management

Abstract

A computer-implemented method of managing resources in a virtual machine environment can include determining a specification of provisioning success corresponding to each of multiple jobs in the virtual machine environment, determining a prediction of resource needs corresponding to each of the jobs, and determining a resource specification corresponding to each of the jobs based on the specification of provisioning success and the prediction of resource needs.

Claims

1. A computer-implemented method of managing resources in a virtual machine environment, comprising:

determining a specification of provisioning success corresponding to each of a plurality of jobs in the virtual machine environment;

determining a prediction of resource needs corresponding to each of the plurality of jobs;

responsive to the specification of provisioning success and the prediction of resource needs, determining a resource specification corresponding to each of the plurality of jobs, wherein determining the resource specifications comprises applying an optimization algorithm that prioritizes approximation speed higher than maximum packing ability;

forming an action list, wherein certain jobs having the most severe predictions of resource needs are placed at the beginning of the action list, and

processing the action list in order, wherein said processing comprises choosing each resource specification for a particular virtual machine.

2. The computer-implemented method of claim 1, wherein determining the specification of provisioning success comprises deriving the specification of provisioning success from a corresponding service level agreement (SLA).

3. The computer-implemented method of claim 1, wherein determining the prediction of resource needs includes building a model based on historical data pertaining to past resource needs.

4. The computer-implemented method of claim 3, wherein predicting the resource needs comprises time of day conditioning.

5. The computer-implemented method of claim 3, wherein predicting the resource needs comprises Markov modeling.

6. The computer-implemented method of claim 1, wherein determining the resource specification corresponding to one of the plurality of jobs comprises determining additional resources that should be specified for the job that extend beyond resources specified for a group of jobs.

7. The computer-implemented method of claim 6, wherein the group of jobs comprises jobs specified previously in a priority order.

8. The computer-implemented method of claim 1, wherein the determined resource specification comprises a minimum amount of resources to be reserved for the corresponding one of the plurality of jobs.

9. The computer-implemented method of claim 1, further comprising:

repeating determining the prediction of resource needs; and

responsive to the repeated determined prediction of resource needs and the determined specification of provisioning success, adjusting a determined resource specification corresponding to one of the plurality of jobs.

10. The computer-implemented method of claim 1, further comprising providing the determined resource specification to a lower-level scheduling module.

11. One or more tangible computer-readable media storing thereon machine-executable instructions that, when executed by a processor, perform the computer-implemented method of claim 1.

12. The computer-implemented method of claim 1, wherein said optimization algorithm is a greedy packing algorithm.

13. The computer-implemented method of claim 1, wherein said choosing comprises giving the virtual machine a resource specification consisting of a minimum resource reservation that will insure that the virtual machine will have all the resources it needs with a failure probability less than p.

14. The computer-implemented method of claim 13, further comprising determining whether a total allocation for a resource pool is large enough that combined requirements of multiple virtual machines sharing the resource pool have a failure probability that is not greater than the failure probability p for the individual virtual machine being processed.

15. The computer-implemented method of claim 14, wherein the optimization algorithm can allocate a large amount of resources to premium jobs until the total allocation reaches a level that is sufficient to satisfy a low failure probability for the resource pool.

16. The computer-implemented method of claim 15, further comprising determining that additional jobs require no separate resource allocation.

17. The computer-implemented method of claim 1, wherein processing the action list comprises giving each virtual machine its individual requirement necessary to meet its allowed failure probability.

18. The computer-implemented method of claim 1, wherein processing the action list comprises ensuring that a total allocation for a resource pool is large enough that the combined virtual machine requirements will not fail with a probability greater than a probability for the individual virtual machine being processed.