# US 8,789,043 B2 · Optimized placement planning for virtual machines in a network by breaking relocation graph into one or more cores to apply different solutions > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 8,789,043 B2 - Document ID: US8789043B2 - Status: Granted - Kind: B2 - Application number: 12/912,805 - Filed: 2010-10-27 - Published: 2012-02-16 - Granted: 2014-07-22 - Earliest claimed: 2009-03-24 - Assignees: International Business Machines Corporation - Applicants: Ofer Biran; Ari Freund; Erez Hadad; Evgeny Hazanovich; Yosef Moatti - Inventors: Ofer Biran; Ari Freund; Erez Hadad; Evgeny Hazanovich; Yosef Moatti - Web page: https://patentgrep.com/patent/US8789043B2 ## CPC - G06F 9/45558: {Hypervisor-specific management and integration aspects} - G06F 9/5066: {Algorithms for mapping a plurality of inter-dependent sub-tasks onto a plurality of physical CPUs (mappping at compile time, see G06F8/451)} - 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)} - G06F 2009/4557: {Distribution of virtual machine instances; Migration and load balancing} - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## Abstract Methods and systems for generating a placement plan for one or more virtual machines (VMs) in a computing environment are provided. The method comprises providing, to a computing system, input parameters comprising a current placement for the one or more VMs on one or more hosts in a computing network; a target placement that assigns at least one of the one or more VMs to at least another host in said one or more hosts; and a set of constraints with which both the current placement and the target placement comply. ## Claims ### Claim 1 A computer implemented method for generating a placement plan for one or more virtual machines (VMs) in a computing environment, the method comprising: providing, to a computing system, input parameters comprising: a current placement for the one or more VMs on one or more hosts in a computing network; a target placement that assigns at least one of the one or more VMs to at least another host in said one or more hosts; a set of constraints with which both the current placement and the target placement comply; and computing a placement plan to achieve the target placement for a target VM based on a placement sequence, wherein intermediary placement states are determined for the target VM according to the placement plan so that the target VM is migrated according to the placement sequence over one or more hosts in such a way to avoid a relocation cycle that results in a deadlock state in view of the set of constraints and the placement plan as applicable to other VMs, wherein the computation of the placement plan further comprises: computing a relocation graph that reflects placement changes for VM deployments, relocations or removals that are to be performed to implement the placement plan, wherein a node in the graph represents a host, and an edge in the graph pointing from a first node to a second node represents a planned VM relocation from a first host to a second host, the first node representing the first host and the second node representing the second host; breaking the relocation graph into one or more cores using the input parameters to the computing system, wherein a core comprises a first relocation graph that is smaller in size than the relocation graph; for a core, determining if the core is a simple core, wherein a core is determined to be simple if VMs in that core have same resource requirements and have no anti-collocation constraints; and in response to determining that the core is a simple core, applying a first solution to the first relocation graph to determine a relocation plan or a placement scheme for VMs in that core. ### Claim 2 (depends on 1) The method of claim 1, wherein the first solution is implemented based on Euler's theorem such that a host is planned to have a same number of VMs relocated from the host as a number of VMs that will be relocated towards the host. ### Claim 3 (depends on 1) The method of claim 1, further comprising: in response to determining that the core is not a simple core, determining whether the core's complexity is below a first threshold; and in response to determining that the core's complexity is below the first threshold, applying a second solution to the first relocation graph to determine the relocation plan for the VMs in that core. ### Claim 4 (depends on 3) The method of claim 3, wherein the second solution comprises performing an exhaustive search on the first relocation graph to determine the relocation plan for the VMs in that core. ### Claim 5 (depends on 3) The method of claim 3, further comprising in response to determining that the core is not a simple core, determining whether the core's complexity is below above a second threshold; and in response to determining that the core's complexity is above the second threshold, rather than performing an exhaustive search, applying a third solution to the first relocation graph to determine the relocation plan or the placement scheme for the VMs in that core. ### Claim 6 (depends on 5) The method of claim 5, wherein the third solution comprises applying one or more relocations for one or more VMs in the first relocation graph to generate another relocation graph. ### Claim 7 (depends on 1) The method of claim 1 wherein the breaking of the graph into one or more cores is done by recursively: identifying relocations which may be initiated immediately without breaking compliance with the set of constraints and without causing any possible relocation cycle and moving those relocations out of the relocation graph and appending them to a prefix of the relocation plan; and identifying relocations which may be initiated after the relocations in the relocation graph without breaking compliance with the constraints and without causing any possible relocation cycle and moving said relocations out of the relocation graph and prepending them to a suffix of the relocation plan. ### Claim 8 (depends on 3) The method of claim 3, wherein complexity of a core is estimated by determining size of a set of incoming relocations for one or more hosts in the core, wherein the estimated complexity of a core is defined as a product of the incoming relocation set sizes, wherein the hosts in a core have at least one incoming relocation. ### Claim 9 A computer implemented system for generating a placement plan for one or more virtual machines (VMs) in a computing environment, the system comprising processing units comprising: a processor; a logic unit for providing, to a computing system, input parameters comprising: a current placement for the one or more VMs on one or more hosts in a computing network; a target placement that assigns at least one of the one or more VMs to at least another host in said one or more hosts; a set of constraints with which both the current placement and the target placement comply; and a logic unit for computing a placement plan to achieve the target placement for a target VM based on a placement sequence, wherein intermediary placement states are determined for the target VM according to the placement plan so that the target VM is migrated according to the placement sequence in such a way to avoid a relocation cycle that results in a deadlock state in view of the set of constraints and the placement plan as applicable to other VMs, wherein the system further comprises the following for computation of the placement: a logic unit for computing a relocation graph that reflects placement changes for VM deployments, relocations or removals that are to be performed to implement the placement plan, wherein a node in the graph represents a host, and an edge in the graph pointing from a first node to a second node represents a planned VM relocation from a first host to a second host, the first node representing the first host and the second node representing the second host; a logic unit for breaking the relocation graph into one or more cores using the input parameters to the computing system, wherein a core comprises a first relocation graph that is smaller in size than the relocation graph; a logic unit for determining if a core is a simple core, wherein a core is determined to be simple if VMs in that core have same resource requirements and have no anti-collocation constraints; and a logic unit for applying a first solution to the first relocation graph to determine a relocation plan or a placement scheme for VMs in that core in response to determining that the core is a simple core. ### Claim 10 (depends on 9) The system of claim 9, wherein the first solution is implemented based on Euler's theorem such that a host is planned to have a same number of VMs relocated from the host as a number of VMs that will be relocated towards the host. ### Claim 11 (depends on 9) The system of claim 9, further comprising: a logic unit for determining whether the core's complexity is below a first threshold, in response to determining that the core is not a simple core; and a logic unit for applying a second solution to the first relocation graph to determine the relocation plan for the VMs in that core in response to determining that the core's complexity is below the first threshold. ### Claim 12 (depends on 11) The system of claim 11, wherein the second solution comprises performing an exhaustive search on the first relocation graph to determine the relocation plan for the VMs in that core. ### Claim 13 A non-transitory computer readable storage medium having computer readable instructions stored thereon, wherein execution of said instruction by a computing machine causes the computing machine to: provide, to a computing system, input parameters comprising: a current placement for the one or more VMs on one or more hosts in a computing network; a target placement that assigns at least one of the one or more VMs to at least another host in said one or more hosts; a set of constraints with which both the current placement and the target placement comply; and compute a placement plan to achieve the target placement for a target VM based on a placement sequence, wherein intermediary placement states are determined for the target VM according to the placement plan so that the target VM is migrated according to the placement sequence in such a way to avoid a relocation cycle that results in a deadlock state in view of the set of constraints and the placement plan as applicable to other VMs, wherein the computation of the placement plan further comprises: computing a relocation graph that reflects placement changes for VM deployments, relocations or removals that are to be performed to implement the placement plan, wherein a node in the graph represents a host, and an edge in the graph pointing from a first node to a second node represents a planned VM relocation from a first host to a second host, the first node representing the first host and the second node representing the second host; breaking the relocation graph into one or more cores using the input parameters to the computing system, wherein a core comprises a first relocation graph that is smaller in size than the relocation graph; for a core, determining if the core is a simple core, wherein a core is determined to be simple if VMs in that core have same resource requirements and have no anti-collocation constraints; and in response to determining that the core is a simple core, applying a first solution to the first relocation graph to determine a relocation plan or a placement scheme for VMs in that core. ### Claim 14 (depends on 13) The non-transitory computer readable storage medium of claim 13, wherein the first solution is implemented based on Euler's theorem such that a host is planned to have a same number of VMs relocated from the host as a number of VMs that will be relocated towards the host. ### Claim 15 (depends on 13) The non-transitory computer readable storage medium of claim 13, wherein execution of said instruction by a computing machine further causes the computing machine to: in response to determining that the core is not a simple core, determine whether the core's complexity is below a first threshold; and in response to determining that the core's complexity is below the first threshold, apply a second solution to the first relocation graph to determine the relocation plan for the VMs in that core. ### Claim 16 (depends on 13) The non-transitory computer readable storage medium of claim 13, wherein the second solution comprises performing an exhaustive search on the first relocation graph to determine the relocation plan for the VMs in that core.