A Budget and Deadline Constrained Fault Tolerant Load Balanced Scheduling Algorithm for Computational Grids

Authors: P. Keerthika, P. Suresh

Abstract:

Grid is an environment with millions of resources which are dynamic and heterogeneous in nature. A computational grid is one in which the resources are computing nodes and is meant for applications that involves larger computations. A scheduling algorithm is said to be efficient if and only if it performs better resource allocation even in case of resource failure. Resource allocation is a tedious issue since it has to consider several requirements such as system load, processing cost and time, user’s deadline and resource failure. This work attempts in designing a resource allocation algorithm which is cost-effective and also targets at load balancing, fault tolerance and user satisfaction by considering the above requirements. The proposed Budget Constrained Load Balancing Fault Tolerant algorithm with user satisfaction (BLBFT) reduces the schedule makespan, schedule cost and task failure rate and improves resource utilization. Evaluation of the proposed BLBFT algorithm is done using Gridsim toolkit and the results are compared with the algorithms which separately concentrates on all these factors. The comparison results ensure that the proposed algorithm works better than its counterparts.

Keywords: Grid Scheduling, Load Balancing, fault tolerance, makespan, cost, resource utilization.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1100891

References:

[1] S. Parsa and R.E. Maleki, RASA: A New Grid Task Scheduling Algorithm, World Applied Sciences Journal, 7 (2009) 152-160.
[2] N. Malarvizhi and V.R. Uthariaraj, A minimum time to release job scheduling algorithm in computational grid environment, Proceedings of the IEEE Fifth International Joint Conference on INC, IMS & IDC, (2009) 13-18, DOI: 10.1109/NCM.2009.373.
[3] Z. Qian, Design of Grid Resource Management System Based on Information Service, J Computers, 5 (5) (2010) 687-694.
[4] H. Lee, D. Park, M. Hong, S.S. Yeo, S.K. Kim and S.H. Kim, A resource management system for fault tolerance in grid computing, Proceedings of the IEEE International Conference on Computational Science and Engineering, (2009) 609-614, DOI: 10.1109/CSE.2009.257.
[5] M. Nandagopal and V.R.Uthariaraj, Fault tolerant Scheduling strategy for computational grid environment, Int J Engineering Science and Technology, 2 (9) (2010) 4361-4372.
[6] B. Schroeder and G.A. Gibson, A large-scale study of failures in highperformance computing systems, IEEE Trans Dependable and Secure Computing, 7(4) (2010) 337-350, DOI: 10.1109/TDSC.2009.4.
[7] F.G. Khan, K. Qureshi and B. Nazir,Performance Evaluation of Fault Tolerance techniques in Grid Computing System, J Computers and Electrical Engineering, 36 (6) (2010) 1110-1122, http://dx.doi.org/10.1016/j.compeleceng.2010. 04. 004.
[8] R. Garg and A.K. Singh, Fault Tolerance in grid computing: State of the art and open issues, Int J Computer Science & Engineering Survey, 2 (1) (2011) 88-97, DOI:10.5121/ijcses.2011.2107.
[9] M. Amoon, A development of fault- tolerant and scheduling system for grid computing, GESJ: Computer Science and Telecommunications, 3 (32) (2011) 44-52.
[10] R. Buyya, M. Murshed and D. Abramson, A deadline and budget constrained cost-time optimization algorithm for Scheduling task farming applications on global grids, Proceedings of the International conference on parallel and distributed processing techniques and applications, (2001) 24–27, http://arxiv.org/ftp/cs/papers/0203/0203020.pdf.
[11] P. Suresh and P. Balasubramanie, User demand aware scheduling algorithm for data intensive tasks in grid environment, European Journal of Scientific Research, 74 (4) (2012) 609-616.
[12] P. Suresh and P. Balasubramanie, Grouping based User Demand Aware job scheduling Approach for computational Grid, Int J Engineering Science and Technology, 4 (12) (2012) 4922-4928, http://www.ijest.info/docs/IJEST12-04-12-093.pdf.
[13] S. Kaur and S. Kaur, Efficient load balancing grouping based job scheduling algorithm in grid computing, Int J Emerging Trends and Technology in Computer Science,2(4)(2013) 138-144.
[14] M.A. Salehi, H. Deldari and B.M. Dorri, Balancing Load in a Computational Grid Applying Adaptive, Intelligent Colonies of Ants, Informatica, 33 (2) (2008) 159-167.
[15] K.Q. Yan, S.S. Wang, S.C. Wang and C.P. Chang, Towards a hybrid load balancing policy in grid computing system, Expert Systems with Applications, 36 (10) (2009) 12054-12064.
[16] B. Yagoubi and M. Meddeber, Distributed Load Balancing Model for Grid Computing, ARIMA Journal, 12 (2010) 43-60.
[17] K.S. Chatrapati,J.U. Rekha, and A.V. Babu, Competitive equilibrium approach for load balancing a computational grid with communication delays, J Theoretical and Applied Information Technology, 19 (2) (2010) 126–133.
[18] R.U. Payli, K. Erciyes, and O. Dagdeviren, Cluster-Based Load Balancing Algorithms for Grids, Int J Computer Networks & Communications, 3 (5) (2011) 253-269.
[19] J. Balasangameshwara and N. Raju, A hybrid policy for fault tolerant Load Balancing in grid computing environments, J Network and Computer Applications, 35 (1) (2012) 412-422, http://dx.doi.org / 10.1016 / j.jnca.2011.09.005,
[20] A.K. Bardsiri and M.K. Rafsanjani, A New Heuristic Approach Based on Load Balancing for Grid Scheduling Problem, J Convergence Information Technology, 7(1) (2012) 329-336.
[21] Y. Hao, G. Liu and N. Wen, An enhanced load balancing mechanism based on deadline control on GridSim, Future Generation Computer Systems, 28 (4) (2012) 657-665.
[22] D. Ramesh and A. Krishnan, Hybrid Algorithm for Optimal Load Sharing in Grid Computing, J Computer Science, 8 (1) (2012) 175-180.
[23] P. Keerthika and N. Kasthuri, An Efficient Grid Scheduling Algorithm with Fault Tolerance and User Satisfaction, Mathematical Problems in Engineering, 2013 (Article ID 340294) (2013).
[24] P. Keerthika and N. Kasthuri, A Hybrid Scheduling Algorithm with Load Balancing for Computational Grid, Int J Advanced Science and Technology, 58 (2013) 13-28.
[25] P. Keerthika and N. Kasthuri, An Efficient Fault Tolerant Scheduling Approach for Computational Grid, American J Applied Sciences, 9 (12) (2013) 2046-2051, Doi:10.3844/ajassp.2012.2046.2051.
[26] P. Suresh,P. Balasubramanie and P. Keerthika, Prioritized User Demand Approach for Scheduling Meta Tasks on Heterogeneous Grid Environment, Int J Computer Applications, 23 (1) (2011).
[27] P. Suresh and P. Balasubramanie, User Demand Aware Grid Scheduling Model with Hierarchical Load Balancing, Mathematical Problems in Engineering, 2013 (Article ID 439362) (2013).