Heuristics Analysis for Distributed Scheduling using MONARC Simulation Tool

Authors: Florin Pop

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

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

References:

[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