Modern approaches to modeling user requirements on resource and task allocation in hierarchical computational grids

Kołodziej, J. ; Xhafa, F.

International Journal of Applied Mathematics and Computer Science, Tome 21 (2011) no. 2, pp. 243-257.

Résumé

Tasks scheduling and resource allocation are among crucial issues in any large scale distributed system, including Computational Grids (CGs). These issues are commonly investigated using traditional computational models and resolution methods that yield near-optimal scheduling strategies. One drawback of such approaches is that they cannot effectively tackle the complex nature of CGs. On the one hand, such systems account for many administrative domains with their own access policies, user privileges, etc. On the other, CGs have hierarchical nature and therefore any computational model should be able to effectively express the hierarchical architecture in the optimization model. Recently, researchers have been investigating the use of game theory for modeling user requirements regarding task and resource allocation in grid scheduling problems. In this paper we present two general non-cooperative game approaches, namely, the symmetric non-zero sum game and the asymmetric Stackelberg game for modeling grid user behavior defined as user requirements. In our game-theoretic approaches we are able to cast new requirements arising in allocation problems, such as asymmetric users relations, security and reliability restrictions in CGs. For solving the games, we designed and implemented GA-based hybrid schedulers for approximating the equilibrium points for both games. The proposed hybrid resolution methods are experimentally evaluated through the grid simulator under heterogeneity, and large-scale and dynamics conditions. The relative performance of the schedulers is measured in terms of the makespan and flowtime metrics. The experimental analysis showed high efficiency of meta-heuristics in solving the game-based models, especially in the case of an additional cost of secure task scheduling to be paid by the users.

Détail

Keywords: computational grids, scheduling, non-cooperative games, user behavior, security, meta-heuristics
Mots-clés : przetwarzanie siatkowe, szeregowanie, bezpieczeństwo

Bibliographie

[1] Abraham, A., Buyya, R. and Nath, B. (2000). Nature's heuristics for scheduling jobs on computational grids, Proceedings of the 8th IEEE International Conference on Advanced Computing and Communications (ADCOM 2000), New Delhi, India, pp. 45-52.

[2] Ali, S., Siegel, H., Maheswaran, M. and Hensgen, D. (2000). Task execution time modeling for heterogeneous computing system, Proceedings of the Heterogeneous Computing Workshop, Cancun, Mexico, pp. 185-199.

[3] Baçsar, T. and Olsder, G. (1995). Dynamic Non-cooperative Game Theory, 2nd Edn., Academic Press, London.

[4] Brandic, I., Pllana, S. and Benkner, S. (2006). An approach for the high-level specification of qos-aware grid workflows considering location affinity, Scientific Programming 14(3-4): 231-250.

[5] Braun, T., Siegel, H. J., Beck, N., Boloni, L. L., Maheswaran, M., Reuther, A. I., Robertson, J. P., Theys, M. D., Yao, B., Hensgen, D. and Freund, R. F. (2001). A comparison of eleven static heuristics for mapping a class of independent tasks onto heterogeneous distributed computing systems, Journal of Parallel and Distributed Computing 61(6): 810-837.

[6] Buyya, R., Abramson, D. and Giddy, J. (2000). An economy driven resource management architecture for global computational power grids, Proceedings of the International Conference on Parallel and Distributed Processing Techniques and Applications (PDPTA 2000), Las Vegas, NV, USA, pp. 517-525.

[7] Buyya, R., Abramson, D., Giddy, J. and Stockinger, H. (2002). Economic models for resource management and scheduling in grid computing, Journal of Concurrency and Computation: Practice and Experience 14(13-15): 1507-1542.

[8] Buyya, R. and Bubendorfer, K. (2009). Market Oriented Grid and Utility Computing, Wiley Press, New York, NY.

[9] Edlefsen, L. and Millham, C. (1972). On a formulation of discrete n-person non-cooperative games, Metrika 18(1): 31-34.

[10] Garg, S., Buyya, R. and Segel, H. (2009). Scheduling parallel aplications on utility grids: Time and cost trade-off management, Proceedings of the Thirty-Second Australasian Conference on Computer Science, Vol. 91, Australian Computer Society, Inc., Darlinghurst, Australia, pp. 139-147.

[11] Ghosh, P., Roy, N., Basu, K. and Das, S. (2005). A game theory based pricing strategy for job allocation in mobile grids, Journal of Parallel and Distributed Computing 65(11): 1366-1383.

[12] Hwang, S. and Kesselman, C. (2003). A flexible framework for fault tolerance in the grid, Journal of Grid Computing 1(3): 251-272.

[13] Khan, S. and Ahmad, I. (2006). Non-cooperative, semicooperative, and cooperative games-based grid resource allocation, Proceedings of the International Parallel and Distributed Proceedings Symposium (IPDPS 2006), Rhodes Island, Greece, pp. 101-104.

