A Load-Balancing Approach Using an Improved Simulated Annealing Algorithm

1. Introduction

Cloud computing is an emerging technology that, soon after its introduction, has become a pillar of the Internet of Everything (IoE) due to the fast advancement of communication technology. It provides a flexible and cost-effective solution for many services through the Internet. Cloud computing offers multiple services to the user [1-8] and resulted in an exponential user growth that exposed a weak cloud resources management. These resources are in the virtual form, which is the most important characteristic of the cloud system.

Subsisting to the user’s needs is very complex and can impact the overall performance of the cloud. Therefore, load balancing was given more attention by multiple researchers. Some load-balancing technics were proposed, but the fast growth of the cloud made them obsolete and no longer able to offer a good load-balancing solution.

This article suggests an improved usage of the meta-heuristic “simulated annealing (SA)” to ensure a better load balancing between a data center’s virtual machines (VMs) in order to ensure a greater quality of service (QoS) and to maximize the use of the provided resources.

We structured our article as follows. In Section 2, we will briefly discuss the previous load-balancing approaches. We will then present our approach in Section 3. Afterward, we will compare the results of our approach, after being implemented into the CloudSim simulator, with other load balancers in Section 4. Finally, in Section 5, we will conclude our findings.

2. State of the Art

Multiple load-balancing approaches were proposed in [9,10]. We will briefly present some of them while exposing their flaws which rendered them unable to balance the workload between VMs. Then, we will proceed by presenting some meta-heuristic approaches in a way that explains our meta-heuristic choice.

2.1 Load Balancers

Load balancers are used to improve task distribution between the VMs. In this section, we will briefly present some load-balancing approaches that were proposed in [10].

2.1.1 General algorithm-based category

Also known as the classical category, this category contains all the classical algorithms, such as round robin (RR) [11], weighted round robin [10], least-connection [12], and weighted least-connection [13]. It also includes load-balancing algorithms that do not need the cloud’s architecture to operate. Some of these algorithms include trust management [14], cloud-friendly load balancing [15], two-phase load balancing [16], and stochastic hill climbing [17].

We will now proceed by explaining the algorithms stated above.

Round robin: RR is a process-scheduling algorithm based on the first come first served (FCFS) algorithm [18] that cyclically execute a process from the queue in a defined time limit. Overall, it is a good algorithm, but it does not have control over the workload distribution.

Weighted round robin: Weighted RR is a scheduling algorithm that adds weight to nodes depending on their CPU capacity. It helps the algorithm by allocating more requests to the server with high capacity. Similar to RR, weighted RR assigns requests to the node cyclically. The only difference is that nodes with higher specifications are given more requests.

Least-connection: This algorithm classifies the nodes by taking into consideration the number of connections between each node. The node with fewer connections will be given new requests. This method is the default method because it provides the best performance.

Weighted least-connection: Like least-connection, this algorithm calculates the connections of each node. Then, it adds the weight parameter to each node depending on its hardware. Weighted least-connection attributes new workloads to servers based on both the node’s connections and its weight.

Trust management: The main idea behind this approach is to propose a VM Manager with adequate characteristics, which will improve resource utilization and decrease the system’s response time. This approach supports both the load balancing between VMs and VMs’ migration. It also offers a better QoS for cloud computing. In this research, however, only a theoretical approach was proposed.

Cloud-friendly load balancing: This approach aims at decreasing the execution time of requests by migrating an object from a virtualized environment with interfering jobs and will also reduce the energy consumption to a lower value. However, this approach causes bottlenecking of the system due to the lack of fault tolerance.

Two-phase load balancing: This approach uses both the opportunistic load balancing and load balancing min-min scheduling algorithms in order to maintain the load balancing of the system while minimizing the execution time. No implementation of the proposed approach was provided.

Stochastic hill-climbing: This approach is based on the hill-climbing approach but with a random uphill move instead of the steepest. It offers better load-distribution management in cloud computing. This approach offers better performance in comparison with other algorithms. The only drawback of this approach is the lack of resource utilization, which is illustrated by the fact that this approach uses only one node.

2.1.2 Architectural-based category

Algorithms that require an architectural environment in order to operate, such as cloud partition load balancing [19], VM-based two-dimensional load management [20], DAIRS [21], and THOPSIS [22] are grouped in this category.

A brief presentation of each algorithm stated above will be provided in the following:

