The Heavy-Traffic Bottleneck Phenomenon in Open Qu

THEHEAVY-TRAFFICBOTTLENECKPHENOMENONINOPENQUEUEINGNETWORKSbyS.SureshandW.WhittAT&TBellLaboratoriesMurrayHill,NewJersey07974ABSTRACTThisnotedescribesasimulationexperimentinvolvingnineexponentialqueuesinserieswithanon-Poissonarrivalprocess,whichdemonstratesthattheheavy-trafficbottleneckphenomenoncanoccurinpractice(atreasonabletrafficintensities)aswellasintheory(inthelimit).Theresultsreveallimitationsincustomarytwo-momentapproximationsforopenqueueingnetworks.KeyWords:queues,openqueueingnetworks,queuesinseries,limittheorems,heavytraffic,two-momentapproximationsFebruary7,1989Revision:January4,19901.IntroductionThepurposeofthisnoteistodescribeasimulationexperimentthatprovidesinsightintothesteady-stateperformanceofnon-product-formopenqueueingnetworks.Inparticular,weshowthattheheavy-trafficbottleneckphenomenoninanopenqueueingnetworkcanoccurapproximatelyatreasonabletrafficintensities.Bytheheavy-trafficbottleneckphenomenon,wemeanthestate-spacecollapsethatoccursifthetrafficintensityofonequeueapproaches1,whilethetrafficintensitiesatallotherqueuesremainbelow1-εforsomeε0.Heavy-trafficlimittheoremsbyIglehartandWhitt[5],Reiman[7,8]andChenandMandelbaum[4]indicatethatifthetrafficintensityatonequeueissufficientlyhigh,whilethetrafficintensitiesofalltheotherqueuesaresubstantiallylower,thenthestandardsteady-staterandomvariablessuchasthewaitingtimeateachqueueandthenumberofcustomersinthenetworkaredistributednearlythesame(relativelytothelevelofcongestionatthebottleneckqueue)asifalltheservicetimesinthenon-bottleneckqueuesweresetequalto0.Sincethenumberofcustomersinthebottleneckqueueshouldgotoinfinityasitstrafficintensityapproaches1,whilethenumberofcustomersatotherqueuesshouldstayfinite,itisintuitivelyobviousthattheproportionofcustomersinthenetworkthatareatthebottleneckqueueshouldapproach1inthislimit.However,itislessobviousthatthenormalizedsteady-statewaitingtimeatthebottleneckqueueshouldbenearlythesameasiftheservicetimesatalltheotherqueuesweresetequalto0,i.e.,asiftheotherqueuesactedasinstantaneousswitches.Thisisthefeaturethatwewishtoidentifyintypicalnetworks.Toexhibittheheavy-trafficbottleneckphenomenoninthisform,wechoosearelativelysimplenetwork.(Itwillbeevidentthatthephenomenonwillholdmoregenerally.)Inparticular,weconsiderseveralsingle-serverqueueinseries.Customersarriveatthefirstqueueaccordingto-2-arenewalprocesswithinterarrivaltimeshavingageneraldistributionwithmean1andsquaredcoefficientofvariation(variancedividedbythesquareofthemean)ca12.Eachqueuehasunlimitedwaitingspace,thefirst-infirst-outdiscipline,andIID(independentandidenticallydistributed)servicetimesthatareindependentofthearrivalprocessandtheotherservicetimes.Theservice-timedistributionatqueueihasageneraldistributionwithmeanρi,whereρi1,andsquaredcoefficientofvariationcsi2.Inthiscontext,theheavy-trafficbottleneckphenomenonoccursifthetrafficintensityofonequeueisallowedtoapproach1;then,by[5],thewaiting-timedistributionatthisbottleneckqueueisasymptoticallythesameasiftheimmediatearrivalprocess(i.e.,thedepartureprocessfromthepreviousqueue)werereplacedbytheexternalarrivalprocesstothefirstqueuewithsquaredcoefficientofvariationca12.Ourpurposeistoshowthatthiscanbeapproximatelytrueatreasonabletrafficintensities.Unfortunately,duetothenon-exponentialdistributions,thismodelisverydifficulttoanalyzeexactly.Ausefulpracticalapproachtothismodelandmoregeneralopenqueueingnetworksistheparametric-decompositionapproximationmethod,asinWhitt[14],SegalandWhitt[10],BitranandTirupati[3]andreferencescitedthere.Forourmodelofqueuesinseries,thestandardimplementationofthisapproachistoapproximatethearrivalprocesstoqueueibyarenewalprocesswitharrivalrate1andsquaredcoefficientofvariationcai2,wherecai2isdefinedrecursivelybyca,i+12=ρi2csi2+(1-ρi2)cai2,i≥1,(1)see(38)of[14]and(23)of[15].Wethencanapproximatethemeansteady-statewaitingtime(beforebeginningservice)atqueueibyE[Wi]~~2(1-ρi)ρi2(cai2+csi2)___________(2)orsomerefinementsuchasprovidedbyKraemerandLangenbach-Belz[6];see(2)and(44)of-3-[14].Asindicatedin[15],approximation(1)canbeviewedastheresultofthepurestationary-intervalmethod,i.e.,anattempttomatchcai2fori1totheactualsquaredcoefficientofvariationofastationaryintervalintheitharrivalprocess(butignoringthedependenceamongsuccessiveinterarrivaltimes).Itissignificantthat(2)doesnotreflecttheheavy-trafficphenomenon,becausetheapproximatingarrivalvariabilityparametercai2atqueueiistotallyindependentofρi.Itmayseemappropriatethatcai2notdependonρi,becausethearrivalprocesstoqueueiisexogenoustoqueuei.However,experiencehasshownthatitmaybedesirabletoletcai2dependonρi,becausethewaythevariabilityinthearrivalprocessaffectsthequeuedependsonthetrafficintensityinthequeue.Analternateapproachdescribedin[13,15]istheasymptoticmethod,whichattemptstochooseavariabilityparametercai2tomatchthecentrallimittheorembehavioroftheitharrivalprocess.Forqueuesinseries,thisleadstotheapproximationcai2=ca12foralli≥1.(3)Intuitively,(3)maynotlooktoopromising,butitisjustwhatispredictedbytheheavy-traffictheorywhenρi→1.(Thiswastheoriginalmotivationfortheasymptoticmethod.)Wethusregardactuals