Grid workflow scheduling based on reliability cost

ABSTRACT

Grid workflow is a complex and typical grid application, but owing to the highly dynamic feature of grid environments, resource unavailability is increasingly becoming severe and poses great challenges to grid workflow scheduling. Though fault recovery mechanism adopted in grid system guarantee the completion of jobs to some extent, but wasting system resources. To overcome the shortcoming, this paper proposes a Markov Chain based grid node availability prediction model which can efficiently predict grid nodes' availability in the future without adding significant overhead. Based on this model, the paper presents a grid workflow scheduling based on reliability cost (RCGS). The performance evaluation results demonstrate that RCGS improves the dependability of workflow execution and success ratio of tasks with low reliability cost.

REFERENCES

• 1: Ian Foster , Carl Kesselman, The grid: blueprint for a new computing infrastructure, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1998
• 2: Soonwook Hwang , Carl Kesselman, GridWorkflow: A Flexible Failure Handling Framework for the Grid, Proceedings of the 12th IEEE International Symposium on High Performance Distributed Computing, p.126, June 22-24, 2003
• 3: A taxonomy and survey of grid resource management systems for distributed computing, Software—Practice & Experience, v.32 n.2, p.135-164, February 2002 [doi>10.1002/spe.432 ]
• 4: Cooper, K., Dasgupata, A., and Kennedy, K., eds. New Grid Scheduling and Rescheduling Methods in the GrADS Project. NSF Next Generation Software Workshop, International Parallel and Distributed Processing Symposium, Santa Fe, IEEE CS Press, Los Alamitos, CA, USA, April 2004.
• 5: Junwei Cao , Stephen A. Jarvis , Subhash Saini , Graham R. Nudd, GridFlow: Workflow Management for Grid Computing, Proceedings of the 3st International Symposium on Cluster Computing and the Grid, p.198, May 12-15, 2003
• 6: Rajkumar Buyya , Manzur Murshed , David Abramson , Srikumar Venugopal, Scheduling parameter sweep applications on global Grids: a deadline and budget constrained cost-time optimization algorithm, Software—Practice & Experience, v.35 n.5, p.491-512, 25 April 2005 [doi>10.1002/spe.646]
• 7: Sandholm, T. and Lai, K. Market-Based Resource Allocation using Price Prediction in a High Performance Computing Grid for Scientific Applications. In Proc. of Fifteenth IEEE International Symposium on High Performance Distributed Computing (HPDC-15), IEEE Computer Society, June 19--23, 2006, Paris, France, pp.132--143.
• 8: Srikumar Venugopal , Rajkumar Buyya , Lyle Winton, A grid service broker for scheduling distributed data-oriented applications on global grids, Proceedings of the 2nd workshop on Middleware for grid computing, p.75-80, October 18-22, 2004, Toronto, Ontario, Canada [doi>10.1145/1028493.1028506]
• 9: Zhao, S. Y. and Lo, V. Result Verification and Trust-based Scheduling in Open Peer-to-Peer Cycle Sharing Systems. Technical Report, University of Oregon, USA, 2005.
• 10: Song, S. S. and Hwang, K. Security Binding for Trusted Job Outsourcing in Open Computational Grids. IEEE Transactions on Parallel and Distributed Systems (TPDS), submitted May 2004, revised Dec. 2004.
• 11: Shanshan Song , Yu-Kwong Kwok , Kai Hwang, Security-Driven Heuristics and A Fast Genetic Algorithm for Trusted Grid Job Scheduling, Proceedings of the 19th IEEE International Parallel and Distributed Processing Symposium (IPDPS'05) - Papers, p.65.1, April 04-08, 2005 [doi>10.1109/IPDPS.2005.397]
• 12: He, Y., Shao, Z., Xiao, B., Zhuge, Q., and Sha, E. Reliability Driven Task Scheduling for Heterogeneous Systems. In Proc. of The Fifteenth IASTED International Conference on Parallel and Distributed Computing and Systems, Vol.1, 465--470, 11/2003.
• 13: Ramendra K. Sahoo , Anand Sivasubramaniam , Mark S. Squillante , Yanyong Zhang, Failure Data Analysis of a Large-Scale Heterogeneous Server Environment, Proceedings of the 2004 International Conference on Dependable Systems and Networks, p.772, June 28-July 01, 2004
• 14: Taliver Heath , Richard P. Martin , Thu D. Nguyen, Improving cluster availability using workstation validation, Proceedings of the 2002 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, June 15-19, 2002, Marina Del Rey, California
• 15: R. K. Sahoo , A. J. Oliner , I. Rish , M. Gupta , J. E. Moreira , S. Ma , R. Vilalta , A. Sivasubramaniam, Critical event prediction for proactive management in large-scale computer clusters, Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2003, Washington, D.C. [doi>10.1145/956750.956799]
• 16: J. Brevik , D. Nurmi , R. Wolski, Automatic methods for predicting machine availability in desktop Grid and peer-to-peer systems, Proceedings of the 2004 IEEE International Symposium on Cluster Computing and the Grid, p.190-199, April 19-22, 2004
• 17: Xiaojuan Ren , Rudolf Eigenmann , Saurabh Bagchi, Failure-aware checkpointing in fine-grained cycle sharing systems, Proceedings of the 16th international symposium on High performance distributed computing, June 25-29, 2007, Monterey, California, USA [doi>10.1145/1272366.1272372]
• 18: Gilks, W. R., Richardson S., and Spiegelhalter, D. J. A. Introducing Markov chain Monte Carlo. pp.1--19, In Markov Chain Monte Carlo in Practice, Chapman & Hall, London.
• 19: Sakellariou, R. and Zhao, H. A hybrid heuristic for dag scheduling on heterogeneous systems. In Proc. of 13th Heterogeneous Computing Workshop (HCW-2004), Santa Fe, New Mexico, USA, 2004.
• 20: Anirban Mandal , K. Kennedy , C. Koelbel , G. Marin , J. Mellor-Crummey , B. Liu , L. Johnsson, Scheduling strategies for mapping application workflows onto the grid, Proceedings of the High Performance Distributed Computing, 2005. HPDC-14. Proceedings. 14th IEEE International Symposium, p.125-134, July 24-27, 2005 [doi>10.1109/HPDC.2005.1520947]
• 21: http://www.chinagrid.edu.cn/CGSP/
• 22: Petri, C. A. Kommunikation mit Automaten. PhD Thesis, Institut für instrumentelle Mathematik, Bonn, 1962
• 23: Object Management Group, Unified Modeling Language (UML), http://www.uml.org/
• 24: Altintas, I., Birnbaum, A., Baldridge, K., Sudholt, W., Miller, M., Amoreira, C., Potier, Y., and Ludaescher, B. A. Framework for the Design and Reuse of Grid Workflows. In Proc. of International Workshop on Scientific Applications on Grid Computing (SAG'04), LNCS 3458, Springer, 2005.
• 25: Haluk Topcuouglu , Salim Hariri , Min-you Wu, Performance-Effective and Low-Complexity Task Scheduling for Heterogeneous Computing, IEEE Transactions on Parallel and Distributed Systems, v.13 n.3, p.260-274, March 2002 [doi>10.1109/71.993206 ]
• 26: Zhao, H. and Sakellarion, R. An experimental investigation into the rank function of the heterogeneous earliest finish time scheduling algorithm. In Proc. of Euro-Par 2003. Springer-Verlag, LNCS 2790, 2003.
• 27: Rizos Sakellariou , Henan Zhao, A low-cost rescheduling policy for efficient mapping of workflows on grid systems, Scientific Programming, v.12 n.4, p.253-262, December 2004
• 28: Sakellariou, R. and Zhao, H. A Hybrid Heuristic for DAG Scheduling on Heterogeneous Systems. In Proceedings of 13^th Heterogeneous Computing Workshop (HCW 2004), 26--30 April 2004, Santa Fe, New Mexico, USA.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems

General Terms:
Design, Experimentation, Standardization

Keywords:
Markov chain, grid computing, reliability cost, workflow