Strategies And Algorithms Of Grid Resource Allocation Based On Economic Theory

Based on the new computing infrastructure—grid technology, this thesis focuses on how to optimize the grid resource allocation using economic theory. The objective of this research is to solve the problem of grid user bids in grid resource allocation and to test the efficiency of the proposed schemes. The grid resource allocation based on economic model is investigated from two aspects: resource allocation algorithm and simulation. The main contents are the resource allocation for parallel tasks, resource allocation for user utility optimization, resource allocation based on load prediction, and resource allocation under bounded rationality. The primary contributions of this thesis include:(1)Grid resource allocation strategy based on maximum entropy method is proposed to solve the optimal problem of user job execution time in the grid resource allocation for parallel tasks. The time optimization problem of multiple users with parallel tasks competing for a common resource is max-min problem. Maximum entroy method is introduced to convert this hard max-min problem into a differentiable optimal problem. Bisection searching method is used to produce a set of optimal user bids to allocate resource capacity proportionally. Particularly, the characteristics of the user bid function are studied in emphasis and the existence and uniquness of this strategy is proved. The results show that the proposed allocation strategy generates a low time complexity and thus can satisfy the dynamic nature of gird environment.(2)Grid resource allocation strategy based on utility optimization is proposed to solve the problem of heterogeneity of user requirements in grid resource allocation. Take comprehensive utility function into consideration when optimizing all grid user utilities. Cobb-Douglas utilty function is used to configure grid resource because it reflects the tradeoff between various variables of the economic model fairly well. The strategy synthetically considers two factors of execution cost and execution time of user job, and gives two feasible schemes (i.e. utility optimization under budget constraint and utility optimization under deadlines constraint) to optimize grid user utilities. Finally, the Lagrangian method is used to solve the optimal problem of user utility function. The results show that strategy could produce a reasonable bid scheme to guarantee the completion of grid user's initeraties.(3)Grid resource allocation strategy based on sequential game is proposed to solve the problem of load prediction of grid resource. Resource load prediction is a crucial and difficult problem affecting resource allocation optimization. This strategy overcomes the disadvantages of heterogeneity and dynamic nature of grid resource. The problem of multiple users bidding to compete for a common computational resource is formulated as a multi-player dynamic game. Through finding the Nash equilibrium solution of the multi-player dynamic game, resource load is predicted. Using this load information, a set of user optimal bids is produced to partition resource capacity according to proportional sharing mechanism. The results show that the proposed strategy could generate reasonable user bids, reduce resource processing time, and adapt better to the dynamic nature of heterogeneous resource in grid environment.(4)Grid resource allocation strategy based on evolutionary game is proposed to solve the problem of strategy equilibrium with bounded rational grid users. The strategy using evolutionary game to investigate the evolutionary process of bid strategy of grid user. An evolutionary game model of grid users is established. Using the method of replicated dynamics, an evolutionary stable strategy is produced to allocate resource. Finally, the evolutionary stable point and evaluation functions characteristics of grid users are discussed under different conditions. The results show that evolutionary game approach make grid users study and adjust strategy constantly through repeated games to achieve evolutionary stable equilibrium, which leads to an optimal allocation of grid resource.