1 Introduction

Social media was defined by Andreas M. Kaplan and Michael Haenlein [13], and it refers to the interaction among human beings. They defined social media as various Internet-based applications that allow users create and share the user-generated content [6]. People create some events and exchange their thoughts in the virtual social communities and worlds. For instance, bloggers may write their works and creations to blog, and share information without face to face conversation [11]. In order to serve and manage the enormous social media services, the well-balanced VM placement and allocation is definitely required in cloud data center.

The evolution of cloud computing not only changes the business model [27] and system architecture [1], but also leads the Internet services to a novel direction [18]. The various resources in the resource pool should be elastic and scalable [16], which is different from the consolidated resource in traditional computing method. Therefore, the researchers start to investigate how to improve the performance [5] and allocate the resource elastically [21]. There are many advantages of virtualization technique, including efficient resource utilization [8], easy management [25], reduced energy consumption [15], simultaneous resource monitoring [29] and so forth. However, it also brings some problems, such as the attack problem [10], performance overhead [22], unnecessary VM migration [24] and so on.

It is clear that the centralized task assignment is infeasible in cloud environment [23]. The researchers in [26] divide the cloud infrastructure into three layers, which are request management level, service management level and service execution level. In this paper, the same three-tier architecture for cloud data center is considered. On the other hand, the tree structure is generally applied in data center. The leaves are various VMs, and the parents are several PMs. If the resource requirement of VMs exceeds the remaining resource in PMs, part of VMs should be migrated to other PMs. The valid VM migration is able to reduce the resource and energy wastage [9]. An efficient and easy method of load balancing is migrating some VMs from the busy PM to the idle PM.

The remainder of this paper is organized as follows. In Section 2, we compare the current researches about VM migration and load balance schemes in cloud data center. The Section 3 defines the solved VM migration problem based on Mixed Integer Linear Programming (MILP), and states the strategy for classifying VMs. Besides, the proposed VM allocation algorithm is also depicted and explained in Section 3. In Section 4, we discuss the simulation results of this work. The conclusion from this research is drawn in Section 5.

2 Related works

There are many researches investigating how to balance payoff between cost and efficiency during VM migration. Most of them study balancing the workload of homogeneous nodes. But it is unfeasible in current cloud data center, the dynamic and heterogeneous systems are used to provide on-demand resources and services [23]. To find out the lower load node for migration, parts of researchers put forward the scheduler to choose the appropriate PM and set a threshold to VM. Once the PM exceed in its utilization, it will recall the schedule and choose a suitable VM to migrate [20]. However, they usually neglect the migration cost during migration process.

The files in data center are created and deleted dynamically. The file chunks are not distributed uniformly in virtual machines [7], hence it leads the imbalanced workload in the entire system. This implies that the task usage is different, and the change between each node is also diverse. Based on the above-mentioned phenomenon, the VM migration is needed and unavoidable. Therefore, some researchers consider that the virtualization technique should be the first step in cloud computing [30].

Some literatures on the VM load balance have been proposed, such as [20], [30] and [14]. In [20], the authors proposed a combined algorithm that focus on the server workload and migration efficiency. The numbers of virtual machines and some migration criteria were studied. The VMs were migrated for the minimum power consumption, and the underutilized PMs were shut down. The energy cost and cooling cost in data center were economized. The authors [30] proposed Multi-agent Genetic Algorithm (MAGA) based on the Genetic Algorithm (GA) and multi-agent technique, and derived it to a mathematical problem from their proposed model. It not only solved the high dimensional function optimization, but also adjusted the parameters in large-scale network to achieve the load balance feature.

Here are some related works to ours, such as [12] and [28]. The authors in [28] detected the resource and the change of hotspot, and found the hotspot that needs to be migrated. It migrated the VMs through remapping the resources of VMs. The most similar work with ours is [12]. According to historical data and current state of VMs, the authors proposed their GA algorithm to put forward a scheduling strategy on load balancing of VM resources. By computing the influence of VMs, they selected the least-effective solution to prevent dynamic migration. However, they didnt consider the stability of VMs. Since the resource in cloud environment is elastic and changeable, the computing states in VMs are differential. It will lead to low utilization of PMs in data center. In this work, we not only consider the stability of the VMs, and also investigate the utilization of the VMs. According to the difference of VMs stability and utilization, we propose an algorithm for allocating VMs stably and steady.

