<figure><img src="image_1.png" /></figure>

HAL
open science

A Scheduling Method for Multiple Virtual Machines
Migration in Cloud

Zhenzhong Zhang, Limin Xiao, Xianchu Chen, Junjie Peng

► To cite this version:

Zhenzhong Zhang, Limin Xiao, Xianchu Chen, Junjie Peng. A Scheduling Method for Multiple Virtual Machines Migration in Cloud. 10th International Conference on Network and Parallel Computing (NPC), Sep 2013, Guiyang, China. pp.130-142, 10.1007/978-3-642-40820-5_12 . hal-01513781

HAL Id: hal-01513781

https://inria.hal.science/hal-01513781

Submitted on 25 Apr 2017

**HAL** is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
A Scheduling Method for Multiple Virtual Machines
Migration in Cloud

Zhenzhong Zhang¹, Limin Xiao¹, Xianchu Chen¹, Junjie Peng²

1. State Key Laboratory of Software Development Environment,
School of Computer Science and Engineering
Beihang University, Beijing, China

2. School of computer engineering and science
Shanghai University, Shanghai, China

Email: zzzhang@cse.buaa.edu.cn, xiaolm@buaa.edu.cn,
chengxc@cse.buaa.edu.cn, jjie.peng@shu.edu.cn

**Abstract.** Infrastructure as a Service(IaaS) is important in Cloud Computing, which provides on-demand virtual machines(VMs) to users. The resource management plays an important role in IaaS cloud, which deploys and relocates virtual machine on available hosts for different targets, such as load balance, power saving and resource utilization improving. The virtual machine placement problem can be considered as a bin packing problem. Many researchers use the heuristic algorithms based approach to solve this virtual machine placement problem. However, they all focus on how to find the optimization solution for the bin packing problem of virtual machine placement. However, these studies did not consider the scheduling of multiple virtual machine migration that involved in the transfer process from one V-P mapping to another. Because of the large overhead produced by virtual machine migration, the optimization of multiple virtual machines migration process could reduce the overhead of resource management in IaaS cloud, and accelerate the migration process. In this paper, we analyse and formal the multiple virtual machines migration problem, and propose a scheduling method to reduce the VM migration times and accelerate the migration process. Experiments show that our method can decrease the VM migration times, reduce the traffic and accelerate the process of multiple virtual machine migration.

**Keywords:** Cloud Computing; Virtual Machine Schedule; Multiple Virtual Machines Migration; IaaS

# 1 Introduction

Cloud computing[1] is a popular trend in current computing which attempts to provide cheap and easy access to computational resources. IaaS(Infrastructure as a Service)[2] provides infrastructure or the actual hardware to customers who are responsible to install operating systems and necessary softwares. Based on virtualization technology[3], IaaS cloud is usually provided to users in the form of Virtual Machines
(VMs), such as Amazon EC2[4] and VMware vCloud[5]. On IaaS cloud platform, resources are provided by need as services, and it guarantees to the subscribers that it sticks to the Service Level Agreement (SLA). IaaS cloud platform needs to dynamically deploy and relocate virtual machine onto proper physical hosts in order to meet different needs, such as avoid hotspot, power saving and load balancing[5-7]. Therefore, how to dynamically and efficiently schedule virtual machines among physical hosts to meet the needs of different targets becomes a problem.

The traditional resource management methods usually schedule virtual machine or allocate resource in cloud when some certain conditions are triggered[8-10], such as threshold for load balancing. Due to the complexity and variability of a large number of virtual machines in IaaS cloud, traditional methods are difficult to carry out global resource optimization management. To address this issue, many optimization theory based virtual machine placement approaches are used to solve the resource management problem in IaaS cloud[11, 12]. In such scenario, the resource management problem is considered as a bin packing problem, which need to find the proper mapping of virtual machines to available physical machines.

