LBMPSO Algorithm for Balancing the Load in Grid Environment

LBMPSO Algorithm for Balancing the Load in Grid Environment

Sivakumar K

Assistant Professor Dept. of CSE

JCT college of Engineering and Technology Coimbatore, Tamil Nadu, India

.AbstractGrid computing is the collection of computer resources from multiple locations to reach a common goal. The grid can be thought of as a distributed system with non-interactive workloads that involve a large number of files. Grid computing is distinguished from conventional high performance computing systems such as cluster computing in that grid computers have each node set to perform a different task/application. In this paper, a heuristic approach based on particle swarm optimization algorithm is adopted to solving task scheduling problem in grid environment. By reviewing through different author papers, it can be seen that particle swarm optimization gives better performance in terms of time, efficiency and balanced workload, etc. This approach aims to propose mathematical model multi- objective Load Balancing Mutation particle swarm optimization (MLBMPSO) to schedule and allocate tasks to resource. MLBMPSO considers two objective functions to minimize makespan and total cost.

KeywordsGrid computing, Scheduling, Particle swarm optimization.

1. INTRODUCTION

   Heterogeneous Computing (HC) systems consist of mixed group of machines, communication protocols and programming environments and offer a diversity of architectural capabilities that has different execution requirements. One of the key challenges of HC system is the task scheduling problem. In general, scheduling is concerned with distribution of limited resources to certain tasks to optimize few performance criterions, like the completion time, waiting time. Task assignment problems can be classified into two categories based on the types of tasks [1]: scheduling a meta-task composed of independent tasks with no data dependencies and assigning an application composed of tasks with precedence constraints.

   PSO has been found to be robust and is successfully applied in solving nonlinear, no differentiable multi-modal problems quickly. It is still in its infancy. Many research works have mentioned application of PSO in task scheduling. PSO is most successful met heuristic for generations of optimal scheduling solutions. PSO scans over solution space during each iteration and accumulates global best and local best solutions. This section presents review of recent proposals which considered PSO in the field of task scheduling in cloud environment. Originally PSO was proposed where PSO was

   proposed as an optimization tool. Two types of PSO namely, Discrete PSO and Continuous PSO versions were proposed. With several passes over the search space and updating local best and global best solutions during each pass, PSO performed much faster than ACO or GA. In [2] authors introduced the concept of inertia weight into the original PSO. With introduction of inertia weight PSO could converge even faster. Initially inertia weight was proposed to lie in the range [0.9, 1.2], which can improve performance of PSO. Different values of inertia allowed better control over solution search space. Higher values of inertia weight will result in overshooting the and lower values will trap search in definite area in search space. A Cost Aware Modified PSO (CA-PSO) was proposed in [3]. In [4] authors exploit PSO for optimizing overall tasks completion cost in a workflow and respecting the given deadline constraints. The proposed met heuristic approach based on PSO succeeds whereas IC-PCP fails to meet applications deadline. In comparison IC-PCP failed to meet deadline constraints as IC-PCP ignored VM boot time. Results prove that PSO performs better than current state-of-the-art algorithms.

   Proposal considered deadline constraint. Proposal generates constraint makespan and performs cost evaluation for various workflows like Montage, Ligo etc. When compared to SCS, proposed algorithm is capable of generating better schedules and achieved cost optimization. In authors proposed mathematical model using a Load Balancing Mutation (balancing) Particle Swarm Optimization (LBMPSO) and considered reliability and availability as the objective parameters of proposals.

   LBMPSO used an algorithm to generate schedule and allocation for Grid computing environment. Algorithm considered available resources for generation of schedule and allocation patterns. Basic PSO suffers from free VMs, allocation of more than one task to same VM, allocation of same tasks to multiple VMs and premature convergence. LBMPSO takes into account execution time, transmission time, make span, round trip time, transmission cost and load balancing between tasks and achieved reliability in task scheduling. Idea of LBMPSO is to reschedule failure tasks to available VM. LBMPSO performance was compared with standard PSO, random algorithm and

   Longest Cloudlet to Fastest Processor (LCFP) algorithm to show that LBMPSO can save in make span, execution time, round trip time, transmission cost.