3 Problem definition and proposed algorithm

3.1 Problem definition

The VM migration problem is defined and formulated based on Mix Integer Linear Programming (MILP), viz the Minimization VM Migration (MVMM) problem in this work. The used variables and notations in MVMM problem are listed and defined as Table 1.

Table 1 Definition of the important notations
Full size table

Let there are N VMs in M PMs, and the utilization of VM n and PM m are U n and U m . Assume that the capacity of the PM m is C m and the minimum resource demand of the VM n is δ n. Then, we consider the utilization of PM m. When the utilization of VM n or PM m is higher than the capacity of PM m, the VM n must be migrated from PM m to other PM, where

$$\begin{array}{@{}rcl@{}} a_{m,n}=\left\{ \begin{array}{lll} 1,~{} if ~{} U_{n}>C_{m}\vee U_{m}>C_{m}. \\ 0,~{}otherwise. \end{array} \right. \end{array} $$
(1)

The VM needs resource to execute tasks. We consider the U m and U n including the common resources, such as CPU, storage and bandwidth utilization. According to above statements, we formulate our MVMM problem as the minimum numbers of VM migration in a time interval T, which is modeled as the following.

Minimize

$$ {Z^{M}_{N}}=T(\sum\limits^{M}_{m=1} \sum\limits^{N}_{n=1} a_{m,n} ). $$
(2)

subject to

$$ a_{m,n} \in \{0.1\},~{}for ~{}\forall n \in \mathbb{N}_{VM}, \forall m \in \mathbb{N}_{PM}, $$
(3)
$$ {Z^{M}_{N}} \geq 0, ~{} for ~{} N \in \mathbb{N}_{VM}, ~{} M \in \mathbb{N}_{PM}, $$
(4)
$$ U_{m} \leq 1, ~{} for !{} \forall m \in \mathbb{N}_{PM}, $$
(5)
$$ U_{n} \leq 1, ~{} for {} \forall n \in \mathbb{N}_{VM}, $$
(6)
$$ \delta_{n}\leq C_{m} \leq , ~{}for~{} \forall n \in \mathbb{N}_{VM}, ~{}\forall m \in \mathbb{N}_{PM}, $$
(7)
$$ T \in \mathbb{Q}. $$
(8)

The objective function (2) minimizes the numbers of VM migration in PMs within a time interval T. Constraint (3) states that the decision of VM migration for \(\mathbb {N}_{VM}\) and \(\mathbb {N}_{PM}\) is a binary, which represents the VM should be migrated or not. Constraint (4) ensures that the numbers of VM migration is a positive integer. In constraints (5) and (6), the utilization of PM m and VM n is less than or equal to one. They are associated with one PM and one VM. Constraint (7) ensures the VM resource requirement should not exceed the PM capacity. Constraint (8) states that the time interval is a rational number.

3.2 VM classification strategy

In this work, the VMs are categorized and classified according to types. We utilize the concept of Support Vector Machine (SVM) [2] to decide the VM types. The concept of SVM could be applied to many research fields, such as anomaly detection [4], appliance recognition [17], and so on. We use the open source tool called LIBSVM [3] to implement the VM classification model.

The space classification of SVM is shown as Fig. 1. It is a well-known approach for data classifying and machine learning. The classifier is trained by the existing categories, and sorts the data by category and type. In SVM, the concept of classification boundary is adopted to demarcate these classification boundaries. Through data training, SVM finds the boundaries between these classifications, which are liner-called liner division and curve-called nonlinear division.

Fig. 1
figure 1

The classification capability of SVM

Full size image

In this work, two main factors influence the types of VMs. One is the average utilization of VMs, and the other one is the stability of VMs. The stability refers to the resource demand during a time period. In other words, the VM is regarded as unstable if its resource usage is frequently changed. Based on these two factors, the VMs are able to classify into four types. We can utilize SVM to discover the boundaries.

We name the four VM types A, B, C and D. The type A VMs are changeable so that the remained resource may be insufficient. It is unstable and needs high resource utilization. The type B VMs are also unstable but need less resource than type A VM. Unlike type A and B, the type C and D VMs are stable which means the resource requirement is steady. The type C VM is stable but needs high resource utilization, and the type D VM requires less resource allocation. Since the boundaries between these four VM types are unknown, the SVM tool is applied to classify them.

The dataflow of proposed classification method is shown as Fig. 2. In order to achieve the decision model, we must provide the training data for SVM. It follows the rule of training data and obtains the decision model. We execute the VMs in advance, and select the data and training data. The original data should be transformed to vector form through hash function, and then the training set is acquired. Through machine learning, the SVM gets decision model of four VM types. Finally, the incoming data can be classified and categorized by the decision model.

Fig. 2
figure 2

The classification dataflow in general SVM

Full size image

3.3 VM allocation algorithm

After the categories of VMs obtained, we propose a VM allocation algorithm to distribute them based on their categories. For minimizing the probability of VM migration, we allot the VMs with the remained resource of PM. Unlike the existing algorithms, we not only consider the average utilization of VMs but also the stability. It will decrease the redundant migration costs.

The notations and functions in proposed algorithm are clarified as follows. The \(\mathbb {N}_{PM}\) stands for the set of PMs. Then, we assume that all PMs have the same capacity C m . The E x is defined as the type of VM. \(\mathbb {N}_{PMY}=(N_{PM},U_{PM})\) used to record the PM which contains the Y type VMs only, and its utilization is U P M . The \(f_{a}(\mathbb {N}_{PM},E_{X},C_{m})\) is used to allot all VMs of type X under the PMs alone. It generates the list \(\mathbb {N}_{PMX}\) and the list S X of VMs selected in type X. Our allocation policy is that the VMs utilization must not exceed the PM capacity C m . This function goes to allocate E X alone under the PMs. Another function \(f_{b}(\mathbb {N}_{PMY},E_{X},C_{m})\) is used to allocate the type X VMs E X under the PMs \(\mathbb {N}_{PMY}\), which had been allocated to the Y type VM. It produced a list S X recording the selected X type VMs. If the list S X is null, it implies that there is no enough resource for the VM type X or the VMs of type X are allocated completely. This function allocates VMs of one type with another type VMs.

We introduce and explain the proposed VM Allocation algorithm herein. From line 2 to line 6, all type A VMs are placed in the PMs. The same procedure with above, the type B VMs are allocated to PMs in line 7 to line 11. From line 12 to line 15, we allot type D VMs to the PMs which allocated to type A VMs in line 2 to line 6, until there is no more resource for type D VMs or there is no type D VMs. From line 16 to line 18, the type C VMs are allocated to the PMs which type B VMs placed before. If the PMs for type C VMs are use up, the type C VMs are allocated to other PMs in line 19 to 24, until all VMs of type C are allocated. From line 25 to line 29, if the VMs of type D is not allocate yet, we allocate the remained type D VMs to PMs. These PMs were allocated for the type C VMs before. Lastly, the unallocated VMs of type D are placed to other PMs in line 30 to line 33. It ensures all of the VMs are allocated.

4 Experiment results

4.1 VM classification model

We utilize a well-known open source, viz. LIBSVM [19] to implement our classification model. The LIBSVM is an SVM library, and the newest version is 3.17 released on April 1, 2013. Firstly, we provide the training data for LIBSVM. The original data should be transferred to SVM format before using training function. In order to avoid the range of features is within the reasonable value, and it can be executed in the kernel function. We scale the training data for LIBSVM tool. The process from training data to scale set is shown as Fig. 3.

Fig. 3
figure 3

The process from training data to training set

Full size image

To obtain the training data, we provide some data about the VMs during a specific running time. The label in training data stands for the species of VMs, and it could be filled in or empty. We classify the total VMs into four kinds. Therefore the SVM categorizes the VMs in training process, and fill in 1 to 4. The c-u(tx), m-u(tx), s-u(tx) and b-u(tx) are the feature values of VMs. They represent the CPU utilization, memory utilization, storage utilization and bandwidth utilization at time tx, respectively. In this paper, we choose 600 records at five time stamps in a unit time as the training data. In the training set, hash function used to transform the training data into SVM format. The scale function converts the training set to the data within a certain range. It is also called scale set, and the scale range is from -1 to 1. Finally, the obtained parameters are used to train the scale set.

For the better training data, we need to find the best configuration for training parameter. During the selection process, the function repeatedly executes to obtain the optimal parameters for VM classification. The parameter is produced and drawn by gnuplot. It is shown as Fig. 4. According to cross validation, the optimal parameter for VM classification is acquired and found.

Fig. 4
figure 4

The process for producing parameter

Full size image
figure f

When the training process finished, we utilize the machine learning function in LIBSVM to classify VMs. The training data achieves the decision model for classifying VMs. The iteration of machine learning in training procedure and the decision model generation is as shown as Fig. 5.

Fig. 5
figure 5

The iterative training process

Full size image

4.2 Planning case

We have acquired the decision model for VM classification. The decision model should be coped with the proposed VM Allocation algorithm to minimize the number of VM migration. The Best Fit algorithm and First Come First Serve (FCFS) algorithm are compared to our algorithm with the planning case and simulation. The object of Best Fit algorithm is try to utilize the PM resource as much as possible, and it will allocate the closest VM to PM in terms of requested demand. The FCFS algorithm distributes VMs according to the incoming order of VMs. Before discussion on the planning case, there are three assumptions should be assumed.

  1. 1.

    The hardware standard and computing resource of all PMs are all the same, including the allocated capacity.

  2. 2.

    In the simulation, we do not define the required bandwidth and storage of all PMs, and the VMs vice versa.

  3. 3.

    We assume that all the related communication effects are consistent, therefore we only consider the cost of VM migration.

The planning condition is shown as Fig. 6. We take 6 PMs and 10 VMs into consideration, and the capacity of each PM is 0.9. In order to compare the difference between three algorithms, we observe and record the utilization of VMs during two unit times. The current requirement and maximum requirement within two unit times are shown as Table 2.

Fig. 6
figure 6

Planning condition

Full size image
Table 2 The requirement of VMs
Full size table

In VM allocation algorithm, we utilize the decision model which achieved by LIBSVM to classify the VM types and acquire the maximum requirement during training time. In the planning case, the training time is 1 unit time. The types and maximum requirements of each VM are shown as Table 3. The results of three algorithms are shown as Figs. 7, 8 and 9.

Table 3 The types of VMs and maximum requirement during training time
Full size table
Fig. 7
figure 7

The planning result of best fit algorithm

Full size image
Fig. 8
figure 8

The planning result of FCFS algorithm

Full size image
Fig. 9
figure 9

The planning result of the proposed VM Allocation algorithm

Full size image

The best fit algorithm maximizes the utilization of PMs, and allocates the VM that has the maximum requirement to PM. Firstly, it sorts all VMs based on their demand in descending order, which is VM5, VM9, VM10, VM3, VM6, VM7, VM1, VM4, VM2, VM8. Then, the VM5 is allocated to PM1. Due to the limitation of PMs capacity, we have to allocate the VM9 to PM2. Moreover, the demand of VM10 is less than the remaining resource of PM1, hence the VM10 is placed to PM1. When there is no remaining resource in PM1, we continue allocating the remaining VMs to PM2. The rest of PMs are continually allocated to PMs with the same method.

In the FCFS algorithm, the VMs are allocated to PMs based on the incoming order of VMs. The incoming sequence of VMs is same as their numeric. Firstly, since the summation of requirement is less than the capacity of PM1, we allocate the VM1, VM2, VM3 and VM4 to PM1. Then, the VM5, VM6 and VM7 are allocated to PM2. Finally, the VM8, VM9, VM10 are allocated to the PM2 according to their incoming order and the PM capacity limitation.

In the proposed VM allocation algorithm, we allocate the VMs according their types, which are judged with the maximum requirement during the training time. Firstly, we respectively allocate the VMs of type A (VM2 and VM6 with red label in Fig. 9) and the VMs of type B (VM1, VM4 and VM8 with blue lebel in Fig. 9) to the PM1, PM2, PM3, PM4 and PM5. Then we distribute the VMs of type D (VM3 and VM7 in this case) to PM1 and PM2. In this phase, we allocate the VMs of type C (VM9 and VM5 with green label in Fig. 9) to PM3 and PM4. At last we distribute the remaining VMs (VM10 in this case) to PM5, which has enough resource for placing VM10. One thing should be mentioned here, the assignment of VMs is based on the maximum requirement during training time, rather than the current requirement.

The comparison of planning result for three algorithms is shown as Table 4. In the planning case, the migration cost is caused when a specific VM migrates to another PM. The number of migration during two unit times for best fit algorithm and FCFS algorithms is 4 and 5 times, while proposed VM allocation algorithms is 2 times. Moreover, the total cost is calculated that the VM migrates from one PM to another PM through the routers and switches. In other words, it is based on routing length of VM migration. The total cost of best fit and FCFS algorithm is 6 and 9 times, and the proposed VM allocation algorithm keeps 2 times. According to this planning case, we consider that the VM allocation algorithm achieves the minimum number of VM migration and the lowest total cost.

Table 4 Planning results
Full size table

4.3 Simulation results

The network structure in simulation is similar to [26]. We focus on the migration time and cost, including the insufficient resource of PM and VM. The used simulation parameters are shown as Table 5.

Table 5 Simulation parameters
Full size table

For the better explanation of proposed algorithm, we addtionally add a benchmark setting of Allocation algorithm in simulation, viz Benchmark. It evaluates the influence on the proportion of four types VM in Allocation algorithm. All of the simulation parameters in Benchmark and Allocation algorithm are same except the proportion of VM types. The proportion of VM types in Benchmark is 1:1:1:1, and it is 2:3:2:3 in Allocation algorithm.

In Fig. 10, the number of VM migration of four algorithms during 10 unit time is shown. The number of VM migration in a time period is calculated and recorded at each unit time. The proposed Allocation algorithm may not predict all the max requirement, because it just obtain the max value during the training course. The resource requirement of VMs may exceed the remained resource, so that the VM migration might be happened. Once the VM request appears, the FCFS and best fit algorithm allocate VMs to PMs immediately. It means that both algorithms do not consider the changeability and stablability of VMs. As the result, their VM migration numbers are severely higher than the proposed Allocation algorithm. The VM migration number of Benchmark and Allocation algorithm are much lower than best fit and FCFS algorithm. Both of them consider the maximum resource requirement through the training process, hence not only the migration times is quite low also the variability. The varition of Benchmark and Allocation algorithm is lower than the FCFS and best fit. Moreover, the Allocation algorithm is always slightly less than the Benchmark due to the uniform distribution on VM types. It means the Allocation algorithm can reduce migration times effectively, and the proportion of four types VMs does not highly influence on the result.

Fig. 10
figure 10

Simulation results of VM migration with varying time unit

Full size image

The total cost of four VM allocation methods is shown as Fig. 11. First of all, the definition of total cost should be defined and clarified. We only focus on the cost of VM migration. The cost is decided by the routing overhead, and caused by the notification of VM migration between two PMs. The proposed Allocation algorithm achieves the lower VM migration probability so that the amount of notification is also lower. Therefore, the total cost of proposed algorithm is much less than the FCFS and best fit algorithm.

Fig. 11
figure 11

Simulation results of total cost wiith varying time unit

Full size image

Because of the PM number is sufficient in this simulation, some PMs are awake to supply service for VMs and some are asleep. We denominate the awake PMs as active PMs, the result is shown in Fig. 12. The active PMs of Allocation algorithm is more than the best fit algorithm and FCFS algorithm. Although the active PMs are more than other algorithms in the beginning, we understand that the gap between them is decreasing with time increasing due to frequent VM migration. Both FCFS and best fit algorithm do not consider the characteristic of VMs, they only consider the remaining resource of PMs and the resource demand of VMs. Therefore, the unstable VMs may migrate frequently in FCFS and best fit algorithm. On the other hand, the active PM number of the proposed algorithm is higher than other algorithms. We consider that this weakness is acceptable. Because the numbers of active PM will increase with time in other two algorithms, but the proposed algorithm provides the better VM allocation result. It minimizes the probability of VM migration and the migration cost. In brief summary, we conclude that the proposed Allocation algorithm is a better method that balances the computing loading of VMs in cloud environments.

Fig. 12
figure 12

Simulation results of active PMs with varying time unit

Full size image

Then, we investigate the influence on number of VMs and migration times. The simulation parameters are same with Table 5. except the increasing number of VMs, and the number of PMs is fixed. The propotion of four types of VMs is 2:3:2:3 in this simulation. The results are shown as Figs. 13, 14 and 15.

Fig. 13
figure 13

Simulation results of VM migrartion with different VM number

Full size image
Fig. 14
figure 14

Simulation resuls of total cost with different VM number

Full size image
Fig. 15
figure 15

Simulation results of active PMs with different VM number

Full size image

The number of VM Migration with varying number of VMs is shown as Fig. 13. When the number of VMs is increasing, the propability of VM migration also increases. Both best fit and FCFS algorithm suffered from the unneccessary VM migration when the number of VMs increased, best fit algorithm especially. It is encouraged that the proposed VM Allocation algorithm keeps the lowest VM migration no matter what VM numbers. The total cost with varying number of VMs is shown as Fig. 14. and it has the similar tendency of the VM migration times. When the the number of VMs is increasing, the total cost is also increasing due to VM migration. It is obvious that the proposed VM Allocation algorithm is lower than best fit and FCFS algorithm. The Fig. 15 shows the influence of VM numbers on active PMs. The comprehensive result that the higher number of VMs leads to more active PMs. The proposed algorithm intends to balance the utilization between active PMs, thereby it is always higher than other two algorithms. However, we consider that it is acceptable due to the significant improvent on VM migration times and total cost. In summary, the proposed VM Allocation algorithm efficiently decrease the unnecessary VM migrations with the slightly additional PMs.

We examine the influence of different PM capacity, and the simulation results are shown as Figs. 16, 17 and 18. The numbers of VM and PM are same and fixed at 100. The proportion of four VM types is still 2:3:2:3. The number of VM migration is shown in Fig. 16. and the total cost is shown Fig. 17. No matter what kind of PM capacity, the proposed algorithm is always better than other algorithms. When the capacity of PM is set to 0.8, all of the three algorithms are downside on VM migration numbers and total cost. We found that the value of VM utilization in our simulation case is suitable for the higher PM capacity. In other words, each PM serves more VMs when the capacity value increases from 0.7 to 0.8. The number of active PMs is shown as Fig. 18. The proposed VM Allocation algorithm activates less PMs when the capacity of PM is lower than 0.8, but higher than other two alogorithms when it is 0.9. Because the proposed algorithm dedicate to balance the loading of PMs, it does not allocate the VMs to a PM if they are possible to migrate from this PM. In other words, the proposed algorithm considers the variance in VM utilization, rather the VM current requirement. We found that the capacity of PMs effects the allocation results defintely, and the proposed algorithm is better than other two algorithms in overall setting.

Fig. 16
figure 16

Simulation results of VM migration with different PM capacity

Full size image
Fig. 17
figure 17

Simulation results of total cost with different PM capacity

Full size image
Fig. 18
figure 18

Simulation results of active PMs with different PM capacity

Full size image

5 Conclusions

The social media services should be established with the well-defined infrastructure. In this paper, the VM migration problem in cloud data center is formulated based on mixed integer linear programming, and the VM Allocation algorithm is proposed to construct a stable, robust, balanced network. Moreover, we particularly focus on the VM migration. The proposed algorithm not only achieves the lower number of VM migration and total cost, but also balances the utilization between PMs. Furthermore, the proposed algorithm is verified in the simulation results, we believe that the constructed VMs and PMs are suitable for large scale data center.