Linear programming[13], genetic algorithm[14] and ant colony algorithm[15] have been used to solve the bin packing problem, and obtained good results. All these researches are focused on how to find the actual mapping of virtual machines to available physical machines(V-P mapping). However, these studies did not consider the scheduling of multiple virtual machine migration that involved in the transfer process from one V-P mapping to another. Because the virtual machine migration process needs to copy large amounts of data(memory data or even virtual disk) from the source host to the destination host, it will produce large CPU overhead and network traffic, and cost much resource. Therefore, the optimization of multiple virtual machines migration process could reduce the overhead of resource management in IaaS cloud and accelerate the migration process. The optimization includes reducing the number of virtual machine migration, and migrating small VM instead of big VM.

In this paper, we study the multiple virtual machines migration problem, and propose a scheduling method to optimize multi-virtual machine migration process. The main contributions of this paper are concluded as the followings: (1)Modeling and formalization of the multiple virtual machines migration problem; (2)A scheduling method optimizing the multiple virtual machines migration process.

## 2 Related Work

For resource management in cloud data center, previous work has focused on the problem of placing and replacing VMs in servers, in order to optimize resource management for different criteria, including performance, power and cost. There are some molded products and research projects on virtualized resource management, such as VMware DRS[8]. They dynamically allocate the CPU, memory and I/O resources to partitioned virtual machines according to customer's requirements, but they ignore the QoS[9]. The work in [16] minimized the number of physical machines using dynamic adaptation technique based on off-line analysis of application performance, which is seen as a function of machine utilization. The load forecasting techniques are also widely used in the management of cloud resources, such as load-balancing and re-
source scheduling[17]. In [18], a model-predictive controller is proposed to minimize the total power consumption of the servers in an enclosure subject to a given set of QoS constraints.

Optimization and heuristic methods are wildly used by virtual machine scheduling and placement in IaaS cloud for different targets, such as load balancing or power saving. Integer Linear Programming is used to solve an interference-aware VM placement problem (IAWMP) [13]. They first formulate this problem by an Integer Linear Programming (ILP) model to solve it optimally. They also propose a polynomial-time heuristic algorithm to efficiently solve the IAWMP problem. In [14] a general model is proposed for resources allocation of virtual machines in multi-tier distributed environments. Their model describes each virtual machine and each physical host by a multi-dimensional resource vector, allowing the coexistence of both quantitative and qualitative resources, also handling different SLAs. [15] proposes a multi-objective ant colony system algorithm for the virtual machine placement problem. Their method could efficiently obtain a set of non-dominated solutions that simultaneously minimize total resource wastage and power consumption. [19] proposes a runtime virtual machine mapping framework (GreenMap), and designs a probabilistic, heuristic algorithm to mapping VMs onto a set of physical machines under the constraint of multi-dimensional resource consumptions.

However, all above optimization and heuristic researches are focus on how to find the actual mapping of virtual machines to available physical machines (V-P mapping). Although some virtual machine migration research [20, 21] can help to accelerate virtual machine migration process, however, the scheduling of multiple virtual machine migration that involved in the transfer process from one V-P mapping to another was rarely considered. Therefore, in this paper, we will study the multiple virtual machines migration problem, and propose a scheduling method to optimize multi-virtual machine migration process.

# 3 Problem Analysis And Formulation

## 3.1 Analysis of multiple virtual machines migration problem

In this paper, the heuristics-based resource management methods are consist of two steps, which is shown in Figure 1. Firstly, the bin packing problem of virtual machine management is solved by a heuristic based algorithm, and the global approximate optimal virtual machine groups are obtained. The VMs mapping to same physical host are in same group, called a VM-cluster. Next, For the global optimal virtual machine grouping, we also need to convert the virtual machines to physical host mapping (V-P mapping) from current state(initial VM location) to the target state(final VM location).

<figure><img src="image_3.png" /><figcaption>Fig. 1. The process of VM placement in IaaS cloud</figcaption></figure>
The same VM group can locate on different hosts, therefore the target state is not unique. This process of V-P mapping convert involves the migration of multiple virtual machines, which could be scheduled to reduce the migration cost of VMs. Our study is focused on the optimization of the multiple virtual machines migration process. The purpose of this optimization is to minimize the overhead of CPU and network cost and avoid resource conflicts during the migration process(migration the number of virtual machines, choose the smaller virtual machine migration, adjust virtual machine migration steps to avoid conflicts). The optimization includes the choosing of VM for migration, the selecting of destination physical host, and accelerate the migration process of all VMs. For example, If several V-P mappings have same effect, we will choose the one that has minimum number of VM migration. If several V-P mapping have same VM migration steps, the one with minimal numbers of VM migration times will be chosen.

