Economic Models for Resource Management and Scheduling in Grid Computing Rajkumar Buyya David Abramson Jonathan Giddy and Heinz Stockinger CRC for Enterprise Distributed Systems Technology School of Computer Science and Software Engineering Monash University Melbourne Australia CMS Experiment Computing Group CERN European Organization for Nuclear Research CH 1211 Geneva 23 Switzerland Email rajkumar jon davida csse monash edu au Heinz Stockinger cern ch Abstract The accelerated development in Peer to Peer P2P and Grid computing has positioned them as promising next generation computing platforms They enable the creation of Virtual Enterprises VE for sharing resources distributed across the world However resource management application development and usage models in these environments is a complex undertaking This is due to the geographic distribution of resources that are owned by different organizations or peers The resource owners of each of these resources have different usage or access policies and cost models and varying loads and availability In order to address complex resource management issues we have proposed a computational economy framework for resource allocation and for regulating supply and demand in Grid computing environments This framework provides mechanisms for optimizing resource provider and consumer objective functions through trading and brokering services In a real world market there exist various economic models for setting the price of services based on supply and demand and their value to the user They include commodity market posted price tender and auction models In this paper we discuss the use of these models for interaction between Grid components to decide resource service value and the necessary infrastructure to realize each model In addition to usual services offered by Grid computing systems we need an infrastructure to support interaction protocols allocation mechanisms currency secure banking and enforcement services We briefly discuss existing technologies that provide some of these services and show their usage in developing the Nimrod G grid resource broker Furthermore we demonstrate the effectiveness of some of the economic models in resource trading and scheduling using the Nimrod G resource broker with deadline and cost constrained scheduling for two different optimization strategies on the World Wide Grid WWG testbed that has resources distributed across five continents 1 Introduction Computational Grids and Peer to Peer P2P computing systems are emerging as a new paradigm for solving large scale problems in science engineering and commerce 1 5 They enable the creation of Virtual Enterprises VE for sharing and aggregation of millions of resources e g SETI Home 23 geographically distributed across organizations and administrative domains They comprise heterogeneous resources PCs work stations clusters and supercomputers fabric management systems single system image OS queuing systems etc and policies and applications scientific engineering and commercial with varied requirements CPU I O memory and or network intensive The producers resource owners and consumers resource users have different goals objectives strategies and supply and demand patterns More importantly both resources and end users are geographically distributed with different time zones In managing such complex environments traditional approaches to resource management that attempt to optimize systemwide measure of performance cannot be employed Traditional approaches use centralized policies that need complete state information and a common fabric management policy or decentralized consensus based policy Due to the complexity in constructing successful Grid environments it is impossible to define an acceptable system wide performance matrix and common fabric management policy 13 The concepts discussed in this paper apply to both P2P and Grid systems although we can argue about some of their technical social and political differences However we use the term Grid for simplicity and brevity In 2 3 4 5 we proposed and explored the usage of an economics based paradigm for managing resource allocation in Grid computing environments The economic approach provided a fair basis in successfully managing decentralization and heterogeneity that is present in human economies Competitive economic models provide algorithms policies and tools for resource sharing or allocation in Grid systems The models can be based on bartering or 1 prices In the bartering based model all participants need to own resources and trade resources by exchanges e g storage space for CPU time In the price based model the resources have a price based on the demand supply value and the wealth in the economic system We envision a future in which economically intelligent and economically motivated peer to peer and Grid like software systems will play an important role in distributed service oriented computing The resource management systems need to provide mechanisms and tools that facilitate the realization of the goals of both resource owners and users The resource consumers need a utility model to allow them to specify resource requirements and preference parameters and brokers to that provide strategies for choosing appropriates resources that meet user requirements The resource owners need mechanisms for price generation schemes to increase system utilization and protocols that help them offer competitive services For the market to be competitive and healthy coordination mechanisms are required that help the market reach an equilibrium price the price at which the supply of a service equals the quantity demanded Most of the related work in Grid computing dedicated to resource management and scheduling problems adopt a conventional style where a scheduling component decides which jobs are to be executed at which site based on certain cost functions Legion 7 Condor 28 AppLeS 26 Netsolve 27 Punch 25 Such cost functions are often driven by system centric parameters that enhance system throughput and utilization rather than improving the utility of application processing They treat resources as if they all cost the same price and the results of all applications have the same value even though this may not be the case in reality The end user does not want to pay the highest price but wants to negotiate a particular price based on the demand value priority and available budget Also the results of different