PARALLEL ALGORITHM FOR GRID RESOURCE ALLOCATION BASED ON NASH EQUILIBRIUM

摘要

This paper presents a proportional sharing resource allocation strategy based on Nash equilibrium in grid computing. Given perfect information, the problem of resource allocation can be formulated as a multi-player game with the players being users purchasing computational service from a common resource. A computable Nash equilibrium for parallel tasks is derived to determine a grid user's bidding strategy. In particular, by introducing maximum entropy method, the initial Nash equilibrium problem can be converted into a differentiable optimal problem. The performance evaluation of the proposed Nash-based strategy is carried out under different configurations. The analytical and simulated results indicate that the Nash-based strategy is efficient, and has better performance than Round-Robin allocation.