用自相似模型刻画骨干网流量- Provisioning IP Backbone Networks to Support Latency Sensitive Traffic

ProvisioningIPBackboneNetworkstoSupportLatencySensitiveTraffic

ChuckFraleighandFouadTobagi

SchoolofElectricalEngineering

StanfordUniversity

Stanford,CA94305

Email:{cjf,tobagi}@

ChristopheDiot

SprintAdvancedTechnologyLabs

1AdrianCourt

Burlingame,CA94010

Email:cdiot@

Abstract—Tosupportlatencysensitivetrafficsuchasvoice,networkproviderscaneitheruseservicedifferentiationtoprioritizesuchtrafficorprovisiontheirnetworkwithenoughbandwidthsothatalltrafficmeetsthemoststringentdelayrequirements.Inthecontextofwide-areaInternetbackbones,twofactorsmakeoverprovisioninganattractiveapproach.First,thehighlinkspeedsandlargevolumesoftrafficmakeservicedifferentiationcomplexandpotentiallycostlytodeploy.Second,giventhedegreeofaggregationandresultingtrafficcharacteristics,theamountofoverprovisioningnecessarymaynotbeverylarge.Thisstudydevelopsamethodologytocomputetheamountofoverprovisioningrequiredtosupportagivendelayrequirement.Wefirstdevelopamodelforbackbonetrafficwhichisneededtocomputetheend-to-enddelaythroughthenetwork.Themodelisvalidatedusing331one-hourtrafficmeasurementscollectedfromtheSprintIPnetwork.Wethendevelopaprocedurewhichusesthismodeltofindtheamountofbandwidthneededoneachlinkinthenetworksothatanend-to-enddelayrequirementissatisfied.ApplyingthisproceduretotheSprintnetwork,wefindthatsatisfyingend-to-enddelayrequirementsaslowas3msrequiresonly15%extrabandwidthabovetheaveragedatarateofthetraffic.

I.INTRODUCTION

IPnetworkscarrymanytypesoftraffic.Sometraffic,suchaswebandemail,cantoleratelongqueuingdelayswhichoccurduringperiodsofnetworkcongestion.Othertraffic,suchasvoice,audio,andvideo,haveunacceptableperformanceiflongdelaysareincurred.Toprovidelowdelayserviceforsuchappli-cations,therearetwobasicapproacheswhichcanbeused.Oneoption,knownasservicedifferentiation,istogivepreferentialtreatmenttolatencysensitivetraffic.Thesecondoption,knownasbandwidthprovisioning,istoprovidesufficientbandwidthsothatalltrafficmeetsthemoststringentdelayrequirement.

InthecontextofIPbackbonenetworks,twofactorsmakethebandwidthprovisioningapproachattractive.First,therearecostsassociatedwithtrafficdifferentiation.Whilesomeofthiscostisrelatedtoadditionalcomplexityrequiredinnetworkrouters,muchofthecostisassociatedwiththemanagementandoperationofthenetwork.Installersmustbetrainedtoconfigurethetrafficdifferentiationmechanismswhenroutersareinstalledinthenetworkandnetworkoperatorsmustbetrainedtomanagethedifferenttrafficclasses.Second,trafficdifferentiationmaynotprovidemuchbenefitinbackbonenetworks.Trafficinback-bonenetworksisaggregatedfrommanythousandsofusers.Asaresultofthehighdegreeofaggregation,aswellasthelowpackettransmissiontimes(a1500bytepackettakesonly5µstotransmitona2.5Gb/sOC-48link),itisexpectedthatqueuingdelaysinbackbonenetworkswillbelow,andthereforelittle

overprovisioningisrequired.

Thispaperinvestigatestheamountofoverprovisioiningre-quiredinbackbonenetworks.Usingasetof331one-hourtrafficmeasurementsfromtheSprintIPnetwork,wedevelopaproceduretoevaluatetheamountofbandwidthneededoneachlinkinthenetworkinordertomeetagivendelayrequirement.

A.Bandwidthprovisioning

