Xing Li

Qinming He
email: yintingeye@zju.edu.cn

Jianhai Chen

Kejiang Ye
email: yekejiang@zju.edu.cn

Ting Yin

Informed Live Migration Strategies of Virtual Machines for Cluster Load Balancing ⋆

Keywords: Virtualization, Live Migration, Workload Aware

Virtualization technology brings great conveniences to cluster and data center management. By using this technique, we can reconstruct a new computing environment quickly and easily. Compared to the traditional cluster environment, load balancing in a virtualized environment needs to address several new problems. This paper focuses on live migration strategies for load balancing in the virtualized cluster. We first divide the whole balancing process into three sub-problems, namely, the selection of the VM being migrated to, the choice of destination host and the determination of the migration execution sequence. Then we perform a series of experiments to investigate the particular features of the live migration of virtual machines in the balancing scenario. Based on our experiment results, we propose an informed live migration strategy which includes affinity-aware decision making and workload-aware migration to improve the efficiency of configuration of the virtualized cluster.

Introduction

Virtualization has recently emerged as an essential technology to the modern computing cluster and data center mainly due to its capabilities of virtual machine isolation, consolidation and migration [START_REF] Barham | Xen and the art of virtualization[END_REF]. The enabled hardware independence and rapid deployment using QCOW technology [START_REF] Qcow | [END_REF], permit one to construct a computing cluster within minutes.

Live migration is an extremely powerful tool for cluster management. It facilitates typical functions such as: load balancing, online maintenance, power saving, and high availability. For example, if a physical machine needs to be removed from a cluster for maintenance, we can simply migrate the virtual machine (VM) from the original host to another available host. Similarly, VMs can be reallocated across the physical servers in the cluster to relieve the workload on congested servers. In these situations the combination of virtualization and migration significantly improves the manageability of clusters.

At present, most of the virtualization platforms use memory Pre-Copy [START_REF] Clark | Live migration of virtual machines[END_REF] as the default algorithm to implement live migration due its ability to decrease the VM downtime to the order of milliseconds which is imperceptible to users. However, the Pre-Copy algorithm will cause workload performance degradation during live migration. It will also produce an inevitable overhead.

In fact, not only the memory transferring mechanism affects the cost of live migration, the choice of the actual migration strategy also impacts greatly on the performance of a migrating VM. Especially, in the scenario of performing load balancing for virtualized cluster, there are often multiple VMs that must be migrated to multiple destination hosts . In such case, the migration strategy of these multiple VMs will be even more important.

In this paper, we study the behaviors of various live migration strategies. We found that some particular features will impact the performance of load balancing. These features include the affinity relationship between migrating VMs and the actual sequence of migration. We then propose an informed live migration strategy that incorporates affinity-aware decision and workload-aware migration. The strategy makes migration decisions according to the VMs' characteristics and the migration sequence. It will improve the reconstruction efficiency of virtualized cluster.

The rest of this paper is organized as follows. Section 2 introduces the background of load balancing in the virtualized cluster and the motivation to study the effective balancing approach. In Section 3, we present our experiments and results, followed by the proposed strategies. Section 4 describes related work and Section 5 presents our conclusions and future work.

BACKGROUND&MOTIVATION

In this section, we briefly introduce the virtual machine technology and the motivation to investigate the live migration strategies.

Live-migration technology. At present, many commercial corporations have their own live migration technology available within their software products. For example, Microsoft has Hyper-V [START_REF]Hyper-V[END_REF] live migration, Cirtix integrates XenMotion [START_REF]XenServer XenMotion[END_REF] with their xenserver, and VMware uses VMotion [START_REF]VMware VMotion[END_REF]. Among a number of live migration algorithms, Memory Pre-Copy is the most prevailing one. The main advantage of the Pre-Copy algorithm is that it produces the minimum downtime. The actual time taken could be as low as 60ms [START_REF] Clark | Live migration of virtual machines[END_REF], so users will not detect the event that the services have been interrupted and the virtual machine is migrating from one host to another. This algorithm copies and sends memory pages from the current host to the destination host iteratively, while ensures that services on the migrating VM are still available. Until the writable working set becomes small enough, will the virtual machine monitor (VMM) suspend the VM and then send the last remaining dirty pages and the CPU state. The network bandwidth being occupied may affect other VMs when network connection is involved in migration.

The performance metrics of live migration. To measure the performance and efficiency of live migration, four typical metrics are used: migration time, downtime, data transferred and workload performance degradation [START_REF] Huang | A Benchmark for Live Migration of Virtual Machine[END_REF]. The migration time measures the time elapsed from the start of a migration process to the end of it. The downtime measures the time period when the migrating VM is stopped to transfer the remaining data. The VM is not responsible during the downtime . The data transferred reflects the total size of virtual machine memory data that has been sent during the migration. The workload performance degradation reflects the performance lose caused by live migration compared to the no-migration case.

Three problems of reconstructing the virtualized cluster. In order to balance the load of a virtualized cluster, three important problems must be addressed in making a wise choice on a good live migration strategy. Firstly, how to select the candidate virtual machine from the overloaded host to migrate out? The different VM selections will result in different outcomes. Criterions of minimum migration costs and earliest completion of reallocation procedure are both very necessary. Secondly, how to choose the destination host for each candidate migrating virtual machines? In other words, how to find the mapping relationship between migrating VMs and those idle hosts. Lastly, if there are many VMs to be migrated at one time, what would be the migration execution sequence of these candidate VMs, that will produce less marginal impact the other VMs. It can be expected that the migration sequence plays a significant role in the overall performance.

EXPERIMENTAL EVALUATION&ANALYSIS

In this section, we describe our detailed migration experiments for different scenarios, and then analyze the measurement results. These results will reveal key characteristics of many migration algorithms when used for load balancing purpose.

The Migrating VMs Selection Problem

In order to release the overloaded host fast, we need to choose the correct candidate VMs for migration to assure the minimum migration costs and make the reallocation procedure finished as quickly as possible. Table 1 displays the migration time, down time and overheads of selected typical workloads.

As we can see, the migration of different workloads will use different lengths of time and cause different overhead. Workloads such as OLTP and SPEC-jbb, which have many memory accesses, need long periods of time to migrate and generate more overhead. The network-intensive workload like webbench will prolong the migration procedure, and cause extra overheads. The pure CPU-intensive workload like SPEC-CPU will have the least impact in all three metrics. In the next experiment, we run a scalable memory dirty workload in the testing VM. We change the VM memory size during the process. The dirty workload was implemented by updating an array continuously and randomly. This was written using the C programming language so that the memory would have a consistently high dirtying rate and would be hard to migrate. The Figure 3 shows that the migration time of a virtual machine is influenced by both the memory size and the memory dirty size. This is because that Xen uses a pre-copy algorithm to transfer the memory data to the destination host iteratively in its live migration implementation.

Figure 4 illustrates that the migration downtime is proportional to the memory dirty size and is unrelated to the memory size. When Xen detects that some parts of the memory are getting dirty frequently, it considers it not worthy to send it repeatedly. In this case, Xen will stop this virtual machine and turn to the Stop-and-Copy phase. Xen then transfers the remainder of the dirty data during the Stop-and-Copy phase. However, this approach leads to the case that the downtime is proportional to size of the dirty memory of the migrating VM.

When there is a need to select several virtual machines to migrate out, both the procedure completion time and migration overhead have to be taken into account. As the above experiments illustrated, we can choose some virtual machines which are running CPU workloads to migrate, and consider additionally criteria such as the small memory size and small dirty size. The dirty logging switch tool we have mentioned in previous section are especially useful in monitoring the dirty rate and dirty size in each domains to support the migration strategies.

The Destination Host Choose Problem

Deciding which host be the suitable destination will greatly impact the migration perfformance. We have designed a group of experiments, the first one runs the SPEC-CPU workload in two virtual machines which are placed on different physical hosts. Then one of the virtual machines will be migrated from its original host to the other, making the two virtual machines running together. To get clear experiment results, one additional condition imposed was that the two virtual machines are pined to a single physical CPU, and share the same L2 cache.

Table 3 shows that, there are visible affinity relationship between some workloads. Theworkload pairs like libquantum and gamess can work well together, but not the other workload pairs like two bwaves not. This is because that the latter two workload would mutual restrain each other and need very long time to complete. Table 3 and Figure 3(a) show that choosing different migration destination hosts will dramatically impact the virtual machine performance. The difference may even reach 37.5% in some cases. The reasons for these differences are that these CPU-bounded workload have different cache accessing types: some workloads like bwaves and libquantum will pollute cache block, while some other workloads like bzip2 and gmaess will not.

Figure 3(b) shows that when placing the two virtual machines, which have a large number of communications, together on the same host, they will get better performance.

We also designed experiments to deploy a virtual cluster of e 16 virtual machines in different number of physical hosts, from one physical host, to 2 hosts each has 8 VMs, and to 4 hosts each has 4 VMs. The comparisons of the three cases are shown in Figure 3(c). In general, the three configurations show similar HPL performance. But the communication performance decreases a lot when deploying these virtual machines to more different hosts. When there are 4 physical hosts, the MPIFFT shows the worst performance. It means that the communication performance of virtual machines is more effective when deployed on the same physical host.

