Keywords

1 Introduction

Cloud computing is an emerging technology and new trend for computing based on virtualization of resources [1]. In cloud environment the physical machines run multiple virtual machines (VM) which are presented to the clients as the computing resources. The architecture of a VM is based on a physical computer with similar functionality [2]. In fact VM is a guest program with software resources functioning similar to a physical computer. Resource allocation technique is an important process to allocate resources based on user’s application demands to achieve an optimal number of servers in use [3]. This process is done dynamically for the purpose of load balancing of non-preemptive tasks. Load balancing is an NP-hard optimization problem in cloud computing. This technique strives to balance the workload across VMs, which aims to minimize response time in order to keep promises and quality of service in accordance with service level agreements (SLA) between the clients and the provider. Furthermore, this process has to be carried out regularly due to the time-variant nature of the loads of Application Environments (AE). In fact cloud’s clients are interested to have their jobs completed in the shortest possible time and at the minimum cost [4]. On the other hand, the cloud providers are interested to maximize the use of their resources with a lower overall cost to increase their profit. Obviously these two objectives are in conflict and often they are not satisfied with the traditional methods of resource allocation and load balancing techniques [5]. The classical methods are very time consuming [6]. Traditional approximate methods are reported inconclusive and inaccurate and often trapped in local optimum [7]. Further algorithms proposed in literature for multi-objective scheduling e.g. FIFO [8] and Round-Robin [8] are in fact not effective in allocating the resources.

Therefore, In order to achieve maximum resource efficiency and scalability, exploring new meta-heuristic algorithms as well as development of novel algorithms are highly desired. Meta-heuristic optimization techniques have had an exceptional growth over the last two decades [9]. The remarkable ability of meta-heuristic techniques is motivated scientists from different fields to solve NP-hard problems. Furthermore, such techniques can often find optimal solutions with less computational effort than optimization algorithms, iterative methods, or simple heuristics. The question that arises is why this technique is remarkably common. The answer will be easily found in four main properties that characterize most meta-heuristics: simplicity, flexibility, derivation-free mechanism, and avoidance of entrapment in local optima.

Accordingly, this paper proposes a hybrid meta-heuristic load balancing algorithm with combination of two relatively new optimization algorithms, which can well contribute in maximizing the throughput using well balanced load across virtual machines and overcome the problem of trap into local optimum. The proposed algorithm is a hybrid of Grey Wolves Optimization (GWO) algorithm [10] and Teaching-Learning-Based Optimization (TLBO) algorithm [11]. The main idea is to integrate the ability of exploitation and exploration in GWO with the ability of the convergence in TLBO to provide a new population-base algorithm for dynamic allocation of virtual resources in cloud environment. Furthermore, the proposed algorithm well balances the priorities of tasks and effectively considers load balancing based on time, cost which consequently leads to minimal amount of waiting time of the tasks in the queue.

2 Related Works

Selecting and developing an appropriate algorithm to solve multi-objective problems is of utmost importance [12]. Therefore, meta-heuristic algorithms which have a global overview, as they ensure convergence to the solution and do not fall into the trap in local optimum, are of importance. Salimi et al. [13] introduce a multi-objective optimization algorithm for scheduling using fuzzy systems for load balancing in the distributed system. The authors aim at minimizing implementation time and costs while increasing the productivity of resources.

Cheng [14] provides an optimized hierarchical resource allocation algorithm using a general meta-heuristic algorithm. His model accomplishes workflow tasks scheduling aiming at load balancing with dividing the tasks into different levels. Gomathi and Karthikeyan [15] introduce a method for assigning tasks in a distributed environment using hybrid swarm optimization algorithm. The aim is to minimize the longest completion of task time among processors and creating load balancing. Pandey et al. [16] introduced a meta-heuristic method based on particle swarm optimization algorithm for scheduling on distributed environment resources. This optimization method is composed of two components, one of them is tasks scheduling operations and the other one is, using particle swarm algorithm (PSA) to obtain an optimal mix of the tasks to resource mapping. In this method, each particle represents a mapping of tasks to available resources. Traditional resource allocation methods [17] due to the multiple objectives and the dynamic nature of the problem and also difficulties in dealing with local optimum need advancement and major improvement. Consequently, the purpose of this paper is to address this research gap.

