Patent Document ID: 20170228249
Application ID: 15496372
Patent Flag: 0

Claim One:
1. A system for generating a virtual machine migration plan, the system comprising: a memory having computer readable instructions; and a processor for executing the computer readable instructions, the computer readable instructions including: 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; identifying a heuristic goal cost to reach the goal state from the intermediate states based on a fewest number of virtual machine movements; 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; analyzing a sequential migration plan in the virtual machine migration plan to redefine one or more portions of the virtual machine migration plan as parallel migrations; sequentially scanning the virtual machine migration plan for one or more virtual machines that move at least twice to define parallelism gates; generating one or more candidate parallel migration plans based on the parallelism gates in combination with serial migrations from the virtual machine migration plan, the one or more candidate parallel migration plans each including at least two virtual machine to host movements performed in parallel; and comparing the one or more candidate parallel migration plans to determine a combination of the serial migrations and at least one of the one or more candidate parallel migration plans that meets migration criteria with a lowest total migration cost.