On the other hand, the Xen memory sharing mechanism and grant table could be used to communicate between domains. By using this mechanism, the domain could lease one of its memory block to another domain temporarily. This method will be more effective than communication through a physical network. However theis memory sharing mechanism is only implemented in the virtual machine monitor Xen. illustrates that, when two disk-I/O-bounded virtual machines working together, there will be a significant degradation in performance. In contact, a disk-I/O-bounded virtual machine and a CPU-intensive one could work well to-gether. It is easy to see that consolidating multiple disk-I/O-bounded workloads has to consider the nonsharable usage of the physical disk I/O operations which restricted the capacity. In summary, we have the following observations when determining a suitable server to host a migrating VM: (1) it would be better to choose the kinds of virtual machines as neighbors, the kinds that have well affinity with the migrating one; (2) it would be better to make the virtual machines that communicate with each other to work on the same host; (3) it would be better to avoid migrating two workloads that have the same nonsharable type of resources together.

The Migration Sequence

When migration involves multiple VMs, the migration sequence becomes a critical issue because it will dramatically affect the whole reconfiguration procedure of the cluster. Our next experiments will show the influence. In this set of experiments, we migrate 8 virtual machines one after the other. One of the 8 virtual machines has a workload running on it, others are idle. By altering the location of the workload VM in the migration sequence, we can observe clearly that the different migration order of the workload virtual machine will affect the other virtual machine that are co-hosted with it. Firstly, we place a memory-dirty workload on the first virtual machine, named VM1, in the migration sequence, and migrate these 8 virtual machines one by one from VM1 to VM8. Then, we place the dirty workload on the second virtual machine VM2 and migrate all the virtual machines in succession. Repeatedly, we place the memory-dirty workload on the VM3, VM4 until VM8. Figure 5(a) illustrates memory dirty workload virtual machine will significantly affect the migration time of these co-hosting virtual machines migrate before it, and these virtual machines which migrate behind the dirty workload VM don't suffer impact. As Figure 5(b)(c) show, the memory dirty workload will not affect the performance of the migration downtime and migration data transferred of the other VMs. It is clear that the memory dirty workload causes large page fault and slows down the other virtual machines' memory copy procedure. The conclusion is simple, We must ensure that the memory dirty workload always have the higest priority to migrate. However, not all the cases own this phenomenon as we can see a complete different situation in the next experiment.

This time we changed the memory dirty program into a NET I/O workload.Thus the workload virtual machine continuously receives the data sent from remote server. In the remainder, we just repeat the process as described in previous experiment. shows NET I/O(receive) virtual machine will greatly impact the migration time of the other virtual machines migrated after it, this is because when the net I/O receiver workload migrates to the destination host, it reduces the destination host's ability to receive the memory data being transferred, and also slows down the migration time of other followed virtual machines. However, this is not the same as previous case. It seems that we need to migrate these virtual machine with NET I/O(receive) workload as late as possible. Figure 6(b) shows that NET I/O will prolong the migration downtime, because when it comes to stop-copy step, it will take a longer time to send the remaining memory data.

In this case, we need a compromise approach to balance the migration time and downtime. For these virtual machines tend to have short migration time. We choose to migrate it before the NET I/O (recv) workload virtual machine. On the other hand, for these virtual machine tend to have short downtime, we choose to migrate it after the workload virtual machine migration.

Then, we change the workload into web server application and repeat the experiment. As Figure 7 shows, the web server workload VM will dramatically impact both of the migration time and migration downtime of its co-hosting virtual machines. Obviously, toese virtual machines migrated before the workload VM will have a long migration time and downtime. This is because the web server load sends data through the network continuous,which occupies large bandwidth, and will slow down both the migration time and downtime. It is easy to reach the conclusion: for these web server workloads, we need to migrate them out as soon as possible.

Our experiments also show that the disk I/O load and CPU workload will not affect the neighboring virtual machine migration performance.

At last, we can assemble these experiments described above together and take an overview. With the workload virtual machine migrating backwards in the migration order, the average migration time of whole migrating VMs sequence will have different features. For the sequence having memory dirty workload, the workload virtual machine gets migrated later the average migration time gets larger?"For the sequence which having NET I/O (recieve) workload virtual machine, the average migration time will be smaller but will have a longer average downtime; For these sequence having web server workload, the later migration will cause both larger migration time and down time. For these having disk I/O or CPU workload sequences, the migration order causes no effect.

Informed Live Migration Strategies

By analyzing the above experimental results, we have found interesting features of the live migration in the scene of virtual cluster load balancing: (1) Different kinds of workloads result in a diversity in the migration time and different performance overheads; (2) Besides the total memory size, the memory dirty rate and dirty area size will also affect the migration time and downtime; (3) There are certain affinity relationship between some workloads, e.g., some kinds of workload consolidation will cause large performance degradation, while others will not; (4) Migrating two virtual machines which communicate through network on the same physical host will obtain performance improvement; [START_REF]VMware VMotion[END_REF] The migration sequence of a group of VMs with different kinds of workloads will greatly affect the whole reconfiguration efficiency.

Based on these specific features, we propose affinity-aware decision making and workload-aware migration to improve the efficiency of live migration.

The strategy contains a set of rules: (1) choosing proper virtual machines to achieve shorter migration procedure time and less migration overheads; (2) taking the virtual machine affinity into consideration to decide suitable destination host; (3) Understanding the virtual machine workload features and determining an optimal migration sequence. In our implementation of the strategy, we tend to choose the VMs that have less total memory and smaller memory dirty size as candidate migrating VMs./ The types of the workloads are also considered (see Table 4.2), the CPU workload and Disk I/O are currently preferred in our testing. When choosing the migration destination host, it's important to avoid consolidating the same type of virtual machine with nonsharable ; but the VMs having network communications should be set to work together. When determining the migration sequence of a group of VMs, the VMs which have dirty memory or web server workload should be considered first. For the VM which have Network I/Os (receiving) and web application running on it, for example, online video, webgame, etc, we need to migrate it at the end of the migration process. This is because it will impact the destination server's bandwidth, slow down the pre-copy operation and increase the downtime of the subsequent migration. So, the VMs which have NET I/O(receive) workload need to be migrated at last. For the VMs which have CPU or disk I/O workload, we just need to ensure that the smaller VM is migrated early using the principle of SJF (Shortest Job First). This will lead to the least average completion time of each migrating VM.

Based on the aforementioned discoveries and mechanisms, we are in a position to implement the features of affinity-aware decision making and workloadaware migration into the balancing system, which establishes our informed live migration strategies for live migration.

RELATED WORK

Many efforts have been made to improve the efficiency of live migration. Some research has been done into improving the efficiency of the live migration mechanism. H.Jin et al. [START_REF] Jin | Live virtual machine migration with adaptive, memory compression[END_REF] presents an implementation of a novel memory-compression based VM migration approach to improve the migration efficiency ; Liu et al. [START_REF] Liu | Live migration of virtual machine based on full system trace and replay[END_REF] described a design and implementation of a novel approach that Adopts checkpointing-recovery and trace-replay technology to Provide fast, transparent VM migration. Luo et al. [START_REF] Luo | Live and incremental whole-system migration of virtual machines using block-bitmap[END_REF] describe a whole-system live migration scheme, which transfers the whole system run-time state, including CPU state, memory data, and local disk storage, of the virtual machine (VM). There are also many efforts have been made to the dynamic placing and consolidation of the virtualized resources. Hermenier et al. [START_REF] Hermenier | Entropy: a consolidation manager for clusters[END_REF] provide substantial improvement over static server consolidation in reducing the amount of required capacity and the rate of service level agreement violations. Choi et al. [START_REF] Choi | Autonomous learning for efficient resource utilization of dynamic VM migration[END_REF] describe a learning framework that autonomously finds and adjusts thresholds at runtime. Verma et al. [START_REF] Verma | pMapper : Power and Migration Cost Aware Application Placement in Virtualized Systems?[END_REF] presented the pMapper architecture and placement algorithms to minimize the power used to a fixed performance requirement. Hermenier et al. [START_REF] Hermenier | Entropy: a consolidation manager for clusters[END_REF] propose the Entropy resource manager for homogeneous clusters, which performs dynamic consolidation and takes migration overhead into account. Differing from the above work, This paper studied the live migration strategies in the scenario of load balancing in a virtualized cluster.

CONCLUSIONS AND FUTURE WORK

In this paper, we study the live migration features in the load balancing scenario of a virtualized cluster, our experiments showed several interesting observations that help to establish rules for live migration to achieve the goal of load balancing. Our proposed informed live migration strategy includes affinity-aware decision making and workload-aware migration. It improves the efficiency of reconfiguration a virtualized cluster.

Our future work will include more comprehensive performance metrics and use workload automatic monitoring to support the informed live migration strategy. Additionally, we will use mathematical modeling methods to evaluate and integrate the multiplicity of factors that influence live migration.