3 Proposed Method

The proposed methodology is based on bonding the algorithms of TLBO and GW. These two algorithms are currently used as approximation algorithm for establishing load balancing based on time and cost between resources and efficiency. With such hybridization it is aimed at speeding up the process while maintaining the improvement of local optimization and increasing the accuracy [18,19,20]. The TLBO and GWO algorithms are later introduced as the primary solutions to the described problem.

The optimization problem is described as a distributed network in a cloud environment with resource systems S1, S2, S3, …, Sn. The resources are ready to service in the distributed network for various nodes. Different jobs are sent for the source systems by nodes. Here the scheduler is responsible to allocate one or more jobs to VM in a distributed system [21]. Scheduler provides a scheduling for resource allocation [22]. Several jobs are allocated and processed in parallel with each other at time t in the distributed system. The number of variables T k is permutation between jobs and resources, this variable is called P, and its value is calculated as follows:

$$ P = n^{m} \quad \left( {n \, is \, number \, of \, tasks \, and \, m \, is \, the \, number \, of \, sources} \right) $$
(1)

As it is described each node includes several jobs j 1 , j 2 ,… j n . Each job requires a series of specific resources R 1 , R 2 ,…R m . If in the particular example, the resources R 1 , R 2 , … R m have the same capacity and processing power and jobs j 1 , j 2 , … j n all need 1% of the processor processing, the professional model can be defined in the form of what jobs use which resources to achieve maximum load balancing, average response time, and minimum cost. For the exact solution of the problem, all possible allocation modes must be calculated and the best mode chosen. Due to the large number of exponential modes, the problem is an example of set packing problems which is of NP-complete type.

Optimization function is defined for resource i and job j. y i is the number of resources. x ij represents that job j is assigned to resource i. C is the maximum capacity for each resource. w i represents the amount of job i that is covered by the resource. The objective function and mathematical programming model that should be optimized are as follows:

$$ Min \, B = \, a*\left( {1 - L_{{(y_{j} )}} } \right) + b*C_{{(y_{j} )}} + c*T_{{(y_{j} )}} $$
(2)
$$ \begin{array}{*{20}l} {\sum\limits_{i = 1}^{n} {w_{i} x_{i\,j} \le \,\,\,Ky_{j} ,\forall j} \,} \hfill \\ {\sum\limits_{j = 1}^{n} {x_{i\,\,j} \le \,\,\,b_{j} ,\forall j\,} } \hfill \\ \end{array} \,\,\,\,\,\,\,\,\,\,\,x_{i\,j} ,y_{i} = 0,1\,\forall \,\,i,j $$
(3)