2. RELATED WORKS

   Swarm intelligence is an important research topic based on the collective behavior of decentralized and self- organized systems in computational intelligence. It consists of a population which simulates the animals behavior in the real world. Now there are many swarm intelligence optimization algorithms, such as genetic algorithms, particle swarm optimization, ant colony optimization, bee colony algorithm, differential evolution, fish-warm algorithm, etc. Due to the simple concept, easy implementation and quick convergence, PSO has gained much attention and been successfully applied in a variety of fields mainly for optimization problems. So far, as for the constrained optimization problems, relatively less work based on PSO can be found than those based on other EAs. Parsopoulos and Vrahatis [22] proposed a non-stationary multi-stage assignment penalty function method to transform the constrained problem to the unconstrained problem. Simulation results showed that PSO outperformed other EAs, but the design of the multistage assignment penalty function is too complex.

   In the work of Hu and Eberhart [23], the initial swarm contains only feasible solutions and a strategy to preserve feasibility is employed. Motivated by multi-objective optimization techniques, Ray and Liew [24] proposed a swarm algorithm with a multilevel information sharing strategy to deal with constraints. In their work, a better performer list (BPL) is generated by a multilevel Pareto ranking scheme treating every constraint as an objective, while the particle which is not in the BPL gradually congregates round its closest neighbor in the BPL. In these swarm intelligence algorithms, the most popular and widely used algorithms for solving the TSP are GAs, ACO and PSO.

   Clerc [25] develops several algorithm variants with those operations and methods and applies them to the asymmetric TSP instance br17.atsp. In his algorithm the positions are defined as TSP tours represented in vectors of permutations of the |N| vertices of the graph correspondent to the considered instance. This approach was applied to tackle the real problem of finding out the best path for drilling operations [27].

   Particle swarm optimization is presented to solve traveling salesman problem [26], where the authors have proposed the concept of swap operator and swap sequence, and redefined some operators on the basis of them. This paper has designed a special PSO, but the special PSO does not improve the updating formula, and the experiment results are worse than ours. Hendtlass [28] proposes the nclusion of a memory for the particles in order to improve diversity.

   The memory of each particle is a list of solutions (target points) that can be used as an alternative for the current

   local optimal point. There is a probability of choosing one of the points of the particles memory instead of the current best point of the whole swarm Pgdb. The size of the memory list and the probability are new parameters added to the standard PSO algorithm. The algorithm is applied to the benchmark TSP instance burma14.

   The results obtained with algorithmic versions with several parameter settings are compared with the results of an Ant Colony Optimization algorithm. Pang et al. [29] extends the work of Wang et al. [26]. Their algorithm alternates among the continuous and the discrete (permutation) space. In order to avoid premature convergence, Pang et al. [29] use a chaotic operator. constant Dmin and the cost of the tour represented in the particles position.