Fig. 1 .

 1 Fig. 1. Factors of Migration time&downtime

Fig. 2 .

 2 Fig. 2. (a)The affinity of SPEC CPU workload.(b)Comparison of webbench on 2 isolated-hosts VMs with co-host.(c)Comparison of HPCC VMs isolated and co-host.

Fig. 3 .

 3 Fig. 3. Two I/O type VMs working together

Figure 4

 4 Figure4illustrates that, when two disk-I/O-bounded virtual machines working together, there will be a significant degradation in performance. In contact, a disk-I/O-bounded virtual machine and a CPU-intensive one could work well to-

Fig. 4 .

 4 Fig. 4. (a)Memory dirty workload VMs will affect these VMs migrated before it.(b)Data transferred of each migrated VMs.(c)Downtime of each migrated VMs

Fig. 5 .

 5 Fig. 5. The impact of NET I/O(receive) VMs on (a)migration time or (b)migration downtime of the other VMs migrated before

Fig. 6 .

 6 Fig. 6. WebServer VMs will impact the migration (a)time,(b)downtime of some other VMs migrated before it

Table 1 .

 1 The typical workload behavior in migration

	workloads	Migration-time(s) Downtime(ms) Overhead(%)
	IOZONE	214.51	1028	7.93%
	WEBBENCH 47.67	113	29.03%
	OLTP	69.32	998	33.26%
	SPEC-CPU 26.69	88	3.31%
	SPEC-jbb	31.25	232	8.29%

Table 2 .

 2 SPEC-CPU workload affinity, the values in the table display the running time of each workloads

	Destination	Workloads be migrating
		milc bwaves bzip2 libquantum Games
	mig-to-milc	1100 1280 824	1530	1270
	mig-to-bwaves	961 1500 633	1470	1270
	mig-to-bzip2	824 1160 628	1190	1240
	mig-to-libquantum 1070 1340 886	1760	1290
	mig-to-gamess	843 1180 588	1100	1240
	max-difference 25.1% 22.7% 33.6%	37.5%	3.9%

⋆ This work is funded by the National 973 Basic Research Program of China under grant NO.2007CB310900 and National Natural Science Foundation of China under grant NO. 60970125.


Lin Zhongwei

Yao Yiping

Accelerating the Requirement Space Exploration through Coarse-Grained Parallel Execution

Keywords: requirement space exploration, coarse-Grained parallel execution, task pool model

The design and analysis of complex systems need to determine suitable configurations for meeting requirement constraints. The Monotonic Indices Space (MIS) method is a useful approach for monotonic requirement space exploration. However, the method is highly time and memory-Consuming. Aiming to the problem of low efficiency of sequential MIS method, this paper introduces a coarse-grained parallel execution mechanism to the MIS method for accelerating the process of requirement space exploration. The task pool model is used to receive and deploy hyperboxes for work balancing. To validate our approach, the speedup is estimated by a mathematical analysis and then an experiment is conducted in a PC cluster environment. The results show that high speedup and efficiency is achieved through our approach.

Introduction

A lot of practical problems, such as getting the system capability requirement indices [1, 2, 3, and 4], getting the effective light intensity space [START_REF] Hu Jian Wen | Analysis and design of search for weapon system indices[END_REF], and getting the effective radar coverage [START_REF] Hu Jian Wen | Analysis and design of search for weapon system indices[END_REF], can be transformed into the problem of requirement space exploration. These problems have a common feature: the requirement measure of these systems is related with several factors (indices), and their combination forms a huge parameter space in which we should explore to make the measurement satisfying requirement constraints. For example, the response time (requirement measure) of a web server is affected by several factors, including the CPU's frequency, memory, network, operating system, and current load, so we are anxious about what configurations of these factors which can satisfy the demand on the response time.

The problem of requirement space exploration can be defined formally as follows.

Definition 1. Requirement space: suppose R n is n-Dimensional Euclidean space, P is non-Empty subset of R n , then P ⊂R n and P = ∅, there exists a function f defined in P , f : P → R, the requirement space S satisfies: S ⊂ P and ∀p ∈ S, f (p) ≥ α, where α is the threshold.

Due to the complexity and uncertainty of some practical problems, it is very difficult or even impossible to get the analytic form of the function f , thus we need to determine the require space in other ways, rather than analytic way.

A few classic methods have been used to solve the requirement space determining problem. The system effectiveness analysis method [START_REF] Bouthonnier | System Effectiveness Analysis of C3 Systems[END_REF] compares the system capabilities and the mission requirements in a common attribute space, while attaining the system mission requirements locus is difficult. ADC model [START_REF]Prediction Measurement[END_REF] is a very strict mathematical method, but the calculation will increase exponentially with the increase of system state dimensions. In multi-Attribute analysis method [START_REF] Hwang | Multiple Attribute Decision Making[END_REF], the design of the weights of each attribute should be very skillful, but very difficult. The Monotonic Indices Space (MIS) method [START_REF] Jian Wen Hu | Monotonic Indices Space Method and Its Application in the Capability Indices effectiveness analysis of a Notional Anti-Stealth Information System[END_REF] introduced by Hu Jianwen takes the typical complex system characteristics into account, and turns out an efficacious way.

Coarse-Grained Multicomputer (CGM) model is a well-known parallel method for multi-Replication simulations. Frank Dehne presented the method [START_REF] Frank Dehne | SCALABLE PARALLEL COMPUTATIONAL GEOMETRY FOR COARSE GRAINED MUL-TICOMPUTERS[END_REF], described and proofed the time cost of the method, and employed it to solve Hausdorff Voronoi Diagrams problem [START_REF] Frank Dehne | A Coarse Grained Parallel Algorithm for Hausdorff Voronoi Diagrams[END_REF]. CGM has been widely used, and turned out effective. Thierry Garcia and David Sem' employed CGM to solve the Longest Repeated Suffix Ending problem [START_REF] Garcia | A Coarse-Grained Multicomputer algorithm for the Longest Repeated Suffix Ending at Each Point in a Word[END_REF], Albert Chan introduced CGM to the next element search problem [START_REF] Chan | Coarse Grained Parallel Geometric Search[END_REF]. According to their results, CGM is highly effective.

The paper is organized as follows. In section 2, we introduce the MIS method in detail. The coarse-Grained approach is described in section 3. We analyze the speedup of our approach formally, and then present some experimental results in section 4 and 5. Future work is arranged in section 6.

Monotonic Indices Space (MIS) Method

The main idea of the MIS method is divide-and-conquer strategy: the whole parameter space is partitioned into a lot of hierarchical sub-spaces which are isomorphic with their parental space. Any sub-space is called a hyperbox which is an important concept of MIS. A hyperbox can be imaged as a hypercube, and it is a description of parameter space.

MIS Method

The MIS method is mainly applied in monotonic vector space. In monotonic vector space P , f should be n-Dimensional monotonic function, that means

∀p(x 1 , x 2 , • • • , u, • • • , x n ), q(x 1 , x 2 , • • • , v, • • • , x n ) ∈ P , if u ≥ v, then f (p) ≥ f (q) or f (p) ≤ f (q). For example: P = [0, 2] × [0, 2] ⊂ R 2 , f (x, y) = x 2 + y 2 ,
the requirement space S = {p : p ∈ P, f (p) ≤ 4}. In this case, the initial hyperbox is P , and the partition point is p * ( √ 2, √ 2) which is on the diagonal of the current hyperbox, and then it produces 4 sub-hyperboxes, as illustrated by Fig. 1.

The main operation of the MIS method is resolving hyperbox, and the resolving includes two procedures: search and partition: 1. Search: search the partition point along the diagonal of the hyperbox. As shown in Fig. 1, the current hyperbox is determined by point p 1 and p 2 , let

a 0 = p 1 , b 0 = p 2 , c 0 = (p 1 + p 2 )/2, if f (c i ) ≤ α, then a i+1 = c i , b i+1 = b i , c i+1 = (a i+1 + b i+1 )/2, if f (c i ≥ α), then a i+1 = a i , b i+1 = c i , c i+1 = (a i+1 + b i+1 )/2
, repeat this operation. Since there must be at least one partition point on the diagonal [START_REF] Jian Wen Hu | Monotonic Indices Space Method and Its Application in the Capability Indices effectiveness analysis of a Notional Anti-Stealth Information System[END_REF], thus the point c i can be considered as the partition point when a i -b i ≤ θl 0 , where θ is a parameter called cut rate, and l 0 stands for the length of the diagonal of the root hyperbox. 2. Partition: each component of the partition point will divide the same dimension of the current hyperbox into two segments, and the combination of all the segments will produce 2 n sub-hyperboxes, see Fig. 1, and the undetermined 2 n -2 sub-hyperboxes should be inspected again. In the partition procedure, sub-hyperboxes that are too little to affect the requirement space (or affect a little bit) will be abandoned directly. Suppose V is the volume of some sub-hyperbox, we can abandon this subhyperbox when V ≤ γV 0 , where γ is a parameter called stop rate, and V 0 stands for the volume of the root hyperbox.

