Automated virtual machine placement planning using different placement solutions at different hierarchical tree levels
First Claim
1. A method of placing virtual machines, comprising:
- representing physical entities upon which the virtual machines are to be placed as a hierarchical tree of bins;
receiving one or more virtual machine-to-physical entity constraints on a placement scheme for the virtual machines; and
using information derived from the hierarchical tree and the virtual machine-to-physical entity constraints to define, for each level of the hierarchical tree, a placement solution that associates given virtual machines to given physical entities by solving, within a computing machine having a hardware element, a bin packing problem, wherein the bin packing problem is solved at a given level of the hierarchical tree using a placement algorithm, together with a placement solution from a prior level.
1 Assignment
0 Petitions
Accused Products
Abstract
A virtual machine placement framework is described to enable a data center operator to develop a placement scheme to satisfy its particular constraints while simultaneously optimizing resource utilization. To generate a placement solution, the virtual machine placement problem is first characterized as a “bin packing” problem. The framework provides simple interface tools and processing modules, and a pluggable architecture for receiving placement algorithms. To generate a solution, an administrator creates an XML representation that abstracts physical entities (e.g., data center, subnet, rack, physical server, and the like) into a hierarchical tree of bins. The administrator also defines a set of “rules” that govern (direct) the placement of the virtual machines by placing constraints on the placement scheme. Using the hierarchical tree and the rules, the framework is executed to generate a placement as a solution to a bin packing problem, preferably on a layer-by-layer basis.
50 Citations
24 Claims
-
1. A method of placing virtual machines, comprising:
-
representing physical entities upon which the virtual machines are to be placed as a hierarchical tree of bins; receiving one or more virtual machine-to-physical entity constraints on a placement scheme for the virtual machines; and using information derived from the hierarchical tree and the virtual machine-to-physical entity constraints to define, for each level of the hierarchical tree, a placement solution that associates given virtual machines to given physical entities by solving, within a computing machine having a hardware element, a bin packing problem, wherein the bin packing problem is solved at a given level of the hierarchical tree using a placement algorithm, together with a placement solution from a prior level. - View Dependent Claims (2, 3, 4, 5, 6, 7, 21)
-
-
8. Apparatus, comprising:
-
a processor; computer memory holding computer program instructions executed by the processor to place virtual machines, the computer program instructions comprising; program code to represent physical entities upon which the virtual machines are to be placed as a hierarchical tree of bins; program code to receive one or more virtual machine-to-physical entity constraints on a placement scheme for the virtual machines; and program code to use information derived from the hierarchical tree and the virtual machine-to-physical entity constraints to define, for each level of the hierarchical tree, a placement solution that associates given virtual machines to given physical entities by solving a bin packing problem, wherein the bin packing problem is solved at a given level of the hierarchical tree using a placement algorithm, together with a placement solution from a prior level. - View Dependent Claims (9, 10, 11, 12, 13, 14)
-
-
15. A computer program product in a non-transitory computer readable storage medium for use in a data processing system, the computer program product holding computer program instructions which, when executed by the data processing system, perform a method of placing virtual machines, the method comprising:
-
representing physical entities upon which the virtual machines are to be placed as a hierarchical tree of bins; receiving one or more virtual machine-to-physical entity constraints on a placement scheme for the virtual machines; and using information derived from the hierarchical tree and the virtual machine-to-physical entity constraints to define, for each level of the hierarchical tree, a placement solution that associates given virtual machines to given physical entities by solving a bin packing problem, wherein the bin packing problem is solved at a given level of the hierarchical tree using a placement algorithm, together with a placement solution from a prior level. - View Dependent Claims (16, 17, 18, 19, 20)
-
-
22. A virtual machine placement framework, comprising:
-
a processor; a configuration tool executed on the processor to generate first data and second data, the first data representing, as a hierarchical tree of data containers, physical entities upon which the virtual machines are to be placed, the second data representing virtual machine-to-physical entity constraints on a placement scheme for the virtual machines; and a placement engine executed on the processor to receive information derived from the first data and the second data, the placement engine executing one or more placement algorithms to generate a placement solution of virtual machines with respect to the physical entities; the one or more placement algorithms including a first placement algorithm that is executed at a first level of the hierarchical tree to generate a first placement solution that associates given first virtual machines to given first physical entities, and a second placement algorithm that is executed at a second level of the hierarchical tree to generate a second placement solution that associates given second virtual machines to given second physical entities, the second placement algorithm also using the first placement solution to generate the second placement solution. - View Dependent Claims (23, 24)
-
Specification