ALLOCATION OF VIRTUAL MACHINES TO PHYSICAL MACHINES THROUGH DOMINANT RESOURCE ASSISTED HEURISTICS

• US 20160216991A1
• Filed: 11/29/2013
• Published: 07/28/2016
• Est. Priority Date: 11/29/2013
• Status: Active Grant

• Current Assignee: New Jersey Institute of Technology
• Original Assignee: New Jersey Institute of Technology
• Inventors: Ansari, Nirwan, Zhang, Yan
• Granted Patent: US 10,048,976 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 2009/4557 Distribution of virtual machine instances; Migration and load balancing
• CPC Class Codes: G06F 9/45558 Hypervisor-specific management and integration aspects
• CPC Class Codes: G06F 9/5077 Logical partitioning of resources; Management or configuration of virtualized resources specific details on emulation or internal functioning of virtual machines G06F9/455
• CPC Class Codes: G06F 9/5094 where the allocation takes 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: Y02D 10/00 Energy efficient computing, e.g. low power processors, power management or thermal management

Abstract

Technologies are generally described to allocation of virtual machines to physical machines through dominant resource assisted heuristics. According to some examples, multiple virtual machines (VMs) may be clustered to two or more unallocated VM clusters according to a dominant resource requirement associated with each of the VMs. The VMs may be sorted according to a size attribute associated with the dominant resource requirement. Multiple physical machines (PMs) may be sorted according to a power efficiency attribute associated with each of the PMs. One of the PMs may be selected from an ordered list of PMs based on the power efficiency attribute. One of the VMs may be selected from another ordered list of PMs based on the size attribute. The selected VM may then be allocated to the selected PM.

Claims

1. A method to allocate virtual machines to physical machines, the method comprising:

sorting a plurality of virtual machines (VMs) according to a size attribute associated with a dominant resource requirement;

sorting a plurality of physical machines (PMs) according to a power efficiency attribute associated with each of the plurality of PMs;

selecting one of the sorted plurality of PMs based on the power efficiency attribute;

selecting one of the sorted plurality of VMs based on the size attribute;

allocating the selected VM to the selected PM; and

in response to a determination that a residual capacity attribute of the selected PM is less than a particular threshold, discontinuing allocation of the selected VM to the selected PM.

2. The method of claim 1, further comprising:

clustering the VMs to at least two unallocated VM clusters based on the dominant resource requirement; and

iterating through the two unallocated VM clusters to allocate each of the plurality of VMs to at least one of the plurality of PMs.

3. The method of claim 2, further comprising:

computing a total residual capacity attribute of the plurality of PMs;

identifying a dominant resource requirement vector from the total residual capacity attribute; and

sorting the plurality of PMs according to the dominant resource requirement vector.

4. The method of claim 3, wherein sorting the plurality of PMs according to the dominant resource requirement vector includes sorting the plurality of PMs according to a dominant resource requirement vector that represents one of a memory capacity and a processor capacity.

5. The method of claim 3, further comprising:

selecting another VM from the plurality of VMs, wherein the another VM is sorter at a top position based on a size attribute associated with each of the plurality of VMs;

selecting another PM from the plurality of PMs, wherein the another PM is sorted at a top position based on the dominant resource requirement vector; and

allocating the another VM to the another PM.

6. The method of claim 2, wherein clustering the VMs to the at least two unallocated VM clusters includes clustering the VMs to at least two unallocated VM clusters that include a memory intensive VM cluster and a processor intensive VM cluster.

7. The method of claim 1, wherein sorting the plurality of VMs according to the size attribute associated with the dominant resource requirement sorting the plurality of VMs according to a size attribute associated with a dominant resource requirement that includes a memory resource attribute and a processor resource attribute.

9. The method of claim 1, wherein allocating the selected VM to the selected PM includes:

utilizing a dot product scheme to determine the selected VM, wherein the dot product scheme allocates the selected VM to maximize a dot product value and to not exceed a capacity constraint of the selected PM.

10. The method of claim 1, wherein allocating the selected VM to the selected PM includes:

utilizing a norm-based greedy scheme to determine the selected VM, wherein the norm-based greedy scheme minimizes a weighted norm distance value between a resource request vector of the selected VM and a residual capacity vector of the selected PM to not exceed a capacity constraint of the selected PM.

24. A computer-readable non-transitory storage medium with instructions stored thereon to allocate virtual machines to physical machines, the instructions, in response to execution by a processor, are executable to cause the method of claim 1 to be performed.

8. (canceled)

11. An apparatus to allocate virtual machines to physical machines, the apparatus comprising:

a communication module configured to communicate with a plurality of virtual machines (VMs) and a plurality of physical machines (PMs) at a datacenter;