During the above two procedures, we can get a hyperbox tree, see Fig. 2: After the above two procedures , we can get a requirement-Satisfied hyperbox s i ( i stands for the identifier of the hyperbox on the hyperbox tree) determined Fig. 2. hyperbox tree. Resolving the current hyperbox will produce 2 n -2 undetermined sub-hyperboxes, and the current hyperbox is the parent of these sub-hyperboxes, then all the hyperboxes form a tree structure.

by p 1 and p * , see Fig. 1, obviously s i ⊂ S, then the requirement space can be determined as follows:

S = ∞ ∪ i=0 s i (1)

Time and Memory Costs of the MIS Method

The MIS method is highly recursive, thus it is very suitable to implement it by recursive program. However the depth of the recursion is the key for precision. We can't get the precise requirement space with low depth. While deep depth will bring in a very large amount of calculation and memory need (as shown in Fig. 2, the hyperbox scale is O (2 n -2) k , and the memory need is O n(2 n -2) k , where n is the dimension of the requirement space, and k stands for the maximal depth of recursion.) which exceed a single computer's capability in a certain period of time. Additionally, extra cost brought by recursion to operating system makes the execution ineffective. Most practical problems are related with high-Dimensional model, they need much more calculation and memory, compared to low-Dimensional model. In some cases, the calculation and memory need are so large that it makes a single computer exhausted or even halted. Thus we come to the edge that we must process the calculation and satisfy the memory need in other way.

Above all, our task becomes accelerating the execution of the MIS method, promising a certain depth of recursion.

Coarse-Grained Approach

Reviewing the MIS method, we can find that the algorithm has immanent parallelism: the resolving of hyperboxes is all independent. Any hyperbox determined by the initial parameters can be resolved without communicating with other hyperboxes, thus the hyperboxes can be resolved concurrently.

A Coarse-Grained Multicomputer model: p processors solving a problem on n data items, each processor has O(n/p) O(1) local memory, and all the processors are connected via some arbitrary interconnection network [START_REF] Frank Dehne | SCALABLE PARALLEL COMPUTATIONAL GEOMETRY FOR COARSE GRAINED MUL-TICOMPUTERS[END_REF], can be represented as CGM (n, p). In the MIS method, each hyperbox is one data item, thus the key is to assign the hyperboxes to the processors, and keep load-Balanced for each processor.

In most cases, the requirement space is not evenly distributed in the parameter space, thus it is not suitable to partition the items (hyperboxes) according to their location in the parameter space. While it is very hard or impossible to predict the requirement space, thus we almost can't partition the items and assign them to the processors before the execution, and we have to do this work during resolving dynamically. New hyperboxes will come out during resolving their paternal hyperbox, and the hyperboxes can be stored into a container (usually called pool), and then a hyperbox will be taken out and assigned to each idle processer if there exists idle processers.

Parallelized Resolving in C/S Mode

There are two core operation of the MIS method: resolving hyperbox and maintaining the hyperbox tree. Generally speaking, resolving hyperbox is a kind of compute-intensive procedure which needs a large amount of calculation, while maintaining the hyperbox tree is a kind of communicate-intensive procedure which needs to communicate with others frequently. Therefore, the two operation should be implemented separately and execute on separate computers.

Basing on the analysis before, the computer which executes resolving hyperbox is called calculative node, and it is in charge of resolving hyperbox. The computer which executes maintaining hyperbox tree is called control node, and it is in charge of receiving and deploying hyperbox. Therefore the calculative nodes and the control node form a client-Server structure.

Resolving Hyperbox on Client

The MIS method will generate a lot of hyperboxes, and the faster the generated hyperboxes resolved the faster the experiment completes, thus we always assign a few calculative nodes in the system. A procedure called clientProcedure is running on each calculative node, and it will process the fundamental tasks of calculative node: resolving the hyperbox and interacting with the control node. The action of calculative node is driven by the commands from the control node, and the command can be packed into a message, such as a socket message, thus the messages can be classified and identified according to the command type. The main body of clientProcedure is to operate according to the message received from the control node. A procedure called resolveProcedure is in charge of searching the partition point and generating sub-hyperboxes and it will be called after the calculative node receiving a message telling a hyperbox from the control node. Two n-Dimensional points can determine a hyperbox uniquely, see Fig. 1, and they also determine the diagonal on which the partition point locates. Thus we can search the partition point along the diagonal of the hyperbox. The model is used to calculate the requirement measure, and it is always implemented as a program whose input is a single point. So the search can be divided into two iterative sub-courses: calculating the input point, and calling the model program. Once the partition point has been determined, 2 n -2 sub-hyperboxes will be produced and filtered. Any hyperbox can be determined by two n-Dimensional points, and the two points can be packed into a message, and then the message will be sent to the control node, telling a hyperbox. Sub-hyperbox is filtered according to its volume, and the one that is too little to affect the requirement space will be abandon directly. After the resolving completed, a message will be sent to the control node to tell that this calculative node has become idle.

Maintain the Hyperbox Tree on Server Maintaining the hyperbox tree is the main task of the control node, and it includes two fundamental operations: receiving the subhyperboxes generated by the calculative nodes and deploying hyperbox to them. A procedure called serverProcedure is running on the control node, and it will process the above two operations.

s e r v e r P r o c e d u r e : I n i t i a l i z e ; t h e u s e r c h o o s e an e x p e r i m e n t c o n f i g u r a t i o n f i l e ; d e p l o y t h e n e c e s s a r y f i l e s t o t h e c o n n e c t e d c l i e n t s ; s t a r t t h e e x p e r i m e n t ; L i s t e n message from t h e c o n n e c t e d c l i e n t s ;

switch ( message ) case f i n i s h : // means c l i e n t c o m p l e t e s r e s o l v i n g put t h e c l i e n t from which t h e message came i n t o i d l e c l i e n t s queue ; i f ( t h e hyperbox queue i s empty && a l l t h e c l i e n t s a r e i d l e ) c a l l r e s u l t P r o c e s s P r o c e d u r e ; e l s e c a l l d e p l o y P r o c e d u r e ; case hyperBox : r e c e i v e t h e hyperbox and put i t i n t o t h e hyperbox queue case r e s u l t F i l e : r e c e i v e t h e r e s u l t f i l e

Task Pool Work Balancing

Task pool is one of implementations of work stealing [START_REF] James Dinan | Scalable Work Stealing[END_REF], and it can be used for load balancing. In this paper, the hyperboxes generated by the calculative nodes will be put into a hyperbox queue which is assigned on the control node and plays the task pool. Once a message telling a hyperbox has been received by the control node, the serverProcedure will unpack the message to get the two n-Dimensional points, and then construct a hyperbox according to the two points. The constructed hyperbox will be put into the hyperbox queue.

The control node maintains a list to record the information of the calculative nodes. In the beginning, the whole parameter space will be constructed as the first hyperbox, and then the hyperbox will be put into the hyperbox queue. After starting the execution , the front hyperbox of the hyperbox queue will be taken out and assigned to the front idle calculative node of the calculative nodes list. To use the calculative nodes fully, we hope that the nodes are keeping resolving hyperboxes if there are unresolved hyperboxes in the hyperbox queue. Once the control node finds an idle calculative node, a hyperbox will be taken out and assigned to the idle node. To decrease the overhead of preparing the message of assigning a task to the idle calculative node, the server always gets the front hyperbox of the hyperbox queue out(time consuming O(1)), and then packs it into the assigning message. Therefore, the calculative nodes are keeping resolving hyperbox controlled by the calculative node. The terminal condition of the whole execution is that the hyperbox queue on the control node is empty and all the calculative nodes are idle.

Speedup Analysis

For the sequential MIS method, the total execution time is the summary of the time of resolving each sub-hyperbox, and suppose T s is the period of time which the sequential MIS method costs, then

T s = N i=1 t i ≥ N i=1 t min ( 2
)
where N is the total number of hyperboxes in the experiment, t i is the period of time which resolving ith hyperbox costs, and t min = min {t i }. T p is the period of time which the parallel algorithm costs, then

T p = N/m j=1 t j ≤ N/m j=1 t max ( 3
)
where m is the number of calculative nodes, and t max = max {t j }, then the speedup is the ratio

speedup = T s T p ≥ t min t max • N N/m ≈ t min t max • m (N m) (4)
In the sequential MIS method, the period of resolving a hyperbox is mainly composed of two parts: time of model calls and the extra cost of the system (including the OS and the program itself). While in the parallel algorithm, the period is mainly composed of five parts: overhead of the server preparing message, the delay of transferring message from the server to the clients (determined by the bandwidth of the network), overhead of the client receiving message, the overhead of the client preparing message (above four are the communication cost), and time of model calls. The communication cost can be represented as following

t com = o s + L + o c + (2 n -2)o c (5)
then the period can be represented as

t j = t com + t call (6)
Suppose the period of single execution of the model f is const T, then the period of model calls t call is proportional to the number of times of the model calls. Reviewing the search procedure of the MIS method , the repeat will have the length of the distance between a i and b i to halve again and again , then the terminal condition of binary search can be described as following

