Bhupesh Kumar Dewangan* | Anurag Jain | Tanupriya Choudhury
© 2020 IIETA. This article is published by IIETA and is licensed under the CC BY 4.0 license (http://creativecommons.org/licenses/by/4.0/).
OPEN ACCESS
Resource optimization is cost effective process in cloud. The efficiency of load balancing completely depends on how the infrastructure is utilizing. As per the current study, the resource optimization techniques are very costly and taking more convergence time to execute the task and load distribution among different virtual machines (VM). The objective of this paper is to develop a hybrid optimization algorithm to find the best virtual machine based on their fitness values and schedule different task to the fittest VM so that each task should get complete on time, and system can utilize the VM as well. The proposed algorithm is hybrid version of genetic (GA), ant-colony (Aco), and particle-swarm (Pso) algorithms, which is implemented and tested in amazon web service and compared with existing algorithms based on VM utilization, completion time, and cost. The proposed hybrid system genetic-aco-pso based algorithm (GAP) perform utmost while comparing with the existing systems.
resource scheduling, completion time, cost, VM utilization, optimization algorithm
In a distributed environment, resource management is implemented under load balancing to minimize the cost, satisfaction of service level agreement (SLA), and efficient utilization of resources. Work found in literature does not meet the efficient resource scheduling parameters like server utilization, quality of service, and cost-effective workload balancing in minimum time collectively. The demand of users and the number of users is never certain. Therefore, there must be some mechanism to handle this growing and shrinking demand of users in such a manner so that it will not impact the quality of service, and also resources must be utilized inefficient manner. In this paper, authors have proposed a load balancing approach by merging the best features of Genetic [1] Particle Swarm Optimization [2], and Ant Colony Optimization [3] approach to ensure even load distribution, efficient usage of resources and satisfaction of service level agreement. Authors have also ensured that limitations of a genetic, ant colony and particle swarm approach are not inherited in the proposed hybrid approach (GAP). The structure of this paper is as follows: In section 2, authors have discussed the different scheduling algorithms to achieve load balancing in the cloud environment. Problem definition and methodology of the proposed new approach are discussed in sections 3 and 4 respectively. Details of the simulation environment, result, and their analysis are given in section 5. It is followed by the conclusion given in section 6.
A real-time scheduling of task in cloud can be optimized through many nature and bioinspired optimization algorithms like Honey Bee, Particle Swarm, Ant Colony, Ant Lion, Grey Wolf, Genetic and other evolutionary patterns. In this research work, the best features of Genetic, Particle-swarm, and Ant-colony have been used to propose a novel idea. Genetic-Algorithm by Holland [4] in 1992 has given a new approach to search by simulating the concept of human evolution. He used the concept of crossover, mutation and recombination to find the best option among a pool of feasible options. At the same time, this concept has also discarded those options, which are lying below a certain level. Based on this concept, many modified and extended approaches are now used in optimization problems. Another bioinspired optimization approach is Ant-colony, it is based on the forging nature of a group of ants. Ants are very social and they collectively find the best path to find foods. This behavior of ant finding the best food in the shortest path is also used in many optimization problems. In continuation of this, another bioinspired approach is the particle-swarm approach. Optimization problems based upon this approach simulate the behavior of swarm which hunting fish and searching food. The fitness function of particles [5] can be given by the formula given in Eq. (1).
$f(i)=\frac{1}{\operatorname{ExecT}}$ (1)
where, i is several particles and belongs to [1, S], S is the total size of particles, and ExecT is task completion time. And completion-time by the task can be defined as:
$\operatorname{ExecT}=\sum_{n=1}^{k} \mathrm{VM}(\mathrm{m}, \mathrm{n})$ (2)
The comparative analysis of the above-studied algorithms is presented in Table 1.
Table 1. Comparative analysis of algorithms
|
Algorithm |
Time Complexity |
Space Complexity |
|
Genetic-Algorithm |
O(g(nm+n) |
O(gnm) |
|
Ant-Colony |
O(n2) |
O(n2) |
|
Particle-Swarm |
O(n2) |
O(n2) |
|
GAP |
nO(logn) |
nO(logn) |
In past decades, many new approaches have been developed by cloud researchers with some specific parameters. In 2020, a recent survey conducted in cloud resource management technique by author Dewangan et at. [6] it is categorized as follows:
2.1.1 Cost-aware approach
This parameter has been considered to schedule the resources at a minimal cost. This results in a low operational cost for both service providers and cloud users [7].
2.1.2 QoS-aware approach
Quality of service attracts to the cloud users to opt cloud services. The satisfaction ratio decides the user’s trust [8].
2.1.3 SLA-aware approach
Service level agreement approach is one of the key factors to enhance user’s trust [9].
2.1.4 Energy-aware approach
In this approach, the authors considered the power consumption rate, they provided novel approaches to reduce energy consumption, which is directly connected with cost [10].
2.1.5 Auction-based approach
Cloud user can approach the service as per demand, in this concept, the service provider does auctions, and users can opt for the required services [11].
2.1.6 Nature-bio-inspired approach
It is based on nature and bio-inspired algorithm to find the optimal resource for scheduling [12].
2.1.7 Profit-based approach
Focused on the profit of both cloud users and service providers [13].
2.1.8 Fault-tolerant approach
Avoid the unnecessary failures of scheduling the job and load balancing approach.
2.1.9 Optimization approach
This approach is used to optimizes several parameters as desire [14].
2.1.10 Autonomic computing
New era in resource management, using some self-characteristics for load balancing [15].
The outcome of this extensive study is presented in Figure 1. In this figure, the different parameters used in all recent approaches which are developed for the load balancing approach have been presented based on its utilization. Based on this review, the resource-utilization, cost, SLA, and execution time parameters are widely used.
Figure 1. Extensive analysis of cloud resource management approaches based on parameters
It is managing a problem diagnosed in a preceding algorithm or previous work interconnected to the task scheduling troubles. The sum of troubles that might be recognized is as: Local optima, Premature convergence [16], Parameter tuning, Stochastic procedures have trouble-based overall performance [17], and PSO algorithm does not have strong global seek capabilities.
3.1 Local optima
In done mathematics and laptop technological know-how, a nearby maximum appropriate of an optimization dilemma is a most suitable answer (either maximal or minimal) within a neighboring set of candidate solutions. This is in assessment to a worldwide most fine that is the choicest solution among all viable solutions, not the ones in a specific community of values. While the characteristic to be optimized is non-prevent, it may be possible to appoint calculus to discover nearby optima. If the primary spinoff exists anywhere, it can be equated to zero; if the character has an unbounded domain, for a factor to be a local premiere it's miles critical that it fulfill this equation. Then the second one by-product check gives enough condition for the factor to be a local highest or nearby minimal [18].
3.2 Premature convergence
Premature convergence' [19] is common because of the loss of diversity.
3.2.1 Diversity
The degree of the amount varies i.e. wide range of diverse solutions [20] in the population, and the way one-of-a-type they're (distance between possibility answers).
3.2.2 Loss of variety
After the population converges, it will become very uniform (all answers resemble the tremendous one [21].
3.2.3 Motives
Too strong selective pressure in the direction of an awesome solution. An excessive amount of exploitation of current building blocks from the contemporary populace (e.g. via recombining them, or mutating them only barely) [22].
The fitness value by GAP is given by the following condition:
fitness$(i)=\frac{1}{\mathrm{x}}$ (3)
where, x is total time need to complete the task, and i lies [0,1], and x can be obtained through:
$x=\sum_{n=1}^{k} \mathrm{VM}(\mathrm{m}, \mathrm{n})$ (4)
where, VM (m,n) is the total time in the nth task to execute the mth virtual machine, where K is the total task allocated to the virtual machine. Then evaluate the value of pbest and gbest that is local/particle best and global best, by using the above equations.
$pbestni (tn+1)=\left\{\begin{array}{lr}\text {pbestn}(t n), & \text { if } f(p n i(t n+1)) \leq f(\operatorname{pni}(t n) \\ p n i(t n+1), & \text { if } f(p n i(t n+1) \geq f(\operatorname{pni}(t n)\end{array}\right.$ (5)
$ gbestni(tn)=\left\{\begin{array}{l}\max (p \operatorname{best} n(t n)), \text { if } f(\max (p n i(t n))) \geq f(g \text { best }(t n)) \\ \text { else gbest }(t n)\end{array}\right.$ (6)
After finding the 2 high-quality values, the particle updates its speed and positions with the following equations:
$\begin{aligned} V i(t n+1)=w . & V i(t n)+C 1 . R 1 .(p b e s t n i(t n) -p i(t n)+C 2 . R 2 .(p b e s t n i(t n) -p i(t n) \end{aligned}$ (7)
$\operatorname{pni}(t n+1)=\operatorname{pni}(t n)+V i(t n)$ (8)
where, tn is total iteration, w is weight, C1 and C2 are train and learn facts, and generally C1= C2 =2, R1 and R2 is a random value within [0, 1], f(pni (tn)) denotes particles fitness function, f(pni (tn+1)) denotes as fitness function during next iteration.
In each iteration the particles rang is specific to (1 ≤ pni(tn) ≤ M) then calculate its velocity then calculate and update the position of particles, then terminate if criteria are satisfied and show the gbest optimal value. If criteria are not satisfied then again go back to the second process and calculate the fitness value and execute the whole loop and repeat the process to optimize solution achieve.
4.1 Task initiation
The tasks are submitted to the cloud service provider for pertaining services. The task initiation process is presented through algorithm-01.
Algorithm-01
|
Start Submit taks T←T1, T2, T3, … Tn For each T do for each T do Calculate the priority value If priority≤ threshold then Swap T with consecutive task End if Enf for End for End |
4.2 Service monitor
Initially, Service Monitor has collected the information from Task Initiation to monitor continuously the task value based on priority (exaction time in this research) as shown in Algorithm-02: Service Monitor (SM).
Algorithm-02
|
Start Set Taks T←T1, T2, T3, … Tn for each T do if ExecT(t1) ≤ ExceT(tn) then Start Swap T with consecutive task End if Alert End for End |
A proposed hybrid method is a novel approach based on GA, ACO, and PSO to find the optimal solutions. Therefore the objective function of the proposed method is:
$\operatorname{min.} f($ExecT$)$ (9)
Subjected to: 0 ≤ ExecT ≤ 1.
4.3 GAP scheduling
The scheduling approach is presented in Algorithm 3.
Algorithm-03
|
Start The pseudo code of the procedure is as follows For initiate each particles do For repeat the following for each particle do Calculate the fitness score of each particle If there is any improvement in the futness score relative to best fitness score(pbest) in the history then update new value as the latest pbest end if end for end for Select the particle having best fitness score of all the particle as gbest For every particle do Compute particle velocity according to equation (7) End for If crossover particle ≥ 0.5 then Apply one point crossover and update position of particle Evaluvate the newly generated crossover particle End if Repeat until minimum error or maximum iteration criterion is not attained. For every particle do Arrange particles (VM’s) in order If particles value ≤ threshold then Separate from group End if Produce Optimal particles (VM’s) End for End |
In the above algorithm, each particle is a virtual machine in this research.
4.4 Service executer and scheduling
The task initialized in task initiation are monitored and managed by service monitor, and ready to be scheduled with the virtual machine. The virtual machine is processed through GAP algorithm which is presented in algorithm 3, and the optimal VM is obtained for scheduling. The service executer executes the task and virtual machine and based on the priority value virtual machine assigned to the tasks through a round-robin algorithm.
The proposed algorithm is initialized with 10 virtual machines and 600 tasks. The virtual machines, which have different weight values as per CPU, and RAM value in the current state. The following analysis has been done to evaluate proposed research work.
5.1 Waiting time
Waiting time represents the time for which task remains in the queue. Higher waiting time indicates the poor performance of the system in terms of load balancing and resource management. The average waiting time of tasks is judged when there are 100, 200, 300, 400, 500, and 600 tasks in the system. From Table 2, it can be concluded that the proposed approach GAP is performing better in the context of waiting time relative to its parent approach. This has also shown graphically in Figure 2. The waiting time is calculated through the following equation:
waiting time = turnaround time - burst time (10)
Figure 2. Waiting time (sec)
Table 2 shows the test results of the waiting time.
Table 2. Comparative analysis of waiting time (sec.)
|
Tasks |
GAP |
PSO |
ACO |
GA |
|
100 |
16 |
23 |
26 |
18 |
|
200 |
21 |
34 |
35 |
32 |
|
300 |
36 |
50 |
37 |
45 |
|
400 |
43 |
64 |
65 |
54 |
|
500 |
60 |
70 |
72 |
62 |
|
600 |
65 |
75 |
79 |
54 |
Execution time represents the time taken by the virtual machine to process the task. Less execution time represents that task is mapped with a suitable virtual machine in terms of its resource requirement. The average execution time of tasks is judged when there are 100, 200, 300, 400, 500, and 600 tasks in the system. From Table 3, it can be concluded that the proposed approach GAP is performing significantly better in the context of execution time relative to its parent approach. This has also shown graphically in Figure 3. Table 3 shows the execution time. The execution time is calculated through the following equations:
execution time = exit time-arrival time (11)
Figure 3. Execution time
Table 3. Comparative analysis of execution time (sec.)
|
Tasks |
GAP |
PSO |
ACO |
GA |
|
100 |
146 |
176 |
209 |
232 |
|
200 |
195 |
287 |
309 |
328 |
|
300 |
329 |
430 |
464 |
495 |
|
400 |
440 |
525 |
577 |
626 |
|
500 |
540 |
578 |
636 |
688 |
|
600 |
593 |
647 |
695 |
716 |
Completion time represents the sum of response time, waiting time, and execution time. Less completion time represents that the load balancing approach is performing better at all fronts. The average completion time of tasks is judged when there are 100, 200, 300, 400, 500, and 600 tasks in the system. From Table 4, it can be concluded that the proposed approach GAP is performing significantly better in the context of completion time relative to its parent approach. This has also shown graphically in Figure 4.
Figure 4. Completion time
While Table 4 shows the completion time of each algorithm. The completion time is calculated through the following equation:
completion time = execution tiwaiting time (12)
Table 4. Comparative analysis of completion time (sec.)
|
Tasks |
GAP |
PSO |
ACO |
GA |
|
100 |
162 |
199 |
235 |
250 |
|
200 |
216 |
321 |
344 |
360 |
|
300 |
365 |
480 |
501 |
540 |
|
400 |
483 |
589 |
642 |
680 |
|
500 |
600 |
653 |
708 |
750 |
|
600 |
658 |
717 |
774 |
790 |
5.4 Cost analysis
Cost is estimated based upon the time for which resources are used by the task. As it has analyzed from Figures 4, 5, and 6 that the proposed approach GAP is taking less waiting, execution, and completion time, this implies that it will also use the resources for less time. This has reflected in Table 5 for 100, 200, 300, 400, 500, and 600 tasks in the system. It has reflected graphically in Figure 5.
Table 5. Comparative analysis of cost (\$)
|
Tasks |
GAP |
PSO |
ACO |
GA |
|
100 |
4.8 |
5.1 |
5.9 |
7 |
|
200 |
6.4 |
6.9 |
7 |
10 |
|
300 |
10 |
12 |
13 |
15 |
|
400 |
14 |
15 |
17 |
19 |
|
500 |
16 |
19 |
21 |
22 |
|
600 |
19 |
21 |
23 |
24 |
5.5 VM utilization
In the proposed approach GAP, while mapping the task with a VM, the fitness value of VM is considered. The fitness value is calculated based upon the present load and resources VM has. So in this manner, it ensures that all VM is used efficiently and no VM is overloaded. This results in better utilization of VM. This has reflected through the data shown in Table 6 for 100, 200, 300, 400, 500, and 600 tasks in the system. It has reflected graphically in Figure 6. Table 6 shows VM utilization.
Table 6. Comparative analysis of VM utilization (sec.)
|
VM Id |
GAP |
PSO |
ACO |
GA |
|
1 |
5 |
4 |
3 |
2 |
|
2 |
5 |
4 |
4 |
3 |
|
3 |
4 |
4 |
3 |
3 |
|
4 |
5 |
3 |
4 |
4 |
|
5 |
5 |
4 |
5 |
4 |
|
6 |
6 |
5 |
4 |
5 |
|
7 |
6 |
4 |
5 |
4 |
|
8 |
4 |
4 |
4 |
5 |
|
9 |
4 |
4 |
5 |
5 |
|
10 |
6 |
5 |
5 |
5 |
5.6 Throughput analysis
Throughput represents the number of tasks completed per unit time. Lesser the sum of response time, waiting time, and execution time, more will be the throughput. Now due to better performance shown on the scale of waiting time and completion time, it is obvious that the proposed approach GAP will also show better performance on the scale of throughput. This has reflected through the data shown in Table 7 for 100, 200, 300, 400, 500, and 600 tasks in the system. It has reflected graphically in Figure 7. While Table 7 shows throughput analysis of each algorithm.
It shows the comparison of different approaches for different number of tasks on the scale of throughput. Better performance on the scale of waiting time, completion time, execution time, resource utilization, cost and throughput results in satisfaction of service level agreement. It also creates a win-win situation for customer as well as cloud service provider.
Table 7. Comparative analysis of throughput (sec.)
|
Tasks |
GAP |
PSO |
ACO |
GA |
|
100 |
0.6 |
0.5 |
0.4 |
0.4 |
|
200 |
0.9 |
0.6 |
0.6 |
0.6 |
|
300 |
0.8 |
0.6 |
0.6 |
0.6 |
|
400 |
0.8 |
0.7 |
0.6 |
0.6 |
|
500 |
0.8 |
0.8 |
0.7 |
0.7 |
|
600 |
0.9 |
0.8 |
0.8 |
0.8 |
By embedding the proposed load balancing approach GAP in hardware like IP server, we can improve the performance and availability of the system. This will provide the capability to handle sudden traffic burst.
In cloud environment, satisfaction of SLA is prime objective. It can be achieved by providing services in minimum time in an efficient manner on a lowest cost by utilizing the resources in efficient manner. This will create a win-win situation to not only cloud user but also for cloud service provider too. In this paper, authors have proposed a hybrid load balancing approach for cloud environment by incorporating the best features of genetic, ant colony and particle swarm optimization algorithms. Authors have tested and compared the proposed algorithm GAP with existing GA, ACO & PSO algorithms in cloud environment developed using 10 virtual machines created in Amazon Web Service environment. It has found that proposed algorithm GAP has outperformed than GA, ACO & PSO based load-balancing algorithm on all the popular parameters.
[1] Ma, J., Li, W., Fu, T., Yan, L., Hu, G. (2016). A novel dynamic task scheduling algorithm based on improved genetic algorithm in cloud computing. Wireless Communications, Networking and Applications, Springer, New Delhi, pp. 829-835. https://doi.org/10.1007/978-81-322-2580-5_75
[2] Jana, B., Chakraborty, M., Mandal, T. (2019). A task scheduling technique based on particle swarm optimization algorithm in cloud environment. In Soft Computing: Theories and Applications, 742: 525-536. https://doi.org/10.1007/978-981-13-0589-4_49
[3] Azad, P., Navimipour, N.J. (2017). An energy-aware task scheduling in the cloud computing using a hybrid cultural and ant colony optimization algorithm. International Journal of Cloud Applications and Computing (IJCAC), 7(4): 20-40. https://doi.org/10.4018/IJCAC.2017100102
[4] Holland, J.H. (1992). Genetic algorithms. Scientific American, 267(1): 66-73.
[5] Engelbrecht, A.P. (2013). Particle swarm optimization: Global best or local best? 2013 BRICS congress on computational intelligence and 11th Brazilian Congress on Computational Intelligence, Ipojuca, pp. 124-135. https://doi.org/10.1109/BRICS-CCI-CBIC.2013.31
[6] Dewangan, B.K., Agarwal, A., Choudhury, T., Pasricha, A., Chandra Satapathy, S. (2020). Extensive review of cloud resource management techniques in industry 4.0: Issue and challenges. Software: Practice and Experience, 1-20. https://doi.org/10.1002/spe.2810
[7] Dewangan, B.K., Agarwal, A., Choudhury, T., Pasricha, A. (2020). Cloud resource optimization system based on time and cost. International Journal of Mathematical, Engineering and Management Sciences, 5(4): 758-768. https://doi.org/10.33889/IJMEMS.2020.5.4.060
[8] Naseri, A., Navimipour, N.J. (2019). A new agent-based method for QoS-aware cloud service composition using particle swarm optimization algorithm. Journal of Ambient Intelligence and Humanized Computing, 10(5): 1851-1864. https://doi.org/10.1007/s12652-018-0773-8
[9] Dewangan, B.K., Agarwal, A., Pasricha, A., Chandra Satapathy, S. (2019). Sla-based autonomic cloud resource management framework by antlion optimization algorithm. International Journal of Innovative Technology and Exploring Engineering (IJITEE), 8(4): 119-123.
[10] Dewangan, B.K., Agarwal, A., Venkatadri, M., Pasricha, A. (2019). Energy-aware autonomic resource scheduling framework for cloud. International Journal of Mathematical, Engineering and Management Sciences, 4(1): 41-55. https://dx.doi.org/10.33889/IJMEMS.2019.4.1-004
[11] Zaman, S., Grosu, D. (2013). A combinatorial auction-based mechanism for dynamic VM provisioning and allocation in clouds. IEEE Transactions on Cloud Computing, 1(2): 129-141. https://doi.org/10.1109/TCC.2013.9
[12] Dewangan, B.K., Agarwal, A., Venkatadri, M., Pasricha, A. (2019). Design of self-management aware autonomic resource scheduling scheme in cloud. International Journal of Computer Information Systems and Industrial Management Applications, 11: 170-177.
[13] Dewangan, B.K., Agarwal, A., Pasricha, A. (2016). Credential and security issues of cloud service models. 2016 2nd International Conference on Next Generation Computing Technologies (NGCT), Dehradun, pp. 888-892. https://doi.org/10.1109/NGCT.2016.7877536
[14] Dewangan, B.K., Agarwal, A., Venkatadri, M., Pasricha, A. (2019). Self-characteristics based energy-efficient resource scheduling for cloud. Procedia Computer Science, 152: 204-211. https://doi.org/10.1016/j.procs.2019.05.044
[15] Dewangan, B.K., Agarwal, A., Venkatadri, M., Pasricha, A. (2018). Autonomic cloud resource management. In 2018 Fifth International Conference on Parallel, Distributed and Grid Computing (PDGC), Solan Himachal Pradesh, India, pp. 138-143. https://doi.org/10.1109/PDGC.2018.8745977
[16] Zhong, Z., Chen, K., Zhai, X., Zhou, S. (2016). Virtual machine-based task scheduling algorithm in a cloud computing environment. Tsinghua Science and Technology, 21(6): 660-667. https://doi.org/10.1109/TST.2016.7787008
[17] Xu, G. (2013). An adaptive parameter tuning of particle swarm optimization algorithm. Applied Mathematics and Computation, 219(9): 4560-4569. https://doi.org/10.1016/j.amc.2012.10.067
[18] Sivaram, M., Batri, K., Amin Salih, M., Porkodi, V. (2019). Exploiting the local optima in genetic algorithm using tabu search. Indian Journal of Science and Technology, 12(1): 9. https://doi.org/10.17485/ijst/2019/v12i1/139577
[19] Zhao, D., Zhang, H., Pan, J. (2019). Solving optimization of a mine gas sensor layout based on a hybrid GA-DBPSO algorithm. IEEE Sensors Journal, 19(15): 6400-6409. https://doi.org/10.1109/JSEN.2019.2909277
[20] Neumann, A., Gao, W., Wagner, M., Neumann, F. (2019). Evolutionary diversity optimization using multi-objective indicators. In Proceedings of the Genetic and Evolutionary Computation Conference, pp. 837-845. https://doi.org/10.1145/3321707.3321796
[21] Bharathan, G., Fernandez, T.T., Ams, M., Woodward, R.I., Hudson, D.D., Fuerbach, A. (2019). Optimized laser-written ZBLAN fiber Bragg gratings with high reflectivity and low loss. Optics Letters, 44(2): 423-426. https://doi.org/10.1364/OL.44.000423
[22] Raju, M., Gupta, M.K., Bhanot, N., Sharma, V.S. (2019). A hybrid PSO–BFO evolutionary algorithm for optimization of fused deposition modelling process parameters. Journal of Intelligent Manufacturing, 30(7): 2743-2758. https://doi.org/10.1007/s10845-018-1420-0
