Process demand prediction for distributed power and resource management

• US 9,519,562 B2
• Filed: 10/25/2011
• Issued: 12/13/2016
• Est. Priority Date: 01/26/2009
• Status: Active Grant

• Current Assignee: Vmware LLC (Broadcom, Inc.)
• Original Assignee: VMware, Inc. (Broadcom, Inc.)
• Inventors: Isci, Canturk, Wang, Chengwei, Bhatt, Chirag, Shanmuganathan, Ganesha, Holler, Anne Marie
• Primary Examiner(s): CONAWAY, JAMES E
• Application Number:
  US13/281,234
• Publication Number:
  US 20120042312A1
• Time in Patent Office: 1,876 Days
• Field of Search: 709/226, 718/104, 718/105
• US Class Current: 1/1
• CPC Class Codes: G06F 1/3203 Power management, i.e. event-based initiation of a power-saving mode
• CPC Class Codes: G06F 11/302 where the computing system component is a software system
• CPC Class Codes: G06F 11/3409 for performance assessment
• CPC Class Codes: G06F 11/3452 Performance evaluation by statistical analysis
• CPC Class Codes: G06F 11/3495 for systems
• CPC Class Codes: G06F 2201/815 Virtual middleware or OS functionality using virtual machines to implement generic software techniques for error detection or fault masking G06F11/1484
• CPC Class Codes: G06F 9/4856 resumption being on a different machine, e.g. task migration, virtual machine migration G06F9/5088 takes precedence
• CPC Class Codes: G06F 9/4893 taking into account power or heat criteria power management in computers in general G06F1/3203; thermal management in computers in general G06F1/206
• CPC Class Codes: G06F 9/5083 Techniques for rebalancing the load in a distributed system
• CPC Class Codes: G06F 9/5088 involving task migration
• CPC Class Codes: Y02D 10/00 Energy efficient computing, e.g. low power processors, power management or thermal management

Abstract

Methods and systems for allocating resources in a virtual desktop resource environment are provided. A method includes making a prediction on the future demand for processes running on a distributed environment with several hosts. The prediction is based on the process demand history and includes the removal of historic process demand glitches. Further, the prediction is used to perform a cost and benefit analysis for moving a candidate process from one host to another, and the candidate process is moved to a different host when the cost and benefit analysis recommends such move. In another embodiment, the predictions on future process demand are used for distributed power management by putting hosts in stand-by mode when the overall demand decreases or by adding hosts to the distributed environment when the load increases.

Claims

1. A method for allocating resources in a virtual desktop environment, the method comprising:

making a prediction for future demand by a plurality of processes running on a first host and a second host, the prediction being based on each process demand history and on removing past process demand glitches, including defining the process demand history on which the prediction is based by identifying any past process demand glitch and by including stable periods while excluding any identified past process demand glitch between the stable periods, wherein making the prediction includes determining the stable periods in the process demand history such that each stable period in the stable periods is a time span during which a demand of the corresponding process stays within a baseline value of a previous stable period and a demand variation threshold, wherein making the prediction further includes determining a group of unstable samples is a process demand glitch based on identifying that a difference between a stable sample preceding the group of unstable samples and a stable sample following the group of unstable samples is within the demand variation threshold and the baseline value;

selecting a candidate process for movement, the candidate process being one of the plurality of processes;

performing a cost and benefit analysis for moving the candidate process from the plurality of processes from the first host to the second host based on the prediction, the cost and benefit analysis being specific to the candidate process; and

executing a move of the candidate process when the cost and benefit analysis recommends the move.

2. The method as recited in claim 1, wherein the demand variation threshold is a predetermined percentage of the sum load capacity of the first host and the second host.

3. The method as recited in claim 1, wherein the demand variation threshold is based on the coefficient of variance of the corresponding process demand history.

4. The method as recited in claim 1, wherein the plurality of processes are a plurality of virtual machines.

5. The method as recited in claim 1 further including,

performing a power cost and benefit analysis for putting the first host in stand by mode, and

moving processes running in the first host to other hosts and putting the first host in stand-by mode when the cost and benefit analysis recommends putting the first host in stand-by mode.

6. The method as recited in claim 1 further including,

performing a power cost and benefit analysis for starting up a third host, and

starting up the third host and moving processes from at least one of the first host and the second host to the third host when the power cost and benefit analysis recommends starting up the third host.