l k /2 r l 0 = θ (7)
where k is the depth of the current hyperbox on the hyperbox tree, l k is the length of the diagonal of the current hyperbox, r is the number of times of the model calls, l 0 is the length of the diagonal of the root hyperbox, and θ is the cut rate. Statistically,

l k = 2 -k l 0 is correct, then r = -log 2 θ -k (8)
In the partition procedure, a sub-hyperbox will be abandoned directly, if its volume is too little to affect the requirement space of the problem. Statistically,

V k = 2 -nk V 0 (n is the dimension of the parameter space)is correct, then 2 -nk V 0 V 0 = γ (9) k = log 2 γ n (10)
formula ( 10) is also the maximal depth of recursion. Let

h 1 (θ, γ, n) = t min t max = (-log 2 θ -k 0 )T (-log 2 θ -k max )T + max {t com } k0=0 = T log 2 θ (log 2 θ + log 2 γ n )T -max {t com } (11)
For a certain experiment, the dimension of the requirement space is stationary, thus the variable n in formula [START_REF] Chan | Coarse Grained Parallel Geometric Search[END_REF] can be considered as const, and then

h 1 (θ, γ, n) becomes h 2 (θ, γ) = log 2 θ (log 2 θ + log 2 γ n ) -max {tcom} T ( 12
)
speedup ≥ h 2 (θ, γ) • m (13)

Experimental Results

To test our approach, we take the system mentioned by Hu Jianwen in [START_REF] Jian Wen Hu | Monotonic Indices Space Method and Its Application in the Capability Indices effectiveness analysis of a Notional Anti-Stealth Information System[END_REF] as an example. It is an air defense information system consisting of three entities: long-Distance warning radar, command and control center, and enemy's aircraft. The scenario is following: one of enemy's aircraft is flying direct to target T which is protected by us, and once the long-Distance warning system discovers the aircraft, it sends the information of the aircraft to the command and control center, and then the center sends firing order to the air defense missiles after processing the information. In this case, the requirement measure is destroying the enemy's aircraft more than 0.7 success probability, and the indices are abstracted into long-Distance warning radar detecting index, system processing delay index, and tracking index of the tracking radar. The model f is implemented by a program, and the sequential algorithm is implemented as a recursive program. The parallel algorithm is implemented and running in a group of PCs (PC of same type) connected by 100M Ethernet with each other. In the group, one PC is assigned as control node to execute the serverProcedure, and several other PCs are assigned as calculative node to execute the clientProcedure. Test the sequential algorithm and the parallel algorithm separately, and then add up the period of their execution. We played two schemes: increase calculative nodes, keeping the parameters (θ and γ) unchanged, and change one of the parameters, keeping the other parameter and calculative nodes unchanged, the results are shown in Table 1.

In this case, the period of single execution of the model call is tens of seconds. For the PCs are connected by 100M Ethernet, then the latency of transferring message is very tiny, and the overhead of the server preparing message is also very tiny because of the dequeue operation. Compared to t call , t com is too tiny to affect h 2 (θ, γ) much, then we can ignore it to estimate the speedup. We can attain pretty speedup through our parallel algorithm, and the speedup increases almost linearly with the number of calculative node, see Fig. 3. But there is a trend that the speedup with more nodes (6, 7, 8 nodes) increases more slowly than that with fewer nodes (2, 3, 4, 5 nodes). The main reason for this trend: during the execution, we found that the calculative nodes were not well-Balanced, in spite of using task pool model. We found that: at some time, several nodes are busy, while the others are idle (the hyperbox queue is empty at that time), but after the busy nodes completing resolving, they will make the idle nodes busy (because the resolving will produce sub-hyperboxes, and the hyperbox queue will not still empty after resolving completed), that means some calculative node were wasted. Therefore, the more calculative nodes we have the more nodes will be idle, and the more speedup will decrease. The cause of the waste is that the deploying of hyperboxes is blindly, thus the realistic work of the calculative nodes are not exactly symmetrical, and the faster ones have to wait for the slower ones. In our test, the practical efficiency is very close to the theoretical efficiency which is determined by formula [START_REF] James Dinan | Scalable Work Stealing[END_REF], and it indicates that formula [START_REF] James Dinan | Scalable Work Stealing[END_REF] is useful to estimate the parallel efficiency in this algorithm, see Fig. 4. As same as the speedup, the practical efficiency will decrease with the increasing of number of calculative node. The main reason for the decrease includes two points: 1) the calculative nodes are not well-balanced; 2) extra work which is brought in by parallelization goes up when the number of calculative node goes up.

Conclusions and Future Work

Basing on the analysis of the MIS method, this paper digs the immanent parallelism of the algorithm, and then introduces a coarse-grained parallel execution mechanism to the MIS method for accelerating the process of requirement space exploration. We implement the algorithm and then test it on PC clusters. The results indicate that the parallel algorithm is much more effective than the sequential algorithm.

In spite of the high parallel effectiveness of our parallel algorithm, we find the communication delay can decrease more, and the memory pressure for the control node can decrease more. In our parallel algorithm, the hyperboxes generated by the calculative nodes should be sent to the control node, and then sent to some calculative node back. In this course, one hyperbox is double-sent, and the delay between the time of generating and resolving will increase logically. In fact, the source and destination of hyperboxes are both calculative nodes, thus a hyperbox can be sent from one calculative node to some other calculative nodes directly or stay on itself controlled by the control node.

In our test, we find that the calculative nodes are not well load-Balanced. In fact, some feature (such as volume, bound, and so on) of hyperbox can be used to estimate the calculation which resolving the hyperbox needs, and the estimated information can be used to improve the deploy policy to adjust the load of each calculative node for load balancing.

1 pFig. 1 .

 11 Fig.1. an example of the MIS method. The root hyperbox is determined by point p1 and p2, and the partition point p * (f (p * ) = α) is on the diagonal. The partition point cuts the current hyperbox into 4 sub-hyperboxes, one of them (determined by p1 and p * ) belongs to requirement space, one (determined by p * and p2) of them doesn't, and the other two should be inspected again.

  c l i e n t P r o c e d u r e : I n i t i a l i z e ; Connect t o t h e S e r v e r ; L i s t e n message from S e r v e r ; switch ( message ) case i n f o r m a t i o n o f e x p e r i m e n t : s a v e t h e i m f o r m a t i o n ; case hyperBox : c a l l r e s o l v e P r o c e d u r e ; case c o l l e c t R e s u l t s : c o l l e c t t h e l o c a l r e s u l t s and send them t o s e r v e r ;

Fig. 4 .

 4 Fig.[START_REF] Jian Wen Hu | Monotonic Indices Space Method and Its Application in the Capability Indices effectiveness analysis of a Notional Anti-Stealth Information System[END_REF]. efficiencies. Keep the parameters(θ and γ) unchanged, and increase calculative nodes step by step, add up the period of sequential execution and the period of parallel execution, and then calculate parallel efficiency.

Table 1 .

 1 results table. Ts: time of sequential MIS, Tp: time of parallel execution, m: number of calculative nodes, θ: cut rate, γ: stop rate, speedup: Ts/Tp, P E: Practical Efficiency (speedup/m), T E: Theoretical Efficiency (formula[START_REF] James Dinan | Scalable Work Stealing[END_REF]).

		Ts(s) Tp(s) m θ	γ speedup PE TE
		5888 3552 2 0.05 0.05 1.658 0.829 0.750
		5888 2518 3 0.05 0.05 2.338 0.779 0.750
		5888 1913 4 0.05 0.05 3.078 0.769 0.750
		5888 1546 5 0.05 0.05 3.809 0.762 0.750
		5888 1456 6 0.05 0.05 4.044 0.674 0.750
		5888 1258 7 0.05 0.05 4.680 0.669 0.750
		5888 1133 8 0.05 0.05 5.197 0.650 0.750
		1789 1121 2 0.05 0.10 1.600 0.798 0.796
		1789 601 4 0.05 0.10 2.977 0.744 0.796
		7158 4567 2 0.0375 0.05 1.567 0.784 0.767
		7158 2375 4 0.0375 0.05 3.014 0.753 0.767
		6
	speedup	2 4						speedup
		0
		2	3	4	5	6	7	8
			number of calculative nodes

Fig.

3

. speedup. Keep the parameters(θ and γ) unchanged, and increase calculative node step by step, add up the period of sequential execution and the period of parallel execution, and then calculate speedup.


Yang Liu

Yunchu Liu

Hanli Bai

VSCM: a Virtual Server Consolidation Manager for Cluster

Keywords: Virtual Server Consolidation, Virtual Cluster, Virtual Machine Bin Packing, Virtual Machine Migration

Virtual server consolidation is to use virtual machines to encapsulate applications which are running on multiple physical servers in the cluster and then integrate them into a small number of servers. Nowadays, with the expanding of enterprise-class data centers, virtual server consolidation can reduce large number of servers to help the enterprises reduce hardware and operating costs significantly and improve server utilization greatly. In this paper, we propose the VSCM manager for virtual cluster, which solves the problems in the consolidation from a globally optimal view and also takes migration overhead into account. Experiment results in virtual cluster demonstrate that, VSCM can greatly reduce the number of servers and the migration overhead.

