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

Joanna Kołodziej; Fatos Xhafa

International Journal of Applied Mathematics and Computer Science (2011)

  • Volume: 21, Issue: 2, page 243-257
  • ISSN: 1641-876X

Abstract

top
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.

How to cite

top

Joanna Kołodziej, and Fatos Xhafa. "Modern approaches to modeling user requirements on resource and task allocation in hierarchical computational grids." International Journal of Applied Mathematics and Computer Science 21.2 (2011): 243-257. <http://eudml.org/doc/208044>.

@article{JoannaKołodziej2011,
abstract = {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.},
author = {Joanna Kołodziej, Fatos Xhafa},
journal = {International Journal of Applied Mathematics and Computer Science},
keywords = {computational grids; scheduling; non-cooperative games; user behavior; security; meta-heuristics},
language = {eng},
number = {2},
pages = {243-257},
title = {Modern approaches to modeling user requirements on resource and task allocation in hierarchical computational grids},
url = {http://eudml.org/doc/208044},
volume = {21},
year = {2011},
}

TY - JOUR
AU - Joanna Kołodziej
AU - Fatos Xhafa
TI - Modern approaches to modeling user requirements on resource and task allocation in hierarchical computational grids
JO - International Journal of Applied Mathematics and Computer Science
PY - 2011
VL - 21
IS - 2
SP - 243
EP - 257
AB - 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.
LA - eng
KW - computational grids; scheduling; non-cooperative games; user behavior; security; meta-heuristics
UR - http://eudml.org/doc/208044
ER -

References

top
  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. Zbl0990.68013
  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. Zbl1007.68612
  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. Zbl0229.90057
  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. Zbl1101.68411
  12. Hwang, S. and Kesselman, C. (2003). A flexible framework for fault tolerance in the grid, Journal of Grid Computing 1(3): 251-272. Zbl1076.68509
  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 alogorithms for job-shop scheduling, International Journal of Applied Mathematics and Computer Science 14(1): 91-103. Zbl1171.90402
  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. Zbl1079.91004
  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. Zbl1080.90046
  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. Zbl0948.91502
  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. Zbl1233.68118
  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. 

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.