Keywords

111.1 Introduction<!--RH>Introduction<!--/RH>

With the increasing popularity of cloud computing, the cloud faces a major challenge in managing an extremely large number of service requests. In order to maintain the stability of the system and provide good service, an effective load-balancing technique for task scheduling in dynamic cloud environment is required. Some researchers developed effective algorithms based on the behavior of social animals, because social organisms can effectively adapt to a changing environment. For example, an ant colony can dynamically allocate tasks without a central manager. The Ant Colony Optimization (ACO) algorithm has been used to solve the load-balancing problem in Peer-to-Peer (P2P) environments [1, 2], and in grid computing [3–5]. Recently, ACO has also been applied to the cloud environment [6–8].

In this paper, an improved ACO algorithm is proposed for load balancing in the cloud environment and the CloudSim tool [9, 10], is used to conduct simulations for comparing the effectiveness of different load-balancing strategies.

The rest of the paper is organized as follows: Sect. 111.2 briefly describes the simple ACO algorithm. Section 111.3 discusses the proposed bidirectional ACO algorithm. Section 111.4 shows the experimental results. Finally, Sect. 111.5 presents conclusions.

111.2 Simple Ant Colony Optimization<!--RH>Simple Ant Colony Optimization<!--/RH>

Ant colony algorithms are computational swarm intelligence methods that were inspired by a number of different behaviors observed in ant colonies. A simple ACO algorithm was proposed by Dorigo et al. [11, 12].

Dorigo et al.’s ACO algorithm was based on the foraging behavior of ants while searching for the shortest path between the ant nest and a food source. Likewise, one can consider the general problem as finding the shortest path between two nodes on a graph. During the shortest-path search, cooperation among the ants is achieved by releasing pheromones to influence the behavior of other ants. How forager ants decide which edge to follow is a probabilistic technique and depends on the pheromone concentrations on different edges. Let τij be the pheromone concentration between nodes of i and j in the graph. Initially, the value τij(0) is assigned a random value to indicate the pheromone at time zero, and a number of ants are placed at the starting node. Each ant then creates a path between the starting node and the terminating node by determining the next edge from the current node at every time step (iteration) t. The transition probability \( p_{ij}^{k} \left( t \right) \) of the kth ant moving from node i to node j at time step t is defined as

