Analyzing Market-Based Resource Allocation Strateg

AnalyzingMarket-basedResourceAllocationStrategiesfortheComputationalGridRichWolskiJamesS.PlankJohnBrevikToddBryanDepartmentofComputerScienceUniversityofTennesseeMathematicsandComputerScienceDepartmentCollegeoftheHolyCrossUniversityofTennesseeTechnicalReportUT-CS-00-453˜rich/publications/CS-00-453.ps.gzAbstractInthispaper,weinvestigateG-commerce—computationaleconomiesforcontrollingresourceallocationinComputationalGridsettings.Wede-finehypotheticalresourceconsumers(represent-ingusersandGrid-awareapplications)andre-sourceproducers(representingresourceownerswho“sell”theirresourcestotheGrid).Wethenmeasuretheefficiencyofresourceallocationun-dertwodifferentmarketconditions:commoditiesmarketsandauctions.Wecomparebothmar-ketstrategiesintermsofpricestability,marketequilibrium,consumerefficiency,andproducerefficiency.OurresultsindicatethatcommoditiesmarketsareabetterchoiceforcontrollingGridresourcesthanpreviouslydefinedauctionstrate-gies.ThisworkwassupportedinpartbyNSFgrantsEIA-9975020,EIA-9975015,andACI-9876895.1IntroductionWiththeproliferationoftheInternetcomesthepossibilityofaggregatingvastcollectionsofcom-putersintolarge-scalecomputationalplatforms.AnewcomputingparadigmknownastheCom-putationalGrid[17,3]articulatesavisionofdis-tributedcomputinginwhichapplications“plug”intoa“powergrid”ofcomputationalresourceswhentheyexecute,dynamicallydrawingwhattheyneedfromtheglobalsupply.Whileagreatdealofresearchconcerningthesoftwaremecha-nismsthatwillbenecessarytobringComputa-tionalGridstofruitionisunderway[3,16,20,8,4,24,21,1,34],littleworkhasfocusedontheresourcecontrolpoliciesthatarelikelytosuc-ceed.Inparticular,almostallGridresourceal-locationandschedulingresearchespousesoneoftwoparadigms:centralizedomnipotentresourcecontrol[18,20,28,29]orlocalizedapplicationcontrol[9,4,2,19].Thefirstiscertainlynotascalablesolutionandthesecondcanleadtoun-stableresourceassignmentsas“Grid-aware”ap-plicationsadapttocompeteforresources.Inthispaper,weinvestigateG-commerce—theproblemofdynamicresourceallocationontheGridintermsofcomputationalmarketeconomiesinwhichapplicationsmustbuytheresourcestheyusefromresourcesuppliersusinganagreed-uponcurrency.Framingtheresourceallocationprob-lemineconomictermsisattractiveforseveralreasons.First,resourceusageisnotfree.WhileburgeoningGridsystemsarewillingtomakere-sourcesreadilyavailabletoearlydevelopersasawayofcultivatingausercommunity,resourcecosteventuallymustbeconsiderediftheGridistobecomepervasive.Second,thedynamicsofGridperformanceresponseare,asofyet,diffi-culttomodel.Applicationschedulerscanmakeresourceacquisitiondecisionsatmachinespeedsinresponsetotheperceivedeffectsofcontention.Asresourceloadfluctuates,applicationscanad-justtheirresourceusage,formingafeedbackcon-trolloopwithapotentiallynon-linearresponse.ByformulatingGridresourceusageinmarketterms,weareabletodrawuponalargebodyofanalyticalresearchfromthefieldofeconomicsandapplyittotheunderstandingofemergentGridbehavior.Last,ifresourceownersaretobeconvincedtofederatetheirresourcestotheGrid,theymustbeabletoaccountfortherelativecostsandbenefitsofdoingso.Anymarketformulationcarrieswithitaninherentnotionofrelativeworthwhichcanbeusedtoquantifythecost-to-benefitratioforbothGridusersandstake-holders.WhilethereareanumberofdifferentplausibleG-commercemarketformulationsfortheGrid,wefocusontwobroadcategories:commodi-tiesmarketsandauctions.TheoverallgoaloftheComputationalGridistoallowapplicationstotreatcomputational,network,andstoragere-sourcesasindividualandinterchangeablecom-modities,andnotspecificmachines,networks,anddiskortapesystems.ModelingtheGridasacommoditiesmarketisthusanaturalchoice.Ontheotherhand,auctionsrequirelittleinthewayofglobalpriceinformation,andtheyareeasytoimplementinadistributedsetting.Bothtypesofeconomieshavebeenstudiedasstrategiesfordis-tributedresourcebrokering[11,35,25,6,7,10].Ourgoalistoenhanceourdeeperunderstandingofhowtheseeconomieswillfareasresourcebro-keringmechanismsforComputationalGrids.ToinvestigateComputationalGridsettingsandG-commerceresourceallocationstrategies,weevaluatecommoditiesmarketsandauctionswithrespecttofourcriteria:1.Grid-widepricestability2.Marketequilibrium3.Applicationefficiency4.ResourceefficiencyPricestabilityiscriticaltoensureschedulingsta-bility.Ifthepricefluctuateswildly,applicationandresourceschedulersthatbasetheirdecisionsonthestateoftheeconomywillfollowsuit,lead-ingtopoorperformance,andthereforeineffec-tivenessoftheGridasacomputationalinfrastruc-ture.Equilibriummeasuresthedegreetowhichpricesarefair.Iftheoverallmarketcannotbebroughtintoequilibrium,therelativeexpenseorworthofaparticulartransactioncannotbetrusted,andagaintheGridisnotdoingitsjob.Applica-tionefficiencymeasureshoweffectivetheGridisasacomputationalplatform.Resourceeffi-ciencymeasureshowwelltheGridmanagesitsresources.Poorapplicationand/orresourceef-ficiencywillmeanthattheGridisnotsucceed-ingasacomputationalinfrastructure.Thus,weusethesefourcriteriatoevaluatehowwelleachG-commerceeconomyworksasthebasisforre-sourceallocationinComputationalGrids.Th