an allocation module configured to manage an allocation of the plurality of VMs and the plurality of PMs; and

a processor coupled to the allocation module, wherein the processor is configured to operate the allocation module to;

cluster the plurality of VMs to at least two unallocated VM clusters based on a dominant resource requirement associated with each of the plurality of VMs;

sort the clustered plurality of VMS according to a size attribute associated with the dominant resource requirement;

sort the plurality of PMs according to a power efficiency attribute associated with each of the plurality of PMs;

select one of the sorted plurality of PMs based on the power efficiency attribute;

select one of the sorted plurality of VMs based on the size attribute;

allocate the selected VM to the selected PM and convey the allocation to the selected VM and to the selected PM through the communication module;

iterate through the two unallocated VM clusters to allocate each of the plurality of VMs to at least one of the plurality of PMs and convey the allocation to each of the plurality of VMs and to the at least one of the plurality of PMs through the communication module; and

in response to a determination that a residual capacity attribute of the at least one of the plurality of PMs is less than a particular threshold, discontinue allocation of the plurality of VMs to the at least one of the plurality of PMs.

12. The apparatus according to claim 11, wherein the processor is further configured to operate the allocation module to:

compute the residual capacity attribute of each of the plurality of PMs;

identify a dominant resource requirement vector from the residual capacity attribute; and

sort the plurality of PMs according to the dominant resource requirement vector.

13. The apparatus according to claim 12, wherein the processor is further configured to operate the allocation module to:

select another VM from the plurality of VMs, wherein the another VM is sorted at a top position based on a size attribute associated with each of the plurality of VMs;

select another PM from the plurality of PMs, wherein the another PM is sorted at a top position based on the dominant resource requirement vector; and

allocate the another VM to the another PM.

14. The apparatus according to claim 11, wherein the at least two unallocated VM clusters include a memory intensive VM cluster and a processor intensive VM cluster.

15. The apparatus according to claim 11, wherein the dominant resource requirement includes a memory resource attribute and a processor resource attribute.

16. The apparatus according to claim 11, wherein the size attribute includes at least one from a set of a weighted resource demand value, a weighted resource capacity value, a weighted sum value of a normalized resource demand, a weighted sum value of a normalized resource capacity, a product of the normalized resource demand, and a product of the normalized resource capacity.

17. The apparatus according to claim 11, wherein the processor is configured to operate the allocation module to:

utilize a dot product scheme to determine the selected VM, wherein the dot product scheme allocates the selected VM to maximize a dot product value and to not exceed a capacity constraint of the selected PM.

18. The apparatus according to claim 11, wherein the processor is configured to operate the allocation module to:

utilize a norm-based greedy scheme to determine the selected VM, wherein the norm-based greedy scheme minimizes a weighted norm distance value between a resource request vector of the selected VM and a residual capacity vector of the selected PM to not exceed a capacity constraint of the selected PM.

19. A system, comprising:

a plurality of virtual machines (VMs);

a plurality of physical machines (PMs);

a controller communicatively coupled to the plurality of VMs and the plurality of PMs and configured to allocate the plurality of VMs to the plurality of PMs through dominant resource assisted heuristics, wherein the controller is configured to perform or cause to be performed;

cluster the plurality of VMs to at least two unallocated VM clusters according to a dominant resource requirement associated with each of the plurality of VMs;

order the clustered plurality of VMs according to a size attribute associated with the dominant resource requirement;

order the plurality of PMs according to a power efficiency attribute associated with each of the plurality of PMs;

select one of the ordered plurality of PMs, wherein the selected PM is ordered at a first identifiable position based on the power efficiency attribute;

select one of the ordered plurality of VMs, wherein the selected VM is ordered at a second identifiable position based on the size attribute;

activate a server that includes the selected PM;

allocate the selected VM to the activated server;

iterate through the at least two unallocated VM clusters to allocate each of the plurality of VMs to one or more servers; and

in response to a determination that a residual capacity attribute of the one or more servers is less than particular threshold, discontinue allocation of the plurality of VMs.

20. The system according to claim 19, wherein the controller is further configured to perform or cause to be performed:

compute the residual capacity attribute of the one or more servers; and

identify a dominant resource requirement vector from the residual capacity attribute.

22. The system according to claim 20, wherein the controller is further configured to perform or cause to be performed:

search the at least two unallocated VM clusters based on an order of the dominant resource requirement vector to locate another VM to allocate to the selected PM, such that a capacity constraint of the selected PM is not exceeded.

23. The system according to claim 20, wherein the first and second identifiable positions comprise a top position in the ordered plurality of VM s and the ordered plurality of PMs.

21. (canceled)