3. PROPOSED SYSTEM

   1. LBMPSO

      Load balancing mutation PSO used to reschedule tasks that failure to schedule. PSO have two problems. First problem, tasks may failure to allocate to virtual machine. Second problem, task may allocate to more than one VM. In this phase solve the problems by reschedule wrong tasks and take in account load balancing of virtual machine. Solving these problems help to achieve reliability, users assert task executed without failure, minimize execution, minimize round trip time and improve other parameters.

      Fig.1: Proposed Model Structure

   2. Task Scheduling Problem Formulation of proposed systems

      There are several tasks (t) and several virtual machines (vms). There are n tasks and m number of virtual machines. Each task may allocate to any vm. Fig.2 shows mapping of Tasks to virtual machines. Each task must schedule to only one virtual machine.

      PSO attempts to select optimal distribution of tasks to virtual machines for achieving objective.

      Three mathematical models proposed for task scheduling. Each model consists of objective function and several constraints. Objective function of first model is to minimize execution time based on expected execution time (EETij) of task i in vmj. Equation (1) used in calculate processing time as: EET(processing time) = lengthi / mipsj. lengthi is number of instruction of task i require to execute. mipsj is number of Instructions executed by vm per second. Second objective function is to minimize transmission time (ETRTij)(6). Expected transmission time ( ETRTij ) of task i to vm j responsible for achieving second objective function. ETRTij equals file size / bandwidth. To minimize round trip time (RTT)

      (3) is achieved by third mathematical model.

      The RTT is the (latency) time for the whole procedure involving the sending and the receiving. ERTTij is expected round trip time calculate by ETRTij + delay + EETij + delay. xij is allocating task i to vm j or not . The value of xij may one or zero. Each model has the same constraints. Each Task allocate to only one virtual machine achieve by first constraint in (2). Equation (3) and (4) represent resource of all virtual machine less than or equal resource of datacenter. xij assign positive number (5).

   3. LOAD BALANCING MUTATION PARTICLE SWARM OPTIMIZATION ( LBMPSO)

   Obtaining an optimal schedule of tasks to resource with Considering constraints of a bi-objective optimization Problem are well-known problems in NP hard category[16]. The particle swarm optimization (PSO) algorithm is one of the heuristic techniques that used to obtain a feasible solution in reasonable time. PSO proposed. by Kennedy and Eberhart [17] . Initially, the PSO algorithm generates a set of particles randomly in the D dimensional search space. Particles defined as a potential solution to a problem. Each particle is represented by a Ddimensional vector Xi where i ranges from 1 to d represent as (xi1, xi2, …, xid).. Each particle is updated its position and its velocity according to equations 6, 7.In the iteration t, the velocity vi(t) has been update based on vi (t-

   1) is the velocity of the pervious iteration, r1, r2 mean a uniform random variables between 0 and 1 this two random values are generated independently, c1, c2 are a positive constant constants called acceleration coefficients, and w is the inertia weight. It also remembers the candidate solution of best fitness value it has achieved thus far during the search (individual best position (pbest)).

   Also, the PSO algorithm maintains candidate solution of the best fitness value achieved among all particles in the swarm (global best position (gbest)). Equation (7) updates each particle's position using the computed vi (t). Tasks allocated to vms using pso to achieve proposed mathematical model. In Task allocation using pso has some problem .such as, some task fail to allocate to vm or task allocate to more than one vm and premature convergence. Solving previous problem in Particle Swarm Optimization add Load balancing mutation to pso as show in Fig. 2. Load balancing mutation improved reliability,availability, minimize round trip time and minimize

   cost .The idea of Multi-objective Load balancing mutation Particle Swarm Optimization (MLBMPSO) reschedule the failure tasks to the available (VM) and reschedule tasks

   that allocate to more than VM with take into account load of each vm. LBM guarantee all vm executed number of tasks appropriate with their load of vm. In LBM, First Determine failure tasks and calculate load of virtual machines as load of vmi= (resource of vmi /total resource)*N. Then sort tasks based on resource needed and sort vms based on load. Last Reschedule failure tasks to vm based on load of each vm as in algorithm 1.

   Fig.2: MLBMPSO Algorithm

4. SIMULATION RESULT AND EVALUATION

   1. GRIDSIM

      Gridsim used to experiment proposed algorithm (MLBMPSO) and compared with, other algorithm. The experiments are implemented with 6 Datacenters with 50 VMs and 1000 tasks. The parameters of cloud simulation are shown in Table1.

      B.EXPERIMENTS AND RESULTS

      In evaluating of scheduling heuristic, each task is independent to other task. The average cost and average make span are parameters used in comparison between two algorithms.

      These comparisons obtained after 15 independent experiments done. We compared between Multi-objective load balancing mutation PSO, other algorithm [18].The result of comparisons between two algorithms based on different parameters when other algorithm group based on time show in fig.3-6.

      In Figure5-6 show comparisons between two algorithms when other algorithm group based on cost. The conclusions show that MLBMPSO is best algorithm which improve availability, reliability and consider load balancing between virtual machines. Also, make span and cost.

      Fig.3: Average Cost

      Fig.4: Average Makespan

      Fig.5: Average Cost

      Fig.5: Average Makespan

5. CONCLUSION

Task scheduling is one of the most important issues that effect in performance of Grid Computing environment.

There are many task scheduling algorithms which not consider important parameters such as availability and reliability. In this paper, we present Dynamic Multi objective task a scheduled based on load balancing Mutation Particle Swarm Optimization (MLBMPSO).

MLBMPSO improves the Reliability of Grid computing and consider availability of resources compared to other algorithms. MLBMPSO used to minimize total cost, minimize round trip time, improves task completion time, improve execution cost, good distribution of tasks onto resources, achieve load balancing between tasks and virtual machine and minimize the complexity in Grid computing environment. In addition, proposed algorithm consider the load balancing when schedule tasks to available and reschedule failure tasks to achieve reliability. It can be used to allocate any number of tasks and resources.

REFERENCES

P. Mell, and T. Grance. (2011). The NIST Definition of Grid computing

