Effective Bandwidth in High Speed Digital Networks

EectiveBandwidthinHighSpeedDigitalNetworksCheng-ShangChangDept.ofElectricalEngineering,NationalTsingHuaUniversityHsinchu30043,Taiwan,R.O.C.Email:[e-mail]n,T.J.WatsonResearchCenterP.O.Box704,YorktownHeights,NY10598,U.S.A.Email:[e-mail]29,1999AbstractThetheoryoflargedeviationsprovidesasimpleuniedbasisforstatisticalmechanics,informationtheoryandqueueingtheory.TheobjectiveofthispaperistouselargedeviationtheoryandtheLaplacemethodofintegrationtoprovideansimpleintuitiveoverviewoftherecentlydevelopedtheoryofeectivebandwidthforhighspeeddigitalnetworks,especiallyATMnetworks.Thisincludes(i)identicationoftheappropriateenergyfunction,entropyfunctionandeectivebandwidthfunctionofasource,(ii)thecalculusoftheeectivebandwidthfunctions,(iii)bandwidthallocationandbuermanagement,(iv)tracdescriptors,and(v)envelopeprocessesandconjugateprocessesforfastsimulationsandbounds.Keywords:ATM,eectivebandwidth,gradeofservice,largedeviations,entropy,fastsimula-tionsSupportedinpartbytheNationalScienceCouncil,Taiwan,R.O.C.,underGrantsNSC83-0208-M007-091andNSC83-0404-E007-052.1IntroductionThenextgenerationofcommunicationnetworkswillcarrydierentclassesoftrac,e.g.voice,video,faxanddata,overthesamenetwork.Sincedierentclassesoftracusuallyrequiredierentgrade-of-service(GOS),anopenandchallengingproblemforthenetworkdesigneristodesignschemesthatintegratethesedierentclassesoftraceciently.Oneofthemostinterestingapproachesindealingwiththisproblemistherecentlydevelopedtheoryofeectivebandwidth.Theeectivebandwidthofatimevaryingsourceistheminimumamountofband-widthrequiredtosatisfyitsGOS,andthetheoryofeectivebandwidthprovidesamethodtocompute(orapproximate)theeectivebandwidth.Theconceptofeectivebandwidthforhighspeeddigitalnetworkswasrstproposedindependentlyin[36,40,34],wheretheconceptwastestedoutfori.i.d.sourcesandON-OFFsources.Thegeneralframeworkofthetheory,includ-ingthecomputationoftheeectivebandwidthforMarkovprocessesandothergeneralprocessesandtheassociatedcalculus,wascarriedoutin[6,43,10,31,56,35].(Fordetailedhistoricalremarks,seee.g.[56]).Furtherdevelopmentofthetheoryfortracregulation,admissioncontrolandotherapplicationscanbefoundin[7,42,47,24,22,28],amongmanyothers.Themainobjectiveofthispaperistoprovideanintuitive,andhopefullyunderstandable,overviewofthistheorythat,insomeways,parallelsthedevelopmentofstatisticalmechanics,andtobrieysurveysomeoftheapplicationsofthistheory.(Wewillalsorefertotheoriginalpapersforreadersinterestedinformalproofs.)Ourapproachinsomewaysisparalleltothedevelopmentofstatisticalmechanicsfromclassicalmechanics.Boltzmann(seee.g.[60])assumedthattheprobabilitydensitythataparticleattimetisatpositionxwithspeedvisf(x;v;t).Usingthisassumption,heintroducedtheHfunctiontoprovidethelinkbetweenthelawsofmechanics(theequationsofmotions)andthelawsofthermodynamics.TheHfunctionwaslateridentiedastheentropyfunction,whichinturninspiredShannon[52]inhisderivationofinformationtheory.InSection2,weviewasourcelikeaparticleinstatisticalmechanicsandstartfromdeningthe\equationsofmotionsinanetwork.Weassumeasourcethatbehavesasaconstantrateuidwithrateforaperiodoftimetwithprobabilityf(;t).Usingthis,thetaildistributionofthequeuelengthinanetworkcanberepresentedbyanintegraloff(;t)overacertainset.Withthehelpoftherecentlydevelopedtheoryoflargedeviations(seee.g.[5,25,27,29,55,53]),theprobabilitydensityfunctionf(;t)(andthedensityfunctionf(x;v;t)inBoltzmann’sframework[29])canbeshowntohavetheformofGibb’sdistribution,i.e.,exp(t()),where()isobtainedfromtheLegendretransformofafunction()thatcanbederivedfromtheGartner-Ellislimitofasource[33,29].Thefunctions()and()arethencalledthe\energyfunctionandthe\entropyfunctionofasource,respectively.Bysolvingforthedominantexponentintheintegraloff(;t),weobtainanapproximationtothequeuelengthdistribution.Thiscorrespondstondingtheminimumactionpathinclassicalmechanics.Inparticular,foraqueuewithcapacitycsubjecttoasourcewiththe1energyfunction(),thedistributionofitsqueuelengthhasanexponentialtailwithrate,whereistheuniquesolutionof()==c.Inviewofthisequality,thefunction()=isthuscalledtheeectivebandwidthfunctionofthesource.InSection3,weintroducethecalculusforeectivebandwidthfunctions.Insteadoffol-lowingtheformalargumentsin[6,8,56,13],wederivethecalculusheuristicallyfromthecorrespondingenergyfunctionsandentropyfunctions.Thecalculusincludesthefollowingnet-workoperations:(i)multiplexingindependentarrivals,(ii)outputfromaswitchoralinkwithtimevaryingcapacity,and(iii)demultiplexingorrouting.Usingthesethreerules,theeectivebandwidthfunctioninanintreenetworkwithroutingcanbederivedinductively.Usingthecalculus,weexplorepossibleapplicationsofthetheoryofeectivebandwidthtobandwidthallocationandbuermanagementinSection4.Weconsidertwotypesofbandwidthallocation:independentbandwidthallocationanddynamicbandwidthallocation.Inthefor-mer,thebandwidthallocatedforatimevaryingsourceisindependentofthesource.Weshowthattheoptimalindependentbandwidthalloc