BackboneIPnetworksprovidehighbandwidthconnectivityacrossawidegeographicarea.Abackbonenetworkconsistsofasetofnodes,knownasPoints-of-Presence(POPs),connectedbyhighspeedlinks.Forexample,abackbonemayhavePOPsinNewYork,Chicago,andSanFranciscoconnectedby10Gb/slinks.CustomersofthebackboneISPconnecttothenetworkat

oneormoreofthePOPs.

BandwidthprovisioningistheprocessbywhichabackboneISPdeterminestheamountofbandwidthneededoneachof

thelinksinordertosupportadesiredlevelofperformance.Forreal-timeapplicationssuchasvoice,areasonablemethodtospecifythisperformancerequirementisintermsofaprob-abilisticdelayrequirementoftheformP[d(i,j)>Dreq]<e,thatistheprobabilitythatthedelaybetweenPOPiandPOPjexceedsDreqislessthane.

ItisimportanttoemphasizethatthisdelayrequirementisthesamebetweenallpairsofPOPsandforalltypesoftraffic.Sincetrafficdifferentiationisnotused,itisnotpossibletoofferonelevelofservicetodatatrafficahigherlevelofservicetoreal-timetraffic.Itisalsonotpossibletoofferonelevelofservicetoonecustomerandasecondlevelofservicetoanothercustomer.Alltrafficreceivesthesameservice,andthisservicemustbesufficienttomeettheneedsofthemoststringentapplication.Whilethismayseeminefficient,wewillseethatsupportingend-to-endqueuingdelayrequirementsaslowas3msrequiresbandwidthonlymarginallygreaterthantheaveragetrafficvolume.

Toprovisionthenetwork,thenetworkprovidermustknowthetrafficdemandbetweeneachpairofPOPs,andthepatheachofthesetrafficdemandsfollowsthroughthenetwork.Thesedemandscanbeforecastusingtechniquessuchas[15].Withthisinformation,thebandwidthrequiredoneachlinkisfoundbysolvinganetworkoptimizationproblemknownastheCapacityAssignment(CA)problem.

0-7803-7753-2/03/$17.00(C)2003IEEE375

frequency

frequency

TheCAproblemhasbeensolvedfornetworkswherethetrafficdemandsaremodeledasaPoissonprocessandwheretheobjectiveistominimizetheaveragedelay[11].UsingtheKleinrockindependenceapproximationandJackson’stheoremonecanderiveexpressionsfortheaveragequeuingdelay.Givenanexpressionfortheaveragedelay,techniquessuchasLa-grangianrelaxationareusedtofindthebandwidthassignmentwhichminimizesthetotalnetworkcost,wherecostisafunctionofthebandwidthoneachlinkinthenetwork.

Ourproblemisdifferentinseveralrespects.First,wecon-siderprobabilisticrequirementsratherthanaveragedelayre-quirements.Second,thePoissonmodelhasbeenshowntonotbeanaccuratemodelforactualnetworktraffic[16],[20].Third,manysolutionstotheCAproblemallowalinktohaveanypossiblecapacity.Inanactualnetwork,athelinkcapacitymustbeselectedfromadiscreteset(e.g.155Mb/sor622Mb/s).

InordertosolvetheCAproblem,wethereforeneed:

•ArealisticmodelforthetrafficdemandbetweenPOPsinabackbonenetwork.

•Amethodtoassessend-to-endqueuingdelayusingthismodel.

•Anproceduretofindthebandwidthneededoneachlinkinordertomeetthedelayconstraints.

WedevelopamodelforbackbonetrafficbyanalyzingtrafficmeasurementsfromtheSprintIPbackbone.Wefindthatback-bonetrafficissignificantlyeasiertomodelthantrafficconsid-eredinpriorstudiessuchas[9],[8],and[17].Thesestudiesfoundthatattimescaleslessthan100ms,thedistributionofthetrafficarrivalprocessisquitecomplex.However,theaveragetrafficarrivalrateofthemeasurementsusedinthesestudieswas

between100kb/sand10Mb/s.Wefindthatoncetrafficvolumereaches50Mb/s(andforsometrafficbetween5Mb/sand50Mb/s),thedistributionofthetrafficarrivalprocessbecomesGaussianatsmalltimescalesandcanbemodeledusingan

extensionofFractionalBrownianMotion(FBM)[13].Wecallthismodeltwo-scaleFBM.