We need to develop a model to describe the scheduling problem of multiple virtual machines migration. In this model, the virtual machines which belong to same physical host are in the same group, and called a VM-cluster. At the initial moment, the VM-clusters of all virtual machines in IaaS cloud are the initial state of V-P mapping. Our schedule method is responsible for converting the V-P mapping from one type of VM-cluster to another VM-cluster. In this process, the proper physical host should be chosen for every VM-cluster, and the proper order of virtual machine migration determined, which is equivalent to create a new mapping of VM-clusters to physical hosts. Of course, this new mapping must meet the demand that the number of VM migration and the amount of traffic are as small as possible.

## 3.2 Formal Description of the VM schedule problem

We formalize the virtual machines to physical hosts mapping problem in this section. Firstly, we define some basic objects below:

* Host is denoted by $H_k(k=1,2...,N)$, and the set of hosts is $H=\{H_1,H_2,...,H_N\}, (N>=1)$. $V_j$ denotes all the virtual machines that need to be migration. The set of virtual machine is $V = \{V_1,V_2,...,V_N\} (n>=1)$. The virtual machines that locate on the same physical host form a virtual machine set. We call this set the VM-cluster which is denoted by $C_i(i=1,2,...,M)$. The set of VM-cluster is $C=\{C_1,C_2,...,C_M\}$. In order to simplify this model, we require M always be no more than N, that is the number of VM-clusters should be less than or equal to the number of hosts.

* $L(V_j)$ is the amount of network traffic that generated by the migration of virtual machine $V_j$. Cost is the total amount of traffic generated by multiple virtual machines migration. In the initial state, each virtual machine running on a particular station host to form a set of virtual machine clusters.

* At the initial state, each virtual machine running on a particular host to form a set of VM-cluster. And it will be converted to another set of VM-cluster by our schedule method. If the virtual machine $V_j$ belongs to a cluster $C_i$, it is denoted as $V_j \in C_i$. The optimal mapping of virtual machines to physical hosts will be selected by our scheduling method.
3.3 The VM scheduling method

After management strategy at initial state, all the virtual machines in the system are
re-divided into a set of VM-clusters(shown as $V_j \in C_i, C_i \in C$). The establishment of
mapping of virtual machines to physical hosts is equivalent to choose the suitable of
physical host $H_k$ for each VM-cluster $C_i$. Our multiple virtual machine migration
scheduling method need to create mapping of VM-cluster set(C) to physical host
set(H) as $f(M \to N)$, and select the optimal one that meet our targets(minimum migra-
tions, etc.). Each mapping establishes a relationship between VM-clusters to hosts,
and determines the target hosts that each virtual machine will migrate to. Therefore
migration path of the virtual machines is also determined. Because the mapping of
VM-cluster(C, the number of C is M) to physical hosts(H, the number of H is N) will
generate a large number of virtual machine migration paths($A_n^m$). Our scheduling al-
gorithm needs to search for the optimal solution in all migration paths, and we will
use heuristic approaches to simplify the process. After the optimal migration path is
obtained, our scheduling algorithm will further determine the optimal virtual machine
migration steps based on the principle of minimum system cost.

<figure><img src="image_4.png" /><figcaption>Fig. 2. The migration path of f1 and f2</figcaption></figure>

We show a simple examples here, to describe our method in detail. As a case that
virtual machines V1-V9 run on three hosts(H1, H2, H3). After bin packing optimiza-
tion, these virtual machines are divided into three clusters(C1:V1,V2,V4,V9;
C2:V3,V6,V8;C3:V5,V7). Two different mappings are available, the mapping of f1 is
(C1→H2,C2→H3,C3→H1), and the mapping of f2 is (C1→H1,C2→H2,C3→H3).
F1 and f2 are shown in Figure 2.A and 2.B. These two mappings correspond to two
multiple virtual machine migration paths. These two migration paths choose different
physical hosts for VM-clusters, resulting in a different number of VM migrations.
Obviously, the path of f2 needs to migrate 5 VMs, which is less than 7 VMs of f1.