Introduction

With the development of information technology, to meet the growing business, many companies start to build their own data centers. In the twenty-first century, enterpriseclass data centers have been expanding, in which the growth rate of the number of servers is very impressive. However, the high costs of hardware and operation and the low utilization of these servers become very important problems. Virtual Server Consolidation (VSC), which can greatly reduce the number of servers, becomes a widespread-used technology for enterprise-class data centers to reduce hardware and operating costs and improve the server utilization. To use virtual machines (VM) to encapsulate applications which are running on multiple physical servers (PS) in the cluster and then integrate them into a small number of servers, VSC can reduce the number of servers greatly and improve their utilization significantly.

Several approaches [START_REF] Bobroff | Dynamic Placement of Virtual Machines for Managing SLA Violations[END_REF][START_REF] Hyser | Autonomic Virtual Machine Placement in the Data Center[END_REF] to VSC have been proposed. However, these approaches use heuristics from a locally optimal perspective according to some strategies, in which resource demands of VMs and resource residuals of PSs could not be considered from a globally optimal perspective. As a result, missing many chances to reduce the number of servers, these approaches could hardly achieve the minimum number of servers. Furthermore, they focus on how to make a new placement in which a VM is able to migrate to another PS, ignoring the migration overhead. Making use of constraint programming (CP) [START_REF] Benhamou | Trends in Constraint Programming[END_REF], Hermenier et al. [START_REF] Hermenier | Entropy: a Consolidation Manager for Clusters[END_REF] have solved above problems. But, they make this accomplishment in a homogeneous cluster environment, and one PS is allowed to run only one VM at a time which is much different from the real cluster of data center. In the real environment, using CP will produce significant time overhead that data center can not afford.

In this paper, we propose a new approach to VSC in virtual cluster that consider both the problem of allocating the VMs to available PSs and the problem of how to migrate the VMs to these servers. Our consolidation manager Virtual Server Consolidation Manager (VSCM) works in two phases. In the first phase, according to the measurements of CPU and memory usages of VMs and servers, VSCM uses Globally Optimal Virtual Machine Bin Packing (GOVMBP) algorithm to calculate a VM placement from the point of globally optimal view, with the objective of reducing the number of servers as much as possible. And in the second phase, based on the feedback mechanism, VSCM uses Feedback based Virtual Machine Migration (FVMM) algorithm to improve the placement and remove the constraints on migration. In our experiment, we simulate such a cluster environment in which there are 64 PSs and 100 VMs that are randomly generated. Compared to consolidation based on previously-used First Fit Decreasing (FFD), GOVMBP saves 10.22% of PSs in average. And FVMM gains a saving of 67.6% of migration step and 34.7% of migration overhead. Promising experiment results show that VSCM not only greatly reduces the number of servers but also significantly reduces the migration overhead.

The rest of the paper is organized as follows. We state the problems in the two phases of VSCM in Section 2. In Section 3, we describe our Virtual Server Consolidation Manager in details. Results from our experimental evaluation are reported in Section 4. We compare our work with related research efforts in Section 5 and conclude in Section 6.

Problem Statements

As mentioned above, VSCM works in two phases. The first phase calculates the minimum number n of servers that are necessary to hold all the VMs. We refer to this problem as the Virtual Machine Bin Packing Problem (VMBPP). The second phase reduces the migration overhead as much as possible, giving the number n. We refer to this problem as the Virtual Machine Migration Problem (VMMP).

The Virtual Machine Bin Packing Problem

The goal of the VMBPP is to calculate the minimum number n of servers that are necessary to hold all the VMs, according to the measurements of CPU and memory usages of VMs and servers. Consider the servers as bins, their resource capacity as bins' volume, VMs as items, and VMs' resource demands as items' volume, this problem can be expressed as Bin Packing problem [START_REF] Coffman | Approximation algorithms for bin-packing -An updated survey[END_REF], a classic NP-hard problem.

A VM cannot be allocated to a PS until the server has enough resource, for example, CPU, memory and etc. Taking into account that we do not study the quantity of VM allocated to one CPU core, for simple, we prescribe that one Virtual CPU (VCPU) of VM occupy one CPU core. Considering these two factors, CPU and memory, VMBPP can be reduced to 2-D Bin Packing problem [START_REF] Lodi | Recent advances on two-dimensional bin packing problems[END_REF].

Used by previous approaches [START_REF] Bobroff | Dynamic Placement of Virtual Machines for Managing SLA Violations[END_REF][START_REF] Verma | Power-aware dynamic placement of HPC applications[END_REF][START_REF] Wood | Black-box and Gray-box Strategies for Virtual Machine Migration[END_REF] as the solution to VMBPP, FFD works as follows: firstly, based on latest resource measurements of VMs and PSs, ranks the VMs in the decreasing order of resource demands; then, for each VM, if the residual resource of PS is enough for the VM, the VM will stay, if not, migrate this VM to the first PS which can hold it; if there's no active PS that can be migrated to, activate a new PS to hold the VM. The description of FFD discloses a strict restriction: VM can not migrate to a PS that has not enough residual resource. Although ensuring the feasibility of the VM migration, this restriction makes FFD a locally optimal solution which misses many opportunities to reduce the number n.

Therefore, FFD can not be competent for VMBPP, and only a solution standing from a globally optimal view is able to dig out the relationship between the demands of VMs and residuals of PSs, to make a plan that needs less number of servers.

The Virtual Machine Migration Problem

Given the minimum number n, the objective of VMMP is to make a placement to reduce the migration overhead as much as possible, and guarantee the feasibility of VM migration at the same time. Therefore, this problem is divided into two parts.

Which PS a single VM should migrate to is the first part of VMMP. Previous approaches [START_REF] Bobroff | Dynamic Placement of Virtual Machines for Managing SLA Violations[END_REF][START_REF] Hyser | Autonomic Virtual Machine Placement in the Data Center[END_REF] pay too much attention to whether a VM could migrate to some PS or not, ignoring the overhead that the migration itself brings. It may not be possible to migrate a VM to the destination PS immediately in the real environment, so the migration overhead plays an important role in the process of migration.

In the second part, migration constraints are taken into account. Hermenier [START_REF] Hermenier | Entropy: a Consolidation Manager for Clusters[END_REF] points out that the placement made by the preceding part may force a VM to migrate to some unqualified PS. In fact, the PS has the capacity to hold that VM at the end, but it may have not enough resources in the middle of the placement. There are two types of constraints on migration: sequential constraint and cyclic constraint.

A sequential constraint takes place when one migration can not start until another migration has finished. Fig. 1(a) shows an example. Once VM1 is activated, it finds deficiency in CPU residual in PS1, so it has to migrate to PS2. However, the residual memory in PS2 can not meet the need of VM1, so a migration of VM2 from PS2 to PS3 should be executed at first. These two migrations can not occur in parallel, that is, the migration of VM1 has to wait till VM2's has completed.

A cyclic constraint occurs when multiple migrations form a cycle. Fig. 1(b) shows an example. Once VM1 is activated, it finds deficiency in CPU residual in PS1, so it has to migrate to PS2. However, the residual memory in PS2 can not meet the need of VM1, so a migration of VM2 from PS2 to PS1 is needed at first. Unfortunately, PS1 has not enough memory for VM2, which requires that the migration of VM1 should be done in the first place. These two migrations can not happen because the two VMs both lock the resources that the other need.

These two types of constraints have severe influence in the establishment of the placement. The migration can not be executed unless these constraints are removed, and the feasibility of migration is greatly threatened. Most of previous approaches [START_REF] Bobroff | Dynamic Placement of Virtual Machines for Managing SLA Violations[END_REF][START_REF] Hyser | Autonomic Virtual Machine Placement in the Data Center[END_REF][START_REF] Verma | Power-aware dynamic placement of HPC applications[END_REF] may not encounter the migration constraints, because they guarantee the feasibility in each step of migration. However, as mentioned above, the locally optimal solution they adopt can not achieve a global optimization. When a migration is not feasible, Wood07 [START_REF] Wood | Black-box and Gray-box Strategies for Virtual Machine Migration[END_REF] identifies a set of VMs to swap to free resources on the destination server. However, this method temporarily needs some space for hosting VMs and the placement issue it is able to solve can not be complex. Girt [START_REF] Grit | Virtual Machine Hosting for Networked Clusters: Building the Foundations for Autonomic Orchestration[END_REF] take an offline strategy in which they suspend the VMs that need migrate till the destination PS is qualified. Yet, this does not work for live migration.

Design and Implementation of VSCM

