Sage Journals: Discover world-class research

Abstract

With the rapid development of information technologies and the popularization of Internet applications, more and more companies and developers pay great attention to the cloud computing. As one of the most significant problems in cloud computing, virtual machine allocation has attracted significant attention. However, early studies usually ignore the load balance issue of the resources. In this article, we aim at multidimensional resource load balancing of all the physical machines in the cloud computing platform to maximize the utilization of resources. To achieve this goal, we leverage the ant colony optimization to design an efficient virtual machine allocation algorithm based on the NP-hard feature of this problem. Specifically, we customize the ant colony optimization in the context of virtual machine allocation and introduce an improved physical machine selection strategy to the basic ant colony optimization in order to prevent the premature convergence or falling into the local optima. Through extensive simulations, we demonstrate that our proposed algorithm can effectively achieve load balancing in virtual machine allocation and improve resource utilization for the cloud computing platform.

Keywords

Cloud computing load balance virtual machine allocation ant colony optimization pheromone

Introduction

Recently, cloud computing has emgerd as a cost-effective paradigm¹ due to its efficient sharing of resources and gained significant popularity. In cloud computing, one of the significant challenges is how to efficiently allocate virtual machines (VMs) with different kinds of resource demands, termed the VM allocation problem.

VM allocation has attained a lot of attention from the research groups in the last few years. Many related reviews and surveys have been made.^2,3 They usually perform the VM placement by live migration using dynamic threshold values⁴ or a layered progressive resource allocation algorithm for multi-tenant cloud data centers based on the multiple knapsack problem.⁵ However, they ignore the load balance of the multiple heterogeneous resources. Users’ different resource requests and the heterogeneity of physical resources make it hard to achieve load balancing and lead to a very low resource utilization. In fact, considering the NP-hardness⁶ of this problem and the practical online VM allocation context, it faces a dilemma of obtaining a suboptimal solution while just needing less time complexity. To address this problem, meta-heuristics emerges due to its smart iteration process and has been widely used in resource allocation problems. Common meta-heuristics include ant colony optimization (ACO),⁷ genetic algorithm (GA),⁸ particle swarm optimization (PSO) algorithm,⁹ and simulated annealing (SA) algorithm.¹⁰ Among many heuristics, we finally select the ACO technique in this study due to the following advantages:

ACO has strong robustness and therefore it can be widely used in many fields;

ACO has a good ability to search solutions, especially in the latter half of the algorithm;

For all ants in ACO, they can search solutions concurrently, which ensures good performance;

ACO can be easily combined with other heuristic algorithms to improve the performance.

In other studies, the ACO technique is widely used to achieve different goals in resource allocation, for example, to maximize the throughput of heterogeneous computing system in a study by Khan and Sharma¹¹ and to reduce energy consumption in a study by Feller et al.¹² In this article, we study VM allocation in the cloud computing platform, aiming at multidimensional resource load balancing of all the physical machines (PMs).

However, we encounter many challenges to be addressed when leveraging the ACO technique in VM allocation:

How to customize the parameters in ACO in our problem?

How to overcome premature or slow convergence when using ACO?

How to determine the value of each parameter of ACO in our problem?

To address the first challenge, we first construct a mathematical model to describe the problem where each feasible solution is represented by a matrix. In addition, an index called global load imbalanced degree, namely, imbalance degree (IBD), is proposed to quantitatively evaluate each solution.

To address the second challenge, we introduce a concept called PM selection expectation $ψ_{0}$ into the basic ACO to avoid the problems of premature convergence and slow convergence problems.

To address the third challenge, we determined the value of each parameter in ACO through a lot of experiments using the control variate method. Moreover, we also analyze the effect of each parameter. Finally, we compare the improved ACO proposed in this article with basic ACO, greedy algorithm, and other heuristic algorithms such as PSO and SA, which shows that improved algorithm can achieve better performance in terms of load balance and utilization.

Next, we summarize the key contributions of this article as follows:

We design a VM allocation algorithm based on ant colony optimization (VMA-ACO) to achieve load balancing of multidimensional resources in the cloud computing platform.

We introduce the concept of PM selection expectation into the algorithm to overcome the shortcomings of basic ACO.

We conducted extensive comparisons among our algorithm, the basic ACO, greedy algorithm, and other heuristic algorithms to demonstrate the efficiency of our proposed algorithm.