When the two mappings have the same VM migration times, the different size and
load of virtual machines will also lead to a larger difference of network traffic and
CPU load. For example, the migration of virtual machine with large memory and
higher workload needs to copy more data and consume more CPU resources. $L(V_j)$
indicates the network traffic generated by virtual machine $V_j$ during migration. The
total transfer data of $fx$ is $Cost(fx)$, which is the sum of all $L(V_j)$. Like the first step,
the cost of each migration paths are estimated and the one with minimum migration
traffic would be chosen.
While the virtual machines starts migrate, the migrating virtual machines which have same source or destination host would migrate one by one. Because the node migration performance of host would decreased significantly due to simultaneous execution of multiple virtual machine migration. And of course, the virtual machines which their migration do not conflict with each other, could migrate at same time.

# 4 Design and implementation

## 4.1 Host Selection Algorithm for Virtual Machine

The host selection algorithm for virtual machine is used to find the optimal mapping from all possible V-P mapping, and to obtain the proper destination hosts for the VMs. Specifically, it needs to search all $A_n^m$ mappings of VM-cluster(C, the number is M) to physical hosts(H, the number is N), and selects the optimal mapping as the multiple virtual machine migration path. The optimal selection principle is minimum migration times of multiple migration process and minimum amount of migration network traffic(ie, the migration of VMs with smaller size will generate less network traffic). An improved genetic algorithm is used to search the best mapping solution in this case. Due to limited space, the details of the genetic algorithm are not shown here.

<figure><img src="image_5.png" /><figcaption>Fig. 3. The algorithm for Optimal mapping selection</figcaption></figure>

The pseudo-code of our based algorithm is shown in Figure 8. The algorithm traverses all $A_n^m$ mappings (lines 1-11) to obtain the minimum value of VM migration times and generates the set F which contains all the mappings with the minimum migration times (lines 8-9). Finally, it calculates the network traffic(Cost(f)) for each
mapping in F, and select the mapping with minimum network as the return result of
the algorithm (lines 12-15). In the algorithm, $V_j$ is the virtual machine with number j,
$Y_j$ is the host where the virtual machine $V_j$ current locates, fs is a mapping of virtual
machines to hosts, $Y'_j$ is the host that $V_j$ will migrate to with the fs mapping, F is a set
of mapping with minimum VM migration times, Cost(f) is the network traffic gener-
ate by VMs migration of mapping f and Min(F) is the mapping with minimum Cost(f)
in set F.

## 4.2 The Migration Order and Parallelization of Multiple VMs Migration

After the selection of target hosts for multiple virtual machine hosts migration, the
schedule algorithm next needs to determine the migration order of these virtual ma-
chines to be migrated. Our scheduling algorithm will generate a trituple $\langle V_j, H_j^s, H_j^d \rangle$
for each virtual machine that needs to be migrated. $V_j$ is the virtual machine need to be
migrated, $H_j^s$ and $H_j^d$ are the source and destination hosts for migration of $V_j$. The
order of multiple virtual machine migration could be represented by this trituple se-
quence. Our algorithm is mainly based on the following two principles to arrange the
order of multiple virtual machine migration, and execute the migration process.

Firstly, the scheduler give priority to migrates virtual machine on high-load host to the low-load host, and give priority to migrates virtual machines with higher workload and bigger size. The migration of virtual machine will cost much CPU resource both on source and destination hosts. While priority migrate virtual machine on high-load host to low-load host, we need only consider the impact of migration on the source host(high-load host). And on the other hand, if migrate VM to a high-load host, there may be no enough resource remained for this virtual machine. Meanwhile, the sched-uler priority migrate virtual machine with higher workload on source host. This is mainly because the virtual machine with higher workload is more sensitive to re-source competition. A bit more workload increase will cause the performance of the application decline. But for the application on low-load virtual machine, the workload increase is tolerable. And based on the queuing theory, the VM with bigger memory size has less priority to migrate. Therefore, according to the above aspects, the sched-uler can minimize the impact of VM migration on application performance.