A typical virtual cluster consists of one management server without virtual environment and multiple computing servers (PSs as mentioned above) with Xen [START_REF] Barham | Xen and the Art of Virtualization[END_REF] virtual environment in which the VMs are placed. System architecture of VSCM is showed in Fig. 2. VSCM is made up of one Control Center in the Management Server and one sensor in each Computing Server. These sensors and the Info Manager in the Control Center are components of Prospector [START_REF] Liu | Design and Implementation of Xen Virtual Cluster Monitor[END_REF], a Xen virtual cluster monitor, which is used to iteratively collect the measurements of resources in PSs and VMs and detect the change of their state. After arranged by Info Manager, the information that is collected by sensors is sent to the core of VSCM, VMBP and VMM, two modules in the Control Center. VMBP Module uses GOVMBP algorithm to solve VMBPP and then VMM Module uses FVMM algorithm to solve VMMP. Once the core finds the current placement not viable, or new placement needs fewer servers, VSCM will call the VM Management Interface to execute the consolidation corresponding to the new plan.

The Globally Optimal Virtual Machine Bin Packing Algorithm

To dig out the possible opportunities to reduce the minimum number n, VMBP module uses a globally optimal algorithm, the GOVMBP, to solve the VMBPP.

Making a new placement according to the current one is the limitation of FFD, so the essence of GOVMBP is to initialize the placement no matter what the current one is.

That is, at the beginning of determining the placement, GOVMBP ignores the current placement, and hypothesizes that each PS is in its initial state, without any VM. Therefore, when considering the placement, GOVMBP faces a brand new cluster instead of complicated placement, which helps to completely take demands of all VMs and residuals of all PSs into account from a globally optimal view before making the decision. GOVMBP firstly takes current placement and measurements of VMs and PSs as input, and save the current placement as begin_cluster. The next step, the kernel of this algorithm, is to initialize the placement to the situation in which there are no VMs on any PS. The following part is based on FFD. Firstly, on the basis of latest resource measurements of VMs and PSs, ranks the VMs in the decreasing order of resource demand; then, for each VM, if the residual of PS is enough for the VM, the VM will stay, if not, migrate this VM to the first PS which can hold it; if there's no active PS that can be migrated to, activate a new PS to hold the VM. Finally, we get the new placement mid_cluster as the output.

As initializing the placement, GOVMBP is no longer limited to the current placement, and finds more possibilities to reduce the number n, the number of active servers in new placement. However, this algorithm introduces migration constraints that are mentioned in Section 2.2 and we are going to solve them in Section 3.2.2.

There's another point to emphasize that, mid_cluster is just a plan which is not executed immediately, and the real placement in the cluster does not change.

Feedback based Virtual Machine Migration Algorithm

Given the minimum number n, VMM module adopts FVMM algorithm to solve the VMMP. Taking current placement as feedback, FVMM improves the new placement made by GOVMBP to reduce the migration overhead, and then removes the migration constraints introduced by GOVMBP to guarantee the feasibility of the migration. The Feedback Mechanism. Previous approaches [START_REF] Bobroff | Dynamic Placement of Virtual Machines for Managing SLA Violations[END_REF][START_REF] Hyser | Autonomic Virtual Machine Placement in the Data Center[END_REF][START_REF] Verma | Power-aware dynamic placement of HPC applications[END_REF] focus on the right PS that the VM should be moved to, ignoring the migration overhead. Therefore, to reduce the migration overhead as much as possible, the feedback mechanism (FM) tries its best to avoid the migration. So, the essence of this mechanism is that, if a migration is avoidable, avoid it. After comparing the new placement with the current one, FM tries to restore the placement. That is, for each migration in the new placement, if canceling this move still guarantees that the PS has the capacity to hold the VMs and the number n is not increased, this migration will be dropped. The final objective of FM is to make every VM stay on the PS where it is placed now.

The FM works as follows. A VM that needs to move (MVM) is the one whose host server in the new placement new_host is not the same one in the current placement old_host. For each MVM v, the FM will make a judgment whether v could stay on the old_host or not by the analysis of the resource measurements of all the VMs and PSs in the new placement. If the following situations happen, v is allowed to stay, and the migration for v in the new placement is cancelled.

(1) The old_host has enough resource residual to hold v (2) The old_host could move some MVMs that are hosted on it to other PSs to free the resources to hold v.

(3) Some MVM that are hosted on old_host could exchange the position with v, without exceeding the resources limits on both servers.

If, unfortunately, above situations do not happen, v has to move from old_host to new_host. The FM will produce a new placement end_cluster in which more VMs are hosted on its old_host than mid_cluster. This leads to fewer migrations and the overhead will be reduced greatly.

The end_cluster is the final placement which will be the real placement after this process of consolidation is done. The migrations in end_cluster can not be avoided and they are put on a list move_list. Like mid_cluster, end_cluster is not executed immediately and the real placement at this moment in the cluster does not change. Methods to Remove Migration Constraints. As GOVMBP introduces migration constraints and the FM aggravates this situation, the feasibility of migration in the latest placement can not be guaranteed. As mentioned above in Section 2.2, there are two types of constraints on migration.

For sequential constraints, the solution lies in the description of this problem. One move M 1 can not be executed until another one M 2 has finished. As a result, finishing M 2 and M 1 in order will remove this constraint. So, for all migrations in move_list, search the feasible ones and remove them from the list. These migrations are executed earlier and free the resources for the ones still on the list. Repeat this process till there are no feasible migrations, and those left on the list are limited by cyclic constraints. The feasible migrations found in the same iteration can be done in parallel because there are no longer constraints between them.

For cyclic constraints, we give the following definition.

A VM vm i needs to move from server s i to server s j while another VM vm j needs to move from s j to s i . If the resource limits both moves, we define this situation as a (s i , s j , s i ) cycle. By extension, if vm j needs to move from s j to s k while VM vm k needs to move from s k to s i , this forms a (s i , s j , s k , s i ) cycle.

According to above definition, a cyclic constraint is hard to find, and we need find a way to recognize the cycle by using Graph Theory. Given k PSs, we construct a digraph G = (V, E). Vertex v i denotes server s i , and vertex set V = (v 0 , v 1 ,…, v k-1 ) is the set of all vertexes. A directed edge e i,j = <v i , v j > from v i to v j denotes that there is a VM that needs to move from v i to v j and edge set E = (e 0,1 , e 1,2 ,…, e k-1,k-2 ) is the set of all directed edges. If there is directed edge e i,j = <v i , v j >, we define v j as the neighbour of v i . We also call v i e i,i+1 v i+1 e i+1,i+2 v i+2 …e k-1,k v k a directed path that connect v i to v k . If there is a directed path v i e i,i+1 v i+1 e i+1,i+2 v i+2 …e k-1,k v k from v i to v k , we say v k is accessible from v i . So, the cycle (s i , s j , s i ) denotes the directed path that goes from v i to v j by the directed edge e i,j and then back to v i by e j,i , that is, v i is accessible from v i itself. We define this path from v i back to v i as a directed cycle (DC) v i e i,j v j e j,i v i . Therefore, to recognize a cycle is to recognize the corresponding DC in the graph G. For example, there are two DCs in Fig. 3 which are v This paper introduces a method to recognize the DC in graph G on the basis of Depth First Search (DFS) algorithm. The essence of this method is that if v i is in a DC v i e i,j v j e j,k v k …e m,i v i , v i is accessible from v i itself. So, in the graph G' which is built by cutting the edge e i,j , there is certainly a path from v j to v i , that is, v i is accessible from v j . Furthermore, in the graph G'' built from G' by cutting the edge e j,k , v i is accessible from v k . Taking advantage of DFS, we can test a vertex v whether it is accessible from itself. If accessible, v is in a DC that includes v.

Pseudo-code of the method to test whether vertex end is accessible from vertex begin on the basis of DFS. The above pseudo-code tests whether vertex end is accessible from vertex begin on the basis of DFS. For each vertex v in the neighbors of begin, if its destination node v.des happens to be end, end is accessible from begin. If not, test whether end is accessible from v.des on the premise that v.des has not been visited before.

Take Fig. 3 as an example. Starting with v 0 , the search sequence is

v 0 -> v 1 -> v 2 -> v 3 -> v 4
, and then we find a unique path from v 4 to v 3 , so we step back to v 2 . However, we will soon find that, after v 2 -> v 5 -> v 6 , v 6 can only reach v 1 . That is, v 0 is not accessible from itself. If we start with v 1 , we will recognize a DC v 1 e 1,2 v 2 e 2,5 v 5 e 5,6 v 6 e 6,1 v 1 . Similarly, another DC v 3 e 3,4 v 4 e 4,3 v 3 is found if we take v 3 as the beginning vertex.

The next step is to untie this cycle, that is, to remove this cyclic restraint. Comparing with the method to recognize the cycle, the one to untie it is much simpler. Search all servers and find one to be a springboard. That is, for each MVM vm in this cycle, if some server s can be found enough resource residual to hold vm, we firstly move vm to s and then move it from s to its original destination. This server s is used as a springboard to hold vm temporarily.

During the process to remove the migration constraints, VSCM generates feasible migration commands for consolidation and calls the VM management interface to execute them. After the consolidation is done, the real placement in the cluster is finally changed to end_cluster.

Evaluation

This section presents results from a number of experiments we conducted to evaluate our algorithms.

Design of Migration Overhead

