Research And Application On The Algorithm Of Grid Resource Allocation And Pricing Based On Combinatorial Double Auction And Trust

The essence of grid is coordinated resource sharing and problem solving in dynamic, multi-institutional virtual organizations. Due to the dynamic and heterogeneous natures of the grid resources, traditional resource management is not suitable for the grid. The grid economy model, which adjusts the actions of grid users and resource providers using market mechanism, has broad prospects in grid resource allocation. It is beneficial to the reasonable and fair uses of the grid resources, and can attract more service providers to participate in grid. The trust issue is also very important for the grid resource allocation, which relates to the security and quality of service in grid resource trading.The main research interest of the thesis is grid resource allocation and pricing. Based on the CoDA (combinatorial double auction) model and grid trust model, it makes deep researches on these points:the unit price based CoDA algorithm; the price elasticity of supply-and-demand based multi-round CoDA algorithm; the algorithms which combine pricing and trust mechanisms; concrete use-case of the CoDA algorithm.The main achievements of the thesis include:(1) A unit price based CoDA algorithm is proposed, which improves the deficiency of the mean price based pricing in traditional CoDA algorithm. The simulation results show that the unit price based algorithm has advantages over the mean price based algorithm from the aspects of pricing error, incentive mechanism, price competitiveness measurement and negative utility.(2) A price elasticity of supply-and-demand based multi-round CoDA algorithm is proposed, which effectively combines the commodity market mechanism and auction mechanism. Based on the supply/demand price elasticity coefficients and the supply-and-demand relationship of the resource market, it computes and announces a market guiding price. Then the auction participators can bid based on this guiding price. Simulation results show that the algorithm efficiently equilibrates the market supply-and-demand, increases the trade rate, and the average trading price accords well with the "law or value" in economics.(3) An equivalent price algorithm is proposed, which combines the CoDA and trust to solve the grid resource allocation and pricing issues. Firstly, it designs the price adjusting coefficients, which map the participators'bid prices under various trust degrees into the equivalent prices under the base trust degree. Then the grid resources are allocated and priced based on these equivalent prices using CoDA. Simulations show that the algorithm has high trade rate, can prevent malicious nodes from entering trade system, and the unit utility can give buyers or sellers incentives to increase or decrease their equivalent unit prices respectively.(4) A weighted average algorithm is proposed, which provides another way of combining the CoDA and trust in grid resource allocation and pricing. Firstly, it identifies malicious nodes according to the weighted average of the trust degree thresholds. Then it designs the normalization methods for the buyer unit price and seller unit price, and measures the comprehensive scores of normal nodes by the weighted average of normalized bid prices and trust degrees. Simulations show that the algorithm has high trade rate, can reliably identify malicious nodes before the auction, and the unit utility can give nodes incentives to increase their comprehensive scores.(5) The traffic features of GridFTP used by the "large file transfer" application are researched, by establishing the GridFTP test-bed and making qualitative analysis and quantitative analysis on the captured traffic, respectively. Firstly, a script which can control the stochastic file transfers is deployed on the test-bed, and the qualitative research on the captured traffic is given from the aspects of packet size and throughput distribution. Then the self-similarity parameters of the GridFTP traffic both in WAN and in LAN are computed using the wavelet coefficient variance method. The results show that both the self-similarity parameter values and the average throughputs increase with the increase of the parallel GridFTP data-flows. (6) The LFT-CoDA (large file transfer based on combinatorial double auction) model and algorithm are proposed, which apply the resource allocation and pricing algorithm into the concrete grid use-case. The architecture of "multi transfer requests and multi parallel paths" is designed, the resource allocation and pricing algorithm of LFT-CoDA is researched, the implementation procedure of the scenario is designed, the LFT-CoDA test-bed is established, and the necessary and related Java-coded components are deployed on the test-bed. Finally, the whole scenario is implemented and demonstrated on the test-bed, and the running results are evaluated from the aspect of incentive mechanism.