Wethendevelopamethodtocomputetheend-to-enddelaythroughanetworkwherealloftrafficdemandsbetweenPOPpairsaremodeledusingtwo-scaleFBM.Usingthismethod,wedevelopanalgorithmtofindthebandwidthneededoneachlinkinthenetworksothattheend-to-enddelaydelayrequirementissatisfied.Theremainderofthepaperisorganizedasfollows.SectionIIpresentsthetwo-scaleFBMmodelandderivesanexpressionforthedelaydistributionforaqueuefedbyatwo-scaleFBMprocess.Usingthemodelweevaluatethemaximumutilizationthatmaybeachievedonasinglelinkwhilemeetingaparticulardelayrequirement.SectionIIIpresentsthemethodtocomputetheend-to-enddelaythroughthenetwork.SectionIVdescribesthealgorithmtofindtheminimumcostnetworkandappliesittotheSprintnetwork.SectionVconcludesanddiscussesareasoffutureresearch.

II.TRAFFICMODEL

Inabackbonenetwork,thetrafficdemandbetweenapairofPOPsistheaggregateoftrafficfrommanyindividualusers.In

t=100ms

120

100

80

60

40

20

0

0

1

0.20.40.60.8

averagetrafficarrivalrate(Mb/s)

t=10ms

18000

16000

14000

12000

10000

8000

6000

4000

2000

0

0

1

0.20.40.60.8

averagetrafficarrivalrate(Mb/s)

Fig.1.DistributionofAt/tforDEC-WRL-2

thissectionwedevelopamodelforsuchaggregatetrafficandderivethedelaydistributionforaqueuefedbysuchtraffic.

Themodelmustcapturethecharacteristicsofthetrafficwhichaffectthequeueingdelay.Wethereforebeginbyreview-ingtheprocedureusedtocomputequeuingdelaydistributions.ConsideraninfinitebufferqueuewithaconstantbitrateserverofcapacityC.LetA[s,t]betheamountoftrafficthatarrives

Thequeuelengthattime0is

atthequeueoverthetimeinterval(s,t],andletAt=A[−t,0].

Q=p0(At−Ct)

andtheprobabilitythatthequeuelengthexceeds北is

P[Q>北]=P[p0(At−Ct)>北]

Thisexpressionisdifficulttoevaluate,soweusethelowerbound

P[p0(At−Ct)>北]≥p0P[At>北+Ct](1)

Thismayseemtobearathercrudeapproximation,butithasbeenshowntobelogarithmicallyaccurateforlarge北[7].

Thequeueingdelayexperiencedbyapacketofsizebbitsisthesumofthewaitingtimeinthequeue,,andtheservicetimeofthepacket,.Thedistributionofthewaitingtime,W,isfounddirectlyfromthequeuelengthdistributionP(W>d)=supt≥0P(At>C(d+t)).Wedonotmodeltheservicetimedistribution,asitissignificantlysmallerthanthedelayboundsinwhichweareinterested.OnanOC-3link(oneofthelowestspeedbackbonelinks),thetransmissiontimeofamaximumsizepacketisonly80µs.

376

frequency

frequency

frequency

Name

Starttime

Averagedatarate

T1

Wed9Aug009:56am

74.6Mb/s

T2

Wed9Aug009:56am

90.1Mb/s

T3

Wed9Aug009:56am

56.8Mb/s

T4

Wed5Sep0110:00am

219Mb/s

T5

Wed5Sep0110:00am

103Mb/s

T6

Wed5Sep0110:00am

132Mb/s

T7

Wed5Sep0110:00am

171Mb/s

T8

Wed5Sep0110:00am

208Mb/s

T9

Wed5Sep0110:00am

179Mb/s

TABLEI

TRACEDATA

A.TrafficCharacteristics

From(1),thedominantcharacteristicwhichaffectsqueuingdelayisthemarginaldistributionofthetrafficarrivalprocessAatdifferenttimescales,t.PriormeasurementstudieshavefoundthatattimescalesgreaterthanseveralhundredmillisecondsthedistributionofAtisapproximatelyGaussian,whilefortlessthanseveralhundredmillisecondsthedistributionofAtisquitecomplex[16],[20],[9].