Secondly, the parallel migration can be used for the virtual machines whose migra-
tion do not interfere with each other. For performance and stability reasons, a physical
host can only deal with one virtual machine migration, either as an source host or as a
destination hosts. Therefore, we can refer to the realization of processor's instruction-
level parallelism to parallel processing the multiple virtual machines migration. In this
case, the trituple sequence of migration VM is handled as the sequence of instructions
of processor. When a VM migration is in processed, the source and destination hosts
are marked busy, and reset free after VM migration. Therefore, while the source and
destination hosts of the trituple being processed are not busy, the migration of this
trituple could be executed immediately. Based on this strategy, our method can
achieves parallel virtual machine migration, and avoid resource conflict.
# 5 Experiment And Evaluation

In this section, we validate and test the multiple virtual machine migration scheduling method, then analysis its performance. Using different test cases of multiple virtual machines migration to verify the effect of our schedule algorithm. The performance of our method is compared with default migration method, which migrate virtual machines one by one randomly.

For our experiment environment, we use a cluster composed by eight computer servers and one storage array. The configuration of server includes two AMD Opteron 2350 quad-core CPUs running at 2.0GHz and 12GB DDR RAM. They are all running XenServer 6.1[22]. The storage array connects four hosts through optical fiber, as a shared storage. All the servers are connected by a Gigabit LAN. The virtual machine templates are configured with one VCPU, 1GB,2GB,4GB RAM and one virtual network card. The load generator program will randomly call some of the popular applications to generate the CPU, network and disk I/O workload, such as kernel compilation, file compression, and FTP, etc.

## 5.1 Verify the effectiveness of our algorithm

We select a test case to validate effectiveness of our scheduling algorithm. This test case uses 12 virtual machines and 8 physical hosts. The detail configuration of each virtual machine and physical host are shown in Table 1. These configurations of test case include input of algorithm, memory of VM and physical, the mapping of virtual machine to physical before and after migration, the workload of each virtual machine and physical host and the output of algorithm at stage 1 and 2.

<table><caption>**Table 1.** The configuration of test case</caption><tr><td>Input of VM-cluster</td><td colspan="3">C1:v1,v2,v3,v10;C2:v4,v5,v6,v7;C3:v8,v9,v11,v12</td></tr><tr><td colspan="4">Information of VMs</td></tr><tr><td>VM ID</td><td>Mem(MB)</td><td>Init reside host ID</td><td>Load(%)</td></tr><tr><td>V1</td><td>1024</td><td>H1</td><td>30%</td></tr><tr><td>V2</td><td>1024</td><td>H1</td><td>60%</td></tr><tr><td>V3</td><td>1024</td><td>H4</td><td>50%</td></tr><tr><td>V4</td><td>2048</td><td>H6</td><td>15%</td></tr><tr><td>V5</td><td>2048</td><td>H4</td><td>80%</td></tr><tr><td>V6</td><td>2048</td><td>H4</td><td>50%</td></tr><tr><td>V7</td><td>3072</td><td>H6</td><td>40%</td></tr><tr><td>V8</td><td>3072</td><td>H2</td><td>35%</td></tr><tr><td>V9</td><td>3072</td><td>H2</td><td>45%</td></tr><tr><td>V10</td><td>4096</td><td>H5</td><td>70%</td></tr><tr><td>V11</td><td>4096</td><td>H7</td><td>50%</td></tr><tr><td>V12</td><td>4096</td><td>H2</td><td>10%</td></tr><tr><td colspan="4">Information of physical hosts before VMs migration</td></tr><tr><td>Host ID</td><td>Mem(GB)</td><td>VMs</td><td>Load(%)</td></tr><tr><td>H1</td><td>12</td><td>V1,V2</td><td>15%</td></tr><tr><td>H2</td><td>12</td><td>V8,V9,V12</td><td>15%</td></tr><tr><td>H3</td><td>12</td><td>None</td><td>0%</td></tr><tr><td>H4</td><td>12</td><td>V3,V5,V6</td><td>30%</td></tr><tr><td>H5</td><td>16</td><td>V10</td><td>10%</td></tr></table>
<table><tr><td>H6</td><td>16</td><td>V4,V7</td><td>10%</td></tr><tr><td>H7</td><td>16</td><td>V11</td><td>10%</td></tr><tr><td>H8</td><td>16</td><td>None</td><td>0%</td></tr><tr><td colspan="4">Information of physical hosts after VMs migration</td></tr><tr><td>Host ID</td><td>Mem(GB)</td><td>VMs</td><td>Load(%)</td></tr><tr><td>H1</td><td>12</td><td>V1,V2,V3,V10</td><td>35%</td></tr><tr><td>H2</td><td>12</td><td>V8,V9,V11,V12</td><td>25%</td></tr><tr><td>H3</td><td>12</td><td>None</td><td>0%</td></tr><tr><td>H4</td><td>12</td><td>None</td><td>0%</td></tr><tr><td>H5</td><td>16</td><td>None</td><td>0%</td></tr><tr><td>H6</td><td>16</td><td>V4,V5,V6,V7</td><td>30%</td></tr><tr><td>H7</td><td>16</td><td>None</td><td>0%</td></tr><tr><td>H8</td><td>16</td><td>None</td><td>0%</td></tr><tr><td colspan="4">Output of stage 1: V10-->H1, V3-->H1, V11-->H2, V5-->H6, V6-->H6</td></tr><tr><td colspan="4">Output of stage 2: V5,V3,V6,V10,V11</td></tr></table>

