Heavy traffic analysis of a storage model with lon

BaltzerJournalsAugust21,1996HeavyTracAnalysisofaStorageModelwithLongRangeDependentOn/OSources.F.Brichet,J.Roberts,A.Simonian,D.Veitch11FranceTelecom-CNET,38-40rueduGeneralLeclerc,92131Issy-les-Moulineaux,FranceE-mail:[e-mail]systemwithinnitestoragecapacityandconstantoutputrateoeredasuperpositionofNidenticalOn/Osources,wheretheratioofinputtooutputrateissmall.TheOnand/orOperiodshaveheavytaileddistributionswithinnitevariance,givingrisetoLongRangeDependenceinthearrivalprocess.Inthelimitofalargenumberofsourcesandhighload,itisshownthatthetailofthestationaryqueuecontentdistributionisWeibullian,implyingmuchlargerqueuecontentsthanintheclassicalcaseofexponentialtails.NotingthatsimilarresultswererecentlyfoundbyI.NorrosforastoragesysteminputbyaFractionalBrownianMotion,wethenshowhowthetwomodelsarerelated,thusprovidingafurtherphysicalmotivationfortheFractionalBrownianMotionmodel.Subjectclassication:AMS(MOS)68M20,60K25,90B22,60F05Keywords::On/OFluidSources,HeavyTrac,LongRangeDependence,FractionalBrownianMotion,TelecommunicationsNetworks.1{IntroductionTheclassicalliteratureinqueueingtheory,whetheritbeappliedtopacketorcir-cuitswitchedtelecommunicationsnetworks,isconcernedessentiallywithsystemswithexponentiallydecayingcovariance(shorttermdependence)intheirarrivalprocesses.Thisgivesrisetodistributionsofqueuecontentorvirtualwaitingtimewithasymptoticallyexponentialtails.Traditionalmodelsgenerallypossessasmallnumberofcharacteristictimescalesaroundwhichtherandombehaviourisconcentrated.Whenaveragesaretakenoverscaleslargerthanthese,inparticularoverinnitetimeintervals,therandomnessissmoothedandamiableexponentialqueueingistheresult.Suchhighlysmoothedresultsareofdubiousvalueinthecontextofhighspeedtelecommunicationsnetworks,suchastheATMbasedB-ISDNwheretheperformanceissuesofinterest,packetlossanddelay,areexpectedtodependonlocalizedperiodsofhighcongestion.Recentmeasurements(Lelandetal.[11]andreferencestherein,PaxsonandFloyd[16])haveshownclearlythatF.Brichetetal./HeavytracanalysiswithLRDsources2highspeedtraccancontradictthesebasicassumptions,exhibitingLongRangeDependence(LRD)andburstinessoveranextremelywiderangeoftimescales.Queueingexperimentsusingrealtractraces(Erramillietal.[5])demonstratethatthislongrangedependencedoesindeedimpactsignicantlyonqueueingdelays.WedeneLRDinthecontextofcovariant-stationaryprocessesftg,wheretrepresentsthearrivalrateattimet.LRDcorrespondstoadivergentcorre-lationintegralR+10()d,whereisthecorrelationfunctionofftg.Thisisessentiallyequivalent(Cox[3])toanunusuallylargevarianceofthecorrespondingworkprocessWt=Rt0sdsnamely,Var(Wt)t2HforlargetandsomeH1=2.ItisnotobviouswhattheeectoftracwithLRDmaybeonqueueingperformance.Intuitioninthesubjectishighlytunedtoshortterm,Markovianthinkingwhich,aswenowillustrate,canbeverymisleading.Considerarenewalprocesswhoseinterarrival-timedistributionhasmean1=butinnitevariance.Itisnotdiculttoshow(Veitch[20])thatsuchaprocessislongrangedependent.ThestandardGI=M=1queueanalysisapplieshowever,wherenewarrivalsndasystemcontaininganexponentiallydistributedamountofwork.ThusLRDalonedoesnotsucetogenerateabnormalqueueingbehaviour(thereishoweveradif-ferenceforhighload,seeAppendix1).Nowletthemeanbeinnitealso,implyinganarrivalrateofzero(Veitch[20]).Despitethefactthatsuchanarrivalprocesscannotbestationaryintheusualsense,GI=M=1theoryremainsvalid,yieldingexponentialqueuesatarrivalinstantseveninthiscase.Thisillustratesthateventhemostfundamentalofconceptssuchastheprimordialityofthemeanarrivalrateparameter,arenotnecessarilybeyondrevision.Finally,takeanexampleattheoppositeendofthespectrum,theM=G=1queuewithservicetimesofinnitevariancegeneratedbyaheavytailedservicedistribution.ThisqueueingsystemcanbeusedtomodelPoissonburstarrivalswherethe\heavyservicetimesrep-resentlargeburstvolumes.Againusingstandardtheory(seeAppendix2),itisnotdiculttoshowthatthewaitingtimedistributioninthiscasehasapowerlawtailwithinnitemean!Thusthenon-classicalchoiceofservicetimeswithoutsecondmomentcausesdramaticallydierentqueueingbehaviour.Inthispaper,weanalyzeauidorstoragequeueingsystemwithLRDinput.Fluidsystemshavebeenusedbefore(e.g.Bensaouetal.[2],Guibert[7])tomodelburstytracfedintoATMmultiplexerqueues,whenconsideringtimescaleswherethegranularityoftheATMcellsnolongerdominates.TheinputsourcesareassumedtobeofOn/Otype,thatis,withmutuallyindependent,alternatingsilenceperiods(noworkarriving)andactivityperiods(workarrivingataconstantrate).WeconsiderasuperpositionofNidentical,independentOn/OsourcesowingintoaninnitereservoirwithxedoutputrateC.TheobjectofstudyisthecomplementarydistributionfunctionQofthestationaryqueuecontent.F.Brichetetal./HeavytracanalysiswithLRDsources3Ifisthemeanarrivalrateforasinglesource,werequireCNforstability.ForNsucientlylarge,Cthenexceedsthepeakrateofanindividualsource.IfthisrateisproportionaltoC=N,sothatitdecreaseswithN,thenweareintherealmof\smallsources.TheM=G=1exampleaboverepresentsthelimitingformofthealternativeassumption,whereinsta