As one of the simplest overhead, migration step is the number of the migrations that the consolidation needs to change the current placement to the new one, directly evaluating various migration algorithms. However, resource usages on servers play a great role in moving one VM from source server to destination server. The higher the CPU or memory usage is, the longer the process of migration takes, for example. And the most important factor is the memory requirement of VM which determine the time of the process. Therefore, we design the migration overhead as follows.

The total overhead of placement O(p) is the sum of each migration overhead O(v) made by VM v moving from source server s src to destination server s des in this migration. (Equation 1)

v p O (p)= O (v)   . (1)
As involving the source server and destination server, O(v) is made up of the overhead to source f (s src ,v) and the overhead to destination f(s des ,v). (Equation 2)

O(v) = f (s src , v) + f(s des , v) . (2)
In consideration of the only focus on CPU and memory in Section 2.1, the overhead f(s, v) made by VM v to server s is determined by following factors: CPU usage of the server s.cpu_util, memory usage of the server s.mem_util and the memory requirement of the VM v.mem. Since v.mem dominates the time of migration process, we construct Equation 3 as follows.

f(s, v) = (s.cpu_util + s.mem_util) * v.mem .

(3)

Experimental Setup

Limited by real environment, we have to evaluate our algorithms on simulation data, to illustrate the range of benefit that VSCM can provide. The virtual cluster we simulate consists of 64 PSs and 100 VMs that are generated randomly. Each PS has 4 CPU cores and 4 GB of memory. For each VM, we generate the VCPU demand randomly in the range of [0, 4] and the memory demand in the range of (0.0, 2.0] GB. For simple, the memory is going to be 0.5 or 1.0 or 1.5 or 2.0GB. The computer configuration for this simulation is shown as follows: Intel(R) Core(TM)2 Duo CPU P8400@2.26GHz, 2x1G DDR3 memory and the operating system is CentOS 5.3. VSCM is implemented in this OS by Python 2.4.3.

Results and Analysis

GOVMBP vs FFD. To test whether GOVMBP uses fewer PSs, we compare it with FFD which is used by most of the previous approaches. The initial cluster is made up of 64 PSs without any VM and then we randomly generate 100 VMs. For the initial placement, both the algorithms adopt the same policies to allocate these VMs to the PSs, and the number of PSs in use is the same. Then we change the configuration of the 100 VMs to simulate the various situations in the real environment. Facing to the new placements in which there are already 100 VMs hosted on the PSs, GOVMBP and FFD will take different policies. As a result, the number of PSs used may not be the same, and neither do the new placements the algorithms produce.

Fig. 4 shows the comparison between GOVMBP and FFD in 20 experiments. The numbers on the right denotes the numbers of servers that GOVMBP saves. We divide them into four classes and find that, in most cases (45%), GOVMBP uses 6-10 fewer servers than FFD. Furthermore, in the vast majority of cases (95%), GOVMBP uses fewer servers than FFD. On the basis of statistics, we find that GOVMBP uses 5.9 fewer servers than FFD and saves 10.22% of servers in average, verifying the superiority of this globally optimal solution. Effect of the Feedback Mechanism. The FM is the kernel of FVMM, so we conduct this experiment to evaluate the effect of the FM on the consolidation. In this comparison, one is the VSCM with FM and the other one is without FM. For the initial cluster where there are 64 PSs without any VM, we randomly generate 100 VMs. Without preceding placement to feed back, VSCM with FM adopt the same policy to allocate VMs to PSs as the one without FM does. Then we change the configuration of the 100 VMs to simulate the various situations in the real environment. With current placement as the feedback, the one with FM and the other one without FM will take different policies. As a result, the overhead which is produced by all the migrations will be different.

Fig. 5 shows the comparison migration overhead between VSCM with FM and the one without FM in 20 experiments. The left part compares migration step. In average, the one with FM needs 34.25 steps to finish the placement while the one without FM needs 106.25 steps which is 3.1 times the former. The right part compares the migration overhead designed by Section 4.1. The result also verifies the benefit of the FM that, the overhead produced by the one without FM is 1.5 times that produced by the one with FM. According to the statistics, the FM is able to save 67.6% of migration step and 34.7% of migration overhead designed by Section 4.1.

Related Work

Most of previous approaches use heuristics from a locally optimal perspective to solve VMBPP, so they lose many opportunities to reduce the number of servers, and they often ignore the migration overhead which is very important for the real cluster. Bobroff et al. [START_REF] Bobroff | Dynamic Placement of Virtual Machines for Managing SLA Violations[END_REF] establishes the virtual server consolidation on a forecast mechanism. They predict the resource demands of VMs on the basis of history, rank the VMs in the decreasing order of the demands, and then use FFD to allocate VMs to PSs in arranged order. For each server, they take the sum of all the VMs' resource demands as the predicted resource overload. If this overload does not exceed the threshold of the server and the resource capacity is enough to handle the resource demand, they allocate the VM to the most suitable server. Strictly speaking, the placement algorithm they use is based on BFD.

Though Khanna et al. [START_REF] Khanna | Application Performance Management in Virtualized Server Environments[END_REF] use heuristics to solve VMBPP, it is gratifying that they pay more attention to the migration overhead while determining the placement. They rank VMs in non-decreasing order of the resource usages of VMs from which migration overhead is calculated. In other words, they rank the VMs in the order of the overhead. They choose the VM whose usage is the lowest on the unqualified PS, and move it to the qualified PS which has the least resource residuals. Wood07 et al. [START_REF] Wood | Black-box and Gray-box Strategies for Virtual Machine Migration[END_REF] also use a greedy algorithm to determine a sequence of moves to migrate overloaded VMs to underloaded servers, in which the migration overhead is considered in the form of defined volume. However, these approaches still base their placement algorithm on the locally optimal solution. Some approaches mention the migration constraints in their work. Girt et al. [START_REF] Grit | Virtual Machine Hosting for Networked Clusters: Building the Foundations for Autonomic Orchestration[END_REF] try to solve the VMMP with the help of Shirako [START_REF] Irwin | Sharing networked resources with brokered leases[END_REF], a system for on-demand leasing of shared networked resources in federated clusters. When a migration can not proceed because of the migration constraint, the VM will be suspended till the destination server is available. This simple method is not qualified in the real-time environment where needs live migration. Wood07 et al. [START_REF] Wood | Black-box and Gray-box Strategies for Virtual Machine Migration[END_REF] identify a set of VMs to swap to free resources on the destination server. This approach is only able to solve simple placement issue and needs some space for hosting VMs temporarily.

Unlike the above approaches, Hermenier et al. [START_REF] Hermenier | Entropy: a Consolidation Manager for Clusters[END_REF] develop the Entropy by Choco [START_REF] Jussien | The CHOCO constraint programming solver[END_REF] to perform consolidation based on constraint programming. From the globally optimal point of view, Entropy solves VMBPP and VMMP pretty well. Comparing to FFD, Entropy greatly reduces the number of servers and the migration overhead. However, Entropy aims at homogenous cluster and one PS is allowed to run only one VM at a time. This is much different from the real cluster of data center where there are usually many VMs placed on one PS. As a result, using CP in a real cluster environment will produce significant time overhead that data center can not afford.

Conclusions

Virtual server consolidation which can reduce large number of servers helps the enterprises reduce hardware and operating costs significantly and improve server utilization greatly in the enterprise-class data center.

In this paper, we propose a new approach to virtual server consolidation that considers both the problem of allocating the VMs to available PSs and the problem of how to migrate the VMs to these servers. Experiment results demonstrate that, our consolidation manager VSCM can indeed reduce the number of servers greatly, as compared to previously used FFD. While reducing the migration overhead significantly, VSCM also guarantees the feasibility of each migration operation.

In future work, we plan to improve the Globally Optimal Virtual Migration Bin Packing algorithm on the basis of more complicated bin-packing algorithm. We also expect to apply VSCM to the real cluster to get convincing experiment results.

Fig. 1 .

 1 Fig. 1. Examples of migration constraints. The Mem and CPU in PS represent the residual resource capacity of the PS, and the Mem and VCPU in VM represent the resource demands of the VM. The dashed circle denotes that VM1 is going to be activated. The 0 of VCPU denotes VM2 is not active.

Fig. 2 .

 2 Fig. 2. VSCM system architecture. Modules of VMBP and VMM constitute the core of VSCM and the sensor and Info Manager are used to collect and arrange the info from VMs and PSs.

  1 e 1,2 v 2 e 2,5 v 5 e 5,6 v 6 e 6,1 v 1 and v 3 e 3,4 v 4 e 4,3 v 3 respectively.

Fig. 3 .

 3 Fig. 3. An example of directed graph G in which there are two DCs, v 1 e 1,2 v 2 e 2,5 v 5 e 5,6 v 6 e 6,1 v 1 and v 3 e 3,4 v 4 e 4,3 v 3 .

Fig. 4 .

 4 Fig. 4. Comparison between GOVMBP and FFD. The numbers on the right represents the numbers of servers that GOVMBP saves.

Fig. 5 .

 5 Fig. 5. Migration overhead comparison between VSCM with FM and the one without FM. The left part compares the average migration step and the right part compares the average migration overhead designed by Section 4.1.