The output of our algorithm is listed in Table 1. Because our algorithm is divided into two stages, our validation also has two stages.

Firstly, the output of the first stage of our algorithm is a set of V-P mapping which has the minimum virtual machine migration times. For this test case, the minimum migration times is 5, and the mapping in the set is (f1: V10-->H1, V3-->H1, V11-->H2, V4-->H4, V7-->H4) and (f2: V10-->H1, V3-->H1, V11-->H2, V5-->H6, V6-->H6). Then the algorithm compares the migration traffic of each mapping, and chooses the V-P mapping with minimum migration traffic as the optimal migration path. In this test case, the Cost(f1) = L(V10)+L(V3)+L(V11)+L(V4)+L(V7) = 14GB, and Cost(f2) = L(V10)+L(V3)+L(V11)+L(V5)+L(V6) = 13GB. Because Cost(f1) is greater than Cost(f2), our algorithm will select the f2 as the optimal migration path for multiple virtual machine migration.

<table><caption>**Table 2.** The trituple Sequence for migration step</caption><thead><tr><th>Id</th><th>Trituple</th><th>Load(VM/Host)</th><th>Mem(MB)</th></tr></thead><tbody><tr><td>1</td><td>(V10,H5-->H1)</td><td>70%/10%</td><td>4096</td></tr><tr><td>2</td><td>(V3,H4-->H1)</td><td>50%/30%</td><td>1024</td></tr><tr><td>3</td><td>(V11,H7-->H2)</td><td>50%/10%</td><td>4096</td></tr><tr><td>4</td><td>(V5,H4-->H6)</td><td>80%/30%</td><td>2048</td></tr><tr><td>5</td><td>(V6,H4-->H6)</td><td>50%/30%</td><td>2048</td></tr></tbody><tfoot><tr><td colspan="4">Migration step: V5,V3,V6,V10,V11</td></tr></tfoot></table>

<table><caption>**Table 3.** The parallel migration process for multiple virtual machine migration</caption><thead><tr><th>Time</th><th>Migrating VMs/ Mem(G)</th><th>Waiting VMs</th><th>Busy Hosts</th></tr></thead><tbody><tr><td>T1</td><td>V5(2G),V10(4G),V11(4G)</td><td>V3(1G),V6(2G)</td><td>H4,H6,H5,H1,H7,H2</td></tr><tr><td>T2</td><td>V5(2G),V10(4G),V11(4G)</td><td>V3(1G),V6(2G)</td><td>H4,H6,H5,H1,H7,H2</td></tr><tr><td>T3</td><td>V10(4G),V11(4G),V6(2G)</td><td>V3(1G)</td><td>H5,H1,H7,H2,H4,H6</td></tr><tr><td>T4</td><td>V10(4G),V11(4G),V6(2G)</td><td>V3(1G)</td><td>H5,H1,H7,H2,H4,H6</td></tr><tr><td>T5</td><td>V3(1G)</td><td>None</td><td>H4,H6</td></tr></tbody></table>