The outline of this article is as follows: section “Modeling and formulation” describes and models the problem and puts forward a method to evaluate each solution of this problem. Section “VM allocation based on ACO” presents our algorithm based on ACO. Our simulation results and analysis are presented in section “Experimental results.” An overview of the related work is presented in section “Related work.” Finally, section “Conclusion” presents the conclusion of this study.

Modeling and formulation

Problem description

A VM is an emulation of a particular computer system. In this article, we focus on system VMs, which provide a complete substitute for the targeted real machine and a level of functionality required for the execution of a complete operating system. A shared PM (or a hypervisor) uses native execution to manage hardware and multiple VMs, isolated from each other, can be executed on this shared PM.

VM allocation in the cloud computing platform can be described as follows: put $m$ VMs to $n$ PMs such that each VM obtains multiple resources such as CPU, memory, and bandwidth from one PM. Each VM can be represented as $VM = (V_{c}, V_{m}, V_{b})$ . Similarly, we use $H = (H_{c}, H_{m}, H_{b}, H_{cL}, H_{mL}, H_{bL})$ to denote each PM. The notations used to define VMs and PMs are listed in Table 1.

Table 1.

Notations.

Notation	Description
$V_{c}$	CPU cores requested by VM
$V_{m}$	Memory requested by VM (unit is MB)
$V_{b}$	Bandwidth requested by VM (unit is Gbit/s)
$H_{c}$	CPU cores held by PM
$H_{cL}$	CPU cores left in PM after allocation
$H_{m}$	Maximum memory held by PM
$H_{mL}$	Memory left in PM after allocation
$H_{b}$	Maximum bandwidth held by PM
$H_{bL}$	Bandwidth left in PM after allocation
$m$	Number of VMs
$n$	Number of PMs

VM: virtual machine; PM: physical machine.

All of the VMs can be represented by an array $VMs = (V M_{1}, V M_{2}, \dots, V M_{m})$ . All of the PMs can be represented by $Hosts = (H_{1}, H_{2}, \dots, H_{n})$ . We need to place all VMs into these PMs, each VM can only be allocated to one PM, and all resources requested by the VM should be satisfied. Resources of any PM cannot be overallocated.

To solve this issue, we need to find a mapping from VMs to PMs. Assuming that $S$ is a feasible solution to this problem, then $S = {S_{V_{i} H_{j}} | V_{i} \in VMs, H_{j} \in PMs}$ . Each $S_{V_{i} H_{j}}$ in $S$ should satisfy the constraint as follows

