Grid Resource Allocation and Grid Economies Yang Wang Papers Grid Resource Allocation and Control Using Computational Economies R Wolski J Brevik J Plank and T Bryan Economic Models for Resource Management and Scheduling in Grid Computing R Buyya D Abramson J Giddy and H Stockinger Grid Resource allocation Current approaches Centralized omnipotent resource control Low execution efficiency Lacks fault resilience Localized application control Unstable resource assignments Fluctuations induced by schedulers themselves Economic Systems Economics systems attractive as an alternative solution because Considerable body of theory that explains overall behavior based on that of the constituents Efficiency is well defined Common sense Process of computational economic research Two approaches to the process of computational economic research Simulation Benefits Repeatability controlled experimentation etc Drawbacks the model of agent behavior is often out of band Empirical studies Need subjects to attach real value to resources Labor intensive to conduct difficult to design Basic Assumptions Basic Assumptions for a resource allocation system to be considered a true economic system The relative worth of a resource must be determined by its supply and demand The price of a given resource is its worth relative to the value of a unit resource i e currency Relative worth is accurately measured only when market equilibrium is reached Computational Economies Two types of computational economies Commodities market A pool of equivalent choices No ability to specify which resource exactly is purchased Auction market Bid on and purchase specific resources Can take on various forms Which is suitable for future Grid setting Commodities Market Commodities market setting A third party market sets a price for resources Queries both producers and consumers for a willingness to sell and buy Observes unsatisfied supply and demand and uses that information to set a new price Consumer takes one of many equivalents Attempt to satisfy all agents at a given price Auctions Market Auctions Market Setting Third party auctioneer collects resources and bids Determines the sale of an individual resource or resource bundle based on the bids Only one bidder is awarded a resource per auction round Process repeated for each available resource Theoretical Predictions Economic theory says that Given a perfectly competitive market if the supply and demand functions are homogeneous continuous and obey Walras Law then there exists a equilibrium price point for the entire market Example Study G Commerce To study the mechanisms necessary to support computational Grid economies Also to study the effect of different economic policies on Grid settings Specifically compare the effects of a commodities market approach and an auctions market approach Two questions Two questions to be answered What is the effect on resource allocation stability of auctions versus commodities markets What is the effect of choosing a particular market formulation on resource utilization The initial study uses simulation The resources Two resources CPU time Each producer sells a number of slots or shares of its CPU time to the Grid Disk space Each producer sells a number of fixed sized files that applications may use for storage Network usage treated as shipping cost The price Seller side determination of price Seller calculates mean price If the offer price from buyers exceeds the seller s own mean price it sells Formula Mean price revenue now num shares The price Consumer side Initial budget plus periodical allowance No carry over Only the CPU and storage of a job is declared No job duration is advertised Once a price is taken by the seller the job is run to completion and the fixed price charged periodically Key assumption consumers act fairly Consumer side cont d Consumer demand Demand generated periodically Each consumer is given a random number of jobs to complete Client computes the price it is willing to offer given the amount of its current jobs and current budget A model only for current allocation and usage pattern for large scale computing centers but not in a P2P or e commerce setting Simulation Simulation is run for both the commodities market approach and the auctions approach Only the Under demand case studied demand is much smaller than system capabilities Results show that the commodities market is more suitable for the Grid economy in terms of both market stability and resource utilization Simulation Result Comparison Commodities Market Comparison Cont d Auctions Comparison Comparison of efficiency Resource utilization Conclusion In the case study G commerce commodities market based resource allocation mechanism is more efficient and stable than the auctions based mechanism Pending verification by empirical studies Economic Models Two key players Supply side Grid Service Provider GSP Demand side Grid Resource Brokers GSB Mediator Grid Market Directory GMD Can use various Economic models Models Commodity Market Model Models Posted Price Model Models Auction Model Models Other models Bargaining Model Tendering Contract Net Model Bid based Proportional Resource Sharing Model Community Coalition Bartering Model Monopoly and oligopoly model Nimrod G Nimrod G Resource Broker Task Farming Engine TFE Scheduler Dispatchers and Actuators Agents The experiment Two experiments different goals Optimize for time Subject to budget constraints Optimize for cost Subject to time constraints Deadline 4 hours Budget constraint 250 000 tokens G The result