A Budget and Deadline Constrained Fault Tolerant Load Balanced Scheduling Algorithm for Computational Grids
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.
[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).
[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).
@article{"International Journal of Information, Control and Computer Sciences:69852", author = "P. Keerthika and P. Suresh", title = "A Budget and Deadline Constrained Fault Tolerant Load Balanced Scheduling Algorithm for Computational Grids", 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.", volume = "9", number = "2", pages = "555-8", }