Toillustratethispoint,wepresentresultsfromamea-surementknownasDEC-WRL-2,collectedonDEC’sprimaryInternetconnectionandusedin[16].Tocomputethemarginaldistributionattimescalet,wedividetheDEC-WRL-2mea-surementintonon-overlappingblocksofsizetandcomputethenumberofbitsthatarriveovereachoftheseblocks(e.g.

wecomputethenumberofbitsthatarriveoverevery100ms

timeinterval).Fig.1plotstheempiricaldistributionoftat100msand10mstimescalesforDEC-WRL-21.Att=100ms,thedistributionappearsapproximatelyGaussian,whileatt=

10msthedistributionisclearlynon-Gaussian.

DEC-WRL-2isanaccuraterepresentationforWANback-bonetrafficasobservedintheearly1990s.However,trafficvolumehassubstantiallyincreasedfromtheaveragerateof267kb/sobservedinDEC-WRL-2.Toinvestigatethecharacteristicsofhighvolumetraffic,wemakeuseofmeasurementsfromtheSprintIPbackbonenetworkcollectedon25linksinAugust2000,July2001,andSeptember2001.Thesetoflinksincluded155Mb/sOC-3linksand622Mb/sOC-12links,andincludedavarietyoflinktypesincludinglinkstopeeringpoints,linkstolargewebservers,linkstolargedial-upnetworks,andlinkstolargecorporations.Themeasurementsareonehourtraceswhichcontainthearrivaltime,packetsize,andfirst40bytesofeverypackettransmittedonalink.ThepackettimestampsaresynchronizedtoaglobalGPSreferenceclockandareaccuratetowithin5µs.Thecompletesetofmeasurementsincludes331traces.TableIgivesthestarttimeandaveragetrafficvolumefornineofthetracesconsideredindetaillaterinthepaper.Whileall9ofthesetraceswerecollectedat10amonaWednesday,thecompletesetoftracescontainsdatafrommultipledaysof

1Wehaveplottedthedistributionofthetrafficrate(At/t)ratherthanthedistributionofthetrafficvolume(At)tonormalizethex-axis.

t=100ms

140

120

100

80

60

40

20

0

0

50

100

150

averagetrafficarrivalrate(Mb/s)

t=10ms

1400

1200

1000

800

600

400

200

0

0

50

100

150

averagetrafficarrivalrate(Mb/s)

t=1ms

10000

9000

8000

7000

6000

5000

4000

3000

2000

1000

00aveetrafficarrivalra150

Fig.2.MarginaldistributionoftrafficarrivalsfortraceT1

theweekandeveryhouroftheday.

OurgoalistomodelthetrafficdemandbetweentwoPOPsinabackbonenetwork,whichisslightlydifferentthanthetrafficobservedinthemeasurements.Themeasurementswerecol-lectedfromlinkswithinasinglePOPandrepresentafractionoftheentiretrafficdemandbetweentwoPOPs.However,boththeinter-POPtrafficdemandsandthesemeasurementsarebothaggregatesofalargenumberofindividualuserconnections.Asaresult,bothareexpectedtoexhibitthesamecharacter-istics.Laterinthispaperwewillconfirmthatincreasingthetrafficvolumetotherangeofinter-POPtrafficdemandsdoesnotchangethefundamentalcharacteristicspresentedinthissection.Wethereforepresentthetrafficmodelbystudyingthecharacteristicsobservedinasingletrace.

WebeginbystudyingthecharacteristicsoftraceT1.Fig.2plotsthedistributionofAtforT1attimescalesof100ms,10ms,and1ms.Att=100msitappearsGaussianwithmean74.7Mb/sandvariance49.5(Mb/s)2.Thisdistributionissimilar

377

timescale(sec)

1

0.9

0.8

0.7

0.6

0.5

0.4

0.3

0.2

0.1

0

0

50

100

150

200

300

250

trafficarrivalrate(Mb/s)

Fig.3.MinimumtimescaleatwhichmarginaldistributionsareGaussian

