A functional central limit theorem for the MGIinfi

arXiv:math/0608258v2[math.PR]5Jan2008AFUNCTIONALCENTRALLIMITTHEOREMFORTHEM/GI/∞QUEUEL.DECREUSEFONDANDP.MOYALAbstrat.Inthispaper,wepresentafuntionaluidlimittheoremandafuntionalentrallimittheoremforaqueuewithaninnityofserversM/GI/∞.Thesystemisrepresentedbyapoint-measurevaluedproesskeep-ingtrakoftheremainingproessingtimesoftheustomersinservie.Theonvergeneinlawofasequeneofsuhproessesafterresalingisprovedbyompatness-uniquenessmethods,andthedeterministiuidlimitistheso-lutionofanintegratedequationinthespaeS′oftempereddistributions.Wethenestablishtheorrespondingentrallimittheorem,i.e.theapproximationofthenormalizederrorproessbyaS′-valueddiusion.1.IntrodutionThequeueswithaninnitereservoirofserversarelassialmodelsinqueueingtheory.Insuhases,alltheustomersareimmediatelytakenareofuponarrival,andspendinthesystemasojourntimeequaltotheirservietime.Beyonditsinteresttorepresentteleommuniationnetworksoromputersarhiteturesinwhihthenumberofresouresisaprioriinnite,thismodel(ommonlyreferredtoaspuredelayqueue)hasbeenoftenusedforomparisontootheroneswhosedynamisisformallymuhmoreompliated,butloseinsomesense.Thentheperformanesofthepuredelaysystemmaygivegoodestimators,orbounds,ofthatoftheothersystem.Thestudiesproposedintheliteraturemainlyfousedonlassialdesriptors,suhasthelengthofthequeue:amongothers,itsstationaryregimeundermar-kovianassumptions([Erl17℄),thetransientbehaviorandlawofhittingtimesofgivenlevels([GS95℄),theuidlimitanddiusionapproximationsofnormalizedsequenes([Bor67,Igl73℄)arenowlassialresults.Letusalsomentionthereentstudyontheexistene/uniquenessofastationaryregimefortheproessountingthelargestremainingproessingtimeofaustomerinthesystem([Moy07b℄).Butwhenoneaimtohavemoreaurateinformationonthestateofthesys-tem,suhasthetotalamountofworkaturrenttime(workload)orthenumberofustomershavingremainingproessingtimeinagivenrange,nosuhsimplestatedesriptoranbeused.Inordertoaddresssuhquestions,onehastoknowaturrenttimetheexhaustiveolletionofresidualproessingtimesofalltheus-tomerspresentinthesystem.Consequently,werepresentthequeuebyapointmeasure-valuedproess(μt)t≥0,puttingDirameasuresatallresidualproessingtimes.Theprietopaytohavesuhaglobalinformationisthereforetoworkonaverybigstatespae,infat,ofinnitedimension.Inthepastfteenyears,an2000MathematisSubjetClassiation.Primary:60F17,Seondary:60K25and60B12.Keywordsandphrases.Measure-valuedMarkovProess,FluidLimit,CentralLimitTheorem,PureDelaySystem,QueueingTheory.12L.DECREUSEFONDANDP.MOYALinreasinginteresthasbeendediatedtothestudyofsuhmeasure-valuedMarkovproesses(fordenitionandmainproperties,seethereferenesurveyofDawson([Daw93℄)onthissubjet).Suhaframeworkispartiularlyadequatetodesribepartilesorbranhingsystems(see[RC86,MR93,Daw93℄),orqueueingsystemswhosedynamisistooomplextobearriedonwithsimplenite-dimensionalpro-esses:theproessorsharingqueue(see[GPW02,Rob03℄),queueswithdeadlines(see[DLS01℄foraqueueundertheearliestdeadlinerstserviedisiplinewithoutreneging,[DM07,DM05℄forthesamesystemwithrenegingand[GRZB06℄foraproessorsharingqueuewithreneging),ortheShortestRemainingProessingtimequeue([BB02℄,[Moy07a℄).Inthispaper,weaimtoidentifythemeanbehaviorofthemeasurevaluedpro-ess(μt)t≥0desribingthepuredelaysystem,introduedabove.Inthatpurpose,weusethereenttoolsofnormalizationofproesses,toidentifytheuidlimitoftheproess,orformallawoflargenumbers.Thisuidlimitistheontinuousanddeterministilimitinlawofanormalizedsequeneoftheseproesses.Wehara-terizeaswelltheaurayofthisapproximationbyprovidingtheorrespondingfuntionalentrallimittheorem,i.e.theonvergeneinlawofthenormalizedpro-essofdierenebetweenthenormalizedproessanditsuidlimit,toadiusion.Formally,itisratherstraightforwardinourasetoidentifytheinnitesimalgeneratoroftheFellerproess(μt)t≥0.Thenaturalbutunusualtermisthatduetotheontinuousdereasingoftheresidualproessingtimesatunitrateastimegoeson.Thisterminvolvesaspatialderivativeofthemeasureμt,anotionwhihanonlyberigorouslydenedwithintheframeworkofdistributions.Beauseofthisterm,theuidlimitequation(see(4))istheintegratedversionofapartialdierentialequationratherthananordinarydierentialequationasitistheruleinthepreviouslystudiedqueueingsystems.Thus,thelassialGronwall’sLemmaisofnousehere.Fortunately,weanirumventthisdiultybysolvingtheinvolvedintegratedequation,knownastransportequation,whihissimpleenoughtohavealosedformsolutionseeTheorem1.Then,weanproeedusingmorelassialtehniquestoshowtheonvergeneinlawofthenormalizedsequenetotheuidlimit(theauthorshavebeeninformedduringthereviewproessofthispaper,thatasimilarresulthasbeenannounedindependentlyin[GRZB06℄).Asaseondstep,weshowtheweakonvergeneofthenormalizedsequeneofdeviationtothelimit,toadiusionproess.Thispaperisorganizedasfollows.Aftersomepreliminariesinsetion2,wede-neproperlytheproleproess(μt)t≥0insetion3,showinpartiularthat(μt)t≥0isFeller-Dynkin,andgivetheorrespondingmartingaleproperty.InSetion4,wegivetheuidlimitof(μt)t≥0.Wededuefromthisresultuidapproxima-tionsofsomeperformaneproessesinsetion5.Weprovethefuntionalentrallimittheoremfor(μt)t≥0insetion6,andgivethedi