USING SHADOW PRICES FOR RESOURCE ALLOCATION IN A COMBINATORIAL GRID WITH PROXY-BIDDING AGENTS

Abstract: Our paper presents an agent-based simulation environment for task scheduling in a distributed computer systems (grid). The scheduler enables the simultaneous allocation of resources like CPU time, communication bandwidth, volatile and non-volatile memory while employing a combinatorial resource allocation mechanism. The resource allocation is performed by an iterative combinatorial auction in which proxy-bidding agents try to acquire their desired resource allocation profiles with respect to limited monetary budget endowments. To achieve an efficient bidding process, the auctioneer provides resource price information to the bidding agents. The calculation of the resource prices in a combinatorial auction is not trivial, especially if the the bid bundles exhibit complementarities or substitutionalities. We propose an approximate pricing mechanism using shadow prices from a linear programming formulation for this purpose. The efficiency of the shadow price-based allocation mechanism is tested in the context of a closed loop grid system in which the agents can use monetary units rewarded for the resources they provide to the system for the acquisition of complementary capacity. Two types of proxy-bidding agents are compared in terms of efficiency (received units of resources, time until bid acceptance) within this scenario: An aggressive bidding agent with intense rising bids and a smooth bidding agent with slow increasing bids.