Computing optimized virtual machine allocations using equivalence combinations

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 a plurality of equivalence sets of VMs, each equivalence set including only VMs having an identical resource requirement size;

generating a group of meta-combinations, each meta-combination corresponding to a respective equivalence set of the plurality of equivalence sets of VMs, each meta-combination representing all possible combinations of individual VMs from the respective equivalence set, each meta-combination and each possible combination representing a number of VMs without specifically enumerating individual VMs;

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

generating a meta-combination listing, wherein the meta-combination listing includes one or more meta-combinations selected from the group of meta-combinations, the meta-combination listing representing a cumulative resource requirement size that is less than or equal to the maximum resource capacity, and

providing a meta-combination assignment to the node, the meta-combination assignment including a list of meta-combination listings, each list having the cumulative resource requirement size and a having a different set of meta-combination listings.

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 , wherein 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 , 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.

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. A computer program product for determining allocation of virtual machines to network nodes, the computer program product comprising a non-transitory computer readable storage medium having program code stored thereon, 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 a plurality of equivalence sets of VMs, each equivalence set including only VMs having an identical resource requirement size;

generating a group of meta-combinations, each meta-combination corresponding to a respective equivalence set of the plurality of equivalence sets of VMs, each meta-combination representing all possible combinations of individual VMs from the respective equivalence set, each meta-combination and each possible combination representing a number of VMs without specifically enumerating individual VMs;

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

generating a meta-combination listing, wherein the meta-combination listing includes one or more meta-combinations selected from the group of meta-combinations, the meta-combination listing representing a cumulative resource requirement size that is less than or equal to the maximum resource capacity; and

providing a meta-combination assignment to the node, the meta-combination assignment including a list of meta-combination listings, each list having the cumulative resource requirement size and a having a different set of meta-combination listing.

11. The computer program product of claim 10 , 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.

12. The computer program product of claim 11 , wherein 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.

13. The computer program product of claim 10 , 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.

14. The computer program product of claim 10 , 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.

15. The computer program product of claim 10 , 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.

16. The computer program product of claim 10 , 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.

17. 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 a plurality of equivalence sets of VMs, each equivalence set including only VMs having an identical resource requirement size;

generate a group of meta-combinations, each meta-combination corresponding to a respective equivalence set of the plurality of equivalence sets of VMs, each meta-combination representing all possible combinations of individual VMs from the respective equivalence set, each meta-combination and each possible combination representing a number of VMs without specifically enumerating individual VMs;

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

generate a meta-combination listing, wherein the meta-combination listing includes one or more meta-combinations selected from the group of meta-combinations, the meta-combination listing representing a cumulative resource requirement size that is less than or equal to the maximum resource capacity; and

provide a meta-combination assignment to the node, the meta-combination assignment including a list of meta-combination listings, each list having the cumulative resource requirement size and a having different set of meta-combination listings.

18. The apparatus of claim 17 , 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.

19. The apparatus of claim 17 , wherein 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.

20. The apparatus of claim 17 , 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.

21. The apparatus of claim 17 , 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.

22. The apparatus of claim 17 , 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.

23. The apparatus of claim 17 , wherein the network is a cloud computing network.