tothedistributionofDEC-WRL-2atthe100mstimescale.Atthe10mstimescale,theT1traceismuchdifferentfromDEC-WRL-2.RatherthanexhibitacomplexdistributionsimilartothatshowninFig.1(b),T1appearsGaussianwithmean74.7Mb/sandvariance178(Mb/s)2.Evenatatimescaleof1ms,T1appearsGaussianwithmean74.7Mb/sandvariance852(Mb/s)2.

TodetermineifthesedistributionsareinfactGaussian,weuseastatisticaltestknownastheKolmogorov-Smirnovtest(K-Stest)fornormality[4].ApplyingtheK-StesttoeachdistributionconfirmsthattheyareconsistentwithaGaussiandistribution.Repeatingthisprocessfortimescalesupto60secondsanddownto100µsfindsthedistributionsatthesetimescalesarealsoGaussian.Below100µsthedistributionsare

quitecomplex,butwedonotneedtoconsiderthesesinceweareinterestedinqueuingdelaysontheorderofmilliseconds.

ThereasonforthedifferencebetweenT1andDEC-WRL-2

isthatT1isaggregatedfromaverylargepopulationofusers.TheDEC-WRL-2measurementandnearlyallothertrafficmea-surementsusedinthepriorstudies,haveaveragetrafficvolumebetweenseveralhundredkb/sand2Mb/s.Thisrepresentstrafficfromarelativelysmallnumberofusers(10,000userconnectionsoveraonehourperiodforthemeasurementusedin[20]).TheT1tracehasanaveragetrafficvolumeof75Mb/s,andhasnearly5millionuniqueuserconnections.

Anaturalquestiontoaskis:howmuchaggregationisneededbeforethemarginaldistributionatsmalltimescalesbecomesGaussian?Wecaninvestigatethisbyconsideringthecomplete

setof331onehourtrafficmeasurements.Forsomeofthe

measurements(especiallyforthosecollectedbetween1:00amand4:00am),theaveragetrafficarrivalratecanreachaslowas1Mb/s.Forothermeasurementscollectedduringafternoonhoursonhighlyutilizedlinks,thetrafficvolumecanreachalmost300Mb/s.UsingtheK-Stest,wecandeterminewhichofthesetraceshaveGaussianmarginaldistributionsatsmalltimescales,andwhichhavethemorecomplexdistributions.

Moreprecisely,wecomputethemarginaldistributionofthetrafficarrivalprocessattimescalesfrom1msto1secforeachofthetraces.AteachtimescaleweapplytheK-Stest

todetermineifthedistributionisGaussian.Foreachtracewe

findthesmallesttimescaleatwhichthemarginaldistribution

isGaussian.

Fig.3plotstheminimumGaussiantimescaleversusthe

meanarrivalrateofthetrafficforeachofthetraces.Weseethatforallbutfourtraceswithtrafficvolumegreaterthan50Mb/s,theminimumtimescaleisbetween1msand8ms.ThesetraceshavecharacteristicsverysimilartothoseshownforT1.Below50Mb/sthereismuchmorevariation.Two-thirdsofthe

traceswithtrafficvolumebetween5Mb/sand50Mb/shavea

minimumGaussiantimescalebetween1msand64ms,whileone-thirdexhibitdistributionssimilartothoseshownfortheDEC-WRL-2measurement.Fortraceswithtrafficvolumelessthan5Mb/s,themarginaldistributionsareneverGaussian.AlloftheselowvolumetrafficmeasurementsresembletheDEC-WRL-2traffic.Thisconfirmstheresultsof[9],whichfoundthatforlowvolumetraffic,thedistributionatsmalltimescalesisquitecomplex.However,asthetrafficvolumeincreases,thesedistributionsbecomemuchlesscomplex.Duringthebusyhourofthedaytrafficvolumeonnearlyallbackbonelinksisgreaterthan50Mb/sandthedistributionsareexpectedtobeGaussian.

Itshouldbenotedthattherearesituationswhere50Mb/s

trafficwillnothaveenoughaggregationtouseGaussianmod-els.Consider,forexample,alinkcarryingthree20Mb/sHDTVvideostreams.Thebandwidthguidelineswepresentareonlyvalidforthetrafficwiththesamemixofuserconnectionsthatweseeintoday’sbackbone.Inparticular,thetrafficmustbeaggregatedfromalargepopulationofusers,andtherateofanindividualusershouldbemuchlessthantherateofthetotaltrafficaggregate.

