NETWORK-AWARE COORDINATION OF VIRTUAL MACHINE MIGRATIONS IN ENTERPRISE DATA CENTERS AND CLOUDS

• US 20130086272A1
• Filed: 06/01/2012
• Published: 04/04/2013
• Est. Priority Date: 09/29/2011
• Status: Active Grant

• Current Assignee: NEC Corporation
• Original Assignee: NEC Laboratories America Inc (NEC Corporation)
• Inventors: Chen, Haifeng, Jiang, Guofei
• Granted Patent: US 8,694,644 B2
• Time in Patent Office: Days
• US Class Current: 709/226
• CPC Class Codes: G06F 9/4856 resumption being on a different machine, e.g. task migration, virtual machine migration G06F9/5088 takes precedence

Abstract

Systems and methods are disclosed to schedule virtual machine (VM) migrations by analyzing VM migration behavior; building a simulation tool to predict time for multiple migrations under different links conditions and VM characteristics; determining a predetermined bandwidth sharing policy for each network link; applying a bin-packing technique to organize bandwidth resources from all network links, and allocating the links to different migration tasks.

Claims

1. A method to schedule virtual machine (VM) migrations, comprising:

analyzing VM migration behavior;

building a simulation tool to predict time for multiple migrations under different links conditions and VM characteristics;

determining a predetermined bandwidth sharing policy for each network link;

applying a bin-packing technique to organize bandwidth resources from all network links, and

allocating the links to different migration tasks.

2. The method of claim 1, comprising analyzing VM migration behavior.

3. The method of claim 1, comprising simulating the performance of a single VM migration.

4. The method of claim 1, comprising simulating the performance of a plurality of VM migrations.

5. The method of claim 4, comprising performing network resource multiplexing.

6. The method of claim 4, comprising determining overhead associated with communication protocols.

7. The method of claim 1, comprising determining global resource assignments.

8. The method of claim 7, comprising determining a network link capacity.

9. The method of claim 7, comprising packing multiple migrations into one.

10. The method of claim 9, comprising performing migration demand estimation.

11. The method of claim 9, comprising packing each item into a bin representing all network links wherein the item denotes each migration task.

12. The method of claim 1, comprising determining available bandwidth in the network links as

13. The method of claim 1, comprising minimizing VM migration time by minimizing a Premigration Overhead, time spent in the ‘

iterative pre-copy’ and

‘

stop-and-copy’

stages, and a Postmigration Overhead.

14. The method of claim 1, comprising determining end-to-end bandwidth demand for migration M_i as a vector

D⁽ⁱ⁾=P⁽ⁱ⁾×

d⁽ⁱ⁾=[1,0,0, . . . , 1]^T×

d⁽ⁱ⁾

Where a binary vector P⁽ⁱ⁾=[1,0,0, . . . , 1]^T represents a path of migration M_i with a value ‘

1’

in the ith entry indicating an inclusion of the ith link in the path and ‘

0’

vice versa and where d⁽ⁱ⁾ is an expected bandwidth allocated to M_i.

15. The method of claim 1, comprising determining a local bandwidth demand d_j⁽ⁱ⁾ of M_i in link l_j⁽ⁱ⁾ as d_j⁽ⁱ⁾=c_j/s_j⁽ⁱ⁾.

16. The method of claim 1, comprising:

transforming a resource demand vector D⁽ⁱ⁾ for each migration M_i into a scalar η

⁽ⁱ⁾, D⁽ⁱ⁾→

η

⁽ⁱ⁾, where η

⁽ⁱ⁾ equals to a summation of all the elements in D⁽ⁱ⁾.

sorting resource demands based on their transformed η

⁽ⁱ⁾ values; and

scanning migration tasks from high to low η

⁽ⁱ⁾s, wherein for each selected migration task, placing the selected task in an earliest time interval T with free capacities to host the task.

17. The method of claim 1, comprising

determining bandwidth demand d_j⁽ⁱ⁾ for all links l_j⁽ⁱ⁾, j=1, . . . , k along M_i'"'"'s path;

and

determining an overall bandwidth demand of M_i as a maximum demand among all the local estimations d⁽ⁱ⁾=max{d₁⁽ⁱ⁾,d₂⁽ⁱ⁾, . . . , d_k⁽ⁱ⁾}.

19. The method of claim 1, comprising means for analyzing VM migration behavior

20. The method of claim 1, comprising means for simulating the performance of one or more VM migrations.

18. A system to schedule virtual machine (VM) migrations, comprising:

means for analyzing VM migration behavior;

means for building a simulation tool to predict time for multiple migrations under different links conditions and VM characteristics;

means for determining a predetermined bandwidth sharing policy for each network link;

means for applying a bin-packing technique to organize bandwidth resources from all network links, and

means for allocating the links to different migration tasks.