where \( x_{j} = \left\{ \begin{subarray}{l} 1\quad job\;j\;is\;used \\ 0\quad job\;j\;is\;not\;used \end{subarray} \right.,\quad y_{j} = \left\{ \begin{subarray}{l} 1\quad resource\;j\;is\;used \\ 0\quad resource\;j\;is\;not\;used \end{subarray} \right. \)

The aim is to find the minimum number of virtual machines y j that minimize the objective functions. The values of L, C, and T (load balancing, cost, and response time) are considered based on the number of virtual resources y j , where a, b, c are variable based on cloud system. The variable of x ij demonstrates that the i th job is in j th virtual machines, and if its value is equal to 0, it means that there is no any resource in j th virtual machine and if its value is equal to 1, it means that there is enough resource to allocate in the j th virtual machine. Every job has capacity of w i . The first limitation shows that total capacity of jobs can be placed at the maximum K available resources. The second limitation shows the maximum capacity of each virtual resource. b j is the capacity of each virtual resource.

3.1 Grey Wolf Algorithm

Mirjalili et al. [10] introduced GW for solving engineering problems. GW is a new optimization algorithm inspired by behaviour of grey wolves’ hunting and their rule hierarchies. The hierarchical structure and social behaviour of wolves is modelled during hunting process in the form of mathematical models and is used for design of optimization algorithm.

3.2 Teaching-Learning-Based Optimization Algorithm

Rao et al. [11] introduced a novel approach to explore a problem space to find the optimal settings and parameters to satisfy the problem’s objectives. This algorithm is inspired from modelling the teaching and learning problem mathematically and presents a new model for solving optimization problems. The algorithm operates in two phases, the first phase is the teacher share to develop class knowledge level and the second phase is the review of courses by students in the same class.

3.3 The Proposed Hybrid Algorithm

Given more convergence power in the global optimality, the GWO algorithm is used as base algorithm in the proposed algorithm. This algorithm can also perform multi-objective optimization [23]. The proposed algorithm is:

figure a

The Steps are as Follows:

In the initial state, a series of random numbers as the initial population are considered with uniform distribution and a basic solution is considered for the problem. Coefficients a, b, c are initialized. Each wolf is considered as a solution to the problem. In other words, each wolf is considered as a solution to the problem. These solutions or wolves have an answer. Wolves are divided into three categories; alpha, beta, and gamma. Yet on the basis of the fitness function (objective), one of them gives a better answer to the fitness function. Further, the solution enters the main loop where after a few iterations best solution for the fitness function is discovered. Based on the equations in the GWO algorithm, the wolves’ position is updated. According to the wolves of first class, the new positions are fitted. Later on more values for the probability of solution are considered. Correspondingly, the values of beta and gamma classes, and new positions of wolves’ and their classifications can be obtained. In addition, a new fitness function for the wolves and division of three new wolves groups is calculated. If a suitable solution is found in the new classification, the algorithm is to be improved further. The best solution between the wolves is considered as the initial solution (initial population) for teaching and learning algorithm. Further the problem using teaching and learning algorithm is solved and the solution is considered as initial population to start again. In this stage the GWO algorithm is implemented.

4 Computational Experiments

Here the main purpose is comparison on the performance of hybrid algorithm with three algorithms of GWO, particle swarm optimization (PSO) [24] and Biogeography-based optimization (BBO) [25]. At the first experiment, the mathematical models of algorithms are implemented using MATLAB (2014) and then it is run for 11 benchmark functions [26]. At the second experiment, the algorithms are simulated for resource allocation using CloudSim tool and the results are compared. Each algorithm has been investigated on a number of generations 200 and a constant population size of 50. It is noteworthy that the algorithms have been run 20 times on a benchmark function, and the final result has been obtained from the average of 20 times of running so that the rate of error decreases. Benchmark functions are divided into two groups: unimodal and multimodal.

According to the results presented in Table 1, the hybrid algorithm outperforms in comparison with all other algorithms in unimodal and multimodal functions. Computational results showed that concerning unimodal functions like sphere and Chang Reynolds, which are simple functions with no local optima, if we have many or few iterations or large or small population, hybrid algorithm outperforms other algorithms. This rule also applies to Schwefel 2/21 function because not only is it a simple function, but it also does not have any local optima. In conclusion, hybrid algorithm is the best algorithm to solve a problem for the simple functions that do not have any local optima. Regarding Schwefel 2/22 function, hybrid algorithm delivered better results than other algorithms. This function is a bit more complex than Sphere function. Therefore, hybrid algorithm could be used to solve a bit complex and problems that contain local optima. Hybrid algorithm outperforms in Restring and Ackley functions. These two functions also have many local optima same as Schwefel 2/22. In Griewank function, which is a rather complex function, hybrid algorithm still delivers the best results. Figure 1 shows an example of proposed algorithm using bin packing problem. In addition to the following example the novel algorithm has been recently used in a number of industrial applications e.g. creating predictive decision models [27], and materials design innovation [28].

Table 1. Results of benchmark functions for 200 generations and population size of 50.
Full size table
Fig. 1.
figure 1

An example of the execution process of proposed algorithm using bin packing problem

Full size image

5 Conclusion

For an effective dynamic resource allocation in cloud computing a novel algorithm is proposed. The evaluation of experimental results indicates the novel hybrid approach has better performance comparing to the existing algorithms, in particular, in high-volume data of cloud scheduler. It is concluded that the main problem in the resource allocation of cloud scheduler is the lack of convergence in the optimal solution.