SinceaGaussiandistributionisfullyspecifiedbyitsmeanandvariance,forbackbonetrafficitissufficienttoknowthemeanandvarianceofAtateachtimescalet.ThemeanremainsthesameforalltimescalesasseenfromFig.2.Thevariance,however,changesfromonetimescaletothenext.Therelationshipbetweenthevarianceandtimescalecanbestudiedusingatechniqueknownasthevariance-time(VT)plot.Thisissimplyaplotofthevarianceversusthetimescalet.

Beforeproceeding,itisimportanttonotethatpriorstudies,suchas[9],havedemonstratedthattheVTplotmaynotprovidemuchinformationaboutthestructureofnetworktrafficat

timescaleslessthan100ms.Thereasonforthisisthatthe

variancedoesnotprovidesufficientinformationtodescribeadistributionsimilartothatshowninFig.1(b).Forsuchdistributionsoneneedstoknowinformationaboutthehighermoments.FromFig.2,however,wecanseethatforlargetrafficaggregatesthedistributionatsmalltimescalesisGaussianandcanthereforebefullydescribedusingonlythemeanandvari-ance.TheVTplot,therefore,providesenoughinformationtocompletelycharacterizethetrafficarrivalprocessforbackbonetraffic.LaterinthissectionwewilladdressthestatisticalbiasthatmaybeintroducedbyusingtheVTplottoestimatethevarianceatsmalltimescales.

Fig.4showstheVTplotfortraceT1.Thevarianceexhibitsatwo-piecelinearrelationshipwiththetimescalet.Itdecaysquiterapidlyattimescalesbetween1msand75ms,andstartstodecaymoreslowlyafterthatpoint.Theslowdecayofthevarianceatlargetimescalesisindicativeofastatisticalpropertyknownaslong-rangedependence(LRD)whichhasbeenobservedinnetworktraffic[16],[20].Fortrafficwith

378

variance

10

14

10

13

10

15

T1

H=0.862

−110

−310

0

1

2

10

10

10

−2

10

timescalet(sec)

Fig.4.Variance-timeplotforT1

LRD,thevarianceofthetrafficarrivalratedecaysasapowerofthetimescalet

var(At/t)∼t2H—2,ast→∞

whereHisknownastheHurstparameterandtakesarangeof0.5<H<1.Foralltheothertraces,thevarianceexhibitsthesametwopiecelinearbehaviorasseeninFig.4.For88%ofthetraces,thetransitionpointbetweenthetwolinearregions

occursattimescalesbetween75msand400ms.

Wenowinvestigatethecausesofthesetwolinearregions.Atlargetimescales,theLRDofnetworktraffichasbeenshowntobetheresultoftheheavy-taileddistributionofindividualuserconnectionsizes[20].Aheavy-taileddistributionisoneinwhichP(X>x)∼x—α,1<α<2,asx→∞.TheHurstparameterisdirectlyrelatedtotheαparameterofthe

Tovalidatethattheuserconnectionsizedistributionisre-

connectionsizedistributionaccordingtoH=(3−α)/2[20].

sponsibleforthelargetimescalebehaviorobservedinT1,wecomputebothαandHfortraceT1.ToavoidthestatisticalbiasoftheVTplot,weuseuseawaveletestimatordevelopedbyAbryandVeitch[19]whichyieldsH=0.862forT1.ToestimateαweusetheHillestimatorasdescribedin[20],andvalidateitusingtheproceduredescribedin[5].Wefindtheconnectionsizedistributionisheavy-tailedwithα=1.30indicatingHshouldbe0.85,whichiswithintheconfidenceintervalsoftheAbry-Veitchestimator.Forreference,inFig.4,weplotalinecorrespondingtoanLRDprocesswithavariancethatdecayswithH=0.862.

