US 9,753,757 B2Granted

Machine learning for virtual machine migration plan generation

AssigneeInternational Business Machines Corporation

InventorsEli M. Dow, Thomas D. Fitzsimmons, Jessie Yu

Life of this patent

Estimating the term…

Loading patent…

Abstract

Embodiments relate to generating a virtual machine (VM) migration plan. A method includes determining an initial mapping of VMs to hosts as an origin state and a final mapping of VMs to hosts as a goal state. Candidate paths are generated from the initial mapping to the final mapping. The candidate paths are evaluated based on a heuristic state transition cost from the origin state through intermediate states to the goal state by recursively obtaining a list of transitions that a parent state underwent. A heuristic goal cost is identified to reach the goal state from the intermediate states based on a fewest number of VM movements. The VM migration plan is generated 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.

Claims17

Dependent claims

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.

5 more elements

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;
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.

8 more elements

Dependencies are inferred from the claim text.

Facts

Application: 14/841,803Filed 1 Sep 2015 · continuation
Priority: 23 Apr 2015
Published: US 2016/0314011 A127 Oct 2016
Granted: 5 Sep 2017
Term ends: Not estimatedThe source records don’t support an estimate.

Classification6 codes

G06F 9/45558
Hypervisors; Virtual machine monitors: hypervisor-specific management and integration aspects
G06F 13/28
For access to input/output bus: using burst mode transfer, e.g. direct memory access DMA, cycle steal
G06N 20/00
Machine learning
G06F 2009/4557
Hypervisor-specific management and integration aspects: distribution of virtual machine instances; Migration and load balancing

Family

Application14/694,011Parent of this continuation · filed 23 Apr 2015
US 2016/0314014 A1Pre-grant publication · published 27 Oct 2016
US 2016/0314011 A1Published application
US 9,727,366 B2Related patent
US 9,753,757 B2This patent

From the US filing history. Foreign family members aren’t listed.