19. The method of claim 1, wherein the second set of stable periods includes a minimum threshold number of periods.

20. The method of claim 1, wherein determining the second set of the stable periods in the process demand history further includes determining that there is not a third set of stable periods succeeding the second set of stable periods, wherein each period in the third set of the stable periods is a third time span during which the demand of the corresponding process stays within the baseline value of the previous stable period and the demand variation threshold.

7. A virtual desktop resource allocation system, the system comprising:

a plurality of hosts in a virtual center;

a process running in a first host from the plurality of hosts; and

a distributed resource manager in the virtual center, wherein the distributed resource manager;

predicts a future demand for the process based on an extended history of process demand and on removing past process demand glitches from determinations of the process demand in order to define the extended history, wherein defining the extended history comprises identifying any past process demand glitch and including stable periods while excluding any identified past process demand glitch between the stable periods, and wherein making the prediction includes determining the stable periods in the process demand history such that each stable period in the sable periods is a time span during which a demand of the corresponding process stays within a baseline value of a previous stable period and a demand variation threshold, wherein making the prediction further includes determining a group of unstable samples is a process demand glitch based on identifying that a difference between a stable sample preceding the group of unstable samples and a stable sample following the group of unstable samples is within the demand variation threshold and the baseline value;

performs a cost and benefit analysis for moving the process to a second host from the plurality of hosts based on the prediction, and

moves the process to the second host on the basis of the cost and benefit analysis.

8. The system as recited in claim 7, wherein the prediction includes a time span for a future stable load period and a future change in the demand at the end of the future stable load period.

9. The system as recited in claim 8, wherein the future stable load period is calculated as an exponential weighted average of durations of previous stable load periods within a predetermined amount of time.

10. The system as recited in claim 8, wherein the future change in the demand is a maximum change in demand throughout the predetermined amount of time.

11. The system as recited in claim 10, wherein the predetermined amount of time is 60 minutes.

12. The system as recited in claim 7, wherein moving the process to the second host further includes,

copying the memory used by the process from the first host to the second host,

copying the processor state from the first host to the second host, and

running the process in the second host and stop the process in the first host.

13. A computer program embedded in a non-transitory computer-readable medium, when executed by one or more processors, for distributed power management, the computer program comprising:

program instructions for making a prediction for future demand by a plurality of processes running on a plurality of hosts, the prediction being based on each process demand history and on removing past process demand glitches, the process demand history being over a period of time that includes stable periods and that excludes any past process demand glitches that are identified as being between two stable periods which are included for making the prediction, wherein making the prediction includes determining the stable periods in the process demand history such that each stable period in the stable periods is a time span during which a demand of the corresponding process stays within a baseline value of a previous stable period and a demand variation threshold, wherein making the prediction further includes determining a group of unstable samples is a process demand glitch based on identifying that a difference between a stable sample preceding the group of unstable samples and a stable sample following the group of unstable samples is within the demand variation threshold and a baseline value;

program instructions for performing a first cost and benefit analysis for changing a number of hosts running based on the prediction;

program instructions for shutting down a host when the first cost and benefit analysis recommends reducing a number of running hosts; and

program instructions for starting up a stand-by host when the first cost and benefit analysis recommends incrementing the number of running hosts.

14. The computer program as recited in claim 13, wherein the demand corresponds to Central Processing Unit (CPU) demand.

15. The computer program as recited in claim 13, wherein the demand corresponds to memory usage demand.

16. The computer program as recited in claim 13, further including,

program instructions for performing a second cost and benefit analysis based on a second demand for a second resource type,

program instructions for performing an overall cost and benefit analysis as a function of the first and second cost and benefit analysis, and

program instructions for recommending shutting down or starting up a host based on the overall cost and benefit analysis.

17. The computer program as recited in claim 13, further including,

program instructions for measuring a first error associated with the prediction, and

program instructions for measuring a second error associated with a post-even prediction based on actual demand, and

program instructions for rating the prediction by comparing the first and the second error.

18. The computer program as recited in claim 13, wherein the program instructions for removing past process demand glitches further includes,

program instructions for finding a glitch in process demand as an unstable period between a first and a second stable period, and

program instructions for removing the glitch in process demand when a load of the second stable period is within a demand variation threshold from a load of the first stable period.