Nextweinvestigatethebehaviorofthevarianceattimescaleslessthan75ms.WeseefromFig.4thatthevarianceatsmalltimescaleshasalinearrelationshipwitht,butthethevarianceismuchhigherthancanbeexplainedbythecon-nectionsizedistribution.ThereasonforthisisthatthetheoryrelatingtheconnectionsizedistributiontoHconsidersuserconnectionstobeconstantbitrate(CBR).Inarealnetwork,however,userconnectionsarefarfromCBR.InT1,aswellasallbutfiveothertraces,over90%ofthetrafficinthenetworkisgeneratedbyTCP.TCPconnectionstransmitaburstofpacketscorrespondingtotheTCPwindowsize,waitoneround-trip-time(rtt)fortheacknowledgment,andthentransmitanotherburstofpackets.Attimescalesgreaterthanthertt,ithasbeenempiricallydemonstratedthattheconnectionscanbeapproximatedasCBRstreams[20].However,asthetime

scalefallsbelowthertt,individualTCPconnectionsbecomemuchmorevariablethanCBRstreamsresultinginthehighervariance.

AdirectrelationshipbetweentherttandthebreakpointbetweenthetwoscalingregionsoftheVTplothasbeendemon-stratedthoughtheuseofsimulation[9].Thisstudyperformedasimulationwhereallconnectionshadarttof24msandasecondsimulationwhereallconnectionshadarttof610ms.

Theyfoundthatthelinearrelationshipbetweenthevarianceandtimescalewhichwasobservedatlargetimescales(i.e.therelationshipduetotheconnectionsizedistribution)brokedownatatimescalejustabovetherttoftheuserconnections.Ingeneral,foreachofthe331one-hourmeasurementswestudy,wefindthatthetransitionpointoccurs“near”themedianrttoftheconnectionsobservedinthetraces2.ForT1inparticular,themedianrttis96.9mswhichisapproximatelythepointatwhichthevariancebeginstorapidlyincrease.

However,wedonotfindastatisticallysignificantcorrelationbetweenthemedianormeanrttandthebreakpointlocation.Ingeneraltherttdistributionisquitecomplex,andthemeanormedianvalueisinsufficienttofullydescribethedistribution.Asaresult,weareunabletofullyexplaintheexactlocationofthebreakpointandthecauseofthelinearbehaviorinthevarianceatsmalltimescales.However,weareabletodevelopamodeltocapturethisbehaviorandcomputetheresultingqueuingdelays.

B.Two-ScaleFractionalBrownianMotion

TomodelbackbonetrafficwewouldlikeaprocesswhichhasGaussianmarginalswithavariancethatobeysthetwo-piecelinearrelationshipobservedinthetraces.FractionalBrownianMotion(FBM)isaprocesswhosemarginaldistributionsareGaussianwithavariancethathasasinglelinearrelationshipwithtanddecaysast2H—2.FBMwasoriginallyappliedtonetworktrafficbyNorros[13],andaccuratelymodelsthelargetimescalecharacteristicsofnetworktraffic.Modelingthesmalltimescalecharacteristics,however,hasbeenquitechallenging.Cascadebasedmodelshavebeenproposedtocaptureboththelargeandsmalltimescalecharacteristics[9],[17],[8].

Thesemodels,however,weredevelopedtocapturethecomplexsmalltimescaledistributionsshowninFig.1(b).SincelargevolumebackbonetraffichasGaussiandistributionsatsmall

timescalesthecomplexitiesintroducedbycascademodelsare

unnecessary,andasimpleextensiontoFBMissufficient.

withaHurstparameterthatvariesatdifferenttimescales.WecanthereforeuseoneHurstparameter,H0,forlargetimescales

andanotherHurstparameter,H1,forsmalltimescales.(MK)−

MultiscaleFBM,(MK)−FBM,isanextensionofFBM

FBMhasbeenusedbyBenassiandDeguy[2]forimagesynthesisandBardetandBertrand[1]tomodelbiomechanicdata.

Thereareseveralotherprocesseswhichcouldalsobeusedtorepresentthetwo-piecelinearrelationshipbetweenthevarianceandtimescale.OnesuchprocessisatraditionalFBMwitha

periodiccomponent.Allsuchprocesses,however,willproduce

2Weestimatetherttusingtheproceduredescribedin[10].

379

99.9thpercentiledelay

thesameresultsintermsofqueuingdelay.Forourpurposesalloftheseprocesses