Patent Document ID: 9753757
Application ID: 14841803
Patent Flag: 1

Claim One:
1. A method for generating a virtual machine migration plan, the method comprising: determining an initial mapping of a plurality of virtual machines to a plurality of hosts as an origin state; determining a final mapping of the virtual machines to the hosts as a goal state; generating a plurality of candidate paths to transition from the initial mapping to the final mapping; evaluating the candidate paths based on a heuristic state transition cost to transition from state-to-state from the origin state through a plurality of intermediate states to the goal state by recursively obtaining a list of transitions that a parent state underwent to reach the parent state from the origin state, wherein the heuristic state transition cost is based on a fixed cost assigned to each one of a plurality of enumerated transition types comprising: a partial transition type that places at least one but not all of the virtual machines onto at least one of the hosts according to the goal state, an endgame transition type that fully satisfies the goal state, a counter movement transition type that takes away at least one of the virtual machines from a targeted host of the goal state, a cycle transition type that moves at least one of the virtual machines back onto a previous host, and a random transition type that shuffles locations of one or more of the virtual machines; identifying a heuristic goal cost to reach the goal state from the intermediate states based on a fewest number of virtual machine movements; and generating the virtual machine migration plan based on the heuristic state transition cost of the candidate paths in combination with the heuristic goal cost of a sequence of transitions from the origin state to the goal state having a lowest total cost.