Cloud partition load balancing: A cloud partition is a model used to manage a large cloud. Basically, a cloud partition is a cloud infrastructure divided based on geographical locations. With the help of the main controller, the requests can be assigned to the nodes that are underloaded, thus improving the cloud’s performances. This approach is still in the theoretical state.

VM-based two-dimensional load management: This approach uses restraints on both requests and nodes based on their metrics while scheduling in order to reduce the requests’ migration. It provides a good task allocation. This algorithm lacks resources utilization

DAIRS: In order to provide better task scheduling, this algorithm considers all of the nodes’ metrics and the different queues in the system. This approach outperforms similar approaches, yet it is not suitable for deployment due to the fact that it is a centralized approach.

THOPSIS: This approach achieves better load balancing in a data center while reducing the VM migration rate by selecting which VM should migrate to a new physical machine and which physical machine should host it. By doing so, the physical machines are kept from being under- and over-loaded while using all of their parameters. Unfortunately, this approach provides a limited QoS to the SLA criteria.

2.1.3 Artificial intelligence-based category

This category contains all load balancers that use an artificial intelligence (AI) approach in order to provide a better load balancing. Some of these algorithms can be classified into the architecture-based category. We will proceed by briefly presenting some of the well-known AI-based algorithm, such as Bee-MMT [23] and ant colony optimization [24].

Bee-MMT: Bee-MMT is a variant of the bee colony algorithm that improves migration time while decreasing the power consumption by using VM migration. The only drawback of this algorithm is its complexity, which makes it more difficult to implement in other systems.

Ant colony optimization: Developed after multiple studies on the behavior of ants while looking for food, this algorithm’s main purpose is to find the shortest path. In other words, it is able to accurately determinate the state of each node. By doing so, it prevents having overloaded and underloaded nodes. The only drawback of this algorithm is its low throughput.

2.2 Meta-Heuristics Algorithms

Meta-heuristic algorithms are robust and known for being able to solve NP-hard and complex problems. Many searchers reached the conclusion that using a meta-heuristic approach instead of a classical optimization one helps to provide a better solution to the load balancing in cloud computing [25]. In the following text, we will briefly present some known meta-heuristics while also presenting and explaining the meta-heuristic used in our approach:

2.2.1 Tabu search

Tabu search is a metaheuristic approach that operates as follows. Initially, the algorithm will choose a random solution to the problem. Then, after a local scan to neighboring solutions, it chooses the best one as the optimal solution at a given time. Using a short-term memory formed by the previously visited solutions, it will avoid making loops on the same solutions by constantly checking the memory [26,27].

2.2.2 Genetic algorithm

The genetic algorithm is a meta-heuristic based on the evolution principle. It aims at finding the global solution of an optimization problem. Initially, the algorithm randomizes a solution that converges to the global minima after some evaluations with the objective function [28].

2.2.3 Bat algorithm

Based on a bat’s sense of echolocation, the Bat algorithm aims at reducing the iterations while looking for the best solution of a given problem and trying to provide the advantages of other algorithms [29].

2.2.4 Simulated annealing

Based on the physical annealing process where a material is processed in order to achieve a uniform structure, Simulated annealing solves complex optimization problems. The main advantage that this algorithm has over other meta-heuristics is its large error margin. In other words, SA is known for finding the global solution of a given NP-hard problem [30]. This margin error is defined as the acceptance probability, P, which allows SA to avoid local solutions. The acceptance probability is defined as follows:

where E defines the energy variation of the material at different time-lapses and T is the temperature. Initially, T has a high value and will slowly decrease in every iteration. SA accepts poor solutions in order to find the global solution [31]. Below, the pseudo-code of SA will be presented [32]:

Initialize the system configuration;

Initialize s as the initial state;

Initialize T with a large value;

Initialize N the number of iterations;

Initialize t the temperature change counter with 0;

Repeat

Initialize n the repetition counter with 0;

Repeat:

Generate [TeX:] $$\mathbf{s}^{\prime}=\mathbf{s}+\Delta \mathbf{s}$$ a neighbor state of s;

Evaluate [TeX:] $$\Delta \mathrm{E}=\mathrm{E}(\mathrm{s})-\mathrm{E}\left(\mathrm{s}^{\prime}\right):$$

Generate [TeX:] $$P=e^{-\Delta E / T}$$ the acceptance probability of s;

Generate R = random (0,1) the acceptance probability of s';

if [TeX:] $$\Delta \mathrm{E}(\mathrm{s})<0$$

keep s as the actual state;

