Heuristics Analysis for Distributed Scheduling using MONARC Simulation Tool
Simulation is a very powerful method used for highperformance
and high-quality design in distributed system, and now
maybe the only one, considering the heterogeneity, complexity and
cost of distributed systems. In Grid environments, foe example, it is
hard and even impossible to perform scheduler performance
evaluation in a repeatable and controllable manner as resources and
users are distributed across multiple organizations with their own
policies. In addition, Grid test-beds are limited and creating an
adequately-sized test-bed is expensive and time consuming.
Scalability, reliability and fault-tolerance become important
requirements for distributed systems in order to support distributed
computation. A distributed system with such characteristics is called
dependable. Large environments, like Cloud, offer unique
advantages, such as low cost, dependability and satisfy QoS for all
users. Resource management in large environments address
performant scheduling algorithm guided by QoS constrains. This
paper presents the performance evaluation of scheduling heuristics
guided by different optimization criteria. The algorithms for
distributed scheduling are analyzed in order to satisfy users
constrains considering in the same time independent capabilities of
resources. This analysis acts like a profiling step for algorithm
calibration. The performance evaluation is based on simulation. The
simulator is MONARC, a powerful tool for large scale distributed
systems simulation. The novelty of this paper consists in synthetic
analysis results that offer guidelines for scheduler service
configuration and sustain the empirical-based decision. The results
could be used in decisions regarding optimizations to existing Grid
DAG Scheduling and for selecting the proper algorithm for DAG
scheduling in various actual situations.
[1] Florin Pop. 2011, Simulation based Evaluation of QoS-guided
Scheduling for Distributed Computing in Large Environments, In Proc.
of ESM 2011, The 2011 European Simulation and Moelling Confernce,
October 24-26, University of Minho, Portugal, pp: 84-90.
[2] Ciprian Dobre, Florin Pop, and Valentin Cristea. 2009. New Trends in
Large Scale Distributed Systems Simulation. In Proceedings of the 2009
International Conference on Parallel Processing Workshops (ICPPW
'09). IEEE Computer Society, Washington, DC, USA, 182-189.
[3] Fatos Xhafa and Ajith Abraham. 2010. Computational models and
heuristic methods for Grid scheduling problems. Future Gener. Comput.
Syst. 26, 4 (April 2010), 608-621.
[4] Florin Pop and Valentin Cristea. 2009. Decentralised meta-scheduling
strategy in Grid environments. Int. J. Grid Util. Comput. 1, 3 (August
2009), 185-193.
[5] Li Chunlin and Li Layuan. 2007. Optimization decomposition approach
for layered QoS scheduling in grid computing. J. Syst. Archit. 53, 11
(November 2007), 816-832.
[6] Peng Li and Binoy Ravindran. 2004. Fast, Best-Effort Real-Time
Scheduling Algorithms. IEEE Trans. Comput. 53, 9 (September 2004),
1159-1175.
[7] Zhiang Wu, Junzhou Luo, and Fang Dong. 2006. Measurement model of
grid QoS and multi-dimensional QoS scheduling. In Proceedings of the
10th international conference on Computer supported cooperative work
in design III (CSCWD'06), Weiming Shen, Junzhou Luo, Zongkai Lin,
Jean-Paul A. Barthos, and Qi Hao (Eds.). Springer-Verlag, Berlin,
Heidelberg, 509-519.
[8] Florin Pop, Ciprian Dobre, and Valentin Cristea. 2008. Performance
Analysis of Grid DAG Scheduling Algorithms using MONARC
Simulation Tool. In Proceedings of the 2008 International Symposium
on Parallel and Distributed Computing (ISPDC '08).
[9] Fabricio A. B. da Silva and Hermes Senger. 2011. Scalability limits of
Bag-of-Tasks applications running on hierarchical platforms. J. Parallel
Distrib. Comput. 71, 6 (June 2011), 788-801.
[10] N.M. Amato, P. An. 2000. Task scheduling and parallel mesh-sweeps in
transport computations, Technical Report TR00-009, Department of
Computer Science, Texas A&M University, January 2000.
[11] Hamed Nooraliei and Amir Nooraliei. 2009. Path Planning Using Wave
Front's Improvement Methods. In Proceedings of the 2009 International
Conference on Computer Technology and Development - Volume
01 (ICCTD '09), Vol. 1. IEEE Computer Society, Washington, DC,
USA, 259-264.
[12] Marek Wieczorek, Andreas Hoheisel, and Radu Prodan. 2009. Towards
a general model of the multi-criteria workflow scheduling on the
grid. Future Gener. Comput. Syst. 25, 3 (March 2009), 237-256.
[13] Dalibor Klus├í─ìek, Lud─øk Matyska, and Hana Rudov├í. 2007. Alea: grid
scheduling simulation environment. In Proceedings of the 7th
international conference on Parallel processing and applied
mathematics (PPAM'07), Roman Wyrzykowski, Konrad Karczewski,
Jack Dongarra, and Jerzy Wasniewski (Eds.). Springer-Verlag, Berlin,
Heidelberg, 1029-1038.
[14] Hui Li and Rajkumar Buyya. 2009. Model-based simulation and
performance evaluation of grid scheduling strategies. Future Gener.
Comput. Syst. 25, 4 (April 2009), 460-465.
[15] Sugree Phatanapherom, Putchong Uthayopas, and Voratas
Kachitvichyanukul. 2003. Dynamic scheduling II: fast simulation model
for grid scheduling using HyperSim. In Proceedings of the 35th
conference on Winter simulation: driving innovation (WSC '03). Winter
Simulation Conference 1494-1500.
[16] Yanfang Fu and Yan Fan. 2010. Research of the Simulation Grid System
Based on Multi-agent Dynamic Scheduling. In Proceedings of the 2010
Second International Conference on Computer Modeling and Simulation
- Volume 03 (ICCMS '10), Vol. 3. IEEE Computer Society, Washington,
DC, USA, 392-395.
[17] Ciprian Dobre, Corina Stratan, and Valentin Cristea. 2008. Realistic
Simulation of Large Scale Distributed Systems using Monitoring.
In Proceedings of the 2008 International Symposium on Parallel and
Distributed Computing (ISPDC '08). IEEE Computer Society,
Washington, DC, USA, 434-438
[1] Florin Pop. 2011, Simulation based Evaluation of QoS-guided
Scheduling for Distributed Computing in Large Environments, In Proc.
of ESM 2011, The 2011 European Simulation and Moelling Confernce,
October 24-26, University of Minho, Portugal, pp: 84-90.
[2] Ciprian Dobre, Florin Pop, and Valentin Cristea. 2009. New Trends in
Large Scale Distributed Systems Simulation. In Proceedings of the 2009
International Conference on Parallel Processing Workshops (ICPPW
'09). IEEE Computer Society, Washington, DC, USA, 182-189.
[3] Fatos Xhafa and Ajith Abraham. 2010. Computational models and
heuristic methods for Grid scheduling problems. Future Gener. Comput.
Syst. 26, 4 (April 2010), 608-621.
[4] Florin Pop and Valentin Cristea. 2009. Decentralised meta-scheduling
strategy in Grid environments. Int. J. Grid Util. Comput. 1, 3 (August
2009), 185-193.
[5] Li Chunlin and Li Layuan. 2007. Optimization decomposition approach
for layered QoS scheduling in grid computing. J. Syst. Archit. 53, 11
(November 2007), 816-832.
[6] Peng Li and Binoy Ravindran. 2004. Fast, Best-Effort Real-Time
Scheduling Algorithms. IEEE Trans. Comput. 53, 9 (September 2004),
1159-1175.
[7] Zhiang Wu, Junzhou Luo, and Fang Dong. 2006. Measurement model of
grid QoS and multi-dimensional QoS scheduling. In Proceedings of the
10th international conference on Computer supported cooperative work
in design III (CSCWD'06), Weiming Shen, Junzhou Luo, Zongkai Lin,
Jean-Paul A. Barthos, and Qi Hao (Eds.). Springer-Verlag, Berlin,
Heidelberg, 509-519.
[8] Florin Pop, Ciprian Dobre, and Valentin Cristea. 2008. Performance
Analysis of Grid DAG Scheduling Algorithms using MONARC
Simulation Tool. In Proceedings of the 2008 International Symposium
on Parallel and Distributed Computing (ISPDC '08).
[9] Fabricio A. B. da Silva and Hermes Senger. 2011. Scalability limits of
Bag-of-Tasks applications running on hierarchical platforms. J. Parallel
Distrib. Comput. 71, 6 (June 2011), 788-801.
[10] N.M. Amato, P. An. 2000. Task scheduling and parallel mesh-sweeps in
transport computations, Technical Report TR00-009, Department of
Computer Science, Texas A&M University, January 2000.
[11] Hamed Nooraliei and Amir Nooraliei. 2009. Path Planning Using Wave
Front's Improvement Methods. In Proceedings of the 2009 International
Conference on Computer Technology and Development - Volume
01 (ICCTD '09), Vol. 1. IEEE Computer Society, Washington, DC,
USA, 259-264.
[12] Marek Wieczorek, Andreas Hoheisel, and Radu Prodan. 2009. Towards
a general model of the multi-criteria workflow scheduling on the
grid. Future Gener. Comput. Syst. 25, 3 (March 2009), 237-256.
[13] Dalibor Klus├í─ìek, Lud─øk Matyska, and Hana Rudov├í. 2007. Alea: grid
scheduling simulation environment. In Proceedings of the 7th
international conference on Parallel processing and applied
mathematics (PPAM'07), Roman Wyrzykowski, Konrad Karczewski,
Jack Dongarra, and Jerzy Wasniewski (Eds.). Springer-Verlag, Berlin,
Heidelberg, 1029-1038.
[14] Hui Li and Rajkumar Buyya. 2009. Model-based simulation and
performance evaluation of grid scheduling strategies. Future Gener.
Comput. Syst. 25, 4 (April 2009), 460-465.
[15] Sugree Phatanapherom, Putchong Uthayopas, and Voratas
Kachitvichyanukul. 2003. Dynamic scheduling II: fast simulation model
for grid scheduling using HyperSim. In Proceedings of the 35th
conference on Winter simulation: driving innovation (WSC '03). Winter
Simulation Conference 1494-1500.
[16] Yanfang Fu and Yan Fan. 2010. Research of the Simulation Grid System
Based on Multi-agent Dynamic Scheduling. In Proceedings of the 2010
Second International Conference on Computer Modeling and Simulation
- Volume 03 (ICCMS '10), Vol. 3. IEEE Computer Society, Washington,
DC, USA, 392-395.
[17] Ciprian Dobre, Corina Stratan, and Valentin Cristea. 2008. Realistic
Simulation of Large Scale Distributed Systems using Monitoring.
In Proceedings of the 2008 International Symposium on Parallel and
Distributed Computing (ISPDC '08). IEEE Computer Society,
Washington, DC, USA, 434-438
@article{"International Journal of Information, Control and Computer Sciences:60638", author = "Florin Pop", title = "Heuristics Analysis for Distributed Scheduling using MONARC Simulation Tool", abstract = "Simulation is a very powerful method used for highperformance
and high-quality design in distributed system, and now
maybe the only one, considering the heterogeneity, complexity and
cost of distributed systems. In Grid environments, foe example, it is
hard and even impossible to perform scheduler performance
evaluation in a repeatable and controllable manner as resources and
users are distributed across multiple organizations with their own
policies. In addition, Grid test-beds are limited and creating an
adequately-sized test-bed is expensive and time consuming.
Scalability, reliability and fault-tolerance become important
requirements for distributed systems in order to support distributed
computation. A distributed system with such characteristics is called
dependable. Large environments, like Cloud, offer unique
advantages, such as low cost, dependability and satisfy QoS for all
users. Resource management in large environments address
performant scheduling algorithm guided by QoS constrains. This
paper presents the performance evaluation of scheduling heuristics
guided by different optimization criteria. The algorithms for
distributed scheduling are analyzed in order to satisfy users
constrains considering in the same time independent capabilities of
resources. This analysis acts like a profiling step for algorithm
calibration. The performance evaluation is based on simulation. The
simulator is MONARC, a powerful tool for large scale distributed
systems simulation. The novelty of this paper consists in synthetic
analysis results that offer guidelines for scheduler service
configuration and sustain the empirical-based decision. The results
could be used in decisions regarding optimizations to existing Grid
DAG Scheduling and for selecting the proper algorithm for DAG
scheduling in various actual situations.", keywords = "Scheduling, Simulation, Performance Evaluation,
QoS, Distributed Systems, MONARC", volume = "6", number = "1", pages = "90-7", }