S_{V_{i} H_{j}} = {\begin{matrix} 1, if V_{i} is put to H_{j} \\ 0, otherwise \end{matrix}

(1)

Thus, S records the number of PMs on which each VM is allocated. It should satisfy the following equation

\sum_{j = 1}^{n} S_{V_{i} H_{j}} = 1

(2)

Performance metrics

For each feasible solution, we need to evaluate its quality and select the best one as the final solution. Load balancing is an important performance metric that measures the balance among each PM overloaded with computing clouds, tasks, or jobs. Through sharing loads across data center infrastructures, load balancing helps to achieve a proficient performance of the systems.¹³ For measuring the load balance of all PMs, we propose the definition of global load imbalance degree $(IBD)$ to quantitatively evaluate each solution as follows

IBD = \sum_{k = 1}^{n} {(u_{ck} - u_{\bar{c}})}^{2} + \sum_{k = 1}^{n} {(u_{mk} - u_{\bar{m}})}^{2} + \sum_{k = 1}^{n} {(u_{bk} - u_{\bar{b}})}^{2}

(3)

where $u_{ck}$ , $u_{mk}$ , and $u_{bk}$ represent the CPU, memory, and bandwidth utilization rates of the $k th$ PM, respectively. Here, $u_{\bar{c}}$ , $u_{\bar{m}}$ , and $u_{\bar{b}}$ represent the average utilization rates of CPU, memory, and bandwidth of all PMs, respectively. In a similar work, Fang and Qu¹⁴ propose a metric called outer load balancing degree (OBD) to reflect the degree of load balancing among the PMs. Gao et al.¹⁵ propose a resource wastage model to minimize the total resource wastage and fully utilize multidimensional resources. Kumar and Raza¹⁶ and Ma et al.¹⁷ also use the resource wastage model to optimize resource utilization. The important parameters of these metrics include the average multi-dimension utilization rate of all PMs and each dimension utilization rate of each PM.

And even in Amazon EC2, CPU, memory, and network usage are the important metrics to measure VMs.¹⁸ We take all the metrics into consideration and propose IBD in order to find the appropriate allocation for each VM to balance multi-dimensional resource usage of all PMs. In this way, we can avoid the situation in which some of the PMs are overloaded, but the others are not used. The commercial cloud providers face more complex problems in reality; therefore, they would take more metrics into consideration including the CPU, memory, and network, but we also believe that the metrics like IBD will be used in the future due to the following three reasons: (1) IBD can work well in the elastic design; (2) IBD can also be used in the migration of VM to rebalance the whole cluster; and (3) the calculation method of IBD can naturally accommodate other influencing factors in order to cover more complex scenes, thus providing more profit for commercial cloud providers.

According to the definition of $IBD$ , a smaller $IBD$ means a better feasible solution. In this article, we would like to obtain a solution with minimum $IBD$ using the algorithm based on ACO.

VM allocation based on ACO

Beloglazov et al.¹⁹ considered that the VM allocation problem can be seen as a bin packing problem with variable bin sizes and prices. Since bin packing is known to be NP-hard in the strong sense,²⁰ VM allocation in the cloud computing platform is also NP-hard in the strong sense. To address such issues, heuristic algorithms are commonly used in order to reduce the time complexity. In this study, we employ the ACO to solve such a problem. In addition, we also introduce an improved policy into the algorithm to avoid falling into the local optimal solution or slow convergence. First, we need to introduce the basic ACO technique.

Basic ACO

In the real world, ants can always find the best path from their nest to food when they are foraging. The reason lies in that real ants will release pheromone while they are moving. And the other ants’ action will be affected by the concentration of pheromone. A large number of ants can form a positive feedback during their traveling. Finally, the best path can be selected. Inspired by the real ants’ behavior, ACO is proposed to mimic the behavior of the real ants.²¹

Customizing ACO in our problem

In one iteration, each ant starts from a random VM and then allocates a VM to a PM one by one. It takes $m$ steps for an ant to complete the allocation. All ants can execute this job in parallel, which can greatly improve performance. When an ant is ready to allocate a VM to a PM, we will calculate each probability $p_{ij}$ as follows

p_{i j} = {\begin{matrix} 0, & i f H_{j} d o e s n o t h a v e e n o u g h r e s o u r c e s f o r V_{i} \\ \frac{ι_{i j}^{α} \cdot η_{i j}^{β}}{\sum_{k = 1}^{n} ι_{i k}^{α} \cdot η_{i k}^{β}}, & o t h e r w i s e \end{matrix}

(4)

where $ι_{ij}$ is the pheromone in the path from $V_{i}$ to $H_{j}$ , which means that the ant prefers $H_{j}$ to place $V_{i}$ in the previous iterations if $ι_{ij}$ is bigger, and $η_{ij}$ is the visibility, which represents the tendency to allocate $V_{i}$ in $H_{j}$ from the perspective of the ant itself. In this article, we introduce the concept of suitability between VM and PM $fi t_{ij}$ to compute $η_{ij}$

η_{ij} = \frac{1}{fi t_{ij}}

(5)

fi t_{ij} = (r_{c_{ij}} - {\bar{r}}_{ij})^{2} + (r_{m_{ij}} - {\bar{r}}_{ij})^{2} + (r_{b_{ij}} - {\bar{r}}_{ij})^{2}

(6)

{\bar{r}}_{ij} = \frac{r_{c_{ij}} + r_{m_{ij}} + r_{b_{ij}}}{3}

(7)

where $r_{c_{ij}}$ , $r_{m_{ij}}$ , and $r_{b_{ij}}$ denote the CPU, memory, and bandwidth accounted for the proportion of the remaining resources in PM, respectively. The larger value of $η_{ij}$ indicates that the ant allocates more tendency to $V_{i}$ in $H_{j}$ . $α$ and $β$ denote the importance of pheromone and visibility, respectively, in the calculation.

In the real-world applications of VMs, the demands of memory and bandwidth may change over time. To simulate such environment, we assume that such demands satisfy the uniform distribution. Therefore, we can express the interval using $[u^{*} (1 - σ), {u_{i}}^{*} (1 + σ)]$ , where $u_{i}$ denotes the average resource utilization of $V_{i}$ and $σ$ denotes the standard deviation in uniform distribution. Therefore, we can take the mean value into consideration.

At first, we will select a PM with maximum $p_{ij}$ to allocate the VM. However, we find that the algorithm falls into the local optima quickly. To address this issue, we improved the PM selection policy. See subsection “Expectation optimization–based improved policy.”

When one iteration is completed, we need to update the global pheromone. We can get $m$ allocation strategies after each iteration and calculate $IBD$ for each feasible solution. Assume that the allocation with minimum $IBD$ in this iteration is $alo c_{k}$ ; then we compare $alo c_{k}$ with the best deployment $alo c_{best}$ so far. If $IB D_{k} < IB D_{best}$ , we will replace $alo c_{best}$ with $alo c_{k}$ and $IB D_{best}$ with $IB D_{k}$ . The pheromone will be updated as follows

ι_{ij} = {\begin{matrix} (1 - ρ)^{*} ι_{ij} + ρ^{*} (\frac{1}{IB D_{best}}), V_{i} is placed in H_{j} \\ (1 - ρ)^{*} ι_{ij}, otherwise \end{matrix}

(8)

where $ρ$ denotes the global pheromone evaporation coefficient and $1 - ρ$ is the global pheromone residual coefficient.

Before calculating the pheromone, we need to initialize it when the algorithm starts. In this article, we will put $V_{i}$ in $H_{j}$ , the $fi t_{ij}$ value of which is minimum one by one. Then we will calculate the initial load imbalance degree $IB D_{init}$ , and the initial pheromone is shown as follows

ι_{init} = \frac{1}{IB D_{init}}

(9)

Expectation optimization–based improved policy

In the PM selection policy mentioned above, it always selects a PM with maximum $p_{ij}$ . However, it will result in that the algorithm may fall into the local optima quickly. To address this issue, we try to randomly select a PM for which $p_{ij} > 0$ . However, it may bring a new drawback: the algorithm gets a very slow convergence. In order to overcome these two problems, we introduce a concept called PM selection expectation $ψ_{0} (0 \leq ψ_{0} \leq 1)$ . For each time of selecting a PM, a random number $ψ (0 \leq ψ \leq 1)$ will be generated and we select a PM according to the policy below

select physical machine {\begin{matrix} with \max p_{i, j}, if ψ < ψ_{0} \\ whose p_{i, j} > 0, otherwise \end{matrix}

(10)

We can easily control the convergence rate of the algorithm using $ψ_{0}$ . A larger value of $ψ_{0}$ will make the ants more inclined to choose a PM with maximum $p_{ij}$ , and the algorithm is more likely to fall into the local optimum. A smaller value of $ψ_{0}$ will result in an opposite effect.

The VM allocation algorithm based on ACO with the improved policy can be described in Algorithm 1 and the flowchart is shown in Figure 1.

Algorithm 1. Virtual machine allocation algorithm based on ant colony optimization.
1. Get initial pheromone.
2. Input $m$ ants.
3. for each iteration I do
4. for each ant $an t_{k}$ do
5. for each virtual machine $V_{i}$ do
6. Place $V_{i}$ to $H_{j}$ according to Physical Machine Selection Policy.
7. end for
8. Calculate $IB D_{k}$ according to the placement of $an t_{k}$ .
9. end for
10. Update the best allocation $alo c_{best}$ and update global pheromone according to Global Pheromone Update Policy.
11. end for
12. Output the best allocation and its $IB D_{best}$ .

Figure 1.

The flowchart of advanced ACO.

At the beginning of the algorithm, it needs to initialize $m$ ants, where $m$ represents the amount of VMs. Each ant contains a copy of information of all VMs and PMs. The ACO consists of multiple iterations. In each iteration, each ant will put all VMs to PMs according to PM selection policy. When an iteration is completed, we will update the global pheromone. The algorithm ends when all iterations are completed and we will obtain the final solution.

Time complexity analysis

The time complexity of initialization is denoted by $O ({| PMs |}^{*} | VMs |)$ . In each iteration, it costs ${| PMs |}^{*} | VMs |$ number of steps to allocate all VMs in each iteration for each ant. Therefore, the time complexity of allocating VMs in each iteration is $O ({| PMs |}^{*} {| VMs |}^{2})$ . In addition, we need to update pheromone after each iteration, the time complexity of which is $O ({| PMs |}^{*} | VMs |)$ . In this article, the maximum iteration number is $MI$ . Thus, the VM allocation algorithm based on ACO is a polynomial-time algorithm with the complexity $O ({| PMs |}^{*} | VMs | + {MI}^{*} ({| PMs |}^{*} {| VMs |}^{2} + {| PMs |}^{*} | VMs |))$ .

Experimental results

Experimental setup

There are serval parameters in this algorithm. In this section, we set the value of each parameter through experiments to achieve better performance. We generate 20 PMs and 100 VMs as the input. Their hardware configurations are shown in Tables 2 and 3. In the experiment, if some VM requests cannot be satisfied, we would reject these requests.

Table 2.

Physical machines.

CPU (core)	Memory (GB)	Bandwidth (Mbit)	Number
16	32	1000	10
24	64	1000	10

Table 3.

Virtual machines.

CPU (core)	Memory (GB)	Bandwidth (Mbit)	Number
1	1	0	5
1	1	10	5
1	2	0	5
1	2	10	5
1	4	0	2
1	4	10	3
2	1	0	2
2	1	10	3
2	2	10	10
2	2	20	10
2	4	10	10
2	4	20	10
4	4	20	10
4	4	50	10
4	8	50	5
8	8	100	5

There are five parameters in this algorithm, that is, $α$ , $β$ , $ρ$ , $ψ_{0}$ , and $σ$ . We always set $σ$ to 0.2. As for the other parameters, we conduct several simulation experiments to adjust the value. While doing these experiments, we just modify the related parameters and keep the other parameters constant. Through these experiments, we also analyze the impact of each parameter.

Experimental results

Comparison to prior art

In this section, we compare our algorithm VMA-ACO with basic ACO and greedy algorithm to evaluate the effectiveness of the algorithm. We test two kinds of basic ant colony algorithms: one is with $ψ_{0} = 1$ , which means that ants will always select PM with maximal $p_{ij}$ and the other one is with $ψ_{0} = 0$ , which means that ants will only randomly select a PM for which $p_{ij} > 0$ to allocate a VM. In greedy algorithm, we use the suitability between VM and PM $fi t_{ij}$ as the greedy policy, and ants will place VM in PM with minimum $fi t_{ij}$ . For these four algorithms, we use the global imbalance degree $IBD$ as the evaluation index, and a smaller $IBD$ means a better performance on load balancing. All of the experimental results showed that the demands of all VMs can be satisfied.

Figure 2 shows the changes of $IBD$ in each iteration. In basic ACO where $ψ_{0} = 1$ , the $IBD$ gets convergence fastest (in the 50th iteration). And the $IBD$ does not get convergence until the 180th iteration in basic ACO for which $ψ_{0} = 0$ . In improved ACO, the $IBD$ gets convergence in nearly the 110th iteration and it gets the minimal $IBD$ .

Figure 2.

The changes of $IBD$ in each iteration.

Figure 3 shows the final $IBD$ of the four compared algorithms. In Figure 3, we can see that ACO can effectively address the problem of VM allocation in the cloud computing platform, and ACO developed in this article can achieve 30% performance improvement compared with basic ACO.

Figure 3.

The final $IBD$ of the four algorithms.

Parameter sensitivity

We first test the impact of different combinations of $α$ and $β$ in the algorithm. From Figure 4, we can see that the larger the $α$ value is, the more likely the algorithm is to fall into the local optimal solution, because ants prefer to search solutions according to the previous experience. On the other hand, a larger $β$ makes the ants prefer to search solutions according to the suitability between VM and PM, which leads to slow convergence for the algorithm.

Figure 4.

The impact of $α$ and $β$ .

Figure 5 shows the impact of $ρ$ on algorithm performance. It is easy to find from the figure that the algorithm converges sooner with a larger $ρ$ , because the pheromone accumulates sooner on the optimal path.

Figure 5.

The impact of $ρ$ .

Figure 6 depicts the effect of PM selection expectation $ψ_{0}$ . We introduce $ψ_{0}$ to control the convergence rate and we can see that a larger $ψ_{0}$ makes the algorithm converge faster.

Figure 6.

The impact of $ψ_{0}$ .

To achieve the best performance of the algorithm, after these experiments, we finally set the four parameters with the values shown in Table 4.

Table 4.

Parameter values used in our algorithm.

$α$	$β$	$ρ$	$ψ_{0}$
0.3	0.7	0.2	0.8

Comparisons of different algorithms

As mentioned above, we have compared basic ACO with our algorithm VMA-ACO and evaluate the impact of different parameters. In order to verify the effectiveness of the proposed algorithm, we further compared it with two classic algorithms, that is, worst fit (WF) algorithm and best fit (BF) algorithm, and two heuristic algorithms, that is, PSO ¹⁶ and improved simulated annealing (ISA) algorithm.²² The PSO focuses on efficient VM allocation to physical servers in order to minimize the total resource wastage. The ISA focuses on improving resource utilization rate in cloud data center. We use the same input mentioned above. The experimental results are shown as follows:

In this experiment, there are three kinds of intelligent algorithms including VMA-ACO, ISA, and PSO. Therefore, it is necessary to determine the values of parameters of the three algorithms. In VMA-ACO, we use the parameter values shown in Table 4 and VMA-ACO performs best under these conditions. In ISA, we should take four main parameters into consideration including T₀, T_final, Step1_max, and Step2_max. We set T₀ to 10,000 and T_final to 0.3. This is a common practice in many classic SA algorithms. And in order to achieve better performance and faster convergence, we set Step1_max to 20 and Step2_max to 5. To facilitate fair comparison, we set the iteration numbers and the number of particles of PSO and ants of VMA-ACO with the same value, which are 200 and 500, respectively.

Figure 7 indicates that VMA-ACO performs best on the objective IBD and the value is around 0.3. BF performs relatively poor on the IBD. WF performs worst and we do not illustrate it for the sake of clarity in this figure. VMA-ACO performs better than WF and BF since in the evaluation process VMA-ACO can achieve a better solution. There is little difference between ISA and PSO in terms of the IBD value. They are only around 0.68 and 0.6, respectively. VMA-ACO also performs best, compared to PSO and ISA. This is expected because in VMA-ACO we introduce a concept called PM selection expectation into basic ACO to avoid falling into the local optima quickly and achieve a very slow convergence. These simulation experiments show that our proposed VMA-ACO can achieve better performance compared to the state-of-the-art algorithms.

Figure 7.

The final $IBD$ of the state-of-the-art algorithms.

Related work

VM allocation is a key problem in the cloud computing platform. It has gained a lot of attention from researchers. VM allocation is an NP-hard problem,^23,24 and classic scheduling algorithms like “first-in first-out (FIFO)” and “round robin (RR)” are not efficient in solving such a problem. In order to reduce the time complexity and get an ideal solution, many heuristics are employed, which replace the global optimal solution with the suboptimal solution. Common heuristics include ACO,⁷ GA,⁸ PSO,⁹ and SA¹⁰ algorithms.

For example, S Pandey et al.²⁵ designed a heuristic method based on PSO for task scheduling in cloud computing, taking into account both computational cost and data transmission cost as the main objectives. S Banerjee et al.²⁶ designed a modified ant colony framework for diversified service allocation and scheduling mechanisms in the cloud environment, the objective of which is to maximize the scheduling throughput to service all the diversified requests. Heuristics are also used in the studies by Goiri et al.,²⁷ Liu et al.,²⁸ and so on.

Among these heuristics, ACO has many advantages as given below compared with other heuristics. Considering the NP-hard feature in VM allocation and the advantages of ACO, we use ACO to solve the problem in this study.

There is a lot of research on ACO to achieve different goals in cloud computing. For example, K Nishant et al.²⁹ developed an improved ACO in which local pheromone update policy is used to obtain the target of load balancing. Khan and Sharma¹¹ put forward an algorithm based on ACO framework to maximize the throughput of heterogeneous computing systems. This algorithm modifies the basic pheromone updating formula and gives better utilization of resources but the computational overhead is high. An algorithm based on ACO is presented in a study by Feller et al.¹² which considers VM allocation as a multidimensional bin packing problem. This approach tries to place all items in the minimum number of bins and reduce energy consumption in cloud computing.

In this article, we mainly focus on the goal of load balancing of multidimensional resource utilization, which is significant for the cloud computing platform to provide service-level agreement (SLA) guarantee of multiple resources. However, premature convergence also exists in ACO like other heuristics, and ACO is sensitive to the initial parameters. These two problems are also resolved in this study by introducing PM selection expectation and setting each parameter carefully by many simulations.

Conclusion

VM allocation is one of the significant challenges in the cloud computing platform. In this article, we focus on how to achieve the goal of load balancing of multi-dimensional resources. Specifically, we first establish a mathematical model for this problem. Based on this model, we then address this problem by leveraging the ACO technique. We also design two strategies to further improve the ACO by proposing the concept of load imbalance degree and introducing PM selection expectation. Simulation experiments show that our proposed ACO-based algorithm can achieve better performance compared to the basic ACO technique and other state-of-the-art algorithms.

Footnotes

Handling Editor: Antonio Puliafito

Declaration of conflicting interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author(s) disclosed receipt of the following financial support for the research, authorship, and/or publication of this article: This work was supported by the National Natural Science Foundation of China (U1534201).

References

Wikipedia. Cloud computing, http://en.wikipedia.org/wiki/Cloudcomputing

Usmani

Singh

. A survey of virtual machine placement techniques in a cloud data center. Procedia Comput Sci 2016; 78: 491–498.

Rathod

. A survey on different virtual machine placement algorithms. Int J Adv Res Comput Sci Manage Stud 2014; 2(2): 266–271.

Choudhary

Rana

Matahai

. A critical analysis of energy efficient virtual machine placement techniques and its optimization in a cloud computing environment. Procedia Comput Sci 2016; 78: 132–138.

et al . Efficient multi-tenant virtual machine allocation in cloud data centers. Tsinghua Sci Technol 2015; 20(1): 81–89.

Gary

Johnson

. Computers and intractability: a guide to the theory of NP-completeness. New York: W. H. Freeman and Company, 1979.

Dorigo

Maniezzo

Colorni

. Ant system: optimization by a colony of cooperating agents. IEEE T Syst Man Cy B 1996; 26(1): 29–41.

Holland

. Adaptation in natural and artificial systems: an introductory analysis with applications to biology, control, and artificial intelligence. Ann Arbor, MI: University of Michigan Press, 1975.

Kennedy

. Particle swarm optimization. In: Sammut

Webb

(eds) Encyclopedia of machine learning. Berlin: Springer, 2011, pp.760–766.

10.

Bertsimas

Tsitsiklis

. Simulated annealing. Stat Sci 1993; 8(1): 10–15.

11.

Khan

Sharma

. Ant colony optimization for effective load balancing in cloud computing. Int J Emerg Trends Technol Comput Sci 2013; 2: 77–82.

12.

Feller

Rilling

Morin

. Energy-aware ant colony based workload placement in clouds. In: Proceedings of the 2011 IEEE/ACM 12th international conference on grid computing, Lyon, 21–23 September 2011, pp.26–33. New York: IEEE.

13.

Al Nuaimi

Mohamed

Al Nuaimi

et al . A survey of load balancing in cloud computing: challenges and algorithms. In: Proceedings of the 2012 second symposium on network cloud computing and applications (NCCA), London, 3–4 December 2012, pp.137–142. New York: IEEE.

14.

Fang

B-B

. Multi-objective virtual machine placement for load balancing. ITM Web Conf 2017; 11: 01011.

15.

Gao

Guan

et al . A multi-objective ant colony system algorithm for virtual machine placement in cloud computing. J Comput Syst Sci 2013; 79(8): 1230–1242.

16.

Kumar

Raza

. A PSO based VM resource scheduling model for cloud computing. In: Proceedings of the 2015 IEEE international conference on computational intelligence communication technology, Ghaziabad, India, 13–14 February 2015, pp.213–219. New York: IEEE.

17.

Liu

Liw

. Multi-objective optimization for initial virtual machine placement in cloud data center. J Inform Comput Sci 2012; 9(16): 5029–5038.

18.

Amazon. Amazon CloudWatch, https://docs.aws.amazon.com/AmazonCloudWatch/latest/monitoring/ec2-metricscollected.html

19.

Beloglazov

Abawajy

Buyya

. Energy-aware resource allocation heuristics for efficient management of data centers for cloud computing. Future Gener Comp Sy 2012; 28(5): 755–768.

20.

Martello

Toth

. Knapsack problems: algorithms and computer implementations. Hoboken, NJ: John Wiley & Sons, 1990.

21.

Dorigo

Birattari

Stutzle

. Ant colony optimization. IEEE Comput Intell M 2006; 1(4): 28–39.

22.

Shi

Chen

et al . Research on virtual machine placement in the cloud based on improved simulated annealing algorithm. In: Proceedings of the 2016 World Automation Congress (WAC), Rio Grande, PR, 31 July–4 August 2016, pp.1–7. New York: IEEE.

23.

Nguyen

Van H

Dang

Tran F

Menaud

M. Autonomic virtual resource management for service hosting platforms. In: Proceedings of the 2009 ICSE workshop on software engineering challenges of cloud computing, Vancouver, BC, Canada, 23 May 2009, pp.1–8. New York: IEEE.

24.

Hyser

Mckee

Gardner

et al . Autonomic virtual machine placement in the data center. Technical report no. HPL-2007-189, 26 February 2008. Palo Alto, CA: Hewlett Packard Laboratories, pp.2007–2189.

25.

Pandey

Guru

et al . A particle swarm optimization-based heuristic for scheduling workflow applications in cloud computing environments. In: Proceedings of the 2010 24th IEEE international conference on advanced information networking and applications, Perth, WA, Australia, 20–23 April 2010, pp.400–407. New York: IEEE.

26.

Banerjee

Mukherjee

Mahanti

. Cloud computing initiative using modified ant colony framework. World Acad Sci Eng Technol 2009; 56: 221–224.

27.

Goiri

Julia

Nou

et al . Energy-aware scheduling in virtualized datacenters. In: Proceedings of the 2010 IEEE international conference on cluster computing, Heraklion, 20–24 September 2010, pp.58–67. New York: IEEE.

28.

Liu

Wang

Liu

et al . GreenCloud: a new architecture for green data center. In: Proceedings of the 6th international conference industry session on autonomic computing and communications industry session, pp.29–38. New York: ACM, http://cse.unl.edu/∼ylu/csce896/papers/p29-liu.pdf

29.

Nishant

Sharma

Krishna

et al . Load balancing of nodes in cloud using ant colony optimization. In: Proceedings of the 2012 UKSim 14th international conference on computer modelling and simulation (UKSim), Cambridge, 28–30 March 2012, pp.3–8. New York: IEEE.

CPU (core)	Memory (GB)	Bandwidth (Mbit)	Number
1	1	0	5
1	1	10	5
1	2	0	5
1	2	10	5
1	4	0	2
1	4	10	3
2	1	0	2
2	1	10	3
2	2	10	10
2	2	20	10
2	4	10	10
2	4	20	10
4	4	20	10
4	4	50	10
4	8	50	5
8	8	100	5

CPU (core)	Memory (GB)	Bandwidth (Mbit)	Number
1	1	0	5
1	1	10	5
1	2	0	5
1	2	10	5
1	4	0	2
1	4	10	3
2	1	0	2
2	1	10	3
2	2	10	10
2	2	20	10
2	4	10	10
2	4	20	10
4	4	20	10
4	4	50	10
4	8	50	5
8	8	100	5

An efficient load balancing algorithm for virtual machine allocation based on ant colony optimization

Abstract

Keywords

Introduction

Modeling and formulation

Problem description

Performance metrics

VM allocation based on ACO

Basic ACO

Customizing ACO in our problem

Expectation optimization–based improved policy

Time complexity analysis

Experimental results

Experimental setup

Experimental results

Comparison to prior art

Parameter sensitivity

Comparisons of different algorithms

Related work

Conclusion

Footnotes

Declaration of conflicting interests

Funding

References

CPU (core)	Memory (GB)	Bandwidth (Mbit)	Number
1	1	0	5
1	1	10	5
1	2	0	5
1	2	10	5
1	4	0	2
1	4	10	3
2	1	0	2
2	1	10	3
2	2	10	10
2	2	20	10
2	4	10	10
2	4	20	10
4	4	20	10
4	4	50	10
4	8	50	5
8	8	100	5