The second stage of the algorithm is to generate a virtual machine migration sequence based on the optimal mapping f2 which obtained by the first stage. The migra-
tion sequence is shown as a trituple sequence in Table 2. According to our optimization strategy, the migration order output by the second stage of our algorithm is V5, V3, V6, V10, V11. This is because the virtual machine V5 has a higher workload, and the physical host V5 reside on has the highest workload in the physical hosts. The virtual machine V10 and V11 migrate at last, due to the large memory(4098MB).

The Table 3 shows the parallel migration process of multiple virtual machines based on the migration order. We divide virtual machine migration process to several periods. During each period, 1GB data could be transferred. As Table shows, the migrating VMs, waiting VMs and physical hosts which be occupied for each period during migration process. In Table 3, at T1 period, the migration of virtual machine V5 is executed. However, VM V3 and V6 are waiting due to resource confliction, and VM V10 and V11 can migrate at T1 period without interference with each other. At the beginning of T3 period, VM V5 finishes the migration. The next VM V3 could not start migration because of the destination host(H1) of V3 is busy. Thus, the VM V6 starts migration at T3 period. The VM V3 finishes migration at end of T5 period. The total time of the parallel migration are 5 periods. Compared with the 13 periods of serial migration, the parallel virtual machine migration greatly reduces migration time(160%), and avoids resource conflicts in multiple virtual machine migration.

## 5.2 Verify the versatility of our algorithm

We choose several test cases to validate the algorithm's versatility. The detailed configuration of these test cases are shown in Table 4. 30 virtual machines are running on three physical hosts, each VM has 1GB memory. The VM-cluster inputs of five test cases are shown in Table 5.

<table><caption>Table 4. The distribution state of virtual machines</caption><thead><tr><th>VM/Host</th><th>Host1</th><th>Host2</th><th>Host3</th></tr></thead><tbody><tr><td>VM ID</td><td>V1~V10</td><td>V11~V20</td><td>V21~V30</td></tr></tbody></table>

<table><caption>Table 5. Five test cases</caption><thead><tr><th>ID/ VM-cluster</th><th>C1</th><th>C2</th><th>C3</th></tr></thead><tbody><tr><td>Case 1</td><td>1,11,12,13,14,15,16,1<br>7,18,19</td><td>2,3,4,5,6,7,8,9,10,20,30</td><td>21,22,23,24,25,26,27,28,29</td></tr><tr><td>Case 2</td><td>1,2,3,5,11,12,14,17,2<br>1,24,25</td><td>4,13,15,16,18,19,20,22,23,26,28</td><td>6,7,8,9,10,27,29,30</td></tr><tr><td>Case 3</td><td>1,2,3,5,24,25</td><td>4,13,15,16,18,19,26,28,11,12,14,17,21</td><td>6,7,8,9,10,27,29,30,20,22,23</td></tr><tr><td>Case 4</td><td>1,14,17,21,24,25,16,1<br>8,19,20</td><td>4,13,15,22,23,26,28,7,8,9</td><td>6,10,27,29,30,2,3,5,11,12</td></tr><tr><td>Case 5</td><td>1,12,14,17,21,24,19,2<br>0,22,9,10,27,25</td><td>4,13,15,2,3,5,11,16,18,23,26,28</td><td>6,7,8,29,30</td></tr></tbody></table>
<figure><img src="image_6.png" /><figcaption>Fig. 4. Migration time of five time cases</figcaption></figure>

The results of migration time for each test case are shown in Figure 9. We can see that, compared with default migration strategy, the average VM migration times of our algorithm is lower. The degree of optimization is different for each test case depending on the initial mapping state. This experiment shows that in most cases, our algorithm can optimize the process of multiple virtual machine migration.

# 6 CONCLUSION AND FUTURE WORK

