3DelayModelsinDataNetworks3.1INTRODUCTIONOneofthemostimportantperfonnancemeasuresofadatanetworkistheaveragedelayrequiredtodeliverapacketfromorigintodestination.Furthennore,delayconsiderationsstronglyinfluencethechoiceandperfonnanceofnetworkalgorithms,suchasroutingandflowcontrol.Forthesereasons,itisimportanttounderstandthenatureandmechanismofdelay,andthemannerinwhichitdependsonthecharacteristicsofthenetwork.Queueingtheoryistheprimarymethodologicalframeworkforanalyzingnetworkdelay.Itsuseoftenrequiressimplifyingassumptionssince,unfortunately,morereal-isticassumptionsmakemeaningfulanalysisextremelydifficult.Forthisreason,itissometimesimpossibletoobtainaccuratequantitativedelaypredictionsonthebasisofqueueingmodels.Nevertheless,thesemodelsoftenprovideabasisforadequatedelayapproximations,aswellasvaluablequalitativeresultsandworthwhileinsights.Inwhatfollows,wewillmostlyfocusonpacketdelaywithinthecommunicationsubnet(i.e.,thenetworklayer).Thisdelayisthesumofdelaysoneachsubnetlinktraversedbythepacket.Eachlinkdelayintumconsistsoffourcomponents.149150DelayModelsinDataNetworksChap.31.TheprocessinRdelaybetweenthetimethepacketiscorrectlyreceivedattheheadnodeofthelinkandthetimethepacketisassignedtoanoutgoinglinkqueuefortransmission.(Insomesystems,wemustaddtothisdelaysomeadditionalprocessingtimeattheDLCandphysicallayers.)2.ThequeueinRdelaybetweenthetimethepacketisassignedtoaqueuefortrans-missionandthetimeitstartsbeingtransmitted.Duringthistime,thepacketwaitswhileotherpacketsinthetransmissionqueuearetransmitted.3.Thetransmissiondelaybetweenthetimesthatthefirstandlastbitsofthepacketaretransmitted.4.Thepropagationdelaybetweenthetimethelastbitistransmittedattheheadnodeofthelinkandthetimethelastbitisreceivedatthetailnode.Thisisproportionaltothephysicaldistancebetweentransmitterandreceiver;itcanberelativelysubstantial,particularlyforasatellitelinkoraveryhighspeedlink.Thisaccountingneglectsthepossibilitythatapacketmayrequireretransmissiononalinkduetotransmissionerrorsorvariousothercauses.Formostlinksinpractice,otherthanmultiaccesslinkstobeconsideredinChapter4,retransmissionsarerareandwillbeneglected.Thepropagationdelaydependsonthephysicalcharacteristicsofthelinkandisindependentofthetrafficcarriedbythelink.Theprocessingdelayisalsoindependentoftheamountoftraffichandledbythecorrespondingnodeifcomputationpowerisnotalimitingresource.Thiswillbeassumedinourdiscussion.Otherwise,aseparateprocessingqueuemustbeintroducedpriortothetransmissionqueues.Mostofoursubsequentanalysisfocusesonthequeueingandtransmissiondelays.Wefirstconsiderasingletransmissionlineandanalyzesomeclassicalqueueingmodels.Wethentakeupthenetworkcaseanddiscussthetypeofapproximationsinvolvedinderivinganalyticaldelaymodels.Whileourprimaryemphasisisonpacket-switchednetworkmodels,someofthemodelsdevelopedareusefulinacircuit-switchednetworkcontext.Indeed,queueingtheorywasdevelopedextensivelyinresponsetotheneedforperfonnancemodelsintelephony.3.1.1MultiplexingofTrafficonaCommunicationLinkThecommunicationlinkconsideredisviewedasabitpipeoverwhichagivennumberofbitspersecondcanbetransmitted.Thisnumberiscalledthetransmissioncapacityofthelink.Itdependsonboththephysicalchannelandtheinterface(e.g.,modems),andissimplytherateatwhichtheinterfaceacceptsbits.Thelinkcapacitymayserveseveraltrafficstreams(e.g.,virtualcircuitsorgroupsofvirtualcircuits)multiplexedonthelink.Themannerofallocationofcapacityamongthesetrafficstreamshasaprofoundeffectonpacketdelay.Inthemostcommonscheme,statisticalmultiplexinR,thepacketsofalltrafficstreamsaremergedintoasinglequeueandtransmittedonafirst-comefirst-servebasis.Avariationofthisscheme,whichhasroughlythesameaveragedelayperpacket,maintainsSec.3.1Introduction151aseparatequeueforeachtrafficstreamandservesthequeuesinsequenceonepacketatatime.However,ifthequeueofatrafficstreamisempty,thenexttrafficstreamisservedandnocommunicationresourceiswasted.SincetheentiretransmissioncapacityC(bits/sec)isallocatedtoasinglepacketatatime,ittakesL/CsecondstotransmitapacketthatisLbitslong.Intime-division(TOM)andfrequency-divisionmultiplexing(FOM)withmtrafficstreams,thelinkcapacityisessentiallysubdividedintomportions-onepertrafficstream.InFOM,thechannelbandwidthWissubdividedintomchannelseachwithbandwidthW/m(actuallyslightlylessbecauseoftheneedforguardbandsbetweenchannels).ThetransmissioncapacityofeachchannelisroughlyC/m,whereCisthecapacitythatwouldbeobtainediftheentirebandwidthwereallocatedtoasinglechannel.ThetransmissiontimeofapacketthatisLbitslongisLm/C,ormtimeslargerthaninthecorrespondingstatisticalmultiplexingscheme.InTOM,allocationisdonebydividingthetimeaxisintoslotsoffixedlength(e.g.,onebitoronebytelong,orperhapsonepacketlongforfixedlengthpackets).Again,conceptually,wemayviewthecommunicationlinkasconsistingofmseparatelinkswithcapacityC/m.Inthecasewheretheslotsareshortrelativetopacketlength,wemayagainregardthetransmissiontimeofapacketLbitslongasLm/C.Inthecasewheretheslotsareofpacketlength,thetransmissiontimeofanLbitpacketisL/C,butthereisawaitof(m-1)packettransmissiontimesbetweenpacketsofthesamestream.OneofthethemesthatwillemergefromourqueueinganalysisisthatstatisticalmultiplexinghassmalleraveragedelayperpacketthaneitherTOMorFOM.Thisisparticularlytruewhenthetrafficstreamsmultiplexedhavearelativelylowdutycycle.ThemainreasonforthepoordelayperformanceofTOMandFOMisthatcommunicationresourcesarewastedwhenallocatedtoatrafficstreamwithamomentarilyemptyqueue,whileothertrafficstreamshavepacketswaitingintheirqueue.Foratrafficanalogy,consideranm-lanehighwayandtwocases.Inonecase,carsarenotallowedtocrossovertootherlanes(thiscorrespondstoTOMorFOM),whileintheothercase,carscanchangelanes(thiscorrespondsroughlytostatisticalmultiplexing).RestrictingcrossoverincreasestraveltimeforthesamereasonthatthedelaycharacteristicsofTOMorFOMarepoor:namely,somesystemresources(highwaylanesorcommunicationchannels)maynotbeutilized,whileothersaremomentarilystressed.Undercertaincircumstances,TOMorFOMmayhaveanadvantage.Supposethateachtrafficstreamhasa\(i.e.,allpacketsarrivesufficientlyapartsothatnopackethastowaitwhiletheprecedingpacketistransmitted.)Ifthesetrafficstreamsaremergedintoasinglequeue,itcanbeshownthattheaveragedelayperpacketwilldecrease,butthevarianceofwaitingtimeinqueuewillgenerallybecomepositive(foranillustration,seeProb.3.7).Therefore,ifmaintainingasmallvariabilityofdelayismoreimportantthandecreasingdelay,itmaybepreferabletouseTOMorFOM.AnotheradvantageofTOMandFOMisthatthereisnoneedtoincludeidentificationofthetrafficstreamoneachpacket,therebysavingsomeoverheadandsimplifyingpacketprocessingatthenodes.Notealsothatwhenoverheadisnegligible,onecanaffordtomakepacketsverysmall,therebyreducingdelaythroughpipelining(cf.Fig.2.37).152DelayModelsinDataNetworksChap.33.2QUEUEINGMODELS-LITTLE'STHEOREMWeconsiderqueueingsystemswherecustomersarriveatrandomtimestoobtainservice.Inthecontextofadatanetwork,customersrepresentpacketsassignedtoacommunicationlinkfortransmission.ServicetimecorrespondstothepackettransmissiontimeandisequaltoLIC,whereListhepacketlengthinbitsandCisthelinktransmissioncapacityinbits/sec.Inthischapteritisconvenienttoignorethelayer2distinctionbetweenpacketsandframes;thuspacketlengthsaretakentoincludeframeheadersandtrailers.Inasomewhatdifferentcontext(whichwewillnotemphasizeverymuch),customersrepresentongoingconversations(orvirtualcircuits)betweenpointsinanetworkandservicetimecorrespondstothedurationofaconversation.Inarelatedcontext,customersrepresentactivecallsinatelephoneorcircuitswitchednetworkandagainservicetimecorrespondstothedurationofthecall.Weshallbetypicallyinterestedinestimatingquantitiessuchas:1.Theaveragenumberofcustomersinthesystem(i.e.,the\ofcustomerseitherwaitinginqueueorundergoingservice)2.Theaveragedelaypercustomer(i.e.,the\inqueueplustheservicetime).Thesequantitieswillbeestimatedintermsofknowninformationsuchas:1.Thecustomerarrivalrate(i.e.,the\ofcustomersenteringthesystemperunittime)2.Thecustomerservicerate(i.e.,the\ofcustomersthesystemservesperunittimewhenitisconstantlybusy)Inmanycasesthecustomerarrivalandserviceratesarenotsufficienttodeterminethedelaycharacteristicsofthesystem.Forexample,ifcustomerstendtoarriveingroups,theaveragecustomerdelaywilltendtobelargerthanwhentheirarrivaltimesareregularlyspacedapart.Thustopredictaveragedelay,wewilltypicallyneedmoredetailed(statistical)informationaboutthecustomerinterarrivalandservicetimes.Inthissection,however,wewilllargelyignoretheavailabilityofsuchinformationandseehowfarwecangowithoutit.3.2.1Little'sTheoremWeproceedtoclarifythemeaningoftheterms\somewhatliberallyaboveinconnectionwiththenumberofcustomersinthesystem,thecustomerdelay,andsoon.IndoingsowewillderiveanimportantresultknownasLittle'sTheorem.Supposethatweobserveasamplehistoryofthesystemfromtimet=0totheindefinitefutureandwerecordthevaluesofvariousquantitiesofinterestastimeSec.3.2QueueingModels-Little'sTheorem153progresses.Inparticular,letN(t)=NumberofcustomersinthesystemattimetaCt)=Numberofcustomerswhoarrivedintheinterval[0,t]T;=TimespentinthesystembytheitharrivingcustomerOurintuitivenotionofthe\ofcustomersinthesystemobserveduptotimetisNt=.tiotN(T)dTwhichwecallthetimeaverageofN(T)uptotimet.Naturally,Ntchangeswiththetimet,butinmanysystemsofinterest,Nttendstoasteady-stateNastincreases,thatis,N=limNtInthiscase,wecallNthesteady-statetimeaverage(orsimplytimeaverage)ofN(T).ItisalsonaturaltoviewAt=a(t)tasthetimeGI'eragearrivalrateovertheinterval[0.tj.Thesteady-statearrivalrateisdefinedasA=limAtt-x(assumingthatthelimitexists).ThetimeaverageofthecustomerdelayuptotimetissimilarlydefinedasT-t-6;=0,\\,0(1)TInet)(3.1)thatis,theaveragetimespentinthesystempercustomeruptotimet.Thesteady-statetimeaveragecustomerdelayisdefinedasT=limTt(assumingthatthelimitexists).ItturnsoutthatthequantitiesN,A,andTabovearerelatedbyasimpleformulathatmakesitpossibletodetermineonegiventheother.Thisresult,knownasLittle'sTheorem,hastheformN=ATLittle'sTheoremexpressesthenaturalideathatcrowdedsystems(largeN)areassociatedwithlongcustomerdelays(largeT)andreversely.Forexample,onarainyday,trafficonarushhourmovesslowerthanaverage(largeT),whilethestreetsaremorecrowded(largeN).Similarly,afast-foodrestaurant(smallT)needsasmallerwaitingroom(smallN)thanaregularrestaurantforthesamecustomerarrivalrate.
Chapter 3_Queueing_Data_Nets