[14] Kołodziej, J. and Xhafa, F. (2010). A game-theoretic and hybrid genetic meta-heuristic model for security-assured scheduling of independent jobs in computational grids, in L. Barolli, F. Xhafa and S. Venticinque (Eds.) Proceedings of CISIS 2010, Kraków, Poland, IEEE Press, Los Alamitos, CA, pp. 93-100.

[15] Kołodziej, J., Xhafa, F. and Kolanko, Ł. (2009). Hierarchic genetic scheduler of independent jobs in computational grid environment, in J. Otamendi, A. Bargieła, J. L. Montes and L. M. Doncel Pedrera (Eds.), Proceedings of ECMS 2009, Madrid, Spain, IEEE Press, Los Alamitos, CA, pp. 108-115.

[16] Kwok, Y.-K., Hwang, K. and Song, S. (2007). Selfish grids: Game-theoretic modeling and nas/psa benchmark evaluation, IEEE Transactions on Parallel and Distributing Systems 18(5): 1-16.

[17] Laccetti, G. and Schmidb, G. (2007). A framework model for grid security, Future Generation Computer System 23(5): 702-713.

[18] Lim, D., Ong, Y.-S. and Jin, Y. (2007). Efficient hierarchical parallel genetic algorithms using grid computing, Future Generation Computer System 23(4): 658-670.

[19] Lin, C., Wang, V. V. Y. and Pruthi, V. (2004). Enhancing grid security with trust management, Proceedings of the 2004 IEEE international Conference on Services Computing, (SCC 2004,), Sanghai, China, pp. 303-310.

[20] Liu, H., Abraham, A. and Hassanien, A. (2009). Scheduling jobs on computational grids using a fuzzy particle swarm optimization algorithm, Future Generation Computer System 26(8): 1336-1343.

[21] Mesghouni, K., Hammadi, S. and Borne, P. (2004). Evolutionary algorithms for job-shop scheduling, International Journal of AppliedMathematics and Computer Science 14(1): 91-103.

[22] Pavlidis, N., Parsopoulos, K. and Vrahatis, M. (2005). Computing nash equilibria through computational intelligence methods, Journal of Computational and Applied Mathematics 175(1): 113-136.

[23] Regev, O. and Nisan, N. (2000). The popcorn market-Online markets for computational resources, Decision Support Systems 28(1-2): 177-189.

[24] Ritchie, G. and Levine, J. (2003). A fast effective local search for scheduling independent jobs in heterogeneous computing environments, Technical report, Centre for Intelligent Systems and Their Applications, School of Informatics, University of Edinburgh, Edinburgh.

[25] Roughgarden, T. (2004). Stackelberg scheduling strategies, SIAM Journal on Computing 33(2): 332-350.

[26] Song, S., Hwang, K. and Kwok, Y. (2005). Trusted grid computing with security binding and trust integration, Journal of Grid Computing 3(1-2): 53-73.

[27] Song, S., Hwang, K. and Kwok, Y.-K. (2006). Risk-resilient heuristics and genetic algorithms for security-assured grid job scheduling, IEEE Transactions on Computers 55(6): 703-719.

[28] Straffin, P. (1996). Game Theory and Strategy, Mathematical Association of America Textbooks, Washington, DC.

[29] Subrata, R., Zomaya, A. Y. and Landfeldt, B. (2010). Cooperative power-aware scheduling in grid computing environments, Journal of Parallel and Distributed Computing 70(2): 84-91.

[30] Wolski, R., Plank, J., Bryan, T. and Brevik, J. (2001). Gcommerce: Market formulations controlling resource allocation on the computational grid, Proceedings of the 15th International Parallel and Distributed Processing Symposium (IPDPS'01), San Francisco, CA, USA.

[31] Wu, C. and Sun, R.-Y. (2010). An integrated security-aware job scheduling strategy for large-scale computational grids, Future Generation Computer Systems 26(2): 198-206.

[32] Xhafa, F. and Abraham, A. (2010). Computational models and heuristic methods for grid scheduling problems, Future Generation Computer Systems 26(4): 608-621.

[33] Xhafa, F., Barolli, L. and Durresi, A. (2008). An experimental study on genetic algorithms for resource allocation on grid systems, Journal of Interconnection Networks 8(4): 427-443.

[34] Xhafa, F., Carretero, J. and Abraham, A. (2007). Genetic algorithm based schedulers for grid computing systems, International Journal of Innovative Computing, Information and Control 3(5): 1-19.

[35] Xhafa, F., Carretero, J., Alba, E. and Dorronsoro, B. (2009). Tabu search algorithm for scheduling independent jobs in computational grids, Computer and Informatics Journal 28(2): 237-249.

[36] Xhafa, F., Gonzalez, J., Dahal, K. and Abraham, A. (2009). A GA(TS) hybrid algorithm for scheduling in computational grids, in E. Corchado, X. Wu, E. Oja, Á. Herrero and B. Baruque (Eds.), Hybrid Artificial Inteligence Systems, Lecture Notes in Computer Science, Vol. 5572, Springer, Berlin/Heidelberg, pp. 285-292.