Market mechanisms for grid computing

Grid Computing uses software to integrate computing resources, such as CPU cycles, storage, network bandwidth, and even applications, across a distributed and heterogeneous set of networked computers. It is now widely deployed by organizations and provides seamless temporary processing capacity expansion to handle peak-period demand on e-commerce servers, distributed gaming, and content storage and distribution. ^ In the first study, we develop a market-based resource allocation model that adds an economic layer to the current approach of treating resource allocation as primarily a scheduling issue. We formulate the problem as a combinatorial call auction and present a portfolio of three solution approaches that trade off economic properties, such as allocative efficiency, incentive compatibility, and fairness in allocation, with computational efficiency. The first is an efficient solution that maximizes social welfare. For markets where having a commodity price is critical, we add fairness constraints to the efficient model. Finally, for markets that require real-time fast solution techniques, we propose a time sensitive fair Grid (tsfGRID) heuristic . Notably, while incentive compatibility is not guaranteed by tsfGRID, computational results comparing it with the efficient solution technique indicate that there are no significant differences in the expected revenue and operational allocative characteristics. ^ In the second study, we design a market-based clock auction model that is able to allocate grid resources and discover separate prices for the different computing resources in the event of stochastic demand as opposed to the first study where the demand was assumed to be deterministic. Stochastic demand occurs because neither the buyer nor the grid operator knows the exact job size. We use a clock auction for discovering unit prices for the resources in each time period. We also explore the incentive issues in a stochastic setting for combinatorial clock auctions. Computational results show that social welfare when the bidders are myopic expected utility maximizing is significantly higher than when bidders bid based on a fixed estimate of CPU consumption. The computations also show that the clock auction mechanism itself performs quite well in terms of social welfare when compared to a globally optimal solution.