Cloud resource allocation system and method
View Patent ↗Assigning virtual machines to host machines in a cloud computing arrangement includes at least one of several techniques that facilitate reducing or minimizing the number of host machines serving virtual machines. One technique includes using place holders in place of a virtual machine that vacates a host machine. The place holders indicate the type of vacated virtual machine and are replaced with a new virtual machine request of a corresponding type. Another technique includes a greedy assignment algorithm for identifying a host machine for a new virtual machine request that will yield an optimized increment to a value of a function that corresponds to a current cloud resource allocation. One technique includes using a modified version of a derivative of the function used in the greedy assignment algorithm, with the modification depending on a number of virtual machines in the cloud system at the time of the new request.
1. A device for managing cloud computing resources, comprising:
at least one computing device including a digital data storage and a processor associated with the digital data storage;
the digital data storage comprising information regarding a cloud computing resource allocation including a plurality of virtual machine type values, the respective virtual machine type values corresponding to a number of virtual machines of the respective type associated with at least one of a plurality of host machines;
the processor being configured to
determine the type of one vacated virtual machine that vacates one of the host machines;
assign a place holder to one of the host machines, the place holder having a place holder type corresponding to the type of the vacated virtual machine, the place holder being distinct from the vacated virtual machine;
determine the type of a virtual machine request; and
assign the virtual machine request to a selected one of the host machines based on correspondence between the type of the virtual machine request and the place holder type of a place holder assigned to the selected host machine.
2. The device of claim 1 , wherein
the place holder is counted as a virtual machine; and
the processor is configured to replace the place holder of the selected one of the host machines with the assigned virtual machine of the virtual machine request.
3. The device of claim 1 , wherein the correspondence between the type of the virtual machine request and the place holder type of the place holder assigned to the selected host machine comprises the place holder type being the same as the type of the virtual machine request.
4. The device of claim 1 , wherein the processor is configured to
determine a first value of a mathematical function that corresponds to the resource allocation prior to assigning the place holder;
determine a plurality of second values of the mathematical function, each of the second values corresponding to the place holder being assigned to a different one of the host machines; and
assign the place holder to the host machine having the corresponding second value that yields an optimized increment to the first value.
5. The device of claim 1 , wherein the place holder expires a preselected time after being assigned to the one of the host machines.
6. The device of claim 1 , wherein the processor is configured to
determine that there are no place holders having a place holder type corresponding to the type of the virtual machine request at a time of the virtual machine request; and
assign the virtual machine request to one of the host machines using a greedy assignment algorithm.
7. A method of managing cloud computing resources, which include a plurality of host machines configured to run a plurality of virtual machines, the method comprising:
determining a type of one vacated virtual machine that vacates one of the host machines;
assigning a place holder to one of the host machines, the place holder having a place holder type corresponding to the type of the vacated virtual machine and the place holder being distinct from the vacated virtual machine;
determining the type of a virtual machine request; and
assigning the virtual machine request to a selected one of the host machines based on correspondence between the type of the virtual machine request and the place holder type of a place holder assigned to the selected host machine.
8. The method of claim 7 , comprising
counting the place holder as a running virtual machine; and
replacing the place holder of the selected one of the host machines with the assigned virtual machine of the virtual machine request.
9. The method of claim 7 , wherein the correspondence between the type of the virtual machine request and the place holder type of the place holder assigned to the selected host machine comprises the place holder type being the same as the type of the virtual machine request.
10. The method of claim 7 , wherein the place holder expires a preselected time after being assigned to the selected one of the host machines.
11. The method of claim 7 , comprising
determining a first value of a mathematical function that corresponds to the resource allocation prior to assigning the place holder;
determining a plurality of second values of the mathematical function, each of the second values corresponding to the place holder being assigned to a different one of the host machines; and
assigning the place holder to the host machine having the corresponding second value that yields an optimized increment to the first value.
12. The method of claim 7 , wherein the optimized increment comprises a smallest increment.
13. The method of claim 7 , comprising
determining that there are no place holders having a place holder type corresponding to the type of the virtual machine request at a time of the virtual machine request; and
assigning the virtual machine request to one of the host machines using a greedy assignment algorithm.