Title: Reverse combinatorial auction-based protocols for resource selection in grids

Authors: G.V.R. Radhanikanth, Y. Narahari

Addresses: Electronic Commerce Laboratory, Department of Computer Science and Automation, Indian Institute of Science, Bengaluru, India. ' Electronic Commerce Laboratory, Department of Computer Science and Automation, Indian Institute of Science, Bengaluru, India

Abstract: Grid computing provides an extremely promising distributed paradigm for executing large-scale resource-intensive applications. Given a distributed pool of resources, a grid user is faced with the problem of selecting an optimal set of resources. We call this problem the resource selection problem and our approach to modelling and solving this problem is through a reverse combinatorial auction. The resource owners submit bids on combinations of resources or tasks in response to the grid user|s request for a bundle of resources. The objective of the grid user is to minimise an appropriately defined cost function based on these bids. The resource selection problem therefore becomes the winner determination problem of the reverse combinatorial auction. Two variants of the problem are considered: (1) resource selection with task-level trading and (2) resource selection with resource-level trading. In both the cases, the resource selection problem turns out to be an integer linear programming problem. We have compared the performance of the proposed resource selection protocols against that of a cost optimisation protocol and a time optimisation protocol which are part of the Nimrod-G resource broker. The protocols proposed are found to have superior overall performance in terms of turnaround time and total cost.

Keywords: grid computing; auction-based resource allocation; resource selection; task-level trading; resource-level trading; reverse auctions; reverse combinatorial auction; integer linear programming; cost optimisation.

DOI: 10.1504/IJGUC.2009.022027

International Journal of Grid and Utility Computing, 2009 Vol.1 No.2, pp.109 - 120

Published online: 16 Dec 2008 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article