This paper presents a schedule method for multiple virtual machine migration. The contributions of this paper include: (1) We analyze and formalize the problem of multiple virtual machine migration; (2) We propose a schedule algorithm for multiple virtual machine migration. The algorithm contains two parts. The first is finding the minimum cost VM migration path from all mapping of virtual machine to physical hosts, and the second is an algorithm generating the optimization virtual machine migration sequence, and accelerating multiple virtual machine migration process based on parallelize techniques; (3) We use some experiments to verify the effectiveness and versatility of the algorithm.

In this paper, the algorithm proposed has high complexity, and its performance is not good while dealing with large-scale multi-virtual machine migration case. Therefore, we need to improve the scalability of our method.

**Acknowledgments:** This work is supported by the National Natural Science Foundation of China(61232009); the State Key Laboratory of Software Development Environment (SKLSDE-2012ZX-07); the Doctoral Fund of Ministry of Education of China (20101102110018); the Hi-Tech Research and Development Program (863) of China (2011AA01A205); the Beijing Natural Science Foundation(4122042); Shanghai Science and Technology Innovation Action Plan(11511500400)
References

1. Armbrust, M., et al., A view of cloud computing. Communications of the ACM, 2010. 53(4): p. 50-58.

2. Zhang, Q., L. Cheng, and R. Boutaba, Cloud computing: state-of-the-art and research challenges. Journal of Internet Services and Applications, 2010. 1(1): p. 7-18.

3. Rosenblum, M. and T. Garfinkel, Virtual machine monitors: Current technology and future trends. Computer, 2005. 38(5): p. 39-47.

4. Amazon Elastic Compute Cloud. http://aws.amazon.com/en/ec2/. (Accessed 2013.5)

5. vCloud. http://en.wikipedia.org/wiki/VCloud. (Accessed 2013.5)

6. Ren, X., R. Lin, and H. Zou, A dynamic load balancing strategy for cloud computing platform based on exponential smoothing forecast. International Conference on Cloud Computing and Intelligence Systems, 2011

7. Srikantaiah, S., A. Kansal, and F. Zhao. Energy aware consolidation for cloud computing. USENIX conference on Power aware computing and systems. 2008

8. VMware. Resource management with VMware DRS. VMware Whitepaper, 2006.

9. Song, Y., et al., A service-oriented priority-based resource scheduling scheme for virtualized utility computing. High Performance Computing, 2008. p. 220-231.

10. Zhang, Z., et al. A VM-based Resource Management Method Using Statistics. International Conference on Parallel and Distributed Systems, 2012

11. Bobroff, N., A. Kochut, and K. Beaty. Dynamic placement of virtual machines for managing sla violations. International Symposium on Integrated Network Management, 2007

12. Verma, A., P. Ahuja, and A. Neogi, pMapper: power and migration cost aware application placement in virtualized systems. Middleware 2008. p. 243-264.

13. Lin, J.W. and C.H. Chen. Interference-aware virtual machine placement in cloud computing systems. International Conference on Computer & Information Science 2012.

14. Campegiani, P. and F.L. Presti. A general model for virtual machines resources allocation in multi-tier distributed systems. International Conference on Autonomic and Autonomous Systems, 2009.

15. Gao, Y., et al., A multi-objective ant colony system algorithm for virtual machine placement in cloud computing. Journal of Computer and System Sciences, 2013.

16. Khanna, G., et al. Application performance management in virtualized server environments. Network Operations and Management Symposium, 2006.

17. Prevost, J.J., et al. Load prediction algorithm for multi-tenant virtual machine environments. World Automation Congress (WAC), 2012

18. Wang, X. and Y. Wang, Coordinating power control and performance management for virtualized server clusters. Transactions on Parallel and Distributed Systems, 2011. 22(2): p. 245-259.

19. Liao, X., H. Jin, and H. Liu, Towards a green cluster through dynamic remapping of virtual machines. Future Generation computer systems, 2012. 28(2): p. 469-477.

20. Liu, H., et al. Performance and energy modeling for live migration of virtual machines. International symposium on High performance distributed computing. 2011

21. Jin, H., et al. Live virtual machine migration with adaptive, memory compression. International Conference on Cluster Computing and Workshops, 2009

22. Xenserver. http://www.citrix.com/products/xenserver/overview.html. (Accessed 2013.5)