Patent Document ID: 7904540
Application ID: 12409548
Patent Flag: 1

Claim One:
1. A computer-implemented method for planning placement of virtual machines VMs in a computing environment comprising a set of hosting machines HMs, said method comprising: providing, at a computing device, a current placement function cp(v) representing a current placement of each of said virtual machines VMs v in one of said hosting machines HMs h; defining, at said computer device, a modifiable copy of said current placement function, mcp( ) defining, at said computing device, a target placement function tp(v) representing a target placement of the virtual machines VMs in said HMs, one or more of said VMs and HMs having a set of policies and resource constraints associated therewith; and, constructing, at said computer device, a graph comprising VM v nodes interconnecting HM h nodes via edges for modeling a current and target deployment states of said VMs; iterating over said HM and VM nodes of said graph and gradually modifying said mcp( ) placement function to resemble the target placement function; and generating, from said iterating, an ordered sequence of VM placement change instructions comprising a plan for changing the current placement of said virtual machines VMs v according to said target placement function tp(v) without violating said associated set of policies and resource constraints, after completion of each of said iterating; and, generating, for output at said computing device, said plan for placing said virtual machines VMs v at said host machines HMs; wherein said graph is a bipartite directed graph, said graph constructing comprising: adding edges to said graph, said edges including: an edge(h, v) for every current placement of said VM v at said HM h with resource allocation rv, and an edge(v, h) for every target placement of said VM v at said HM h with said resource allocation rv.