Analytical Performance Modeling for Computer Systems.pdf

《Analytical Performance Modeling for Computer Systems.pdf》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

AnalyticalPerformanceModelingforComputerSystems SynthesisLecturesonComputerScienceAnalyticalPerformanceModelingforComputerSystemsY.C.Tay2010TheTheoryofTimedI/OAutomataDilsunK.Kaynar,NancyLynch,RobertoSegala,andFritsVaandrager2006 Copyright©2010byMorgan&ClaypoolAllrightsreserved.Nopartofthispublicationmaybereproduced,storedinaretrievalsystem,ortransmittedinanyformorbyanymeanselectronic,mechanical,photocopy,recording,oranyotherexceptforbriefquotationsinprintedreviews,withoutthepriorpermissionofthepublisher.AnalyticalPerformanceModelingforComputerSystemsY.C.Taywww.morganclaypool.comISBN:9781608454402paperbackISBN:9781608454419ebookDOI10.2200/S00282ED1V01Y201005CSL002APublicationintheMorgan&ClaypoolPublishersseriesSYNTHESISLECTURESONCOMPUTERSCIENCELecture#2FirstEdition10987654321SeriesISSNSynthesisLecturesonComputerSciencePrint1932-1228Electronic1932-1686 AnalyticalPerformanceModelingforComputerSystemsY.C.TayNationalUniversityofSingaporeSYNTHESISLECTURESONCOMPUTERSCIENCE#2MMorgan&cLaypoolpublishers&C ABSTRACTThisbookisanintroductiontoanalyticalperformancemodelingforcomputersystems,i.e.,writingequationstodescribetheirperformancebehavior.Itisaccessibletoreaderswhohavetakencollege-levelcoursesincalculusandprobability,networking,andoperatingsystems.Thisisnotatrainingmanualforbecominganexpertperformanceanalyst.Rather,theobjectiveistohelpthereaderconstructsimplemodelsforanalyzingandunderstandingthesystemsinwhichtheyareinterested.Describingacomplicatedsystemabstractlywithmathematicalequationsrequiresacarefulchoiceofassumptionsandapproximations.Theseassumptionsandapproximationsmakethemodeltractable,buttheymustnotremoveessentialcharacteristicsofthesystem,norintroducespuriousproperties.Tohelpthereaderunderstandthechoicesandtheirimplications,thisbookdiscussestheanalyticalmodelsin20researchpapers.Thesepaperscoverabroadrangeoftopics:processorsanddisks,databasesandmultimedia,wormsandwireless,etc.AnAppendixprovidessomequestionsforreaderstoexercisetheirunderstandingofthemodelsinthesepapers.KEYWORDScomputersystemperformance,analyticalmodelingtechniques,simulation,experimen-talvalidation,Markovchains,queueingsystems,fluidapproximation,transientanalysis viiContentsPreface......................................................................xi0Preliminaries.................................................................11ConceptsandLittlesLaw.....................................................71.1Concepts..................................................................71.2OpenandClosedSystems...................................................81.3LittlesLaw...............................................................101.4Discussion................................................................102SingleQueues..............................................................132.1ApplyingLittlesLawtoa1-serverQueue...................................132.2QueueSpecification.......................................................142.3Pollaczek-KhinchinFormula...............................................152.4Discussion................................................................183OpenSystems...............................................................213.1ResidualLife..............................................................213.2Birth-DeathProcess.......................................................223.3OpenQueueingNetworks:JacksonNetworks................................253.4Discussion................................................................264MarkovChains.............................................................294.1MarkovChainforaClosedNetwork........................................294.2MarkovChainforaMulti-classNetwork....................................304.3StateAggregation.........................................................324.4Discussion................................................................33 viii5ClosedSystems.............................................................355.1PASTA...................................................................355.2ArrivalTheorem..........................................................365.3MeanValueAnalysis(MVA)...............................................365.4Discussion................................................................386BottlenecksandFlowEquivalence...........................................416.1BottleneckAnalysis........................................................416.2FlowEquivalence.........................................................436.3Equivalencebetweenopenandclosed.......................................446.4Discussion................................................................457DeterministicApproximations...............................................497.1AverageValueApproximation(AVA)........................................497.2FluidApproximation......................................................507.3Discussion................................................................538TransientAnalysis...........................................................578.1Decomposinganequilibrium...............................................578.2EpidemicModels..........................................................598.3Discussion................................................................619ExperimentalValidationandAnalysis........................................639.1CaseStudy:DatabaseTransactionLocking..................................639.2ModelValidationandExperimentalAnalysis.................................659.2.1Theneedforvalidation659.2.2Datapresentation669.2.3Realsystemsandworkloads669.2.4Simulation669.2.5Parameterspacereduction679.2.6Uninterestingregionsofparameterspace679.2.7Quantitativepredictionvs.qualitativeunderstanding68 CONTENTSix9.2.8Analyticvalidation689.3Discussion................................................................6910AnalysiswithanAnalyticalModel............................................7710.1TheScience&ArtinPerformanceModeling................................7710.1.1Power7710.1.2Technique7810.1.3Assumptionsandapproximations7810.1.4Metrics7910.1.5Scienceandtechnology7910.1.6Intuitionandcontradiction8010.2Discussion................................................................82AExercises...................................................................87Bibliography................................................................93AuthorsBiography..........................................................97Index.......................................................................99 PrefaceInwritingthisbook,Ihaveinmindthestudent,engineer,orresearcherwho:(a)isinterestedintheperformanceofsomeparticularcomputersystem,and(b)wantstoanalyticallymodelthatbehavior,but(c)doesnotintendtobecomeanexpertinperformanceanalysis.Fornetworksystems,theliteraturehasnumerousexamplesofanalyticalperformancemodels;evidently,thisresearchcommunityhasfoundsuchmodelsuseful.Thisbookwillhaveserveditspurposeifitcanhelptheresearchersinothercommunities(hardwarearchitecture,operatingsystems,programminglanguages,databasemanagement,etc.)addamodelingchaptertoathesisorasimilarsectioninapaper.Thereisacommonperceptionthatperformancemodelingrequiresalotofqueueingtheory.Thisisnotso.Queueingsystemsareusedinthisbookonlyasanexpositorydeviceforacoherentpresentation.Theconcepts(e.g.,open/closedinChapter1,residuallifeinChapter3,flowequivalenceinChapter6,stabilityinChapter8),techniques(e.g.,MarkovchainsinChapter4,AverageValueApproximationandfluidapproximationinChapter7,equilibriumdecompositioninChapter8),andresults(LittlesLawinChapter1,effectofvarianceonresponsetimeinChapter2,PASTAinChapter5,bottleneckanalysisinChapter6)areapplicabletomorethanjustqueueingsystems.Thisfactisborneoutbythe20papersdiscussedinthebook.Theyare:(1)StreamJoinsJ.Kang,J.F.Naughton,andS.Viglas.Evaluatingwindowjoinsoverunboundedstreams.InProc.Int.Conf.onDataEngineering(ICDE),341352,March2003.DOI:10.1109/ICDE.2003.1260804(2)SleepingDisksQ.Zhu,Z.Chen,L.Tan,Y.Zhou,K.Keeton,andJ.Wilkes.Hibernator:helpingdiskarrayssleepthroughthewinter.InProc.ACMSymp.OperatingSystemsPrinciples(SOSP),39(5):177190,October2005.DOI:10.1145/1095810.1095828(3)GPRSG.Nogueira,B.Baynat,andP.Eisenmann.AnanalyticalmodelforthedimensioningofaGPRS/EDGEnetworkwithacapacityconstraintonagroupofcells.InProc.MOBICOM,215227,August2005.DOI:10.1145/1080829.1080852(4)InternetServicesB.Urgaonkar,G.Pacifici,P.Shenoy,M.Spreitzer,andA.Tantawi.Analyticmodelingofmul-titierInternetapplications.ACMTrans.Web,1(1):2,2007.DOI:10.1145/1232722.1232724 xiiPREFACE(5)OpenClosedB.Schroeder,A.Wierman,andM.Harchol-Balter.Openversusclosed:acautionarytale.InProc.Symp.NetworkedSystemsDesignandImplementation(NSDI),May2006.http://www.usenix.org/events/nsdi06/tech/schroeder.html(6)TCPJ.Padhye,V.Firoiu,D.Towsley,andJ.Kurose.ModelingTCPthroughput:asim-plemodelanditsempiricalvalidation.InProc.SIGCOMM,303314,September1998.DOI:10.1145/285243.285291(7)BitTorrentD.QiuandR.Srikant.ModelingandperformanceanalysisofBitTorrent-likepeer-to-peernetworks.InProc.SIGCOMM,367378,2004.DOI:10.1145/1015467.1015508(8)CodeRedC.C.Zou,W.Gong,andD.Towsley.Coderedwormpropagationmodelingandanalysis.InProc.ACMConf.ComputerandCommunicationsSecurity(CCS),138147,November2002.DOI:10.1145/586110.586130(9)WirelessCapacityP.GuptaandP.R.Kumar.Thecapacityofwirelessnetworks.IEEETrans.onInformationTheory,46(2):388404,2000.DOI:10.1109/18.825799(10)802.11Y.C.TayandK.C.Chua.AcapacityanalysisfortheIEEE802.11MACprotocol.WirelessNetworks,7(2):159171,2001.DOI:10.1023/A:1016637622896(11)MediaStreamingY.-C.Tu,J.Sun,andS.Prabhakar.Performanceanalysisofahybridmediastreamingsystem.InProc.ACM/SPIEConf.onMultimediaComputingandNetworking(MMCN),6982,January2004.DOI:10.1117/12.538806(12)StorageAvailabilityE.Gabber,J.Fellin,M.Flaster,F.Gu,B.Hillyer,W.T.Ng,B.Özden,andE.A.M.Shriver.Starfish:highly-availableblockstorage.InProc.USENIXAnnualTech.Conf.,151163,June2003.http://www.usenix.org/event/usenix03/tech/freenix03/gabber.html(13)TransactionalMemoryA.Heindl,G.Pokam,andA.-R.Adl-Tabatabai.Ananalyticmodelofoptimisticsoftwaretransactionalmemory.InProc.IEEEInt.Symp.onPerformanceAnalysisofSystemsandSoftware(ISPASS),153162,April2009.DOI:10.1109/ISPASS.2009.4919647(14)SensorNetR.C.Shah,S.Roy,S.Jain,andW.Brunette.Datamules:Modelingathree-tierarchitecturefor PREFACExiiisparsesensornetworks.InProc.IEEEWorkshoponSensorNetworkProtocolsandApplications,3041,May2003.DOI:10.1109/SNPA.2003.1203354(15)NetworkProcessorJ.LuandJ.Wang.Analyticalperformanceanalysisofnetworkprocessor-basedapplicationdesign.InProc.Int.Conf.ComputerCommunicationsandNetworks,7886,October2006.DOI:10.1109/ICCCN.2006.286241(16)DatabaseSerializabilityP.A.Bernstein,A.Fekete,H.Guo,R.Ramakrishnan,andP.Tamma.Relaxedcurrencyserializ-abilityformiddle-tiercachingandreplication.InProc.ACMSIGMODInt.Conf.ManagementofData,599610,June2006.DOI:10.1145/1142473.1142540(17)NoCJ.Kim,D.Park,C.Nicopoulos,N.Vijaykrishnan,andC.R.Das.DesignandanalysisofanNoCarchitecturefromperformance,reliabilityandenergyperspective.InProc.ACMSymp.ArchitectureforNetworkingandCommunicationsSystems(ANCS),173182,October2005.DOI:10.1145/1095890.1095915(18)DistributedProtocolsI.Gupta.Onthedesignofdistributedprotocolsfromdifferentialequations.InProc.ACMSymposiumonPrinciplesofDistributedComputing(PODC),216225,July2004.DOI:10.1145/1011767.1011799(19)NonstationaryMixC.Stewart,T.Kelly,andA.Zhang.Exploitingnonstationarityforperformanceprediction.InProc.EurosysConf.,3144,March2007.DOI:10.1145/1272998.1273002(20)SoftStateJ.C.S.Lui,V.Misra,andD.Rubenstein.Ontherobustnessofsoftstatepro-tocols.InProc.IEEEInt.Conf.NetworkProtocols(ICNP),5060,October2004.DOI:10.1109/ICNP.2004.1348084Ihavechosenthesepaperstoillustratetheconcepts,techniques,andresults,anddemonstratebreadthintheirapplication.Severalwerechosentoshowhowananalyticalmodelcanofferinsightnotavailablethroughexperiments.Butmostimportantofall,IhopethereaderswhoIhaveinmindcangainconfidencefromstudyingtheseexamplesandseethattheytoocanconstructananalyticalmodelfortheperformancebehavioroftheirsystem. xivPREFACEThisbookwastest-runwithcoursesatNationalUniversityofSingaporeandUniversityofCalifornia,LosAngeles.ManythankstoDickMuntzforhostingmysabbaticalatUCLA,andtothereviewersfortheirencouragingcomments.Y.C.TayKentRidge,WestwoodApril2010 1CHAPTER0PreliminariesThischapterpresentssomebasicdefinitionsandresultsthatarefrequentlyusedinmodelingcom-puterperformance.Wewilluseitalicswhenreferringtoanequation,figure,table,section,etc.,inacitedpaper.WhiletheGaussian(ornormal)distributionismostimportantinstatisticalanalysis,thedominantdistributioninperformanceanalysisisexponential:Definition0.1Letλbeapositiverealnumber.AcontinuousrandomvariableXhasanexponentialdistributionwithparameterλ(denotedX∼Exponential(λ))ifandonlyif1−e−λtift≥0,Prob(X≤t)=0ift<0.Thisdistributioniswidelyusedinperformancemodeling,forwhichtisusuallytime,soλisarate.Lemma0.2IfX∼Exponential(λ),thenEX=1andVarX=1.λλ2Notethat,thehighertherateλ,thesmallerthemeanEXandvarianceVarX.Theexponentialdistributionisverysimple.Ifitisusedtomodelaperformancemetric(e.g.,latency)foreachcomponentofalargersystem,thentheseexponentialdistributionscombinetogivemorecomplicateddistributionsforthesystem.Inparticular:Definition0.3LetX1,...,Xkbeindependentrandomvariables,Xi∼Exponential(λi).(a)Supposek≥2.TherandomvariableY=X1+···+XkhasaHypoexponentialdistribu-tion;itiscalledErlang-kifλ1=···=λk.(b)Supposeλ1,...,λkarenotallequal.Letp1,...,pkberealnumbers,0s+t|X>s)=Prob(X>t)foranys,t>0;adiscreterandomvariableNismemorylessifandonlyifProb(N>h+k|N>h)=Prob(N>k)foranyh,k≥0.Thememorylesspropertymakestheexponentialandgeometricdistributionsunique: 40.PRELIMINARIESTheorem0.9Acontinuousrandomvariableismemorylessifandonlyifitisexponentiallydistributed;adiscreterandomvariableismemorylessifandonlyifitisgeometricallydistributed.Thus,ifthetimeTthataPhDstudenttakestograduatehasamemorylessdistribution,thenafter4years,theprobabilitythatshewilltakeanother3yearsormoreisjustProb(T>3),sinceProb(T>7|T>4)=Prob(T>3).Similarly,ifthenumberNofbabiesittakesforamothertogetaboyisgeometricallydistributed,thenafter5girls,theprobabilitythenextbabyisaboyissimplyProb(N=1),sinceProb(N=6|N>5)=Prob(N=1).Itisclearthatthememorylesspropertyisastrongrequirement.Nonetheless,itiswidelyused(oftenimplicitly)inderivationsas,otherwise,acomplicatedsystemwouldbecomeanalyticallyintractable.Thisiswhytheexponentialandgeometricdistributionsaresocommoninperformanceanalysis.Insomecases,itmaybepossibletojustifyusingtheexponentialdistributionwiththefollowing:Theorem0.10(Renyi)SupposeX1,...,XNareindependentandidenticallydistributedcontinuousrandomvariableswithEXi=m>0andN∼Geometric(p).ThenpX1+···+XN∼Exponential()approximately,forsmallp.mNotethatXicanhaveanydistribution,andNisarandomvariable.Theexponentialdistributioniscloselyrelatedtoanotherdiscretedistribution:Definition0.11AdiscreterandomvariableNhasthePoissondistributionwithparameterm(denotedN∼Poisson(m))ifandonlyifmkProb(N=k)=e−mfork=0,1,2,....k!Lemma0.12IfN∼Poisson(m),thenEN=VarN=m. 5OnewaytoseetherelationshipbetweentheexponentialandPoissondistributionsistoconsiderjobsarrivingatasystem.Definition0.13SupposeasystemhasarrivalsattimesT0,T1,T2,...,whereT0μ,thenjobsarrivefasterthantheycanbeserved,thequeuewillgrowindefinitely,thereisnosteadystate,andaverageshavenomeaning.Whatifλ=μ?Theanswerdependsonwhethertheinter-arrivalandservicetimesarede-terministic.Suchdetailsarespecifiedbythenotationweintroducenext.2.2QUEUESPECIFICATIONIntheKendallNotationA/S/K/B/N/d,Aisthearrivalprocess(e.g.,Mformemoryless,i.e.,Poissonarrivals);Sistheservicetimedistribution(e.g.,Dfordeterministic,Gforgeneral);Kisthenumberofservers(possiblyinfinite);Bisthebuffercapacity(includingjobsinservice;bydefault,Bisinfinity);Nisthejobpopulationsize(bydefault,Nisinfinity);disthequeueingdiscipline(bydefault,disFCFS,i.e.,first-come-first-served). 2.3.POLLACZEK-KHINCHINFORMULA15Anotherfrequentlyusedqueueingdisciplineisprocessorsharing,wherenjobsataserverwilleachμgetservicerate;thisisanidealizedmodelofround-robinscheduling.nThus,M/M/1denotesaqueuewithexponentiallydistributedinter-arrivalandservicetimes,1server,unlimitedbuffercapacityandpopulationsize,andFCFSscheduling.Anotherexample:M/D/3denotesaqueuewithPoissonarrivals,deterministicservicetimes,andthreeservers,asillustratedinFig.2.3.Iftheservicerateisμforeachserver,thentheservicerateforthequeuewouldbeμifithasonly1job,2μifitthereare2jobs,and3μifthereare3ormore.μλμμFigure2.3:M/D/3hasPoissonarrivals,deterministicservicetimes,threeservers,andinfinitebuffercapacity.Notetheimplicitassumptionherethatajobwillneverwaitifthereisanidleserver.Thisisanexampleofaworkconservingqueue.Moresophisticatedqueueingdisciplinesmayviolatethisassumption;forexample,toavoidasituationwherelongjobshogallservers,oneservermaybededicatedtoshortjobsandthereforeallowedtoidleifalljobsinthequeuearelong.Notealsothat,foraqueuewithKservers,steadystateispossibleforλ>μaslongasλ0Hence,thesolutionβ1t(cosωβ2tu(t)=c1e1t+isinω1t)v1+c2e(cosω2t+isinω2t)v2 7.2.FLUIDAPPROXIMATION51β1<β2<0β1=β2<0β1=β2<0ω1=ω2=0ω1=−ω2=0ω1=ω2=0Figure7.1:Stableequilibriumsandcorrespondingeigenvalues.0<β1<β2β1=β2>0β1=β2>0ω1=ω2=0ω1=−ω2=0ω1=ω2=0Figure7.2:Unstableequilibriumsandcorrespondingeigenvalues.hasstableequilibrium(i.e.,limu(t)=0)ifβ1<0andβ2<0,andanunstableequilibriumift→∞β1>0andβ2>0.Fig.7.1showsthreepossiblescenariosforu(t)toconvergetoastableequilibrium,whileFig.7.2showsthreepossiblescenariosforu(t)todivergefromanunstableequilibrium.Theremaybenoequilibriumforsomeothercombinationofeigenvalues,asillustratedinFig.7.3.abStabilitycanalsobecharacterizedbythetraceanddeterminant.IfA=,thencddet(A−ψI)=(a−ψ)(d−ψ)−bc=ψ2−trace(A)ψ+det(A)=0, 527.DETERMINISTICAPPROXIMATIONSβ1<0<β2β1=β2=0β1=β2=0ω1=ω2=0ω1=−ω2=0ω1=ω2=0Figure7.3:Someotherpossibletrajectoriesandcorrespondingeigenvalues.sotherootsaretrace(A)+trace(A)2−4det(A)trace(A)−trace(A)2−4det(A)ψ1=andψ2=.22Casetrace(A)<0anddet(A)>0:Iftrace(A)2−4det(A)<0,thenω1=0,ω2=0andβ1=β2=trace(A)<0.Iftrace(A)2−4det(A)≥0,thenω1=ω2=0andtrace(A)+trace(A)2−4det(A)<0(sincedet(A)>0),soβ1<0andβ2<0.Eitherway,theequilibriumisstable,asillustratedinFig.7.1.Casetrace(A)>0anddet(A)>0:Iftrace(A)2−4det(A)<0,thenω1=0,ω2=0andβ1=β2=trace(A)>0.Iftrace(A)2−4det(A)≥0,thenω1=ω2=0andtrace(A)−trace(A)2−4det(A)>0(sincedet(A)>0),soβ1>0andβ2>0.Eitherway,theequilibriumisunstable,asillustratedinFig.7.2.Foraninhomogeneoussystemdu=Au+b,whereAisinvertibleandbisconstant,dtthesteadystate(particular)solutionisu=−A−1b,sothegeneralsolutionisu(t)=cβ1tβ2t−11e(cosω1t+isinω1t)v1+c2e(cosω2t+isinω2t)v2−Ab. 7.3.DISCUSSION537.3DISCUSSIONStreamJoins[13]InTable1,thenumberoftuplesBisarandomvariableforalogicalwindow,andthenumberofhashbuckets|B|isalsonotaconstant.OnecanthereforeviewB/|B|inEq.(8)asanexampleofAVA.GPRS[23]U˜TheexpressionX˜=inEq.(10)isasimilarexampleofAVA.Q˜TCP[24]ThesysteminthispaperreferstoabulktransferinaTCPRenoconnectionovermultiplerouters.Thecentralissueishowpacketlossandtimeoutaffectthethroughputviatheprotocol(windowadjustment,retransmission,etc.)seeEq.(31).Themodelusesthetechniqueofdiscretizingtimeintorounds(Fig.2).Insteadofmakingvariousassumptions(thatarehardtoverifyorjustify,consideringthemanyapproximations),onecouldjustviewsomeofthederivationsasanapplicationofAVA.Forexample,insteadofconsidering{Wi}itobeaMarkovregenerativeprocess,wecouldjustuseAVAtogetB=EYinEq.(1).Similarly,onecouldforegotheassumptionofmutualEAindependencebetween{Xi}and{Wi}andderiveEq.(12)fromEq.(10)byAVA.Ratherthanassumeroundtriptimestobeindependentofcongestionwindowsizeandroundnumber,onecoulduseAVAtoderiveEq.(6):Xi+1EXi+1EX+1EAi=Erij≈Erij=Erij=(EX+1)Er,j=1j=1j=1wheretheapproximationregardsEXtobeaninteger.Astheformulasbecomemorecomplicated,itisnolongerclearwhatassumptionsaresufficientforthederivations,andtheauthorssimplyapplyAVAinEq.(25):Q=EQ(W)ˆ≈Q(EW).ˆEq.(19)isanexampleofafixedpointapproximation(Sec.5.3):TCPthroughputB(p)isexpressedintermsoflossprobabilityp,whichinturndependstoB(p).BitTorrent[25]ThesystemconsistsofpeerssharingfilesthroughachunkprotocolthatissimilartoBitTor-rent;apeerbecomesaseedwhenithasfinisheddownloadingthedesiredfile.Noticethatthecentralizedtracker,whilecrucialtothefunctioningofthesystem,isomittedfromtheperformancemodel. 547.DETERMINISTICAPPROXIMATIONSThemovefromaserver-clientsystemtoonethatispeer-to-peerisbasicallymotivatedbyscalability,andthemodelisusedtostudythisandrelatedissuesthegrowthinnumberofseeds,theimpactofdownloadabortionandbandwidthconstraint,theeffectivenessoftheincentive,andunchokingmechanisms.Themainparametersforthemodelaretherequestarrivalrateλ,theuploadingbandwidthμ,thedownloadingbandwidthc,theabortrateθ,andthepeerdeparturerateγ.Themodelisadeterministicfluidapproximationthatdescribestheevolutioninnumberofdownloadersx(t)andseedsy(t)asapairofordinarydifferentialequations.InEq.(1),λ−θxcorrespondstothetransitionratefromstatex,ytox+1,yinaMarkovchainmodel,−γythetransitionratefromx,ytox,y−1,andmin(cx,μ(ηx+y))thetransitionratefromx,ytox−1,y+1LittlesLawisusedtoderivetheimportantperformancemeasureTinEq.(6).Afterderivingthesteadystate,itsstabilityisanalyzedbyexaminingtheeigenvaluesofthepairofequations.Notethattheλtermmakesthepairinhomogeneous.ThemodelhereisaninterestingcontrasttothatinMediaStreaming[35]:althoughbothcon-siderpeer-to-peerdownloading,onestudiessteadystatesolutionwithafluidapproximation,whiletheotherisatransientanalysisusingdiscretizedtime.StorageAvailability[8]TheauthorsusethemachinerepairmanmodeltoderiveEq.(1),buttheformulasuggeststhatthereisacombinatorialderivation.Infact,onecanusethefollowingAVAargument:Thefailurerateisλandtherecoveryrateisμ,sotheaverageup-timebetweenconsecutivefailuresis1/λ,andtheaveragedown-timeforrecoveryis1/μ.ByAVA,theavailabilityforanSE(i.e.,theprobabilitythatitisup)is1λ1=.1+11+ρλμItisclearthatthissolutionholdsevenifλ≥μ(soρ≥1).SincetheSEsareassumedtobeindependent,theprobabilitythatatleastQSEsareavailabilityisbinomial,i.e.,NN1jρN−j,j1+ρ1+ρj=QwhichisequivalenttoEq.(1).Thisargumentdoesnotassumethedistributionsareexponential,andmaybemorereadilyacceptedbyengineers.However,itstillassumesindependenceoffailures.TransactionalMemory[11]TheuseofL−wE(Q),insteadofL−wiinthedenominatorsforEq.(3)isanexampleofAVA.Eq.(12)hasE(Q)onbothsides,sothemodelresultsinafixedpointapproximationthatissolvediteratively. 7.3.DISCUSSION55SensorNet[29]OnecanderiveEq.(3)withthefollowingAVAargument:Givenarandomwalkonatorus,withalldirectionsequilikely,aMULEisequallylikelytobeanywherealongitspath.IftheexpectedpathlengthisE[Ri],thentheprobabilityofbeingatgridpointiisπi=1/E[Ri].OnecandoasimilarderivationofCorollary2.1:ByEq.(3)theaverageinter-arrivaltimeofaspecificMULEtoasensorisN,sothearrivalrateis1/N;sincethereareNmules,thearrivalrateofMULEstothatsensorisNmules/N=ρmules;theinter-arrivaltimeofMULEsistherefore1/ρmules,whichgivesthebufferoccupancyinEq.(17).NoC[15]On-chipinterconnectsarereplacingbusesandpoint-to-pointwires.Theperformance,fault-toleranceandenergyissuesforsuchnetwork-on-chipareinter-related.Forexample,errorsfromcrosstalk,electromagneticinterferenceandcosmicradiation(ofincreasingimportancewithminiaturization)cancausepacketretransmissions,thusincreasinglatencyandenergyconsumption.Thispaperproposesaqueueingmodelasadesigntoolforfastevaluationofrouterdesigns.Fig.1illustratesthesystemunderstudy.MajorinputparameterstothequeueingmodelarenumberofhopsH,numberofflitsperpacketM,injectionprobabilityPpe,andflitbuffersizeD.TheperformancemodelfocusesonlatencyT(Eq.(3))andthepowermetricPR(Eq.(25)).WormholeroutingonanNoCislikeavirtualcircuitinawide-areanetwork:theflitsofapacketfollowtheheaderflitspathlikeaworm,simultaneouslyoccupyingmultiplenodes.Thismeansthearchitecturecannotbemodeledasaqueueingnetwork(sinceajobinaqueueingnetworkdoesnotoccupymultiplequeues).Theauthorsdiscretizetimebyanalyzingwhathappensineachcycle.Thisalsoallowsthemtoswitchfromconsideringanarrivalratetoderivinganeventprobabilityinacycle,inthefollowingsense:Supposethearrivalrateataninputvirtualqueueisλflitspercycle;sinceatmost1flitcanbeprocessedpercycleatanyqueue,soλ<1andcanbeinterpretedastheprobabilitythatthereisaflitinthatcycle.ThisissimilartoutilizationbeingalsoaprobabilityinEq.(2.3)fora1-serverqueue.ThisrelationshipinducedbyLittlesLawbetweenarrivalrateandprobabilitycanalsobeseeninEq.(6).Similarly,theflitinjectionprobabilityPpeisthearrivalrateofflitspercycle.IfthereareRrouters,thenthetotalflitarrivalrateatallqueuesisRPpeH,andthisisdividedamongtheRNqueuestogivePc.Onemusttakecaretoapplysanitycheckswhenmakingapproximationsinamodel,andweseeherethatEq.(4)putsalimitonH(sincePc<1).Eq.(7)alsorequiresPh<1−Pcon_va.TheMarkovchaininFig.3isforanM/M/1/Dqueue.However,theauthorsusethesolutionfromM/M/1forr=0,1,2,...toapproximatetheblockingprobabilityinEq.(17).Eq.(19)showstheuseoftheM/M/1expressionforaveragewaitingtime(seeEq.(2.8)).Incidentally,theservicetimeisobviouslynotmemoryless,sinceflitshaveboundedsize. 567.DETERMINISTICAPPROXIMATIONSThemodelrequiresaniterativesolutionbecausetherearecyclicdependenciesamongthevariables.Forexample,Pready_busydependsonP(Eq.(6)),PdependsonPcon_va(Eq.(7)),hhandPcon_vadependsonPready_busy(Eq.(10)). 57CHAPTER8TransientAnalysisAnalyzingtransientbehaviorisgenerallyadifficulttask;forexample,LittlesLawnolongerapplies.Thisiswhy,exceptforthestabilityanalysisinthepreviouschapter,wehavefocusedonthesteadystate.Inthischapter,weapplydecompositiontodoadifferentstabilityanalysisoftheequilibriumforaninteractivesystem.WethenuseafluidapproximationtostudythespreadofawormovertheInternetthisisanexamplewhereinterestliesinthetransient,notthesteadystate.8.1DECOMPOSINGANEQUILIBRIUMConsideraclosedinteractivesystem,withNusers,Kofwhomarewaitingforjobstofinish,andaveragethinktimeZ.Usingflowequivalence,Njobsaveragethinktime=Z......KX(K)system=systemapprox.whereByLittlesLaw,N=K+X(K)Z,whereX(K)isthethroughput.Wecanrewritethisasλ=λN−Kinout,whereλin=Zandλout=X(K),andinterpretKasdeterminedbyanequilibriumbetweenaninflowλinandanoutflowλout,asinFig.8.1.ForfixedNandZ,λinisadecreasinglinearfunctionofK.IfX(K)ismonotonicincreasing,wegetanintersectionbetweenλinandλout,thusdeterminingauniqueequilibriumpoint,asillustratedinFig.8.2(a).Wecanviewλinasworkdemandgeneratedatrate1/ZbyN−Kusers,λoutasworksupplyprovidedbythesystemtoKjobs,andtheequilibriumasabalancebetweendemandandsupply.IfweadoptafluidapproximationtoviewthejobflowinandoutofthequeueinFig.8.1,wecangetanintuitivewayofexaminingthestabilityofthesteadystateinFig.8.2(a),asfollows:Suppose 588.TRANSIENTANALYSISλinλoutKFigure8.1:TheequilibriuminKviewedasabalancebetweenademandinflowandasupplyoutflow.stableNequilibriumstablehighZλinNequilibriumλoutλinZunstableequilibriumstablelowλoutequilibriumKK0NKK0−εK0+εKK000K"N(a)oneequilibriumpoint(b)multipleequilibriumpointsFigure8.2:(a)AstableequilibriumatK0isabalancebetweendemandλinandsupplyλout.(b)IfX(K)eventuallydecreases,theremaybethreeequilibriumpoints:onehighandstable,oneunstable,onelowandstable[4].NλinZdecreaseNincreaseZλoutKKKNFigure8.3:AsystemcanreturntoahighequilibriumifNdecreasesorZincreases.theequilibriumisatK=K0.Considerasmallε,ε>0.AtK=K0−ε,wehaveλin>λout,soKincreases(seeFig.8.1)andmovestowardsK0.Similarly,atK=K0+ε,wegetλin<λout,soKdecreasesand,again,movestowardsK0.Thus,asmalltransientfluctuationfromK0willcauseKtoreturntoK0,sotheequilibriumisstable.Inrealsystems,however,alargeKoftenresultsininefficiencies(overheads,resourcecon-tention,etc.)thatcauseX(K)(i.e.,λout)toeventuallydecrease.Forsuchasystem,wecangetmultipleequilibriumpoints,asillustratedinFig.8.2(b). 8.2.EPIDEMICMODELS59However,theirstabilitymaybedifferent.InFig.8.2(b),theequilibriumpointsatK0andKarestable,buttheoneatKisnot:asmalltransientfluctuationinKfromKwillcauseKto000movefurtherfromK,drivingittoastableequilibriumatK0orK.SincetheequilibriumatK000isunstable,itisimpossibletoobserveinarealsystem,oreveninsimulations.OnlyananalyticalmodelcanrevealthisK,thisboundarybeyondwhichthesystemwouldslipfurtherouttoastable0butlowequilibrium.Astablebutlowequilibrium(likeK)isundesirable.Howcanasystemgetoutofsucha0degradedstate?Intuitively,performanceshouldimproveifNisreduced(byadmissioncontrol,say).WecanseethisinFig.8.3,wherereducingNcausesaparallelshiftintheλinline,possiblyrelocatingtheequilibriumtoapointwhereperformanceishigher.ThesystemcanalsorecoverbyitselfthroughincreasingZ(duringoff-peakhours,say).Thiscausestheλinlinetotiltand,again,relocatingtheequilibrium.Here,weseehowthesimpleideaofdecomposingthesystemequilibriumintoλinandλouthelpsusunderstanditsdynamics.8.2EPIDEMICMODELSWenowdoatransientanalysisofhowaninfectionspreadsamonghosts.Thesystemconsistsofhoststhatarelinkedtoeachother;ifsomehostsareinfected(byaworm,say),theinfectioncanspreadlikeanepidemictoothersthroughthelinks.Letybethefractionofhostsinthesystemthatareinfected.Thefollowingisaclassicalepidemicmodel:dy=ky(1−y)for00andy0=limy.(8.1)dtt→0LetthenumberofhostsbeN.Nisaninteger,soyisstrictlyspeakingnotacontinuousvariable.Intreatingitasone,wearethususingafluidapproximation.Now,ky(1−y)=k(yN)(N−yN)/N2,whereyNandN−yNarethenumberofinfectedanduninfectedhosts.Ifanyinfectedhostcaninfectanyuninfectedhost,thenEq.(8.1)modelstheinfectionrateasproportionaltothenumberofpossibleinfections.Afterrearranging,integrationgives11+dy=kdty1−ysolny−ln(1−y)=kt+constant1i.e.,y=.1+1−1e−kty0 608.TRANSIENTANALYSISForsmallt,wehavee−kt≈1,so11kt=≈y0e,1+1−1e−kt1−e−kt+1y0y0ektdyi.e.,ystartsoutbyincreasingexponentially.Also,>0for00fory<1d2ydy⎨2=k(1−2y)dt2dt⎩1<0fory>2Therefore,thereisaninflectionpointwheny=1,markingachangeofphaseintheepidemic.2Themodelaboveassumesthataninfectedhostisforeverinfectious.If,instead,aninfectedhostcanberemoved(i.e.,itisnolongerinfectiousbecauseitrecoversordies),thenonemightadopttheKermack-McKendrickModel:LetNbethenumberofhosts,Sthenumberofhostsarearesusceptibletoinfection,Ithenumberofhoststhatare(infectedand)infectious,andRthenumberofhoststhatare(infectedbut)removed;thendS=−βSIwhereβ>0(8.2)dtdR=γIwhereγ>0(8.3)dtN=S+I+R(8.4)Equations(8.2)and(8.3)givedS1γ=−Swhereρ=,dRρβ−1RwithsolutionS=S0eρ,soSdecaysexponentiallywithR.Next,Equation(8.4)givesdIdSdRdSdRdR1dR=−−=−−=(S−ρ)dtdtdtdRdtdtρdtTherefore,forI=0(seeEq.(8.3)),dI>0⇐⇒S>ρ;dtthischaracterizesthetimeatwhichinfectionbeginstodecrease.Infact,thisalsosaysthatifS<ρinitially,thendI/dt<0andtherewillbenoepidemic. 8.3.DISCUSSION618.3DISCUSSIONInternetServices[36]Thepaperadoptedaclosedinteractivemodel(Z=1sec),soitsequilibriumcanbeanalyzedbyadecompositionintoλinandλout.Aseparablequeueingnetworkcannotmodelefficiencylossathighload,soλoutwillbemonotonicincreasing(unlikeFig.8.3)andtherewillbeasingle,stableequilibrium.TheCPUbottleneck(Figs.7and8)imposesaboundonλout,whichthereforeflattensoutasthenumberofsessionsNincreases.Withasimilarplateauforresponsetime(Figs.4,8,and9),LittlesLawsaysthatthenumberofconcurrentsessionsinthethreetiersalsobecomesdropconstant.ThismeansthatmostoftheincreaseinNisactuallyinthethinkstageQ0andQiatthebottleneckinFig.5.CodeRed[38]ThesysteminthispaperreferstoawormspreadingamongInternethoststhroughTCPconnections.ThemainparametersarethenumberofhostsN,theinfectionrateβandtheremovalrateγ.ThecentralperformancemetricisthenumberofinfectedhostsI.ThebasicissueishowIvarieswithtimeasinfectionspreads.ThepaperseekstocraftamodelthatmatchesthemeasuredgrowthanddecayinIfortheCodeRedworm,andusethattoanalyzetheimpactofcountermeasures,congestionandtopology.Thisisnecessarilyatransientanalysis;inthesteadystate,allhostswouldhavebecomeinfectedorimmune,sodI/dt=0.ThemassivenumberofInternethostsinvolvedinawormpropagationmakesitreasonabletoadoptadeterministicmodelusingdifferentialequations.Thepaperstartedwiththeclassicalepidemicmodel,withFig.4illustratingtheinitialexponentialincreaseinyandthephasechangeaty=1.AlthoughthesefeaturesmatchthegrowthinFigs.1and2,thedyingphase2ofthewormrequiresamodelforthecountermeasures.Forthis,theauthorsadoptedtheKermack-McKendrickmodel.TheS>ρconditioninEq.(6)thenlocatestheturningpointinFig.1.MediaStreaming[35]Thedeterminationofk0,whenthereareenoughpeerstotakeovertheserversroleinsatisfyingrequests,requiresatransientanalysis.BydiscretizingtimeandwritingadifferenceequationforP(k),i.e.,Eq.(1),theauthorsdemonstrateanalternativetomodelingwithdP(t)/dt.DatabaseSerializability[1]Ifweapplydemand-supplyequilibriumdecompositiontothemodel,thethroughputbecomesthesupplycurveλout.FromFig.5,weseethatwitharelaxedtimeconstraint,BSAFC-100hasthroughputlookinglikeλoutinFig.8.2(a).Withatightertimeconstraint,however,BSAFC-10hasthroughputthatlookslikeλoutinFig.8.2(b),sotheremaybemultipleequilibriumpoints.Whetheroneofthesewillresultinastablelowequilibriumdependsonhowlowthetailgetsforthethroughputcurve. 628.TRANSIENTANALYSISDistributedProtocols[9]Thispaperproposesaframeworkfordesigningdistributedprotocolsthroughdifferentialequations;thisway,onecanleverageonthelattersrichtheorytoderivedesirableproperties(stability,scalability,etc.)fortheprotocols.Thesystemisasetofprocessesconnectedbyanasynchronousnetwork.TheinputparametersarethenumberofprocessesNandtheconstants(α,β,etc.)inthedifferentialequations,andthemetricsarethevariables(x,y,etc.).Themodelissimplytheequationsthemselves.Theequationsareafluidapproximation,treatingthevariablesascontinuouseventhoughtheyrepresentprocesses(andsoarediscrete).Moreover,changesinprocessstatehappenatthebeginningofprotocolperiodsandarepromptedbytheexchangeofmessages,sosystemevolutionisalsodiscrete.Theframeworktransformsthedifferentialequationsintoastatemachine(likeFig.1):avariablebecomesastate,andatermbecomesanaction.Thestatemachinecan,inturn,beinterpretedasaMarkovchain,butwithtransitionratesthatdependonthestatese.g.,thetransitionratefromreceptivetostashinFig.1isβy,wherey=Prob(stash).Indeed,thebalanceequationsaretheoriginaldifferentialequationsatequilibrium.(ThisinterpretationofafluidmodelasaMarkovchainhasaconversethatwehavealreadyseen:RecallthemodificationoftheMarkovchaininTransactionalMemory[11]describedinChapter3,wherethereisatransitionfromcommittedstatek+1tostartstate0,sothemodelbecomestheflowdiagramforthestateoftheentiresystem.Eachnodejinthediagramthenrepresentsalltransactionsholdingjlocks,andtheedgesrepresenttheflowoftransactions.Inotherwords,theMarkovchainbecomesafluidapproximation.)Naively,onemightmodelthesystemofNprocessesasanN-dimensionalMarkovchain,withstatespace{s1,...,sN|si∈{receptive,stash,averse}}.Anaggregationofthese3Nstatesmaycauseanunnecessarylossofinformation.Instead,theapproachhereistosolvetheper-processMarkovchain(i.e.,Fig.1)ineachdimension.Ifdesired,onecouldconstructtheN-dimensionalchainbytakingtheproductofthese1-dimensionalchains.ThestabilityanalysiswedoinFig.8.2issimilartotheperturbationanalysis,whereGuptastartedthesystematx∞(1+u),y∞(1+v),z∞(1+w)forsomesmallu,v,andw.Byintroducingthenewvariablet=˙u,theperturbedequationsreducetoahomogeneoussystem(Eq.(4));onecanthenexaminethestabilityofthesystemthroughtheeigenvalues(Sec.7.2). 63CHAPTER9ExperimentalValidationandAnalysisEveryanalyticalmodelofacomputersystemneedsexperimentalmeasurementstovalidateit.Theseexperimentsareoftenusedtoanalyzethesystemaswell.Thischapterdiscussessomeissuesinmodelvalidationandexperimentalanalysis.Tomakethediscussioncoherent,werelatetheissuestoacasestudy,namelytheimpactofdatabaselocksontransactionperformance.Wefirstdescribethisproblem.9.1CASESTUDY:DATABASETRANSACTIONLOCKINGAdatabaseisacollectionofinterrelateddata.Adatabasemanagementsystemisadatabasetogetherwithasuiteofprogramsfororganizing,updating,andqueryingthedatabase.Usersaccessadatabasethroughapplicationprogramsthatrunontopofthedatabasemanagementsystem.ExamplesofsuchapplicationsareairticketreservationandInternetauctions.Databasemanagementsystemshavethreeimportantfeatures:persistence−ifaprogrammod-ifiessomedata,thechangesremainaftertheprogramhasterminated;sharing−morethanoneprogramcanconcurrentlyaccessthedata;andreliability−thedatamustremaincorrectdespitehardwareandsoftwarefailures.Inmanipulatingdata,aprogrammaycausethedatabasetobetemporarilyincorrect.Forinstance,intransferringanamountofmoneyfromanaccountAtoanotheraccountB,thedatabasewouldbeincorrectintheintervalaftertheamountisdeductedfromAandbeforeitisaddedtoB(sincethatamountismissingfromthetotalofthetwoaccountsfortheduration).Thepersistenceofchangesandthispossibilityofatemporaryinconsistencyleadtotherequirementthateitherallchangesmadebytheprogramuptoitscommitment(i.e.,successfultermination)isreflectedinthedatabase,ornoneatall.Thisistheconceptofatransaction.Sinceadatabasesystemallowsseveraltransactionstobeactiveatthesametime,theactionsoftransactionsonshareddataareinterleaved.Topreventthisinterleavingfromproducinginconsistentdata,theremustbeaconcurrencycontrolprotocoltocoordinatethetransactionsactions. 649.EXPERIMENTALVALIDATIONANDANALYSISTheprevailingtechniqueforconcurrencycontrolislocking:beforeatransactioncanreadorwriteonapieceofdata,thetransactionmustsetareadlockorawritelock(accordingly)onit.Ifanothertransactionalreadyholdsalockonthatdata,andoneofthetwolocksisawritelock,thenthereisaconflict,whichmustberesolvedinsomeway.Conflictresolutioniscentraltotheproblemofmodelinghowtransactionlocksaffectperformance.Therearetwowaysofresolvingaconflict:(1)Oneofthetwoconflictingtransactionsisaborted−allitschangestothedatabaseareundone,itslocksarereleased,andithastostartallover.(2)Thetransactionthatistryingtosetthelockisblocked−itjoinsaqueueoftransactionswaitingforthelocktobereleased.Thisblockingmayleadtoadeadlock,whereseveraltransactionswaitforoneanother,unabletoproceed.Suchasituationmustbedetectedandremovedbyabortingoneofthetransactions.Concurrencycontrolisjustonefactoramongamyriadothersthatinfluencesystemperfor-mance,butthecomplexityinmodelingthisonefactorisalreadyevidentfromthebriefdescriptionabove.Thedependenciesinvolvedandthesheersizeoftheproblem(someapplicationshavemassiveamountsofdataandthousandsofconcurrenttransactions)aremind-boggling.Anexactstochasticanalysiswouldbecompletelyintractable−onecouldnotbegintowritedownthestatespace.Performance-relatedquestionsarisenaturallyoncewelookintothedetailsoflocking.Forexample,thedivisionofsecondarymemoryintopagesmakesitmostconvenienttolockapageatatime,evenifatransactionsreadsandwritesrefertorecords,andapagecontainsmorethanonerecord.Thisbringsupthequestionofgranularity:Howmuchdatashouldbelockedatatime?Intuitively,lockingmorewouldreducethelevelofconcurrency.Ontheotherhand,itwouldreducethenumberoflocksatransactionneeds,andtherebyreducethelockingoverhead.Howdoesgranularityaffectperformance?Movingtoamoreabstractstandpoint,whichisabetterwayofresolvingaconflict:blockingthetransactionrequestingthelock,orabortingoneoftheconflictingtransactions?Inabortingatransaction,alltheworkthatisalreadydonebythetransactionwouldbewasted,whereasinblockingatransaction,theworkthatisdonebythattransactionisconserved.Itwouldthusseemthatweshouldalwaysblocktherequestingtransaction,ratherthanabortoneofthetwotransactions.Isthatcorrect?Whenthereisadeadlock,whichtransactionshouldweaborttobreakthecycle?Onecould,say,abortthetransactioninthecyclethathasconsumedtheleastamountofresources.Atransactioninadeadlockmaybeblockingafewtransactions,soonecouldalsoargueforabortingthetransactionthatisblockingthelargestnumberoftransactions.Thereareseveralotherpossiblecriteriaforchoosingthevictim.Whichisoptimum?Itispossibletoavoiddeadlocksaltogether.Supposeatransactionisnotallowedtobeginexecutionifanyofthelocksitneedsisalreadygrantedtosomeothertransaction.Itmustwaituntil 9.2.MODELVALIDATIONANDEXPERIMENTALANALYSIS65allthoselocksareavailable,getthem,thenbeginexecution;thereafter,itisnotallowedtoaskformorelocks.Thisiscalledstaticlocking,asagainstdynamiclocking,wheretransactionsgettheirlocksastheyareneeded.Intuitively,staticlockinghasthedisadvantagethattransactionstendtoholdontolocksforalongerperiodthaniftheyacquirethelocksonlywhennecessary.Theadvantageisthatonceatransactiongetsitslocks,itwillnotbeblocked(sotherewillbenodeadlocks)becauseitwillnotaskformorelocks.Whichisthebetterpolicy?Fundamentaltotheproblemoflockingperformanceisthefactthatlockingisnecessaryonlybecausetransactionsareruninamultiprogrammingfashion.Withmultiprogramming,therearetwokindsofcontention.Thereistheusualresourcecontention−e.g.,queueingforprocessorcyclesandI/Oand,inthecaseofmultiprocessorsystems,contentionovermemoriesandbuses;addedtothisisdatacontention−conflictsoverdatathatresultinlockqueuesandtransactionabortion.Eachformofcontentiondegradessystemperformance.Whatistheeffectofeach,andhowdotheyinteract?9.2MODELVALIDATIONANDEXPERIMENTALANALYSISWenowdiscusssomeissuesinmodelvalidationandexperimentalanalysis,usingthecasestudyaboveforillustration.9.2.1THENEEDFORVALIDATIONToformulateamodelforacomplicatedsystemwithalimitednumberofequationsandvariables,wemustinevitablymakeassumptionsanduseapproximations.However,wemustmakesurethattheseassumptionsandapproximationsdonotremoveessentialfeaturesofsystemperformance(e.g.,linearizingwhatisactuallynonlinear).Hencetheneedtovalidatethemodelwithexperimentalmeasurements.Thereisanother,relatedreasonforexperimentalmeasurements:Thereareoftenalternativewaysofmodelingthesamesystem,usingdifferenttechniques.Forexample,therearemodelsfortransactionlockingthatuseMarkovchains,andothersthatusequeueingnetworks.Infavoringaparticulartechniqueandmodel,wethereforeneedsomesupportingevidencefromexperiments.Evenforthesamemodelandtechnique,thereisusuallyachoiceofwhethertoadoptapar-ticularassumption,orhowtomakeanecessaryapproximation.Infact,experimentalmeasurementscanhelpusmakethechoice.Inthecaseofdatabaselocking,forexample,shouldatransactionsownlocksbetakenintoaccountincalculatingtheprobabilityofaconflict?Nothavingtodosomaygreatlysimplifytheanalysis.Onecouldmakethechoicebydevelopingthemodelbothways,andusingsimulationmeasurementstoseeifthesimplificationcausesasignificantlossinaccuracy. 669.EXPERIMENTALVALIDATIONANDANALYSIS9.2.2DATAPRESENTATIONInpresentingexperimentaldatatovalidateamodel,oneshouldbearinmindtheapproximationsinthemodelandtheaccuracyoftheexperiment.Forexample,itisnotmeaningfultousemultipledecimalplaceswhensuchprecisionisunwarranted.Itisofteneasiertocomparenumericalvalueswithadataplot.However,onesjudgementcanbeskewediftheaxesaretranslatedorscaled.Forinstance,averticalaxisthatdoesnotstartat0canexaggeratetheperformancedifferencebetweentwoalgorithms,andalogarithmicaxiscanunderstatethedifferencebetweenmodelpredictionandexperimentalmeasurement.Onarelatednote,thedifferencebetweenmodelandexperimentcanalsobereducedbychoosingaclosed,insteadofanopen,model.ThisisanissuethatisexaminedinOpenClosed[26].9.2.3REALSYSTEMSANDWORKLOADSIdeally,amodelshouldbevalidatedwiththerealsystemitselfforexample,theexperimentsinInternetServices[36]usedactualimplementationsoftheserversandapplications.Unfortunately,thisisnotalwayspossible.Databaseadministratorsloatheexperimentswithproductionsystems,andvendorszealouslyguardagainstpublicationofperformancemeasurementsoftheirproducts.Onepossiblecompromiseistologtheeventsinarealsystem,thenreplaythemonasimulator.Replayingsuchatracewouldbemorerealisticthanrunningasyntheticworkload(liketheTPC-CbenchmarkusedinSleepingDisks[37]).Onecouldevenmassagethetracebyrunningitatadifferentspeed,orcuttingitandplayingdifferentpiecesconcurrently,etc.However,therealismisalsoaweakness.Forexample,thetracefromadatabasesystemisalreadyfilteredthroughitsconcurrencycontrol,possiblyalteringthespatialandtemporalcorrelationinthetrace.Onemaythereforegetmisleadingresultsfromplayingitonanothersystem,withadifferentconcurrencycontrol,oratadifferentmultiprogramminglevel.9.2.4SIMULATIONGiventhedifficultyofexperimentingwitharealsystemandtheissueswithusingtraces,itisnotsurprisingthatmostmodelsarevalidatedbysimulation.Sincethesimulatorisplayingtheroleoftherealsystemincheckingthemodel,thesimulatorneedstobeasrealisticaspossible.Asimulatorthatadoptsthesameassumptions(e.g.,exponentialdistribution)andapproximations(e.g.,negligibleoverhead)doesnotserveitspurpose.Somesimulationparametersmaybecalibratedwithmicrobenchmarks.Forexample,diskser-vicetimemaybemeasuredbyissuingalongsequenceofIOrequests.Suchmicrobenchmarksare 9.2.MODELVALIDATIONANDEXPERIMENTALANALYSIS67sometimesusedalsotovalidateamodelbut,eveniftheyarerunonarealsystem,suchintenserepeatedactivitymaylacktherealismrequiredforvalidation.9.2.5PARAMETERSPACEREDUCTIONThemorerealisticasimulatoris,themoreparametersithas.Someparametersmaybebounded;forexample,0≤u≤1forsomeutilizationu.Otherparametersmaynotbebounded,thusmakinganexhaustiveexplorationofthesimulatorsparameterspaceinfeasible.Toreducetheparameterspace,somesubsetofparametersareoftenfixedthroughouttheexperimentswithmagicvalues,sotheybecomevoodooconstants.Forexample,thereisoneprocessorandtwodisks,orthinktimeisZ=1sec.Suchconstantsmayaffectthegeneralityoftheconclusionsdrawnfromtheexperimentalanalysis.Sometimes,parametersareinstantiatedthroughnormalization;e.g.,BitTorrent[25]assumeswithoutlossofgeneralitythatfilesizeis1.Suchnormalizationcanobscuretheimpactthataparameterhasonperformance.Forexample,settingL=1canpreventonefromseeinganL2factorinaperformancemeasure.OneanalyticallysoundwayofreducingtheparameterspaceistoidentifyasubsetofparametersS,andshowthatperformancedependsonSonlythroughsomeaggregateparameterWthatisexpressibleintermsofS.Inthecaseoftransactionlocking,forexample,ifmultiprogramminglevelisNanddatabasesizeisD,thenonecanshowthat(undercertainassumptions)theconflictprobability,responsetimeandrestartratedependonS={N,D}onlythroughW=N/D.Ineffect,thisreducestheparameterspacebyonedimension.9.2.6UNINTERESTINGREGIONSOFPARAMETERSPACEAsoneincreasestheworkload,systemperformancemusteventuallysaturateordegrade.Thereisthennopointinexperimentallyexploringtheparameterspacebeyondthat.Forexample,iftransactionlengthisk,thenagainonecanshowthatthereisaconstantcsuchthatthroughputdegradeswhenk2N/D>c,wherecdependsontheassumptions.Attentioncanhencefocusontheregionwherek2N/D≤c.Theparameterspacecanalsobedelimitedbyperformancemeasuresthemselves.Forexample,onecanreasonablysaythat,fortransactionlocking,aworkloadisofnointerestiftheresultingconflictprobabilityexceeds0.5.Similarly,onecanuserealisticwide-areapacketlossratestoruleoutlargeareasofparameterspaceforInternettraffic.Thereisanotherreasonforsuchperformance-basedconfinementoftheparameterspace:anyexperimentalanalysisfrombeyondwouldbeofnopracticalinterest.Forexample,tostudywhich 689.EXPERIMENTALVALIDATIONANDANALYSIStransactioninadeadlockcycleshouldbechosenforabortion,onewouldneedtohaveworkloadsthatgeneratelargecycles.However,itisknownthatsuchworkloadswoulddrivethesystemfarintoitsperformancedegradationzone;thisimpliesthatvictimselectionforlargecyclesis,infact,anon-issuefordatabasetransactions.Attheotherextreme,someregionsofparameterspaceareuninterestingbecausetheworkloadislightandperformanceislinear.Performancemodelingforlightworkloadsshouldbeastraight-forwardexercise.Thechallengeliesincraftingamodelthatcapturesnonlinearbehavior.9.2.7QUANTITATIVEPREDICTIONVS.QUALITATIVEUNDERSTANDINGOnereasonforhavingananalyticalmodelistouseitforperformanceprediction(e.g.,Sleep-ingDisks[37]usesaqueueingmodeltodynamicallydecidediskspeed),butthereisacommonmisunderstandingthatpredictionistheonlyreason.Forexample,amodelfortransactionswithanonuniformaccesspatternoveradatabaseofsizeDmayyieldanequationthatsaystheperformanceisequaltohavinguniformaccessoveradatabaseofsizeαD,whereαdependsontheaccesspatternandisnotknownapriori.Suchanequationcanbevalidatedthroughexperiments,butwhatisthepointofdoingso,ifsuchanequationcannotbeusedtopredictsystemperformance?Ananalyticalmodelisnotrendereduselessifitsresultscannotbeusedforquantitativeprediction,astheymayhelpusunderstandqualitativelythebehaviorofthesystem.Toseethedifference,consider:Noparentexpectstopredictachildsbehavior,butallparentsseektounderstandtheirbehavior.Ifamodelcanhelpusunderstandhowasystemshouldbehave,thatmaysufficefor,say,configurationdebuggingandanomalydetection.9.2.8ANALYTICVALIDATIONAnalyticmodelingisanart,inthatwepickapproximationstotradeaccuracyfortractabilityandinsight.Adifferentchoiceofapproximationswouldgivedifferentexpressionsfortheperformancemeasures.Hence,theoreticalconclusionsfromananalyticmodelmustbevalidatedtomakesurethattheydescribepropertiesofthesystem,ratherthanpropertiesofthemodel.Icallthisanalyticvalidation.Insteadofcomparingexperimentalmeasurementandmodelcalculation,onecandoananalyticvalidationbycomparingexperimentalmeasurements.Forexample,ifthemodelshowsthattheperformanceoftransactionsthatsetreadandwritelocksforadatabaseofsizeDisequivalenttotheperformanceoftransactionsthatsetonlywritelocksforadatabaseofsizeβD(forsomeβthatdependsonfractionofwritelocks,accesspattern,etc.),thisisaresultthatcallsforanalyticvalidation. 9.3.DISCUSSION69OnecandothisbyrunningtwoexperimentsonewithreadandwritelocksforadatabaseofsizeD,andonewithwritelocksforadatabaseofsizeβD;anagreementintransactionperformancefromthetwoexperimentsthenservestoanalyticallyvalidatethemodel.Isanalyticvalidationnecessary?Doesitnotsufficetohaveanumericalvalidationtocheckthatthemodelisaccuratewhencomparedtoexperimentalmeasurements?Yes,ifthemodelandexperimentsagreeexactly,thenthereisnoneedforanalyticvalidation.However,theapproximationsneededfortractabilityalwaysimplysomelossofaccuracy(andoneshouldbesuspiciousofanymodelthatcanprovideexactagreement).Thereisasubtlepurposetoanalyticvalidation:Areaderisaskedtosuspenddisbeliefasthemodeladoptsoneapproximationafteranothertogettothetheoreticalconclusions,andtheanalyticvalidationservestoreturnthereadersfaith.9.3DISCUSSIONStreamJoins[13]Parametersinthemodelarecalibratedwithmicrobenchmarks.Forexample,thecostPdforaccessingonetupleindatastructuredduringsearchiscalibratedbymeasuringthetotalrunningtimefor6000tuplesat100tuples/sec.Itisnotclearifsuchacalibrationissensitivetotheworkloadmixaswhenthereare,say,multiplestreamsandprocessorcachecontention.Theusualexperimentalvalidationofamodelwouldshowatableorplotwheremeasurementiscomparedtocalculation.Here,however,themeasurementandcalculatedvaluesareshownintwoseparateplotsFigs.2and3.Thisisaformofanalyticvalidation:Thearrange-mentoflinesobtainedwiththemodeliscomparedtothearrangementfromexperimentalmeasurement.Thetwoplotsareimpressivelysimilar,exceptforsomenon-monotonicbehaviorinthemea-surementforsmallandlargeλa/λbinFig.3.Thisbehaviorispossiblyahintthatthereissomenonlineareffectsnotmodeledbytheequations(i.e.,somelimittotheirvalidity);ifso,thesubsequentplotsFigs.47maynotshowstraightlinesiftheparametricvaluesweredifferent.InEq.(8),theparametersPn,Ph,In,Ihareinstantiated,andtheratioB/|B|setto10.Thisobscuressomepossiblyinterestingissues:WhatifIh6.SensorNet[29]ConsiderEq.(5),whichsaysexpectedMULEbufferoccupancyisE(M)=ρsensorsN2.WhyshouldbufferoccupancydependonN,whichisanarbitraryparameter?Surely,ifwerefinethegrid(e.g.,use4NinsteadofN),thatshouldnotaffectE(M)?Incontrast,theexpressionρsensors/(ρAPρmules)inEq.(18)isindependentofN. 9.3.DISCUSSION73Here,thetimeandspacediscretizationaretootightlyrelated.Supposethemodelincludesanotherparameters,andateachclocktick,aMULEtakes1stepinthegridandeachsensorgeneratessunitsofdata.Theexpressionsforperformancemeasureswouldthenincludes,andwouldscaleappropriatelyifthegridsizeischanged.Byfixings=1,themodeladoptsanormalizationthatintroducesanartifact(performancedependsongridsize).Theexperimentsusethesamespace/timediscretizationasthemodel.Thevalidationwouldbestrongeriftheexperimentscouldshowthattheresultsstillholdevenifthemodeling√assumptionswererelaxed.Forexample,themodelassumesthatAPsarespacedexactlyKgridpointsapart;thisassumptionisusedforthefoldingargumentinFig.4.However,theexperimentsshowthatthenumericalresultsaresimilareveniftheAPsarerandomlyplacedthisisavalidationofthemodelthatdeservestobemorethanjustafootnote(Sec.IX).Similarly,whileadiscrete-timerandomwalksimplifiestheanalysis,theexperimentscouldhaveusedanalternativemobilitymodel[2]overacontinuousspace.Althoughmanymobilitymodelsarenotrealistic,ifsimulationwiththesemodelsagreenumericallywiththeanalyticalmodel,thatwouldstrengthenitsvalidation.TheauthorsdescribesthecurvesinFigs.10and11assteep,forgettingthatthehorizontalaxesarelogarithmic.NetworkProcessor[19]TheSpliceNPthroughputcalculationwiththequeueingnetworkmodelinFig.4showsimpressiveaccuracy,especiallysincethecomparisoniswitharealimplementation.Fig.5isatypicalexampleoftheT-vs-λcurveillustratedinFig.2.5foranopensystem.DatabaseSerializability[1]Theinteractionbetweenresourcecontentionanddatacontentioncanbeseeninthispaper:Anincreaseindatacontention(e.g.,raisingthemultiprogramminglevel)causesmoreblocking,sothatmayreduceresourcecontention;ontheotherhand,theincreasedblockingcausesmorefreshnessviolation,andmoreabortedtransactionsandwastedresources.Conversely,anincreaseinthenumberofcachesmakesitmorelikelythatatransactioncanaccessalocalcopy,possiblyreducingdatacontention;ontheotherhand,morecachesalsoimpliesmorecopiers,andthatmayleadtohigherdatacontention.Fig.12showsthat,withBSAFC-0,thisdatacontentionwhenscalingout(i.e.,increasingthenumberofcaches)cancausethethroughputtodrop,possiblytobelowthatfornocaches.NoC[15]Fig.5showsgoodagreementbetweenmodelandsimulation,evenaslatencyincreasessharply.Thisisdespitethemanyapproximations(memorylessservicetime,useofM/M/1formulasforM/M/1/D,etc.).ItalsomeansthatthepowerconsumptionlinearityandagreementinFig.6arenotbecausePpeissmall.However,thelinearityalsosuggeststhatthenonlinear 749.EXPERIMENTALVALIDATIONANDANALYSISterms,likeBPleak_flitinEq.(26)aremadenegligiblebythesmallvalueofPleak_flit.Thatmeanstheelaboratequeueingmodelisunnecessaryforestimatingpowerconsumption.Inanalyticalmodeling,itisoftenusefultofirstrunsomeexperiments(withasimulator,say)todeterminewhataspectsofthesystemthemodelshouldfocuson,beforeformulatingthemodel.Notethatthepowerconsumptionparameters(Pr_buf,etc.)inthesimulatorarecalibratedwithahardwareimplementation.NonstationaryMix[30]Achallengethatonefaceswhenmodelingarealsystemisthatparametersthatoneroutinelyusetoconstructamodelmaynotbeavailable.Forexample,servicetimesmaybeunknownbecausetheyrequirepossiblyintrusiveinstrumentationofaproductionsystem.Onesolutionwouldbetodevicesomeindirectcalibrationoftheparameters.However,realsystemsusuallyrunamixoftransactiontypes,andthemixcanvarydrasticallyovertime.Howcantheparametersbecalibratedwhenthemixisnonstationary?Theseissuesarecommoninothercomputingsystems.WhenmodelingInternettraffic,forexample,oneoftenhaveapplicationdataattheendhostsonly(noroutermeasurements,etc.)andthetrafficmixisconstantlychanging.Theauthorsideaforaddressingthisissueliesintheinsightthatthenonstationarityalsoprovidesacollectionofindependentdatapoints(e.g.,asamplingfromthesetofpointsinFig.1)thatcanbeusedtocalibratemodelparametersbylinearregression.Thisprovidesanalternativetocalibrationbycontrolledexperiments(withbenchmarks,say).Thepaperconsidersanenterprisesystemrunningamixoftransactions.Themodeldiscretizestimeinto5-minintervals.ThemodelparametersareNij(thenumberoftypejtransactionsinthei-thinterval),andtheregressioncoefficientsαjandβjr.ThesecoefficientsareobtainedbyregressionusingNijandresponsetimeyi(Eq.(2))andutilizationUir(Eq.(5));thesevaluesareusuallyavailablefromroutinesystemlogs.TheBasicmodelstartswithTij=αjNij.RecallfromSec.6.1thatT≈rDrwhenthereislittlequeueing(cf.Assumption4inSec.3.1).SinceαjissumofservicetimesoverallresourcesrandDrisproductofnumberofvisitsandservicetimepervisit,theBasicmodelworksbestifeachresourceisvisitedjustonce,likeinFig.6.Oneinterpretationofthisisthat,foreachresourcer,themodeladdstheservicetimesformultiplevisitstothatresource,andconsiderthesumtobetheservicetimeforjustonevisit.Thisrearrangementofvisitswillgivesimilarperformanceifthereislittlequeueingonanyvisit.Althoughtheemphasisofthispaperisonnonstationarity,theExtendedmodel(Eq.(4))usesU2thesteady-stateM/M/1waitingtime1ir(seeEq.2.7)toestimateyi.Thisrecallstheλi1−Uirideaofflowequivalence(seeSec.6.2):althoughthetransactionmixarrivingatthesystem 9.3.DISCUSSION75(representedbytheM/M/1queue)isnonstationary,theapproximationmayworkwellifthesystemreachesequilibriumwithineach5-minuteinterval.TheCompositemodelseekstoreplacetheperformancemetricUirintheExtendedmodelwithanexpressionintermsofinputparameters.Ifλij,Vijr,andSjrarethearrivalrate,visitsperjob,andservicetimeperjob(i,j,rasbefore),thenNijVijrSjrUir=λijVijrSjr=VijrSjr=Nij,LLjjjsotheservicedemandβjrinEq.(5)assumesVijrdoesnotchangewithintervali.Evenwhentwoisolatedworkloadsarewellunderstood,predictingtheirperformancewhenruntogetherisdifficultbecauseperformancemeasureslikequeuelengthsandresponsetimescannotbesimplyaddedtogether.However,arrivalratesandthereforeutilizationcanbeadded.SincetheExtendedmodelusesutilization,iteasilyleadstotheConsolidatedmodelinSec.5.1.Nonetheless,thismodelwouldbreakifU+U≥1;here,themodelagainreliesonAssump-irirtion4(i.e.,over-provisioning).Whileaggregateerrors(e.g.,Table2)andcumulativedistributions(e.g.,Fig.11)giveanoverviewofthemodelsaccuracy,furtherdetailsarenecessaryforabetterunderstanding.Forexample,alargeerrorinpredictingsub-secondresponsetimes(e.g.,PetStoreinTable1)maynotmatter,andasmallerrorinpredictingahighutilizationof,say,0.98iseasytoachieve(sinceitisabottleneck).Fig.8illustrateshowananalyticalmodelcanbeusedtoidentifybugswhenmeasuredperfor-mancedeviatessignificantlyfromprediction. 77CHAPTER10AnalysiswithanAnalyticalModelThepreviouschapterexaminessomeissuesconcerningexperiments.Wenowcontinuebydiscussingtheformulationandfunctionofanalyticalmodels.10.1THESCIENCE&ARTINPERFORMANCEMODELINGWhereappropriate,weagainusethecasestudyontransactionlockingasillustration.10.1.1POWERWhyhaveananalyticalmodel?Acommonargumentisthatsolvingthemtakeslesstimethanrunningsimulationsbut(giventherapidincreaseincomputepower)thisclaimisincreasinglyweak.Anotherargumentisthatsomesimulatorsareverycomplicated(e.g.,thenetworksimulatorns-2),andcontainbugsthatmayaffectthereliabilityoftheirresults,butsolversforanalyticalmodelscanhavebugstoo.Althoughanalyticalmodelsareoftenproposedasalternativestosimulation,manyareinfactusedassimulators,inthefollowingsense:Aftervalidatingthemodelwithcomparisonstoexper-imentalmeasurements,themodelisusedtoplottherelationshipbetweenperformancemeasuresandinputparameters,andconclusionsthendrawnfromtheseplots.Icallthisanalyticsimulation.Ifconclusionsaretobedrawnfromlookingatplots,thenonemaybebetteroffgeneratingthoseplotswithasimulator,sincethemodelsassumptionsandapproximationsmayintroducemisleadinginaccuracies.Thepowerinananalyticalmodelliesnotinitsroleasafastsubstituteforasimulator,butintheanalysisthatonecanbringtobearonitsequations.Suchananalysiscanprovideinsightsthatcannotbeobtainedbyeyeballinganynumberofplots(withoutknowingwhatyouarelookingfor),andconclusionsthatnosimulatorcanoffer. 7810.ANALYSISWITHANANALYTICALMODEL10.1.2TECHNIQUEThepowerofananalyticalmodelismostobviouswhenitprovidesexpressionsthatexplicitlyrelatetheperformancemeasurestothesystemparameters.Suchclosed-formexpressionscanthenbesubjectedtomathematicalanalysis.Inthecaseofdatabaselocking,thiswashowtheworkloadboundk2N/Dc),sooneisinfactstudyingaphenomenonthatisofquestionableinterest.10.1.5SCIENCEANDTECHNOLOGYTheimpactoftransactionlockingonperformanceistheresultofanintricateinteractionbetweendataandresourcecontention:Intensedatacontentioncancausemanytransactionstobeblocked,therebyleadingtomorecontext-switchingandswapping,bothofwhichaddtoresourcecontention.Ontheotherhand,ifmoretransactionsareblocked,thenthereislessdemandonprocessorcyclesanddiskbandwidth,soresourcecontentionisreduced.Howshouldonestudythisinteraction?Onecouldpointtothecomplexityofthemutualdependencyasajustificationforusingonlyanexperimentalorsimulationstudy.However,thegeneralityoftheconclusionsfromsuchastudywouldbelimitedbytheparticularhardware/softwareimplementationorthesimulationparameters.Forperformanceanalysistobeascience,itsresultsmustwithstandchangesintechnology.Fortransactionlocking,weseekananalysisofdatacontentionthatisindependentofthehardwareandsoftwareunderlyingthesystem,yetpermitsustodrawconclusionsabouttransactionperformancewithdifferentlevelsandmodesofresourcecontention.SuchananalysiscanbedonebymodelingresourcecontentionwithavariableT,thetimebetweentwolockrequestsifthetransactionisrunalone(i.e.,withoutdilationfromblocking).IfweconsiderthisvariableTtobeafunctionofthenumberofactive(i.e.,nonblocked)transactionsNactive,thendatacontentiondeterminesNactive,whileresourcecontentiondeterminesT(Nactive). 8010.ANALYSISWITHANANALYTICALMODELNow,Nactiveisarandomvariable,soevaluatingthedatacontentiontodetermineNactivemayinvolvearecursionthatincorporatesbothdataandresourcecontentionatothervaluesofNactive[21].However,ifweusejusttheaveragevalueofNactivetoestimateT(Nactive),thenitispossibletoevaluatethedatacontentionandresourcecontentionindependently(e.g.,aMarkovchainfortheformerandaqueueingnetworkforthelatter),thenintegratethetwo[32].WeseeherethatAverageValueApproximation(AVA)isusefulnotjustforderivations,butitisalsoananalytictechniquefordecouplingtwocloselyinteractingforcesinasystem.Suchadecouplingprovidesaframeworkforreasoninginformallytoanengineeraboutsystembehavior.Anaggingworry,however,isthatsomeimportantsynergisticeffectmaybelostthroughthisdecoupling.10.1.6INTUITIONANDCONTRADICTIONTodesignandengineeracomplicatedsystem,weneedhelpfromintuitionthatisdistilledfromexperience.Experiencewithrealsystemsislimitedbyavailabilityandconfigurationhistory.Wecangetaroundthatthroughsimulationexperiments.However,theoverwhelmingsizeoftheparameterspaceusuallymeansweneedtolimititsexploration,butexperimentdesignanditsinterpretationmay,inturn,beswayedbyintuition.Onewayofbreakingthiscircularityistoconstructananalyticalmodelthatabstractsawaythetechnicaldetailsandzoomsinonthefactorsaffectingthecentralissues.Wecanthencheckourintuitionwithananalysisofthemodel.Intuitionisimprovedthroughcontradictions:theypointoutthelimitsontheoldintuition,andnewintuitionisgainedtoreplacethecontradictions.Again,suchcontradictionscanbehardtofindinalargesimulationspace,butmaybeplaintoseewithananalyticalmodel.Inthecaseoftransactionlocking,therewereseveralexamplesofoldintuitionbeingcontra-dicted.Forexample,oneverysimpleconflictresolutionpolicywouldbetorestartatransactionifalockitneedsisalreadyheldbyanothertransaction.Thisistheso-calledno-waitingpolicy.Intuitionsuggeststhatthispolicywillperformbadly:whyrestartatransaction(thuslosingwhatithasdonesofar)whenitcostsnothingtojustblockit?Infact,thereisacostinblocking.Whenatransactionisblocked,itisnotusingthelocksthatitalreadyholds,whilepreventingothertransactionsthatneedthoselocksfromgettingthemandmakingprogress.Evenifonecouldimmediatelyseethisanti-socialeffectofblocking,itisstilldifficulttobelievethatitcouldbeworsethanthedraconianno-waitingpolicy.Butitcould.Foranotherexample,recallthatstaticlockingiswhereatransactiondoesnotbeginexecutionuntilitgetsallthelocksitneeds.Incontrast,dynamiclockingiswhereatransactiongetsalockonlywhenitneedsthelock.Inbothcases,thelocksareheldtilltheendofthetransaction.Intuitively,staticlockingisaloser,sincethetransactionisgettinglocksbeforeitneedsthem,thusreducingthelevelofconcurrency.Thisreasoningturnsouttobesuperficial.Thereareconditionsunderwhichlocksareheldlongerunderdynamiclockingthanunderstaticlocking. 10.1.THESCIENCE&ARTINPERFORMANCEMODELING81Thethirdexampleconcernsthroughputdegradationasconcurrencyincreases.Intuitionmaytellusthatthisiscausedbydeadlocksandrestarts,i.e.,thesystemhasbeendriventoapointwhereitisspendingtoomuchofitstimeredoingdeadlockedtransactions,thuslosingitsthroughput.Suchanintuitionwouldbeconsistentwithpagethrashinginoperatingsystems,butiswrong.Thesethreeexamplesarenothypotheticaltheycanbefoundintheliterature.Howcouldonesintuitiongowrong?Intheexampleoftheno-waitingpolicy,thereareatleasttworeasonswhytheintuitionispartlycorrect.Oneofthemistheconfusionbetweenresourceanddatacontention,andtheotherinvolveslookingattheappropriateperformancemeasure.Anexcessiveamountofrestartsisbadonlybecauseitcausesintensecontentionforresources;asameansofresolvingdatacontention,restartsarenoworsethanblockingintheireffectonperformance,ifwefactorouttheresourcecontention.Also,restartsarebadforresponsetime,butnotnecessarilybadforthroughput.Inasense,restartsallowthesystemtopickfromtheinputstreamthosetransactionsthatcangetthroughwithnohassle,anddelaytheresttilltheconflictingtransactionshaveleft.Inthesecondexample,thereisacriticaldifferencebetweenstaticanddynamiclocking:atransactionholdsnolockswhenitisblockedunderstaticlocking,whileablockedtransactionunderdynamiclockingmaybeholdinglocks.Eachtimeatransactionisblockedunderdynamiclocking,theperiodoverwhichitholdsitslocksislengthened.Itisthuspossiblethattransactionsendupholdingontolockslongerthaniftheyhadusedstaticlocking,soitisnotclearthatstaticlockingisreallyaloser.Inthethirdexample,lockingcancausethroughputdegradationnotthroughdeadlocks,butwhentoomanytransactionsaretiedupwaitingforlocksthattheyneedbutcannotget.Foreachaddedtransaction,morethanonetransactionmaybecomeblocked,sothroughputdrops.Thepictureoffrenziedactivityforpagethrashinginoperatingsystemsleadsonetoexpectasimilarpicturefordatabasesystems,wheninfacttheappropriateoneisofalargenumberofidlingtransactionswaitingforafewtransactionstofinish,sotheycanproceed.Thefailureofintuitionintheseexamplesispartlycausedbyanunfamiliaritywiththeimpactofdatacontentionanditsinteractionwithresourcecontention.Togiveanotherexample,recalltheissueoflockgranularity.Theintuitionthereisthatcoveringmoredataperlockwillreducethenumberofconcurrenttransactionsbutsaveoninstructionoverhead.Now,refininggranularityincreasesthenumberofdataitemsDaswellasthenumberoflockskthatatransactionneeds.Onceananalyticalmodelshowsthatperformanceisdeterminedbyk2N/D,itbecomesclearfromk2thatanincreaseinDcaninfactreduceconcurrency.Moreover,anincreaseinconcurrencycanworsenperformancebecauseconcurrenttransactionscompeteforresources.Incidentally,thefirstandsecondexamplesconcernextremepolicies.Otherextremepoliciescanbefoundincachemanagement,admissioncontrol,loadbalancing,etc.,andtheyareoften 8210.ANALYSISWITHANANALYTICALMODELbelievedtogiveworst-caseperformance.Theno-waitingpolicyandstaticlockingaboveshowthatsuchabeliefcanbewrong.Theabilitytorevealandresolvecontradictions,andthusimproveengineeringintuition,isonedemonstrationofthepowerofanalyticmodeling.10.2DISCUSSIONStreamJoins[13]Theauthorsmadegooduseofthemodeltoanalyzetheissuesthatmotivatedthepaper.InSec.5.1,forexample,theyusedtheequationstoderiveclosed-formexpressionsforwhenoneparticularjoincombinationisbetterthananother.TheseexpressionsinEqs.(8)and(11)wouldbemoreinformativeiftheparametersB/|B|,Ih,Phetc.werenotinstantiated,soonecouldbetterunderstandhowthecomparisondependsontheseparametricvalues.SleepingDisks[37]Thispaperusesthequeueingmodelnotforanalysis,butforthecalculationtominimizeenergyconsumptionsubjecttotheresponsetimeconstraintRlimit(Sec.3.1.1).GPRS[23]Sec.5usestheanalyticalmodeltoplotperformancecurvesforanalysis.Thisisanexampleofanalyticsimulation:thosecurvescouldhavebeenplottedwiththesimulator,withgreaterfidelity.Itturnsoutthattheperformancemetrics(p(n),U˜,etc.)dependontB,toff,xBandxononlythroughx=tBxoninEq.(6).ThisisanexampleofhowtheparameterspaceisreducedwithxBtoffthehelpofananalyticalmodel.Forexample,Sec.6usesthemodelfordimensioning:Givenamaximumacceptableblockingprobability(0.02,say),whatisthemaximumnumberofcells,ormaximumnumberofmobilespercell?TheanswercanbefoundfromFigs.14and15,intermsofx.Withouttheintroductionofxfromtheanalyticalmodel,asimulationstudy(say)ofdimensioningusingtB,xon,etc.wouldbequiteintractable.Fig.12showsthat,forafixednumberofuserspercellandasxincreases,throughputfirstincreases,thendecreases.Suchnon-monotonicbehaviorismoreinterestingthanthemono-toniccurvesinpreviousplots,andbearscloserstudy.Forexample,itsuggeststhatxshouldonlyincreaseuntilwherethroughputbeginstodecrease,thusfurtherdelimitingtheparameterspace.InternetServices[36]Basedonthequeueingnetworkmodelofthesystem,theMVAalgorithmisusedfordynamic 10.2.DISCUSSION83provisioning,todeterminethenumberofserversneededtomaintainaresponsetimetarget(Fig.12b)asarrivalschangeovertime(Fig.12a).TCP[24]NoticethatEq.(31)expressesTCPthroughputB(p)intermsoflossprobabilitypandroundtriptimeRTT.Clearly,foranynontrivialInternetpath,pandRTTcanonlybemeasured,notpredicted.IfoneistomeasurepandRTT,onemightaswellmeasureB(p)too,sowhatisthepointofhavingthatequation?ThesignificanceoftheequationliesnotinpredictingB(p),butincharacterizingitsrelation-shipwithpandRTT.SuchacharacterizationledtotheconceptofTCP-friendlinessandthedesignofequation-basedprotocols[7].CodeRed[38]TheparametertuningneededforEq.(17)tofittheobservedinfectionmeansthatthemodelcannotbeusedtopredicttheepidemicatthebeginningoftheinfection.However,knowingthattheequationdoesincorporatethemajorfactorsshapingtheinfection,onecanuseittoanalyzetheeffectivenessofaspecificcountermeasure.Itmayevenbepossibletocalibratetheparametersdynamically(asdataisreceived),tohelpchoosethecountermeasureforcurbingthespread.802.11[31]ThesystemconsistsofawirelesscellwithstationarymobilenodesusingIEEE802.11(basicaccess)tosendtraffictotheaccesspoint.Packetcollisionsinduceretransmissionsandbackoff,somaximumpossiblethroughputislowerthanthechannelbandwidth.Theissueishowthissaturationthroughputdependsontheparameters,andonthetradeoffbetweencollisionandbackoff.ThemainparametersarethenumberofnodesnandtheminimumcontentionwindowsizeW;themainperformancemeasuresarethecollisionprobabilitypandthesaturationthroughputS.Table1listsotherparametersandmetrics.Fig.2showsthemodelskeyidea,formulatedusingAVAasp=1/Wbackoff.Therestofthemodelfollowsinastraightforwardmannerfromthefirst-orderapproximationinEq.(4).Itispossiblethatsuchanapproximationmayresultinatriviallinearmodel,buttheexperimentsshowthatitinfactsufficestomodelthenonlinearbehavioroftheprotocol.Theparameterspaceisfirstrestrictedtowherep<0.5.AcomparisonofFigs.3and4showsthatthereisthroughputsaturationevenundersucharestriction.Thisissimilartothecasefortransactionlocking,wherethroughputbeginstodegradeevenbeforethedeadlockprobabilitybecomessignificant.Thespaceisfurtherreducedthroughthreeresults:Claim1reducestheparameterstoW,mandn,Claim2tomandg(=W/(n−1))andClaim3tojustg. 8410.ANALYSISWITHANANALYTICALMODELGiventhemultipleapproximations,somegross(likeEq.(12))andsomearbitrary(likeEq.(13)),thereisaclearneedforanalyticvalidationoftheclaims.ThisisdoneinTable3(forClaim1),Fig.7andFig.8(forClaim2)andTable5(forClaim3).Notethatthesetablesandfiguresaregeneratedbythesimulatoralone,tovalidatetheclaimsgeneratedbythemodel.ThereisfurtheranalyticvalidationinTable4(forCor.1),Table6(forClaim6),andTable7(forClaim7).TheinsightsgainedfromanalyzingtheequationsarecapturedinCor.1(theequivalencebetweenminimumwindowsizeWandnumberofnodesn),Cor.2(howWshouldvarywithnandpacketsize),Claim2(howthegapgtransformsFig.3intoFig.7andFig.4intoFig.8),andClaim6(howmaximumthroughputisatradeoffbetweencollisionsandbackoffs).Suchinsightsarehardtogetiftheanalytictechnique(e.g.,Markovchain)doesnotyieldclosed-formexpressions.MediaStreaming[35]TheauthorsusestheiranalyticalmodeltoshowthatthemultiplexingprotocolinTheorem3.1isoptimal.Suchaproofofoptimalityishardtodobysimulation.AsFig.7ashows,ifthefailurerateissufficientlyhigh,thenthesystemmaynotbeabletogenerateenoughpeerstosupportthedemand(sorejectionrateneverreaches0);themodeldoesnotsayhowbigscangetbeforethishappens.TransactionalMemory[11]Themodelisusedforanalyticsimulation,tocomputeTablesIIandIII,andthusdrawcon-clusionsabouttheperformanceofsoftwaretransactionmemory.Itislikelythatmuchmoreinsightcanbedrawnfromthismodel,asdemonstratedintheno-waitingcasefordatabasetransactions[33].ThekeyliesinsimplifyingtheexpressionforqiinEq.(4).Thisistheissue,discussedinSec.9.2.1,ofhowatransactionslocksaffectsitsownperformance.SensorNet[29]Thispapergivesagoodexampleofhowananalyticalmodelthatprovidesclosed-formex-pressions(likeEq.(18))canbringcrispinsighttoaproblem.However,thekeyperformancemetricisdatasuccessrateS.Itisusuallydifficulttoobtainexplicit,closed-formexpressionsforsuchaprobability,sothereislittlethatonecandowiththeformulasforSinSec.VIIIbesidesplottingthem.DatabaseSerializability[1]Thispaperisanexamplewherethequeueingnetworkisusedasasimulationmodelandnotasananalyticalmodelforderivingequationstodescribethesystem.Thequeueingnetworkisnotseparable;e.g.,Fig.3showsnoserversfortheReadyQueueandBlockedQueue.NotefromFig.6thatthedataforStrict2PLreachesapeak,thendecreasesasmultipro-gramminglevelincreases.(ThismayalsohappenfortheBSAFCcurvesforhigherwrite 10.2.DISCUSSION85probabilities.)Thissubsequentdecreaseisnotcausedbyresourcecontention,sincethereareinfiniteresourceunits.Rather,itistheresultofdatacontentionseeSec.10.1.6.Weseeherethatwhetherinfiniteresourcesisrealisticisbesidethepoint,asitisawayoffactoringoutresourcecontentionsowecanclearlyseetheeffectofdatacontention.Also,onemustnotassumethatinfiniteresourcesgiveaperformancebound;ifmorecachescancausemoredatacontention,infiniteresourcesmayresultinmoredatacontentionandpoorerperformancethanfiniteresources.Onecanarguethatfreshnessconstraintsbringathirdforceintoconcurrencycontrolperfor-mance,namely,timecontention.Intuitively,resourcecontentionincreasesifmoretransactionswanttousearesource(CPUcycleordiskaccess,etc.),anddatacontentionincreasesifmoretransactionsrequirelocks(onrecordsortables,etc.).Similarly,timecontentionincreasesifmoretransactionsneedtosatisfytheirfreshnessconstraint:morereadsarerejectedandtrans-actionsareaborted.Onemayobjectthatthisisjustanotherformofdatacontentionorresourcecontention.Ontheotherhand,onecouldalsoconsiderdatacontentionasjustanotherformofresourcecontention(thedatalockbeingtheresource),butitisnowgenerallyacceptedthatthetwoaredifferent.Anyanalyticalmodelthatcanestablishordismisstimecontentionasathirdforcewouldbemakingascientificcontributionthatgoesbeyondthetechnologicalissuesofcachedeploy-ment,serializationalgorithm,etc.Todoso,suchamodelwouldneedtoprovideclosed-formexpressionsforanalysis;aqueueingnetwork(liketheoneinthispaper)wouldnotsuffice.AcomparisonofFigs.5and6showsthatStrict2PLisaboveBSAFC-0inoneplot,butbelowintheother.Theyillustratehowtwosimulationstudiesofthesameprotocolscanreachdifferentconclusionsiftheparametervaluesaresetdifferently.Thisiswhyaperformancestudymustcarefullydelimitandexploretheparameterspace,andwhytheuseofmagicconstants(like1secondforthinktimeinTable1)isanissue.Furthermore,theperformancereversalbetweenStrict2PLandBSAFC-0isnotdeterminedbydatacontention,butbyresourcescontention(sincethedifferencebetweenFigs.5and6liesintheresourcecontention).NoC[15]Thereisnodemonstrationofhowtheanalyticalmodelisusedtoevaluatetheirrouterdesign.DistributedProtocols[9]TheanalysisinSec.4.1.3showsthattheendemicprotocolhasliveness(sinceγ>0),fairness(sincetheprotocolissymmetric)andsafetyforthesecondequilibrium.Onecanviewthespace-timeplotinFig.8asananalyticvalidationofthoseclaims.Thispapergivesanexcellentdemonstrationofthepowerofananalyticalmodel:itshowshowsuchamodelcanbeusedtodesignprotocols. 8610.ANALYSISWITHANANALYTICALMODELSoftState[20]Theuseofsoftstatesisaparadigmfavoredbymanydesignersofdistributedprotocols.Thispaperprovidesexamplesofhowthehardwareandsoftwarecanbeabstractedawaybyamodeltoprovideascientificbasisforengineeringintuition.Thesystemconsistsoftwopartiesrunningsomeconnectionprotocoloverapossiblylossychannel,withattentionfocusedontheexchangeofcontrolmessages.Thecentralissueisthedifferencebetweenhardandsoftstate,whichischaracterizedasatradeoffbetweenthecostofrefreshingstateandthecostofstalestates.Themodelusedvarieswiththesetting:aflowdiagramforprotocolstate(Fig.2)inSec.3,a2-dimensionalMarkovchaininSec.4,andanM/M/∞serverinSec.5.ComparetheinsightgainedfromthemodelsinSecs.3and4:thesimpleflowdiagramresultsinaconciseEq.(1)thatcharacterizesthetradeoffbetweenhardandsoftstate,intermsofconnectionlifetime,lossprobabilitiesandcosts;incontrast,onecannotextractanyclosed-formexpressionfromtheMarkovchain,sinceitssolutionisonlyimplicitlydefined.Notethestateaggregation(Sec.4.3)thatreducestheN-dimensionalstatespacetoa2-dimensionalMh.Althoughtheanalysisstartsoffbyderivingaclosed-formfortheoptimalrefreshinterval(Eq.(1)),therestofthepaperusesthemodelsforanalyticsimulation(i.e.,plottinggraphs).Ideally,thereshouldbesomeanalyticvalidationtoverifytheconclusionsfromsuchanabstractstudy;e.g.,checkifmeasurementswithrealprotocolsrunningoversomerealnetworkcanreproduceaplotlikeFig.4(a).Suchvalidationisnecessary,toguardagainstbehavioralartifactsthatmayresultfromthemodels(e.g.,Eq.(2)forchannelloss).Fig.3(a)hasalogarithmichorizontalaxis,andaverticalaxisthatdoesnotstartfrom0;thesetendtovisuallyexaggeratethedifferencebetweenthetwocurves.Also,therelativepositionsofthetwolinesdependonthevaluesofa,b,Css,etc. 87APPENDIXAExercisesThefollowingaresomeexercisesonthemodelsdiscussedinthisbook.1.J.Kang,J.F.Naughton,andS.Viglas.Evaluatingwindowjoinsoverunboundedstreams.InProc.Int.Conf.onDataEngineering(ICDE),pages341352,March2003.DOI:10.1109/ICDE.2003.1260804Thetuplesinastreammayhavevaryinginter-arrivaltimes,andthejoiningtimemayalsovaryfromonetupletoanother.Thismakesitnecessarytohaveabufferforstoringarrivingtuplesastheywaittheirturntobeprocessed.Supposewemodeltheinter-arrivaltimeandprocessingtimeofeachtupleasexponentiallydistributed(withratesλa,λbandμ).AssumingtherearenoCPUandmemoryconstraints,estimatehowmuchmemoryspaceisoccupiedwhenjoiningtwostreamswithwindowsizesAandB.2.Q.Zhu,Z.Chen,L.Tan,Y.Zhou,K.Keeton,andJ.Wilkes.Hibernator:helpingdiskarrayssleepthroughthewinter.Proc.ACMSymp.OperatingSystemsPrinciples(SOSP),39(5):177190,2005.DOI:10.1145/1095810.1095828Exp(tij)InSec.3.2.4,theauthorsexpressionforRusestoestimatethedelaycausedbyij2servicingonebackgroundrequest.(I)ExplainwhythisestimateisinconsistentwiththeirM/G/1modelforthedisk.(II)Provideanalternativeestimate.3.G.Nogueira,B.Baynat,andP.Eisenmann.AnanalyticalmodelforthedimensioningofaGPRS/EDGEnetworkwithacapacityconstraintonagroupofcells.InProc.MOBICOM,pages215227,August2005.DOI:10.1145/1080829.1080852IntheirON/OFFmodel,anONperiodcorrespondstoservicetimeandanOFFperiodcorrespondstointer-arrivaltime.(I)UsingthevariablesintheirGPRSmodelandslotsastheunitoftime(insteadofseconds),estimatetheaverageinter-arrivaltimeandservicetimeoftransfers.(II)Deducethearrivalrateandservicerateoftransfers.(III)GiveaninterpretationforxinEq.(6). 88A.EXERCISES4.B.Urgaonkar,G.Pacifici,P.Shenoy,M.Spreitzer,andA.Tantawi.Analyticmodelingofmul-titierInternetapplications.ACMTrans.Web,1(1):2,2007.DOI:10.1145/1232722.1232724ConsidertheexperimentforFig.9.Forthecaseof400simultaneoussessions,estimate:(I)theservicedemandatthemiddletier;(II)thegoodputattheCPUinthemiddletier;(III)theaveragenumberofsessionsthatarewaitingforresponsetotheirrequests;(IV)thearrivalrateofrequests;(V)theprobabilitythatarequestisdropped(i.e.,notcompleted).5.B.Schroeder,A.Wierman,andM.Harchol-Balter.Openversusclosed:acautionarytale.InProc.Symp.NetworkedSystemsDesignandImplementation(NSDI),2006.http://www.usenix.org/events/nsdi06/tech/schroeder.htmlThepaperimplicitlyassumestheprobabilityp(thatausermakesanotherrequestafterarequestcompletes)isconstant.Supposepdecreasesasloadincreases.(I)Explainwhythismayhappen.(II)SuggesthowPrinciple(vii)shouldbemodified:Principle(vii)Asloadincreases,...6.J.Padhye,V.Firoiu,D.Towsley,andJ.Kurose.ModelingTCPthroughput:asimplemodelanditsempiricalvalidation.InProc.SIGCOMM,pages303314,September1998.DOI:10.1145/285243.285291GiveanAVA(AverageValueApproximation)argumentforEq.(21):E[Y]+Q∗E[R]B=.E[A]+Q∗E[ZTO](Youcanignorethesubscripti.)7.C.C.Zou,W.Gong,andD.Towsley.Coderedwormpropagationmodelingandanalysis.InProc.ACMConf.ComputerandCommunicationsSecurity(CCS),pages138147,2002.DOI:10.1145/586110.586130Inthewormmodel,onefactorthatreducestheinfectionrateβisnetworkcongestioncausedbywormpropagation.(I)SuggesthowanM/M/1queuecanbeusedtomodelcongestiondelay.(II)Expressβintermsofthequeuesarrivalandservicerates.(III)ExplainwhyyourM/M/1queuemaybeapoormodelforcongestiondelay. 898.D.QiuandR.Srikant.ModelingandperformanceanalysisofBitTorrent-likepeer-to-peernetworks.InProc.SIGCOMM,pages367378,2004.DOI:10.1145/1015467.1015508LetTabortedandTcompletedbetheaveragedownloadingtimeforadownloadthatisabortedorcompleted,respectively.Showthat(I)x¯=(λ−θx)T¯completed+θxT¯aborted;(II)thefractionofdownloadsthatwillbecomeseedsisλ−θx¯ifandonlyifλTcompleted=Taborted.9.P.GuptaandP.R.Kumar.Thecapacityofwirelessnetworks.IEEETrans.InformationTheory,46(2):388404,2000.DOI:10.1109/18.825799AssumethedomainhasareaAm2,insteadof1m2.(I)FortheProtocolModel,pointoutwhereAentersthederivation.ThepaperassumesAisfixedwhenthenumberofnodesnisincreased,sodensity(#nodespersquaremeter)increases.(II)Supposedensityisfixedwhennincreases,soAincreases.WhatwouldbethenewboundforλL¯?(III)ExplainintuitivelywhythisnewboundisO(1)insteadofO(√1).n10.Y.C.TayandK.C.Chua.AcapacityanalysisfortheIEEE802.11MACprotocol.WirelessNetworks,7(2):159171,2001.DOI:10.1023/A:1016637622896ItfollowsfromClaim5that,forafixedbandwidthandsufficientlylargepacketsize(measured√in#slots),thesaturationthroughputismaximumwhenW≈(n−1).Suggesthowthesimulatorcanbeusedtovalidatethis.11.Y.-C.Tu,J.Sun,andS.Prabhakar.Performanceanalysisofahybridmediastreamingsystem.InProc.ACM/SPIEConf.onMultimediaComputingandNetworking(MMCN),pages6982,January2004.DOI:10.1117/12.538806(I)Fig.2indicatesatimek1(beyondk0)wherebandwidthusageoftheCDNserversbecomes0.Giveanequationforthepartofthecurvebetweenk0andk1.(II)Arequestingpeermay,afterstreaminghasstarted,decidetoabortthedownload(becausethestreamingqualityispoor,say).ExplainhowyoucanmodifyEq.(1)tomodelstreamabortion.(III)Whatisthegradient(expressedintermsofmodelparameters)oftheasymptoticlineinFig.3b(TotalPeersvsTime)? 90A.EXERCISES12.E.Gabber,J.Fellin,M.Flaster,F.Gu,B.Hillyer,W.T.Ng,B.Özden,andE.A.M.Shriver.Starfish:highly-availableblockstorage.InProc.USENIXAnnualTech.Conf.,pages151163,June2003.http://www.usenix.org/event/usenix03/tech/freenix03/gabber.htmlSupposeN=3,the3SEshavedifferentfailureandrecoveryrates,andQ=1.Whatistheavailabilityofthesystem?13.A.Heindl,G.Pokam,andA.-R.Adl-Tabatabai.Ananalyticmodelofoptimisticsoftwaretransactionalmemory.InProc.IEEEInt.Symp.onPerformanceAnalysisofSystemsandSoftware(ISPASS),pages153162,April2009.DOI:10.1109/ISPASS.2009.4919647Supposeweremovetheabsorbingstatek+1inFig.1byaddingatransition,withprobability1,fromstatek+1tostate0.(I)Writesteadystatebalanceequationsforthisequivalentmodel.(II)Showthatpi=p0q0q1···qi−1fori=1,2,...,k+1.(III)DeduceEq.(8)from(II).14.R.C.Shah,S.Roy,S.Jain,andW.Brunette.Datamules:Modelingathree-tierarchitectureforsparsesensornetworks.InProc.IEEEWorkshoponSensorNetworkProtocolsandApplications,pages3041,May2003.DOI:10.1109/SNPA.2003.1203354Supposetherearenoaccesspoints.Instead,MULEsarriveatrateλfromoutsidethesensornetworkandmoveaboutinarandomwalktocollectdata.AfteranexponentiallydistributedtimeT,aMULEstopsitscollectionandleavesthenetwork.(I)DrawaMarkovchainforthenumberofMULEsinthenetwork.(II)WhatistheprobabilitythattherearenoMULEsinthenetwork?(III)ExplainwhytheexpectednumberofdataunitscollectedbyaMULEdoesnotdependonET.15.J.LuandJ.Wang.Analyticalperformanceanalysisofnetworkprocessor-basedapplicationdesign.InProc.Int.Conf.ComputerCommunicationsandNetworks,pages7886,October2006.DOI:10.1109/ICCCN.2006.286241Withboundedqueuelength,packetsaredroppedwhentheinputbufferisfull.Thismaycausethepacketsourcetoretransmitthepacket.Thearrivalrateλshouldthereforeincluderetransmittedpackets,soλdependsonthepacketrejectionprobabilitypKinEq.(3-17).(I)HowwouldyoumodeltherelationshipbetweenλandpK?(II)Supposetheinputbufferisfiniteanddroppedpacketsareretransmitted.Suggesthowthenetworkprocessormodelcanbesolved,usingafixedpointapproximationorsomeothermethod. 9116.P.A.Bernstein,A.Fekete,H.Guo,R.Ramakrishnan,andP.Tamma.Relaxed-currencyse-rializabilityformiddle-tiercachingandreplication.InProc.ACMSIGMODInt.Conf.Man-agementofData,pages599610,June2006.DOI:10.1145/1142473.1142540Supposetheequilibriumisdecomposedintodemandλinandsupplyλout(seeChapter8).(I)Howdoesthecurrencyboundaffectsupplyλout?(II)Assumeaflashcrowdismodeledbyanincreaseinnum_terminals(Table1).Howdoesthataffectthedemandlineλin?(III)TheideainRC-Serializabilityistotradecurrencyforperformanceamorerelaxedcurrencyconstraintwillhelpimproveperformance.Intuitively,amorerelaxedcurrencycon-straintcanmakeperformancelesssensitivetoflashcrowds.Usethedecompositionintoλinandλouttoexplainthisintuition.17.J.Kim,D.Park,C.Nicopoulos,N.Vijaykrishnan,andC.R.Das.DesignandanalysisofanNoCarchitecturefromperformance,reliabilityandenergyperspective.InProc.ACMSymp.ArchitectureforNetworkingandCommunicationsSystems(ANCS),pages173182,October2005.DOI:10.1145/1095890.1095915GiveanexampleofAverageValueApproximation(AVA)inthispaper.18.I.Gupta.Onthedesignofdistributedprotocolsfromdifferentialequations.InProc.ACMSymposiumonPrinciplesofDistributedComputing(PODC),pages216225,July2004.DOI:10.1145/1011767.1011799(I)ThestatemachineinFig.1canbeviewedasaMarkovchain.ForthisMarkovchain,whatdox,yandzmeanandwhatarethetransitionrates?(II)WhatistheaveragelengthofeachlineinFig.8?(III)ExplainwhyEq.(7)isequivalenttox˙=0.3xz−0.3xyy˙=0.3yz−0.3xyz˙=−0.3xz−0.3yz+0.3xy+0.3xy(Theadvantagehereisthat0.3canbeinterpretedasaprobabilityforflippingandone-time-sampling.)19.C.Stewart,T.Kelly,andA.Zhang.Exploitingnonstationarityforperformanceprediction.InProc.EurosysConf.,pages3144,March2007.DOI:10.1145/1272998.1273002Byconsideringthenumberofvisitspertypejtransactiontoresourcer,andtheservicetimeatresourcer,justifytheterm 92A.EXERCISES1U2nirNijλi1−Uirrj=1inEq.(4).20.J.C.S.Lui,V.Misra,andD.Rubenstein.Ontherobustnessofsoftstateproto-cols.InProc.IEEEInt.Conf.NetworkProtocols(ICNP),pages5060,October2004.DOI:10.1109/ICNP.2004.1348084(I)SuggesthowyoucanperformananalyticvalidationofEq.(1)forasoft-stateprotocolP.Youmayassumea=b=1.(II)InSec.4,theclientforahard-stateprotocoltriesntimestotelltheserverthatitwantstoterminatetheconnection.ExplainwhyEq.(4)maynotbeagoodmodelfortheserversfailuretoreceivethenotification. 93Bibliography[1]P.A.Bernstein,A.Fekete,H.Guo,R.Ramakrishnan,andP.Tamma.Relaxed-currencyserializabilityformiddle-tiercachingandreplication.InProc.ACMSIGMODInt.Conf.ManagementofData,pages599610,June2006.DOI:10.1145/1142473.114254046,47,61,73,84,99[2]T.Camp,J.Boleng,andV.Davies.Asurveyofmobilitymodelsforadhocnetworkresearch.WirelessCommunications&MobileComputing(WCMC):SpecialIssueonMobileAdHocNet-working:Research,TrendsandApplications,2:483502,2002.DOI:10.1002/wcm.7273,100[3]A.Chesnais,E.Gelenbe,andI.Mitrani.Onthemodelingofparallelaccesstoshareddata.Commun.ACM,26(3):196202,March1983.DOI:10.1145/358061.35807378,99,100[4]P.J.Courtois.Decomposability,instabilities,andsaturationinmultiprogrammingsystems.Commun.ofACM,18(7):371377,1975.DOI:10.1145/360881.36088744,58,100[5]P.J.DenningandJ.P.Buzen.Theoperationalanalysisofqueueingnetworkmodels.ACMComput.Surv.,10(3):225261,1978.DOI:10.1145/356733.35673537,100[6]L.DowdyandC.Lowery.P.S.toOperatingSystems.Prentice-Hall,Inc.,UpperSaddleRiver,NJ,USA,1993.33,100[7]S.Floyd,M.Handley,J.Padhye,andJ.Widmer.TCPFriendlyRateControl(TFRC):ProtocolSpecification.RFC5348,September2008.http://www.ietf.org/rfc/rfc5348.txt83[8]E.Gabber,J.Fellin,M.Flaster,F.Gu,B.Hillyer,W.T.Ng,B.Özden,andE.A.M.Shriver.Starfish:highly-availableblockstorage.InProc.USENIXAnnualTech.Conf.,pages151163,June2003.http://www.usenix.org/event/usenix03/tech/freenix03/gabber.html18,19,27,46,54,72,101[9]I.Gupta.Onthedesignofdistributedprotocolsfromdifferentialequations.InProc.ACMSymposiumonPrinciplesofDistributedComputing(PODC),pages216225,July2004.DOI:10.1145/1011767.101179962,85,100[10]P.GuptaandP.R.Kumar.Thecapacityofwirelessnetworks.IEEETrans.InformationTheory,46(2):388404,2000.DOI:10.1109/18.8257997,71,102 94A.EXERCISES[11]A.Heindl,G.Pokam,andA.-R.Adl-Tabatabai.Ananalyticmodelofoptimisticsoftwaretransactionalmemory.InProc.IEEEInt.Symp.onPerformanceAnalysisofSystemsandSoftware(ISPASS),pages153162,April2009.DOI:10.1109/ISPASS.2009.491964727,47,54,62,72,84,102[12]J.R.Jackson.Jobshop-likequeueingsystems.ManagementScience,10(1):131142,1963.DOI:10.1287/mnsc.10.1.13125,100[13]J.Kang,J.F.Naughton,andS.Viglas.Evaluatingwindowjoinsoverunboundedstreams.InProc.Int.Conf.onDataEngineering(ICDE),pages341352,March2003.DOI:10.1109/ICDE.2003.12608048,10,18,53,69,82,101[14]G.Kesidis.AnIntroductiontoCommunicationNetworkAnalysis.JohnWiley,Hoboken,NJ,2007.DOI:10.1002/978047016868424,100[15]J.Kim,D.Park,C.Nicopoulos,N.Vijaykrishnan,andC.R.Das.DesignandanalysisofanNoCarchitecturefromperformance,reliabilityandenergyperspective.InProc.ACMSymp.ArchitectureforNetworkingandCommunicationsSystems(ANCS),pages173182,October2005.DOI:10.1145/1095890.109591555,73,85,100[16]L.Kleinrock.QueueingSystems,Vol.1.JohnWiley,NewYork,NY,1975.21,100[17]S.S.Lavenberg.Closedmultichainproductformqueueingnetworkswithlargepopulationsizes.InR.L.DisneyandT.J.Ott,editors,AppliedProbability-ComputerScience:TheInterface,Vol.1,pages219249.Birkhauser,1982.44,100[18]S.S.LavenbergandM.Reiser.Stationarystateprobabilitiesatarrivalinstantsforclosedqueuingnetworkswithmultipletypesofcustomers.J.AppliedProbability,17:10481061,1980.DOI:10.2307/321321436,99[19]J.LuandJ.Wang.Analyticalperformanceanalysisofnetworkprocessor-basedapplicationdesign.InProc.Int.Conf.ComputerCommunicationsandNetworks,pages7886,October2006.DOI:10.1109/ICCCN.2006.28624138,46,73,100[20]J.C.S.Lui,V.Misra,andD.Rubenstein.Ontherobustnessofsoftstateproto-cols.InProc.IEEEInt.Conf.NetworkProtocols(ICNP),pages5060,October2004.DOI:10.1109/ICNP.2004.134808486,101[21]R.J.T.MorrisandW.S.Wong.Performanceanalysisoflockingandoptimisticconcurrencycontrolalgorithms.PerformanceEvaluation,5(2):105118,May1985.DOI:10.1016/0166-5316(85)90043-480,99[22]R.MuntzandJ.Wong.Asymptoticpropertiesofclosedqueueingnetworkmodels.In8thAnnualPrincetonConf.onInformationSciencesandSystems,March1974.43,99 95[23]G.Nogueira,B.Baynat,andP.Eisenmann.AnanalyticalmodelforthedimensioningofaGPRS/EDGEnetworkwithacapacityconstraintonagroupofcells.InProc.MOBICOM,pages215227,August2005.DOI:10.1145/1080829.10808527,26,33,34,53,70,78,82,100[24]J.Padhye,V.Firoiu,D.Towsley,andJ.Kurose.ModelingTCPthroughput:asimplemodelanditsempiricalvalidation.InProc.SIGCOMM,pages303314,September1998.DOI:10.1145/285243.2852917,53,70,78,83,101[25]D.QiuandR.Srikant.ModelingandperformanceanalysisofBitTorrent-likepeer-to-peernetworks.InProc.SIGCOMM,pages367378,2004.DOI:10.1145/1015467.10155087,53,67,70,99[26]B.Schroeder,A.Wierman,andM.Harchol-Balter.Openversusclosed:acautionarytale.InProc.Symp.NetworkedSystemsDesignandImplementation(NSDI),2006.http://www.usenix.org/events/nsdi06/tech/schroeder.html8,45,66,100[27]P.J.Schweitzer.Approximateanalysisofmulti-classclosednetworksofqueues.InProc.oftheInt.Conf.StochasticControlandOptimization,pages2529,1979.38,101[28]K.C.SevcikandI.Mitrani.Thedistributionofqueuingnetworkstatesatinputandoutputinstants.J.ACM,28(2):358371,1981.DOI:10.1145/322248.32225736,99[29]R.C.Shah,S.Roy,S.Jain,andW.Brunette.Datamules:Modelingathree-tierarchitectureforsparsesensornetworks.InProc.IEEEWorkshoponSensorNetworkProtocolsandApplications,pages3041,May2003.DOI:10.1109/SNPA.2003.120335433,55,72,84,101[30]C.Stewart,T.Kelly,andA.Zhang.Exploitingnonstationarityforperformanceprediction.InProc.EurosysConf.,pages3144,March2007.DOI:10.1145/1272998.127300274,100[31]Y.C.TayandK.C.Chua.AcapacityanalysisfortheIEEE802.11MACprotocol.WirelessNetworks,7(2):159171,2001.DOI:10.1023/A:10166376228968,83,99[32]Y.C.Tay,N.Goodman,andR.Suri.Lockingperformanceincentralizeddatabases.ACMTrans.DatabaseSyst.,10(4):415462,1985.DOI:10.1145/4879.488080,99[33]Y.C.Tay,R.Suri,andN.Goodman.Ameanvalueperformancemodelforlockingindatabases:Theno-waitingcase.J.ACM,32(3):618651,1985.DOI:10.1145/3828.383128,72,84,99[34]Y.C.Tay,D.N.Tran,E.Y.Liu,W.T.Ooi,andR.Morris.Equilibriumanalysisthroughseparationofuserandnetworkbehavior.ComputerNetworks,52(18):34053420,2008.DOI:10.1016/j.comnet.2008.09.00810,46,99[35]Y.-C.Tu,J.Sun,andS.Prabhakar.Performanceanalysisofahybridmediastreamingsystem.InProc.ACM/SPIEConf.onMultimediaComputingandNetworking(MMCN),pages6982,January2004.DOI:10.1117/12.53880611,27,54,61,71,84,100 96A.EXERCISES[36]B.Urgaonkar,G.Pacifici,P.Shenoy,M.Spreitzer,andA.Tantawi.Analyticmodelingofmul-titierInternetapplications.ACMTrans.Web,1(1):2,2007.DOI:10.1145/1232722.12327242,5,38,45,61,66,78,82,100[37]Q.Zhu,Z.Chen,L.Tan,Y.Zhou,K.Keeton,andJ.Wilkes.Hibernator:helpingdiskarrayssleepthroughthewinter.Proc.ACMSymp.OperatingSystemsPrinciples(SOSP),39(5):177190,2005.DOI:10.1145/1095810.10958287,18,26,66,68,69,78,82,101[38]C.C.Zou,W.Gong,andD.Towsley.Coderedwormpropagationmodelingandanaly-sis.InProc.ACMConf.ComputerandCommunicationsSecurity(CCS),pages138147,2002.DOI:10.1145/586110.5861307,61,70,78,83,99 97AuthorsBiographyY.C.TAYY.C.TayreceivedhisBScfromtheUniversityofSingaporeandPhDfromHarvardUniversity.HeisaprofessorintheDepartmentofMathematicsandDepartmentofComputerScienceattheNationalUniversityofSingapore.HehasspentsabbaticalsatPrincetonUniversity,MIT,UCLA,UniversityofCambridge,andIntelResearch,andwasaconsultantfortheMicrosoftWindowsNTPerformanceGroup.HehasservedonprogramcommitteesforSIGMETRICS,SIGMOD,VLDB,andICDE.Hismainresearchinterestisperformancemodeling(databasetransactions,wirelessprotocols,trafficequilibrium,cachemisses).Otherinterestsincludedatabasesystemsanddistributedprotocols.Hehaswonseveralteachingawards. 99Index802.11[31],8,83,89closed-formexpressions,78,82,8486CodeRed[38],7,61,70,78,83,88aggregationcoefficientofvariation,2parameters,67,72,82convolution,33queues,32,43correlationcoefficient,49states,32,33,62,86subnetwork,43datapresentationanalyticsimulation,77,82,84,86dataplot,66,73,86arrivalrate,5,10,13,18,22,44,55,75,87,88numericalaccuracy,19,66ArrivalTheorem[18;28],36databaselocksartifact,34,73,78,86dataandresourcecontention[32],47,65,assumptionsandapproximations,53,65,66,73,7981,8571,77,78memorylessproperty[3],78robustresults,78no-waitingpolicy[33],28,72,8082,84simplistic,78recursion[21],80DatabaseSerializability[1],46,47,61,73,84,AverageValueApproximation(AVA),49,915355,80,83,88,91databasetransactionlocking,6365birth-deathprocess,23,24,29,32D/D/1,18BitTorrent[25],7,53,67,70,89decompositionblockingprobability(lostjob),27,55,70,82,equilibrium,57,59,61,9188hierarchical,43,46,47ErlangsBformula,24,27network,43bottleneck,11,26,4142,4547,61,74,75queue,39,46[22],42decoupling,80dumbbell,42degradation,59,65,67,68,79,81,83software,46delaycenter,15,36,38,39,46branchingprobability,25,29,47demandandsupply,57,58,61,91buffercapacity,13,15websurfing[34],10,46deterministicchange,7closedmodel,8,11,28,3439,4245,66discretization 100INDEXspace,34,73Kendallnotation,14time,27,34,5355,61,62,7274Kermack-McKendrickepidemicmodel,60,DistributedProtocols[9],62,85,9161,70,83dynamicsystems,7Kesidis[14],24Kleinrock[16],21eigenvalues,50,51,54,62epidemicmodels,5961,70,83Lavenberg[17],44equilibriumLittlesLaw,10,11,13,18,19,26,28,36,37,decomposition[4],5759,61,9141,42,45,54,55,57,61stable,51,52,58,59,61,62,70load-dependentqueue,43,44,46,47unstable,51,52,59localbalanceequations,23,30Erlang-kdistribution,1machinerepairmanmodel,27,54exponentialdistribution,15,11,15,19,21,Markovchain,78,80,84,86,90,9123,25,36,54,66,87,90continuoustime,22,25,2834,43,44,46,extremepolicy,8154,55,62finitebuffer,18,24,39correctnessofalgorithm[6],33first-come-first-served(FCFS),15,22,23,36discretetime,27,34fixedpointapproximation,38,53,54,90M/D/1,17,18,36flowdiagram,28,62MeanValueAnalysis(MVA),3639,43,46,83flowequivalence,43,44,46,57,74MediaStreaming[35],11,27,54,61,71,84,89Courtois[4],44memorylessproperty,3,15,21,22,27,29,31,35,36,55,70,72,73fluidapproximation,50,54,57,59,62,70databaselocks[3],78ForcedFlowLaw[5],37M/G/1,15,16,42,87geometricdistribution,3,4,24,25M/G/K/K,24globalbalanceequations,23,30M/M/1,15,17,35,55,75,88GPRS[23],26,33,34,53,70,78,82,87M/M/∞,15,86M/M/K/K,24hierarchicaldecomposition,43,46,47mobilitymodel[2],73hyperexponentialdistribution,1,2hypoexponentialdistribution,1,2NetworkProcessor[19],38,46,73,90nines,19infiniteserver,15,36NoC[15],55,73,85,91inter-arrivaltime,5,10,13,23,27,55,87non-monotonicbehavior,82,84interactivemodel,9,38,42,44,45,57,61NonstationaryMix[30],74,91InternetServices[36],2,5,38,45,61,78,88intuition,8082OpenClosed[26],8,45,66,88openmodel,8,11,19,21,25,30,39,42,Jacksonnetwork[12],25,26,30,464446,73 INDEX101parameters,8closed,2932,36,42calibration,66,69,70,72,74,83nonseparable,41,44,84spacereduction,67,83open,25,42,46aggregateparameter,67,72,82,83product-form,25,36magicvalues,67,85separable,25,36,39,44,61normalization,67,71,73,89uninterestingregions,6768,70,79,83randomfield,7valuebound,67Renyi,4voodooconstants,67residuallife,21,26,36PASTA,35,37responsetime,9,28,42,45,47,61,70,8183performancemetric,8,79roundrobin,15uninteresting,79SchweitzersApproximation[27],38Poissondistribution,4SensorNet[29],33,55,72,84,90AdditiveProperty,5servicedemand,3739,41,75,88Poissonarrivals,5,14,15,18,25,26,35,36servicerate,13,87,88SplitProperty,5,18shortest-job-first,45Pollaczek-Khinchinformula,15,19,24,26sleeptime,9populationsize,8SleepingDisks[37],7,18,26,66,68,69,78,82,prediction,68,71,75,82,8387preemptivepriority,30SoftState[20],86,92processorsharing,15,36statespace,22,29,62,64,86protocoldesignstatetransitiondiagram,22distributedsystem,62states,7,22,24,27,28,30,62,86networking,83absorbing,28,90aggregation,32,33,62,86qualitativeunderstanding,59,68,71staticstate,7queue,1318steadystate,7decomposition,39stochasticprocess,7load-dependent,43,44,46,47StorageAvailability[8],19,27,46,54,72,90queueingdisciplineStreamJoins[13],8,18,53,69,82,87first-come-first-served(FCFS),15,16,system,722,23,36systemtimeT,10,17preemptivepriority,30processorsharing,15,36TCP[24],7,53,70,78,83,88round-robin,15thinktime,9,11,44,46,61,67,85shortest-job-first,45throughput,8,28,32,37,39,42,47,53,61,67,queueingnetwork,39,41,46,55,73,78,80,72,73,79,818482,84,85timeseries,7 102INDEXTransactionalMemory[11],27,47,54,62,72,workload,6684,90transientanalysis,7,54,5761waitinglengthL,17waitingspace,13utilization,8,9,1417,32,41,45,55,67,74,waitingtimeW,14,17,3575WirelessCapacity[10],7,71,89workconservingqueue,15validation,65,71,73,78workloadanalyticvalidation,68,69,72,8486,89,microbenchmark,39,66,69,7292realsystem,66,7073numericalvalidation,66,6971,73trace,66,69simulation,66,70,72worst-caseperformance,82