COMPUTING OPTIMIZED VIRTUAL MACHINE ALLOCATIONS USING EQUIVALENCE COMBINATIONS

• US 20140215073A1
• Filed: 01/28/2013
• Published: 07/31/2014
• Est. Priority Date: 01/28/2013
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Dow, Eli M., Schmidt, Steven K., Gilchrist, James P., Stocker, Charles J.
• Granted Patent: US 9,329,888 B2
• Time in Patent Office: Days
• US Class Current: 709/226
• 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: H04L 67/10 in which an application is distributed across nodes in the network software deployment G06F8/60; multiprogramming arrangements G06F9/46
• CPC Class Codes: Y02D 10/00 Energy efficient computing, e.g. low power processors, power management or thermal management

Abstract

A method for determining allocation of virtual machines includes: at least one of generating and accessing a list of virtual machines (VMs) configured to run on a network, each VM having at least one network resource requirement, each VM in the list associated with a size of the at least one network resource requirement; selecting at least one equivalence set of VMs having a resource requirement size that is at least substantially identical; generating a plurality of meta-combinations from the at least one equivalence set of VMs, each meta-combination representing all possible combinations of a selected number of individual VMs from the equivalence set; determining a maximum resource capacity of a node in the network; and providing a meta-combination assignment to the node, the meta-combination assignment including a group of meta-combinations having a cumulative resource requirement size value that is less than or equal to the maximum resource capacity.

Claims

1. A method for determining allocation of virtual machines to network nodes, comprising:

at least one of generating and accessing a list of virtual machines (VMs) configured to run on a network, each VM having at least one network resource requirement, each VM in the list associated with a size of the at least one network resource requirement;

selecting at least one equivalence set of VMs having a resource requirement size that is at least substantially identical;

generating a plurality of meta-combinations from the at least one equivalence set of VMs, each meta-combination representing all possible combinations of a selected number of individual VMs from the equivalence set;

determining a maximum resource capacity of a node in the network; and

providing a meta-combination assignment to the node, the meta-combination assignment including a group of meta-combinations having a cumulative resource requirement size value that is less than or equal to the maximum resource capacity.

2. The method of claim 1, wherein selecting the at least one equivalence set includes selecting at least a first equivalence set of VMs having a first resource requirement size and a second equivalence set having a second resource requirement size that is different than the first resource requirement size.

3. The method of claim 2, w herein generating the plurality of meta-combinations includes generating at least a first plurality of meta-combinations from the first equivalence set and a second plurality of meta-combinations from the second equivalence set.

4. The method of claim 1, w herein providing the meta-combination assignment includes generating a plurality of groups of different meta-combinations and selecting the group that is closest to the maximum resource capacity.

5. The method of claim 1, wherein providing the meta-combination assignment includes selecting the group of meta-combinations based on a greedy search algorithm to find the group that represents a multi-dimensional best fit for the node.

6. The method of claim 1, wherein providing the meta-combination assignment includes generating a list of all possible groups of meta-combinations having a combined resource requirement that is less than or equal to the maximum resource capacity.

7. The method of claim 1, wherein the network includes a plurality of nodes, determining a maximum resource capacity includes determining a maximum resource capacity of each of the plurality of nodes, and providing the meta-combination assignment includes generating a plurality of meta-combination assignments and providing a meta-combination assignment for each of the plurality of nodes.

8. The method of claim 1, wherein the network includes a plurality of nodes, and the maximum resource capacity is the maximum resource capacity of the largest node in the network.

9. The method of claim 1, wherein the resource requirement is selected from at least one of memory size, number of CPU cores, networking throughput required and disk throughput required.

10. The method of claim 1, wherein each meta-combination represents a number of VMs without specifically enumerating individual VMs.

11. A computer program product for determining allocation of virtual machines to network nodes, the computer program product comprising a computer readable storage medium having program code embodied therewith, the program code readable/executable by a processor to perform a method comprising:

at least one of generating and accessing a list of virtual machines (VMs) configured to run on a network, each VM having at least one network resource requirement, each VM in the list associated with a size of the at least one network resource requirement;

selecting at least one equivalence set of VMs having a resource requirement size that is at least substantially identical;

generating a plurality of meta-combinations from the at least one equivalence set of VMs, each meta-combination representing all possible combinations of a selected number of individual VMs from the equivalence set;

determining a maximum resource capacity of a node in the network; and

providing a meta-combination assignment to the node, the meta-combination assignment including a group of meta-combinations having a cumulative resource requirement size value that is less than or equal to the maximum resource capacity.

12. The computer program product of claim 11, wherein selecting the at least one equivalence set includes selecting at least a first equivalence set of VMs having a first resource requirement size and a second equivalence set having a second resource requirement size that is different than the first resource requirement size.

13. The computer program product of claim 12, w herein generating the plurality of meta-combinations includes generating at least a first plurality of meta-combinations from the first equivalence set and a second plurality of meta-combinations from the second equivalence set.

14. The computer program product of claim 11, wherein providing the meta-combination assignment includes generating a plurality of groups of different meta-combinations and selecting the group that is closest to the maximum resource capacity.

15. The computer program product of claim 11, wherein providing the meta-combination assignment includes selecting the group of meta-combinations based on a greedy search algorithm to find the group that represents a multi-dimensional best fit for the node.

16. The computer program product of claim 11, wherein providing the meta-combination assignment includes generating a list of all possible groups of meta-combinations having a combined resource requirement that is less than or equal to the maximum resource capacity.

17. The computer program product of claim 11, wherein the network includes a plurality of nodes, and the maximum resource capacity is the maximum resource capacity of the largest node in the network.

18. The computer program product of claim 11, wherein each meta-combination represents a number of VMs without specifically enumerating individual VMs.

19. An apparatus comprising:

at least one processing device disposed in at least one of a network node and a network control device; and

a storage device having instructions stored thereon that, when executed by the at least one processing device, cause the apparatus to;

at least one of generate and access a list of virtual machines (VMs) configured to run on a network, each VM having at least one network resource requirement, each VM in the list associated with a size of the at least one network resource requirement;

select at least one equivalence set of VMs having a resource requirement size that is at least substantially identical;

generate a plurality of meta-combinations from the at least one equivalence set of VMs, each meta-combination representing all possible combinations of a selected number of individual VMs from the equivalence set;

determine a maximum resource capacity of a node in the network; and

provide a meta-combination assignment to the node, the meta-combination assignment including a group of meta-combinations having a cumulative resource requirement size value that is less than or equal to the maximum resource capacity.

20. The apparatus of claim 19, wherein the apparatus is configured to select the at least one equivalence set by selecting at least a first equivalence set of VMs having a first resource requirement size and a second equivalence set having a second resource requirement size that is different than the first resource requirement size, and generating the plurality of meta-combinations includes generating at least a first plurality of meta-combinations from the first equivalence set and a second plurality of meta-combinations from the second equivalence set.

21. The apparatus of claim 19, w herein the apparatus is configured to generate a plurality of groups of different meta-combinations and select the group that is closest to the maximum resource capacity as the meta-combination assignment.

22. The apparatus of claim 19, wherein the apparatus is configured to select the group of meta-combinations based on a greedy search algorithm to find the group that represents a multi-dimensional best fit for the node.

23. The apparatus of claim 19, wherein the apparatus is configured to generate a list of all possible groups of meta-combinations having a combined resource requirement that is less than or equal to the maximum resource capacity.

24. The apparatus of claim 19, wherein the network includes a plurality of nodes, and the maximum resource capacity is the maximum resource capacity of the largest node in the network.

25. The apparatus of claim 19, wherein the network is a cloud computing network.