else if [TeX:] $$R>P$$

s' is the new state;

Increment n by 1 until reaching N;

Increment n by 1 until reaching N;

Increment t by 1 until reaching T;

Stop;

As presented above, the main criteria that made us choose SA in order to develop our approach are its ability to find global optima. It is also easily implemented, flexible, and is able to solve nonlinear problems efficiently.

The only issue with the classical SA approach is the huge amount of iterations required to reach the best solution. In the following section, we will explain the part that we added to the SA to make it faster while keeping its capacity to reach the global solution.

3. Contribution

Multiple load balancer studies lead us to the following conclusion: QoS management is still lacking due to the fact that the metrics of tasks and VMs are not fully used while managing the workload. Different approaches were proposed to provide better load balancing while taking into consideration both the state of a VM and the task’s parameters [33-36]. Following these approaches, we propose our load balancer based on several parameters which influence the normal unfolding of the burden-sharing and the allowance of the tasks between the VMs of a data center.

We chose to collaborate with the research carried out by [37]. This choice has as the main aim of the inclusion of the VMs’ characteristics as input parameters—in addition to the tasks’—to provide a better task allocation to those VMs.

This approach can be described as follows:

Each VM possesses a metric dependent on the number of cores it has, called MIPS [37], which can be defined as “million instructions per second”.

In order for a task to be executed, some instructions need to be computed that are also known as the task’s length (TL) [37].

We define the strip length, S, defined in (2) below, of each VM as the optimal number of tasks it can support before being classified as overloaded. It is illustrated by the following equation:

Even if we estimated the strip length of each VM at a given time, the tasks’ allocation is still not optimized [36].

Thanks to the strip length, we are now one step closer from providing a satisfactory load balancer.

In the next step, we will introduce the meta-heuristic SA to provide better tasks’ allocation. The modifications that we are proposing are as follows:

- Initialize E(i) from (1) as [TeX:] $$\mathrm{E}(\mathrm{i})=\mathrm{MIPS}_{i}-\mathrm{TL}_{\mathrm{j}}, \text { where MIPS }_{\mathrm{i}}$$ is the MIPS value of the [TeX:] $$\mathrm{VM}_{i} \text { and } \mathrm{TL}_{j}$$

- When [TeX:] $$\mathrm{E}(\mathrm{i})>0$$ , the task j will be given to [TeX:] $$\mathrm{VM}_{\mathrm{i}}$$

- When [TeX:] $$\mathrm{E}(\mathrm{i})<0,$$ we will let P, the acceptance probability of the [TeX:] $$\mathrm{VM}_{\mathrm{i}},$$ determine whether the task will be given to the [TeX:] $$\mathrm{VM}_{i}$$

We will now proceed by detailing the implementation of the acceptance probability P to the approach proposed in [34].

When [TeX:] $$\mathrm{MIPS}_{\mathrm{i}}-\mathrm{TL}_{\mathrm{j}}<0,$$ we will proceed by calculating [TeX:] $$MIPS _{i} -TL _{j+1}.$$ That way we will have the following:

Knowing that the only drawback of the SA is the great number of iterations that has to be set initially, we will consider [TeX:] $$\Gamma_{s},$$ the sum of the tasks in the queue, which will be the number of iterations required. That way, our approach will be faster than the normal SA approach, while staying accurate by taking into consideration the strip length of each VM.

The modified acceptance probability is as follows:

Afterward, we will compare P to R, a random value that will reset its value at each iteration:

If [TeX:] $$\mathrm{P}>\mathrm{R} \rightarrow \mathrm{VM}_{i}$$ will take the task j.

If [TeX:] $$\mathrm{P}<\mathrm{R} \rightarrow \mathrm{VM}_{i}$$ will take the task j+1.

The following flowchart (Fig. 1) and algorithm summarize how our approach works.

MIPS-based SA

Initialize the system configuration;

Initialize the initial state of the VMs;

Initialize T the number of tasks in the queue;

For ([TeX:] $$v: 0 \rightarrow$$the list of the VMs)

Get the MIPS of VM(v);

Calculate [TeX:] $$\mathrm{S}=\mathrm{MIPS}(\mathrm{v})^{*} \mathrm{T} / \Sigma \mathrm{v} \mathrm{MIPS}$$

Set I=0;

For ([TeX:] $$c: 0 \rightarrow$$the list of the Tasks)

Get the length of the Task(c)

