Dynamic scheduling model of computing resource based on MAS cooperation mechanism
Tóm tắt
Allocation of grid resources aims at improving resource utility and grid application performance. Currently, the algorithms proposed for this purpose do not fit well the autonomic, dynamic, distributive and heterogeneous features of the grid environment. According to MAS (multi-agent system) cooperation mechanism and market bidding game rules, a model of allocating allocation of grid resources based on market economy is introduced to reveal the relationship between supply and demand. This model can make good use of the studying and negotiating ability of consumers’ agent and takes full consideration of the consumer’s behavior, thus rendering the application and allocation of resource of the consumers rational and valid. In the meantime, the utility function of consumer is given; the existence and the uniqueness of Nash equilibrium point in the resource allocation game and the Nash equilibrium solution are discussed. A dynamic game algorithm of allocating grid resources is designed. Experimental results demonstrate that this algorithm diminishes effectively the unnecessary latency, improves significantly the smoothness of response time, the ratio of throughput and resource utility, thus rendering the supply and demand of the whole grid resource reasonable and the overall grid load balanceable.
Tài liệu tham khảo
Baruah S K, Cohen N K. Plaxton in resource allocation. Algorithmica, 1996, 15(6): 600–625
Wolski R, Plank J S, Brevik J. Analyzing market-based resource allocation strategies for the computational grid. Int J High Perform Comput Appl, 2001, 15(3): 258–281
Subramoniam K, Maheswaran M, Toulouse M. Towards a misty economic model for resource allocation I grid computing system. In: The 2002 IEEE Canadian Conf on Electrical & Computer Engineering, Manitoba, 2002. 278–290
Buyya R. Economic-based distributed resource management and allocation for grid computing. Dissertation for the Doctoral Degree. Melbourne, Australia: Monash University, 2002. 42–47
Cheng J Q, Wellman M P. The WALRAS algorithm: convergent distributed implementation of general equilibrant outcomes. Comput Econ, 1998, 12(1): 1–24
Ygge F. Market-oriented programming and its application ability load management. Dissertation for the Doctoral Degree. Lund: Sweeten Lund University, 1998. 86–105
Weng C L, Lu X D. A double auction method for resource allocation on computational grids (in Chinese). Chin J Comput, 2006, 43(6): 1004–1009
Buyya R, Abramson D, Venugopal S. The grid economy. Proc IEEE, Special issue on grid computing, 2005, 93(3): 698–714
Buyya R, Vazhkudai S. Compute ability market: Towards a market-oriented grid. In: CCGRID. San Francisco: IEEE Computer Society Press, 2001. 574–581
Buyya R, Abramson D, Giddy J. A case for economy grid architecture for service-oriented grid computing. In: Proc of the 10th IEEE Int Heterogeneous Computing Workshop. Washington: IEEE Computer Society, 2001. 776–790
Buyya R, Murshed M. GridSim: A toolkit for modeling and simulation of grid resource management and allocation. J Concurr Comput Pract Exper, 2002, 14(13–15): 1175–1220
Abramson D, Buyya R, Giddy J. A computational economy for grid computing and its implementation in the nimrod-G resource broker. Future Gener Comput Syst, 2002, 18(8): 1061–1074
Subramoniam K, Maheswaran M, Toulouse M. Towards a microeconomic model for resource allocation in grid computing system. In: The 2002 IEEE Canadian Conf on Electrical & Computer Engineering, ManitOBA, Canada, 2002. 373–391
Cao H Q, Xiao N, Lu X C, et al. A market-based approach to allocate resources for computational grids (in Chinese). J Comput Res Develop, 2002, 39(8): 913–916
Wolski R, Plank J S, Brevik J, et al. Analyzing market-based resource allocation strategies for the computational grid. Int J High Perform Comput Appl, 2001, 15(3): 258–281
Chun B N, Ng J, Parkes D C. Computational resource exchanges for distributed resource allocation. Technical Report, Harvard University, 2004
Feldman M, Lai K, Zhang L. A price-anticipating resource allocation mechanism for distributed shared clusters. In: Riedl J, ed. Proc of the 6th ACM Conf on Electronic Commerce. New York: ACM Press, 2005. 127–136
Nash J F. Non-cooperative games. Ann Math, 1951, 54(2): 286–295
Kwok Y K, Song S S, Hwang K. Selfish grid computing: gametheoretic modeling and NAS performance results. In: Proc of the IEEE Int Symp on Cluster Computing and the Grid. Washington: IEEE Computer Society, 2005. 349–356
Bredin J, Kotz D, Rus D, et al. Computational markets to regulate mobile-agent systems. Auton Agent Multi-Ag, 2003, 6(3): 235–263
Maheswaran R T, Basar T. Nash equilibrium and decentralized negotiation in auctioning divisible resources. Group Decision Negotiat, 2003, 12(5): 361–395
Jin Y, Kesidis G. Nash equilibrium of a generic networking game with applications to circuit-switched networks. In: Proc of IEEE INFOCOM 2003. San Francisco: IEEE Computer Society Press, 2003. 2.1242–1249
Waidspurger C, Hogg T. Spawn: a distributed computational economy. IEEE Trans Softw Eng, 1992, 18(2): 18–32
Bredin J, Kotz D, Rus D. Utility driven mobile agent allocation: [Tech Rep. CS-TR98-331]. Dartmouth college, Hanover, NH, 1998. 191–206
Archer A, Tardos E. Truthful mechanisms for one- parameter agents. In: Proceedings of the 42nd IEEE Symposium on Foundations of Computer Science. Lasvegas: IEEE Computer Society Press, 2001. 482–491
Jiang W J, Wang P. Research on distributed solution and correspond consequence of complex system based on MAS. J Comput Res Develop (in Chinese), 2006, 43(9): 1615–1623
Rajkumar R, Lee C, Lehoczky J, et al. Practical solutions for QoS-based resource allocation problems. In: Proc of the 19th IEEE Real-Time Systems Symopsium. Masrid: IEEE Computer Society Press, 1998. 482–491
Contreras J, Candiles O. A cobweb bidding model for competitive electricity markets. IEEE Trans Abil Syst, 2002, 17(1): 51–64
Cao X R, Shen H X, Milito R, et al. Internet pricing with a game theoretical approach: concepts and examples. IEEE/ACM Trans Netw, 2002, 10(2): 208–216
Roth A E. Game theory as a tool for market design. In: Fervent P, Garcia J, StefTijs, eds. Game Practice: Contributions from Applied Game Theory, Kluwer, 2000. 7–18
Zhang W Z, Fang B X, Hu M Z. Multisite co-allocation scheduling algorithms for parallel jobs in computing grid environments. Sci China Ser F-Inf Sci, 2006, 49(6): 906–926
Xu K, Wang Y X, Wu C. Formal verification technique for grid ser-vice chain model and its application. Sci China Ser F-Inf Sci, 2007, 49(1): 1–20
Gao Y, Huang J Z, Rong H. Adaptive Grid job allocation with genetic algorithm. Future Genre Comp Syst, 2005, 21: 151–161