Optimized placement planning for virtual machines in a network by breaking relocation graph into one or more cores to apply different solutions

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.

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.