$$ p_{ij}^{k} \left( t \right) = \left\{ {\begin{array}{lll} {\frac{{(\tau_{ij} (t))^{\upalpha} }}{{\sum\limits_{{u \in J_{k} (i)}} {(\tau_{iu} (t))^{\upalpha} } }}} & {if \quad j \in J_{k} (i)} \\ 0 & {otherwise} \\ \end{array} } \right., $$
(111.1)

where Jk(i) is the set of feasible nodes linked to node i along the path of the kth ant, and α is a parameter used to intensify the influence of pheromone concentrations. When an ant has traversed a path within the time step t, the ant retraces its path and deposits pheromone on every edge of the path. The concentration of the deposited pheromone on the edge (i, j) is inversely proportional to the length of the path. That is,

$$ \varDelta \tau_{ij}^{k} (t) \propto \frac{1}{{L^{k} (t)}} $$
(111.2)

where \( \varDelta \tau_{ij}^{k} \) is the deposited pheromone, and \( L^{k} (t) \) is the length of the path created by the kth ant at time step t. The total pheromone intensity of an edge is then updated using Eq. (111.3).

$$ \tau_{ij} (t + 1) = (1 - \beta_{eva} ) \times \tau_{ij} (t) + \sum\limits_{k = 1}^{n} {\Delta \tau_{ij}^{k} (t)} $$
(111.3)

where βeva is the pheromone evaporation rate with βeva ∈ [0, 1], and n is the number of ants. The iterations are executed until one of the terminating conditions is true. The solution is the shortest path found among all the paths traversed by the ants.

111.3 The Proposed Algorithm<!--RH>The Proposed Algorithm<!--/RH>

In this paper, a Bidirectional Load Balancing ACO (BLBACO) algorithm that is inspired by Li et al. [6] and Nishant et al. [7] is proposed. The BLBACO used the Load Balancing ACO (LBACO) [6] characteristics to determine the loading and computing capacity of each virtual machine, and BLBACO also adapted the concept proposed in [7], where the movements of the ants in the system are defined as either a forward movement or a backward movement. Forward movement is the direction of ants moving from the nest to a food source, and backward movement is the direction from the food source to the nest. In the computing cloud, forward movement can be defined as the direction of an under-loaded virtual machine (nest) seeking an over-loaded virtual machine (food), while backward movement is the reversed direction. Once the search is completed, a portion of the tasks that were originally assigned to the over-loaded virtual machine can be reassigned to the under-loaded virtual machine.

The proposed algorithm performs the following procedures:

  • Initialize pheromone

At the beginning, an amount of pheromone intensity is initialized at each virtual machine, and each ant is randomly positioned on a virtual machine.

  • Select a virtual machine

The probability of the kth ant selecting the jth virtual machine is calculated by the following formula [6]:

$$ p_{j}^{k} \left( t \right) = \left\{ {\begin{array}{*{20}llll} {\frac{{\left[ {\tau_{j} (t)} \right]^{\alpha } \left[ {EV_{j} } \right]^{\beta } \left[ {LB_{j} } \right]^{\gamma } }}{{\sum\limits_{{u \in J_{k} (i)}} {\left[ {\tau_{u} (t)} \right]^{\alpha } \left[ {EV_{u} } \right]^{\beta } \left[ {LB_{u} } \right]^{\gamma } } }}} & {,if \quad j \in 1 \ldots m} \\ 0 & {,otherwise} \\ \end{array} } \right. $$
(111.4)

where \( p_{j}^{k} \left( t \right) \) is the probability of the kth ant selecting the virtual machine j at time step t, \( \tau_{j}(t) \) is the pheromone concentration deposited on the virtual machine j at time step t,\( EV_{j} \) is the computing capacity of the virtual machine j, \( LB_{j} \) is the load balancing factor of the virtual machine j, α, β, and γ are parameters, and m is the total number of virtual machines.

  • Update pheromones

Two sets of formulae are used to update pheromones. If all virtual machines are over-loaded or all virtual machines are under-loaded, a one-way update formula is used; otherwise, a set of bidirectional update formula is used. The formulae are described as follows:

  1. Case 1:

    If all virtual machines are over-loaded state or all virtual machines are under-loaded, a one-way formula is used to update the pheromone intensity:

    $$ \tau_{j} (t + 1) = (1 - \beta_{eva} ) \times \tau_{j} (t) + \sum\limits_{k = 1}^{n} {\varDelta \tau_{j}^{k} (t)} $$
    (111.5)

    where τj(t) is the total pheromone intensity of node j at time step t, \( \varDelta \tau_{j}^{k} \) is the pheromone deposited by ant k, and βeva is the pheromone evaporation rate as defined in Eq. (111.3).

  2. Case 2:

    If the cloud environment contains both over-loaded and under-loaded virtual machines, two pheromone-update formulae are used [7]. The first formula is used when an ant is at an under-loaded node and is searching for an over-loaded node:

    $$ FP_{j} (t + 1) = (1 - \beta_{eva} )FP_{j} (t) + \sum\limits_{k = 1}^{n} {\varDelta FP_{j}^{k} } $$
    (111.6)

    where FPj(t) is the total amount of foraging pheromone at node j at time step t, and \( \varDelta FP_{j}^{k} \) is the pheromone deposited by ant k.

The other formula is used when an ant is at an over-loaded node and is returning to the under-loaded node:

$$ TP_{j} (t + 1) = (1 - \beta_{eva} )TP_{j} (t) + \sum\limits_{k = 1}^{n} {\varDelta {\rm T}P_{j}^{k} } $$
(111.7)

where TPj(t) is the total amount of tracing pheromone of node j at time step t, and \( \varDelta TP_{j}^{k} \) is the pheromone deposited by ant k.

111.4 Experimental Results<!--RH>Experimental Results<!--/RH>

The proposed BLBACO algorithm was implemented using the Java language and was tested on the CloudSim platform [9, 10]. The LBACO [6] algorithm has outperformed the First-Come-First-Serve (FCFS) algorithm and the basic ACO algorithm. In addition, the approach proposed by Nishant et al. [7] is not suitable for a dynamic environment. Therefore, the proposed BLBACO algorithm compared with LBACO [6]. The experiments used the parameter settings in [6]; that is, the number of ants n is 8, the pheromone evaporation rate βeva is 0.01, and the parameters α, β, and γ in Eq. (111.4) are 3, 2, and 8, respectively.

In the first category of experiments, we fixed the total number of virtual machines to be 50 in each trial, and we varied the number of task requests to be 500, 300, 100, 50, and 25 in different trials. BLBACO and LBACO each executed 5 times for each trial. The makespan averages are shown in Table 111.1.

Table 111.1 Number of virtual machines = 50 (fixed)
Full size table

The second category of experiments verified the effectiveness of load-balancing strategies when the cloud environment contains both over-loaded and under-loaded virtual machines. To simplify the experiments, we set an equal number of virtual machines and task requests, and we assumed that the system would contain both under-loaded and over-loaded nodes. The results are listed in Table 111.2. To easily compare the performance of BLBACO with the performance of LBACO, we choose one trial from each category of experiments. The left panel of Fig. 111.1 shows the performance of the first category experiment with 50 virtual machines and 500 task requests, and the right panel shows the performance of the second category experiment with 300 virtual machines and 300 task requests. Based on the experimental results, the performance of BLBACO is better than that of LBACO. This validates the effectiveness of the proposed BLBACO algorithm.

Table 111.2 Number of virtual machines = Number of tasks
Full size table
Fig. 111.1
figure 1

Overall performance of the first experiment category with 500 tasks (left) and of the second category experiment with 300 tasks (right)

Full size image

111.5 Conclusions<!--RH>Conclusions<!--/RH>

In this paper, an improved method of cloud load balancing based on the ACO algorithm was proposed. The proposed BLBACO algorithm considers the loading and computing capacity of each virtual machine with bidirectional movement in ACO. The experiments showed that the BLBACO algorithm has better performance compared to LBACO [6]. This indicates that BLBACO can effectively deal with task allocation in a dynamic cloud environment.