If [TeX:] $$(\mathrm{MIPS}(\mathrm{v})>=\mathrm{TL}(\mathrm{c}))$$

[TeX:] $$\mathrm{VM}(\mathrm{v}) \leftarrow \text { Task }(\mathrm{c})$$

T--;

I++;

Else

For ([TeX:] $$b: c+1 \rightarrow$$the list of the Tasks)

Calculate [TeX:] $$\mathrm{P}=\exp (-(\mathrm{TL}(\mathrm{c})-\mathrm{TL}(\mathrm{b})) / \mathrm{T})$$

Generate R a random value

[TeX:] $$\text { If }(\mathrm{P}>\mathrm{R})$$

[TeX:] $$\mathrm{VM}(\mathrm{v}) \leftarrow \text { Task }(\mathrm{c})$$

T--;

I++;

Repeat until T=0 and I=S

4. Experiments and Results

4.1 Experiments

In order to obtain concrete results for our proposed algorithm, we need a platform that simulates a cloud-based environment. We chose the CloudSim simulator due to the fact that it gives us full control of our datacenter’s and tasks’ metrics.

In the initialization stade, we used 1 physical machine, 2 VMs, and 10 tasks. Table 1 contains the details of this configuration, while Table 2 contains the tasks’ lengths.

The MIPS value of each VM is randomly chosen from one to nine. In this scenario, VM 0 has six MIPS, and VM 1 has three MIPS.

The results of this simulation are explained in the following section.

4.2 Results

As we implemented our algorithm on the CloudSim simulator, some classical algorithms were also implemented in order to provide a concrete comparison in terms of performance. The same scenario of having 10 tasks, 1 server, and 2 VMs was imposed on all the other algorithms.

At first sight, our approach provided a better task distribution than the other approaches (Fig. 2). The allocation can be proven by calculating the strip length of each VM:

- First VM:

[TeX:] $$\mathrm{S}(\mathrm{VM} 0)=6 * 10 / 9 \approx 7$$

- Second VM:

[TeX:] $$\mathrm{S}(\mathrm{VM} 1)=3 * 10 / 9 \approx 3$$

As demonstrated, VM 0 will process seven tasks while VM 1 will process three tasks.

The second comparison performed between all approaches (Fig. 3, Table 3) is the execution time of each task for different algorithms. We chose FCFS, RR, and the classical implementation of the SA algorithm to compare with our approach. As shown in Fig. 3, our approach provides a faster process time which is greatly dependent on the tasks’ allocation. While proceeding in the comparison, we noticed that some tasks have a higher length than the MIPS of the VMs processing them (Table 2). This allocation is supported due to the acceptance probability P and by comparing it with R, we can explain why the task was given to the VMs:

Task 1 allocation to VM 1:

[TeX:] $$\mathrm{P}=\exp [-(6-3) / 9]=0.72$$

[TeX:] $$R=0.895$$

[TeX:] $$\mathrm{P}<\mathrm{R},$$ which means that VM1 process Task 1

The same thing is noticed for Task 7 and VM0:

[TeX:] $$\mathrm{P}=\exp [-(6-3) / 3]=0.37$$

[TeX:] $$\mathrm{R}=0.318$$

[TeX:] $$P>R,$$ this explains why VM0 added Task 7 to its workload

From the results of the previous experiments (Figs. 2, 3, and Table 3), we can declare that our approach offers an improved task distribution. This allows us to avoid having overloaded and underloaded VMs. Furthermore, our approach provides faster load balancing, which can be seen in the overall process time of our approach being shorter than the processing time of the other load balancers (Table 3).

5. Conclusions and Future Works

Cloud computing is a recent and rapidly evolving environments, which leads to many flaws and issues regarding QoS management in cloud computing. While aiming at providing a better solution, we proposed an improved version of the simulated annealing meta-heuristic in order to provide the appropriate task distribution to the VMs. Our approach, firstly, estimated the optimal workload of each VM provides a better task allocation. Then, by taking into consideration the tasks’ parameters and the VM’s strip length, the tasks are distributed to the VMs that can process them. This prevents VMs from being overloaded or underloaded. Additionally, if the length of the task is greater than the VM’s MIPS, our approach introduces the acceptance probability of the SA, which has high fault tolerance. This will allow for better task allocation.

As for future works, we plan on (1) ameliorating this approach by adding more metrics and conditions to further improve the load’s distribution and (2) expanding the experiments so that it can reflect realistic cloud environment usage.