.NIST[Online]. Available: http://csrc.nist.gov/publications/nistpubs/800- 145/SP800- 145.pdf

1. R.Buyya ,C.S. Yeo, S.Venugopal ,J.Broberg and I.Brandic Grid computing and emerging IT platforms: Vision, hype, and reality for delivering computing as the 5th utility ,Future Generation Computer Systems , 2009 ,vol.25,no.6,pp.599616.

2. Paul, M. et al. Task scheduling in Grid computing using credit based assignment problem, International journal of Comput. Sci. Eng, 2011, pp. 26-30.

3. A.I.Awad, N.A.El-Hefnawy and H.M.Abdel_kader , Enhanced Particle Swarm Optimization For Task Scheduling In Grid computing Environments , in International Conference on Communication, Management and Information Technology (ICCMIT 2015),2015.

4. G.Caire, JADE Tutorial: JADE Programming for Beginners, http://sharon.cselt.it/projects/jade/

5. P. Angin and B. Bhargava, An Agent-based Optimization Framework for Mobile-Grid computing,Journal of Wireless Mobile Networks,Ubiquitous Computing, and Dependable Applications, 2013, vol. 4,pp. 1-17.

6. C.Mateos, E.Pacini and C. G.Garino,, An ACO-inspired algorithm for minimizing weighted flowtime in cloud-based parameter sweep experiments, Advances in Engineering Software, 2013, vol.56,pp. 38 50.

7. P.Samal and P.Mishra, "Analysis of variants in Round Robin Algorithms for load balancing in Grid computing", International Journal of Computer Science and Information Technologies, 2013, Vol. 4, no.3, pp. 416-419.

8. B.Mondala, K.Dasgupta and P.Duttab, Load Balancing in Grid computing using Stochastic Hill Climbing-A Soft Computing Approach, in 2nd International Conference on Computer, Communication, Control and Information Technology , on February 25 26, 2012, vol.4, PP. 783

   789,.

9. S.Pandey, L.Wu, S.M.Guru2 and R.Buyya, A Particle Swarm Optimization-based Heuristic for Scheduling Workflow Applications in Grid computing Environments, in IEEE International Conference on Advanced Information Networking and Applications (AINA), 2010, pp. 400 – 407.

10. G.Liu, J.Li and J.Xu, An Improved Min-Min Algorithm in Grid computing, Proceedings of the International Conference of Modern Computer Science and Applications, 2012, vol .191,pp.47-52.

11. W.Wang, G.Zeng, D.Tang and J.Yao,Cloud-DLS: Dynamic trusted scheduling for Grid computing, Expert Systems with Applications , 2012,vol.39,no.3, PP. 2321 2329,.

12. B. Xu, C.Zhao, E.Hu and B.Hu,Job scheduling algorithm based on Berger model in cloud environment, Advances in Engineering Software, 2011 ,vol. 42,no.7, PP. 419425.

13. S.Ambike, D.Bhansali, J.Kshirsagar and J.Bansiwal An

    Optimistic Differentiated Job Scheduling System for Grid computing International Journal of Engineering Research and Applications (IJERA) 2012, Vol. 2, no. 2, pp.1212-1214.

14. H.Zhong, K.Tao and X.Zhang , An Approach to Optimized Resource Scheduling Algorithm for Open-source Cloud Systems , in Fifth Annual China Grid Conference, ,on 16-18 July ,2010 , pp. 124 – 129.

15. A. S. Ajeena Beegom and M. S. Rajasree, A Particle Swarm Optimization Based Pareto Optimal Task Scheduling in Grid computing ,in Proceedings of 5th International Conference, ICSI 2014, October 17- 20, 2014 , pp 79-86.

16. Eberhart R , Kennedy J, A New Optimizer Using Particle Swarm Theory", 6th International Symposium. Micro Machine and Human Science, Nagoya;1995,p. 39-43.

17. M.Choudhary and S.K.Peddoju A Dynamic Optimization Algorithm for Task Scheduling in Cloud Environment ,International Journal of Engineering Research and Applications (IJERA), , 2012 Vol. 2, no.3, pp.2564-2568.

18. S.Ghanbaria and M.Othmana, A Priority based Job Scheduling Algorithm in Grid computing,in International Conference on Advances Science and Contemporary Engineering , 2012 ,vol.50, and PP. 778 785