On the impact of aggregation on the performance of traffic aware routing

A.Sridharan

S.Bhattacharyya,C.Diot

SprintLabsBurlingame,CA

R.Gu´erin

J.Jetcheva,N.Taft

U.Pennsylvania

Philadelphia,PAU.PennsylvaniaPhiladelphia,PASprintLabsBurlingame,CA

Thispaperinvestigatestheimpactoftrafficaggregationontheperformanceofroutingal-gorithmsthatincorporatetrafficinformation.Wefocusontwoissues.Firstly,weexploretherelationshipbetweenaveragenetworkperformanceandthecoarseness(granularity)oftrafficsplittingacrossroutes.Specifically,weareinterestedinhowaveragenetworkperformanceim-proveswithourabilitytodistributetrafficarbitrarilyacrossmultiplepaths.Secondly,weshiftourattentionfromaveragetoshort-termperformance,withagainafocusontheimpactoftraf-ficgranularity.Inparticular,weexploretherelationbetweentheleveloftrafficaggregationanditsvariability,whichdirectlyaffectsshort-termroutingperformance.Ourinvestigationreliesontraffictracescollectedfromanoperationalnetwork,anditsresultsprovideinsightintothecost-performancetrade-offassociatedwithdeploying“trafficaware”routingprotocols.1.Introduction

AsIPnetworksbecomethelife-lineofbusinessandcommercialapplications,theneedforbetterserviceguaranteesandimprovedperformancearedrivingthedeploymentofservicedif-ferentiationandtrafficengineeringinIPnetworks.Bothtypicallyinvolvedatapathmecha-nismslikepacketclassificationetc.andcontrolpathmechanismslikesignallingandextensionstoroutingprotocols.Inthispaperwefocusonrouting,inparticular,onevaluatingthetrade-offthatexistsbetweentheaddedcomplexityandcostoftheextensionsrequiredtoaccommodatetrafficengineering,andtheperformancebenefitsitaffords.Webelievethatsuchanunderstand-ingisimportanttodecidewhetherornottrafficawareroutingisworthdeploying.

Trafficawareroutingconsistsofprotocolsandalgorithmsthatincorporateinthecomputationofroutestheknowledgeofbothavailablenetworkresources,e.g.,availablelinkbandwidth,andtrafficrequirements.Thegoalissomeoptimizationofnetworkusageorserviceguarantees.Therehavebeenmanystudiesdevotedtothedesignandevaluationoftrafficawareroutingalgorithmsandprotocols,andtheycanbebroadlyclassifiedintwocategories.Thosewithatrafficengineeringfocus,andthosethattargetanon-demandmodel(see[5,9,2]forexamplesofthefirst,and[4,1]and[8]despiteitstitleforexamplesofthesecond).Thefocusofthispaperisonthetrafficengineeringusageofrouting,whereatrafficmatrixcharacterizingthebandwidth

requirementsbetweenpairsofingress-egressnodesisassumedknown4andusedtocomputeroutesinanattempttooptimizenetworkperformance.Thetrafficinformationistypicallyobtainedbymeasuringatingressnodestheamountoftrafficheadedtovariousdestinations.Ourmaingoalistogainabetterunderstandingofthecost-benefittrade-offassociatedwithincorporatingtrafficinformationintoroutingfortrafficengineeringpurposes.Thetwomaincontributorstothecostofsuchtrafficawareroutingare:(1)matchingtraffictoroutes(paths)soastoachieve“optimal”networkperformance;(2)updatingroutestoaccommodatevariationsintrafficpatternsorintensity.

Thefirstcostcanbefurtherbrokendownintoatrafficclassificationcostattheingressrouterandaforwardingstatecostinthecorenetworkbothofwhichareaffectedbythegranularityatwhichtrafficneedstobesplit(classified)toachieve”optimalloads”.Weaddressthiscostissuebyevaluatingtheimpactoftrafficgranularityontheperformanceoftrafficawarerouting.Trafficgranularityreferstotheleveloftraffic(androute)aggregationthatconstrainstheloadbalancingabilityoftrafficawarerouting.Coarsegranularityaggregationbundlestrafficintoasmallnumberof“streams”thatmustthenberoutedindividually.Thisdecreasesclassificationcostbutmayaffectroutingperformancebylimitingitsabilitytoarbitrarilysplittrafficacrosspathstoachieveoptimallinkloads.

Thesecondcostisrelatedtothefactthattrafficpatterns,andhencetrafficmatrices,changeovertime.Frequentupdatingofroutingtablestoreflectthischangeisnotdesirableandisbestkeptaslowaspossible.Toaddressthesecondcostissueregardingthefrequencyofroutingupdates,westudytheinfluenceoftimegranularityonroutingperformance.Inparticular,weassumethatroutesarecomputedonthebasisof(longterm)averagetrafficmeasures,andremainfixedforthedurationoftheexperiments.Wethenevaluatenetworkperformanceatdifferenttimescales,whentrafficisdistributedoverthisfixedsetofroutes.Byvaryingthegranularityofthetimeoverwhichperformanceismeasured,wewanttocapturetheimpactofthevaria-tions,fromthemeasuredlongtermaverages,oftrafficintensityoverdifferenttimescales.Themagnitudeofthosevariationsdependsonboththelengthofthetimeintervaloverwhichwemeasureperformance,andthegranularityofthetrafficstreamsthatwereavailablewhencom-putingroutes.Ourgoalistounderstandthisrelationshipastrafficgranularitychanges,aswellasinvestigateitsimpactonroutingperformance,andinparticularshorttermperformance,i.e.,overshortertimeintervalsthantheonesusedbyroutingtocomputeoptimalroutes.

Theinteractionbetweentrafficandtimegranularityinthecontextoftrafficawareroutingisasfollows5.Optimalrouting,ignoringforthetimebeinggranularityconstraints,computesasetof“optimalpathsandassociatedlinkloads”basedonlongtermaveragetrafficintensities,e.g.,dailyaverages.Achievingtheseoptimallinkloadsoftenrequiresafinegrainsplittingoftrafficintosmallstreams,whichinturntendstoincreasetrafficvariability.Asaresult,finegrainsplittingoftraffic,besidesincreasingclassificationcost,thiscanproducehighershorttermtrafficvariabilityand,therefore,possiblymorefrequenttransientlinkoverloads(underloads).Thiscouldthenleadtopoorershorttermnetworkperformance.Notethatthiswillobviouslydependontheextenttowhichthegreatervariablilityoffinergranularitystreamsalsotranslatesintomorevariablelinkloads.Thiswilldependontheassignmentofstreamstopaths,andthisisoneoftheaspectsweinvestigate.Ontheotherhand,althoughusingcoarsertrafficgranularity,e.g.,usingsupernets,maynotallowustooptimallydistributetrafficoverlinks,itforcestrafficto

remainaggregated.Thismaythenresultinsmallershorttermtrafficfluctuationsand,therefore,fewerperiodsoftransientoverloadandbetteroverallperformance.

Understandingtheextenttowhichthesedifferentparametersaffectthetrade-offbetweenperformanceandcostinthecontextoftrafficawareroutingisthemaingoalofthispaper.Ourapproachisbasedonevaluatingtheperformanceoftwoheuristicroutingalgorithmsfor“optimally”routingtrafficgivencertaingranularityconstraints.Weevaluatebothshorttermandlongtermperformanceaswevarytrafficgranularity.Therehavebeenanumberofpreviousstudiesdevotedtothedesignandevaluationoftrafficengineeringprotocolsandalgorithms[5,9,2]inthecontextofIPandMPLSnetworksthatweassumehere.Theyhoweverrepresentadifferentsettingfromtheoneweconsiderinthispapersincenoneofthemfocusesontheinteractionoftimeandtrafficgranularityandtheireffectonroutingperformance.

Therestofthispaperisstructuredasfollows.Section2,reviewsthetrafficmeasurementpro-cedureswerelyontoestimatethetrafficmatricesusedinthepaper.Section3focusesontheimpactoftrafficgranularityonroutingperformance.Section4investigateshowroutingperfor-mancevariesovertimeasafunctionoftrafficgranularity.Inparticular,itexploreshowtrafficgranularityaffectsthedifferencethatexistsbetweenshorttermandlongtermperformance.Finally,Section5summarizesthefindingsofthepaperandpointsoutpotentialextensions.2.TrafficMeasurementandTrafficMatrixGeneration

ThegenerationoftrafficmatricesforourstudyisbasedonmeasurementstakenwithinSprint’sIPbackbone.TheSprintIPbackbonemonitoringproject[6]provideduswithpacket-leveltracesfromasinglePOP(calledthe“monitoredPOP”).OpticalsplittersandIPMONsys-tems[6]areusedoneachofthemonitoredlinkstocapturethefirst44bytesofeveryIPpackettraversingthelink.These44-byteheadersincludeaddressandsizeinformationforeachpacket.Inaddition,eachIPpacketistime-stampedusingagloballysynchronizedclock(GPSbased).Fromthisinformation,wecandeterminethenumberofbytesheadedtootherdestinationsacrosstheSprintnetworkduringanytimeinterval.Thisdataformsthebasisfordetermining(i)trafficintensitiesbetweenthemonitoredPOPandtheother15POPsintheSprintbackbone(see[6]forageneraldescriptionoftheoveralltopologyandtheinternalarchitectureofaPOP),and(ii)thevariationsofthistrafficondifferenttimescalesandatdifferentlevelsofgranularity.Inthiswork,weusedatracethatis800minuteslongandwascollectedatapeeringlink.

Inourtrafficmatrix,eachrowrepresentsaningressPOPandeachcolumnrepresentsanegressPOP.ThusinitssimplestformanentryinthetrafficmatrixrepresentsthetotalvolumeoftrafficflowingfromtheingressPOPtotheegressPOPoverthedurationofthetrace.WefurtherbreakthisdatabetweenpairsofPOPs(ineachdirection)intomultiplelevlesoftimegranularityandstreamgranularityandthusendupwithamultidimensionaltrafficmatrix.

ThefirststepinbuildingsuchamatrixfromdataconsistsofidentifyingtheegressPOPforeachpacketmonitoredattheingressPOP.WedownloadedIBGPtablesfromthemonitoredPOPatthesametimethatthetraffictracesweregathered.UsinginformationintheIBGPtableinconjunctionwithdetailedknowledgeaboutthenetworktopology,weusedthemethoddescribedin[11]toidentifytheegressPOPforeverypacketinthetrace.

Trafficgranularityreferstothelevelofaggregationusedtodeterminewhichpacketsaremappedontoagivenstream.PacketsbetweentwoPOPscanbeaggregatedintostreamsac-cordingtodifferentcriteria.Forexample,packetscanbemappedtostreamsbasedontheir

sourceanddestinationaddresses,portnumbersandprotocolnumbers.Thiswouldgeneraterelativelyfinegranularitystreams.Alternatively,coarsergranularitystreamscanbeobtainedbyaggregatingpacketsonthebasisofacommondestinationaddressprefix.Byusingmulti-pleprefixmasksofspecificlengths,itispossibletovarythelevelofaggregation(i.e.,streamgranularity)overapre-determinedrange.Becauseofitssimplicityandthefactthatitprovidesasystematicapproachtovaryinggranularity,weusethisapproach.

Inparticular,weuseprefixlengthsof0,4,6,and8.Aprefixlengthof’0’correspondstoaggregatingallthetrafficbetweentwoPOPsontoasinglestream.Aprefixlengthof4aggregatesallpacketswiththesamefirst4bitsintheIPdestinationaddressfieldintoasinglestream.Morelevelsofgranularityaresimilarlydefinedusingprefixesoflength6and8.(Weusethenotationp0,p4,p6andp8torefertoeachofthesegranularitylevels.)Theuseoflongerprefixlengthsleadstoalargernumberofindividualstreamswhichcanthenberoutedindividually.Ingeneral,asthelengthoftheaddressprefixusedtoaggregatepacketsincreases,sodoesthenumberofstreams,andconversely,trafficgranularitydecreases.

Ateachtrafficgranularity,wealsomeasuredthebandwidthlevelsatdifferenttimegranu-larity.Thetimegranularityreferstothelengthofthemeasurementintervaloverwhichtheaveragebandwidthperstreamwascalculated.Sinceourtracewasminuteslong,anminuteaveragerepresentsthecoarsesttimegranularity.Wealsoused10minutemeasurementstocapturetheshorttermvariabilityofstreams.Measuringtheaveragebandwidthofstreamsondifferenttimescalesenablesustoidentifyshort-termfluctuationsaroundlonger-termav-erages.Forexample,theeightyten-minuteestimatesobtainedforeachstream,showhowthetrafficassociatedwithagivendestinationprefixvariesaroundits800minutesaverageduringthoseeightyconsecutiveten-minutemeasurementintervals.Table1summarizessometypicalnumbersthatthisprocessyieldedforourdata.Itindicatestherangeonthenumberofstreams,andtherangeofaveragebandwidthperstream,foreachofthegranularitylevels.

Morespecifically,thetrafficmatrix“row”obtainedasaresultofthisprocessprovidesuswithasetofbandwidthestimatesoftheform,whereidentifiestheegressnode;indicatestheprefixlengthusedtoseparatetrafficintofinergranularitystreams;andidentifiesthetimegranularityatwhichtrafficisbeingmeasured.Inparticular,isitselfa“matrix”ofbandwidthestimatesfortrafficfromthemoni-toredPOPtoegressPOPnumber10.EachrowinthismatrixcorrespondstoasinglestreamassociatedwithallthepacketsheadingtowardsPOPnumber10withthesame8-bitdestina-tionaddressprefix.Eachcolumnofthismatrixcorrespondstooneoftheeightyten-minutebandwidthestimates.Asaresult,givestheaveragetrafficintensityinthe22ndten-minutemonitoringintervalforstreamnumber5associatedwithan8-bitdestinationaddressprefixforpacketsfromthemonitoredPOPtoPOPnumber10.

Becausemonitoringequipmentisexpensiveandverydifficulttodeployinoperationalnet-works,wewereonlyabletoobtaintracesfromasinglePOP.Thisgeneratesdataforasinglerowofourtrafficmatrix.Inordertopopulatetheother15rowsofthetrafficmatrixwecombinedcoarsetrafficinformationobtainedforotherPOPsusingSNMP,withthedetailedstructuralin-formationprovidedbythemeasurementsdoneatthemonitoredPOP.Theremaining15rowsofthetrafficmatrixwereconstructedbyusingthecompleterowsasatemplateandcreatingnewstreamsbyrandomlyselectingastreamfromtheoriginalpoolandapplyingrandomcyclicshiftsofthetimeslotsandsmallrandomperturbationstothestream.Onceanentirerowiscompleted,theintensityofthestreamswasscaledtomatchtheaverageintensityoftrafficob-granularitylevelp0

[5-10]

p6

[25-]

bandwidthranges(Mbps)

[1-14]

[0-4]

linkloadsachievedbyrouting.Thereareobviouslymanyothercostfunctionsthatarepossible,butinthecontextoftrafficengineering,minimizingthedelayexperiencedbyuserpacketstraversingthenetworkisareasonabletarget.Inaddition,other“typical”costfunctionslikeminimizingmaximumlinkload,areknown,e.g.,[12]toyieldresultssimilartothoseofaminimumdelaycostfunction.Mostimportant,however,istheconvex,non-linearnatureofthecostcurve.Intherestofthepaper,welimitourselvestothisspecificcostfunction.

Inthatcontext,weexploretheimpactoftrafficgranularityontheachievablenetworkdelaybyanalyzingthebehavioroftwoheuristics,whicharebrieflydescribedlaterinthissection.Weuseheuristicssinceitiswell-known,e.g.,[7],thatcomputingoptimalrouteswhilesatisfyingtrafficgranularityconstraintsisanNP-hardproblem.

3.1.HeuristicRoutingAlgorithms

Thetwoheuristicswedescribenextattempttoapproachunconstrained,optimalperfor-mances,whileaccountingforthetrafficgranularityconstraintsimposedbytheexistenceofindividualunsplittablestreams.Weusethemtoevaluatetheimpactoftrafficgranularityonourabilitytoapproachtheperformanceofanoptimalroutingalgorithm.Notethatourpri-maryintentisnottodemonstratethesuperiorperformanceofoneheuristicovertheother,butinsteadtoassesstheimpactoftrafficgranularityonroutingperformance,andhenceprovidemotivations,orlackthereof,formovingtowardsfinergranularityinthecontextoftrafficawarerouting.Duetolackofspace,andgiventhefactthatourmainfocusisontheimpactofgran-ularity,weonlygiveabriefdescriptionofthealgorithms.Theinterestedreaderisreferredto[10]foramoredetaileddiscussion.

3.1.1.Heuristic1

Thefirstheuristicisasimplegreedymethodthataddsstreamsoneatatime,whileeachtimeselectingapaththatminimizesdelay.Thisheuristicisinspiredfrommethodsusedinan“on-demand”modeloftrafficawareroutingwhererequestsaregenerateddynamicallyandneedtoberoutedoneatattime.Themainvariationsforthisfirstheuristicareintermsoftheorderinwhichindividualstreamsarerouted,e.g.,inascending,descending,orrandomordersintermsoftheirtrafficintensity.Inourexperimentswefoundthatsortingthestreamsindescendingordergivesthebestperformance(forbothheuristics)amongthethreeorderings.Henceforthweshallimplicitlyassumesuchanordering.

Akeyfeatureofthisheuristicisthatitisindependentoftheactualtrafficofferedbetweendifferentnodes.Thisclearlymakesforgreatersimplicity,butalsopointstoalimitationoftheapproach,asitdoesnotexploitkeyinformationthatisavailabletotheroutingalgorithm.3.1.2.Heuristic2

Thesecondheuristictakesintoaccounttheknowledgeofthetotaltrafficmatrix,andinpar-ticulartheoutput(setofpathsandassociatedloads)generatedbyanoptimalroutingalgorithm,thatignoresgranularityconstraintsimposedbystreams.Themotivationforusingthisinforma-tionisthatitrepresentsthebestperformanceachievable.Wegiveabriefoutlineoftheheuristicandreferthereaderto[10]formoredetails.

Theoptimalroutingproblemcanbesetupasastraightforwardmulti-commodityflowprob-lem[10]whichissolvedusingPPRN6.Theheuristicproceedsbyassigningstreamsto(optimal)

pathsinamannerthatattemptstogetascloseaspossibletothelinkloadsachievedbytheop-timalalgorithm.Thisreliesonatwophaseprocedure.Thefirstphaseinvolvesroutingstreamsone-by-one,asinthefirstheuristic,butonanetworkwith(fictitious)linkcapacitiesinitiallysetequaltothedesiredoptimalloads.Aseachstreamisadded,itisroutedonthepaththatyieldstheminimum“delay”giventheassumedlinkcapacities.Inordertotakethegranularnatureoftrafficintoconsiderationwerelaxthe“fictitious”capacityconstraintwhileroutingoverthisnetwork,byallowingastreamtoberoutedifitdoesnotexceedthecapacityofanylinkonthatpathbymorethanafactorof.Theparametercontrolstheamountbywhichthelinkconstraintisviolated.Inthesecondphase,anystreamforwhichnofeasible7pathwasfoundduringthefirstphase,isroutedusingastandardminimumdelayalgorithm,butusingnowtheactuallinkcapacitiestogetherwiththelinkloadsthatresultedfromthefirstphase.

3.2.PerformanceEvaluation

Inthissection,weinvestigatetheimpactoftrafficgranularityonroutingperformance,whereperformanceismeasuredintermsofthetotalnetworkaveragedelaycomputedusingthelong-termaverageload.First,wecomparetheperformanceofthetwoheuristicsagainsttheoptimalroutingalgorithm,whileassumingthefinestgranularityavailablefromourtrafficmeasure-ments.i.e.,theuseofanaddressprefixmaskoflength8.Thisprovidessomeinsightintothedifferencesinperformancethatexistbetweenheuristicsthatincorporateknowledgeofthetraf-ficmatrix(Heuristic2)andthosethatdon’t(Heuristic1).Unlessspecified,thestreamorderingusedforboththeheuristicswasindecreasingfashion,i.e.,largerstreamswereroutedfirst.Inordertocomparetheperformanceoftheheuristics,wescaledtheaverageintensityofarandomlyselectedsetofsource-destinationpairsintheTrafficMatrixtocreatehotspots.WeshowtheperformanceofthetwoheuristicsandoftheoptimalroutingalgorithminFigure1.Notethatwhilethetwoheuristicswereconstrainedtoroutingindividuallystreamsgeneratedfromlength8prefixes,theoptimalalgorithmdidnotfollowanysuchconstraint.Ascanbeseen,Heuristic2outperformsHeuristic1andcloselyfollowstheoptimaltillthe’knee’,thereafterthegranularityofthestreamsforcesadifferentsub-optimumallocation.Themainreasonfortheinabilityofbothheuristicstoapproachtheoptimalperformance,evenatthefinestgranularitylevel(p8)canbefoundinTable1,whichshowsthatlargebandwidthstreamsremain.Thoselargebandwidthstreamsaffecttheloadbalancingabilityofanyalgorithm.Thisfactornot-withstanding,thebetterperformanceofheuristic2illustratesthefactthatusingtheinformationavailablefromthetrafficmatrixcanyieldbetterperformance.Inwhatfollows,weexplorefurthertheimpactthattrafficgranularityhasonroutingperformance.

Westartthiscomparisonbyusingthedifferentlevelsoftrafficgranularitygeneratedfromourtrafficmeasurements.Specifically,trafficcanbeaggregatedontostreamsusingprefixoflengths0,4,6,or8,which,asshowninTable1,translateintoaveragenumberofstreamsrangingfrom1(prefixlengthof0)to(prefixlengthof8).Clearly,onecanexpectalargernumberofstreamstoresultinbetterperformance,asitgivesroutingmoreflexibilityinassigningtraffictopaths.Theaspectwewanttoexploreistheevolutionofroutingperformanceasthenumberofstreamsvaries,i.e.,whatisthemagnitudeofperformanceimprovementsasthenumber

0.010.0090.0080.0070.006secondsHeuristic 1Heuristic 2Optimal 0.0050.0040.0030.0020.00101.71.81.922.12.2Total Traffic into Network in Bits/sec2.32.4x 109Figure1.OptimalRoutingvsRoutingUnderGranularityConstraints.9x 10−4Delay for Long Term Average LoadMask 0Mask 4Mask 6Mask 8876Delay543212345% 455% 567 Networks (Decreasing Load)833% 91028% Figure2.OntheImpactofTrafficGranularity.(DelayComputedforLongTermAverageLoad).

Granularity

1

Mask4()

Max.No.ofDistinctPaths

7

2.3

Mask8()16Table2

StatisticsforTheNumberofDistinctPathsUsedatEachGranularityLevelforTopology1(MostHeavilyLoaded).

ofstreamsvaries.Weproceededtodoso,bycomputingthemeandelayaveragedover30trafficmatricesforeachgranularitylevel,eachofwhichwasroutedon10networkswiththesametopologybutincreasingcapacities(decreasingloads).EachtrafficmatrixwasgeneratedusingthemethoddescribedinSection2andthetotalaverageintensitiesforeachS-Dpair(foreachmatrix)werescaledtothevaluesobtainedusingSNMPdatatoobtainafaircomparison.Differentloadvaluesweregeneratedbyscalingdownlinkcapacities.

TheresultsareplottedinFigure2,whichshowstheaveragenetworkwidedelayasafunctionofnetworksizing.Weimmediatelyseethatalargefractionoftheperformancegainisachievedwhengoingfromaprefixlengthof0tooneof4,andsubsequentimprovementsaremuchmoremodest.Thisstandstoreason,sincethenumberofpathsthroughthenetworkislimited,sothatbeyondacertainlevel,additionalstreamsarestillroutedoverthesamesetofpaths.Wejustifythisclaimbyproviding,inTable2,statisticsregardingtheactualnumberofdistinctpathsusedforeachgranularitylevel.WenoticethattheaveragenumberofpathsuseddoublesfromMask0toMask4,butincreasesslowlythereafterindicatingthelimitedavailabilityofpathsforallthesource-destinationpairs.Wealsonotethattheimprovementinperformancedecreasesrapidlyasweincreasethecapacityofthenetwork,whichisnotunexpected.

4.OntheImpactofTimeGranularity

Thepurposeofthissectionistoexploreanotherdimensionofhowperformanceisaffectedbythegranularityatwhichroutingisperformed.Specifically,wesawinSection3thatfinergranularityleadstoaloweraverageloadonthelinks,whichtranslatesintoloweraveragedelay,thatis,betterlongtermperformance.However,performancemeasuredoverfinertimescalescanbesignificantlydifferent.Thetraffic,andhencelinkloadsmeasuredatfinertimescalesfluctuatearoundthelongtermaveragevalues.Thiscombinedwiththenon-linearnatureofthedelayfunctioncanresultinsignificantlydifferentperformanceascomparedtothatobtainedus-inglongtermaverageload.Thisisbecausefluctuationsatthehigherendofthecurvecontributemuchmoretothedelaythanthoseatthelowerendduetothenon-linearconvexnatureofthecurve.Hence,boththemeanloadandthevariabilityofthetrafficdeterminehowroutingperfor-mance,measuredovershorttimeintervals(10minutes),differsfromitsexpectedvaluebasedonthelongtermaverageload(800minutes).Thegoalofthissectionistoshedsomelightonhowthesedifferentfactorsinteractandultimatelyaffectroutingperformance.Especiallysince,asweshowinthenextsub-section,splittingtrafficintofinerstreamsincreasestheirvariability.Thiscanpotentiallyoffsettheadvantageofaloweroperatinglinkload,andresultinahigher

delayoversmallertimescalesascomparedtothatobtainedwithcoarsergranularitystreams.4.1.EvaluatingtheImpactofTimeVariability

Inordertoinvestigatethispotentialtrade-offbetweenimprovedaverageperformanceandgreatertrafficvariability,wefirstproceedtoevaluatehowtrafficgranularityaffectsitsvari-ability.Wedosobycomputingthecoefficientofvariationofthetrafficintensityofindividualstreamsfordifferentlevelsofgranularityover8010-minute-intervalmeasurementsamples.TheresultsaresummarizedinFigure3,whichclearlyindicatesthatasthenumberofstreamsincreases,i.e.,fromMask()toMask(),sodoesthevariabilityofindividualstreams.

Coefficient of Variation for Mask 075045Coefficient of Variation for Mask 40535Number of Streams3025201510Number of Streams432150−2024 Coefficient of Variation68100−2024 Coefficient of Variation6810(a)(b)Coefficient of Variation for Mask 690150Coefficient of Variation for Mask 8807060Number of StreamsNumber of Streams1005040305020100−2024 Coefficient of Variation68100−2024 Coefficient of Variation6810(c)(d)Figure3.RelationBetweenTrafficVariabilityandStreamGranularity.

Thisimpliesthatthepotentialbenefitsofimprovedaverageperformancemaybeoffsetbytheimpactofthisgreaterstreamvariabilitywhichcouldresultinhigherlinkloadvariations,ifitalsotranslatesintogreatervariabilityatthelinklevel,i.e.,afterstreamshavebeenassigned

topaths.Notethatgreaterstreamvariabilityneednotnecessarilyimplygreaterlinktrafficvariability.Forexample,routingallstreamsfromthesameS-Dpaironthesamepathwouldobviouslyresultin(link)trafficcharacteristicsthatareidenticaltothoseobservedwithoutfirstsplittingthetrafficintostreams.However,suchascenarioisunlikely,astheloadbalancingdecisionsofroutingwilltypicallyresultinstreamsfromthesameS-Dpairbeingroutedoveradistinctsetofpaths.Inthatcontext,itisunclearhowaggregatingstreamsfromdifferentS-Dpairswillaffectthevariabilityoflinktraffic.

Inordertoassestherelativeeffectofthesecompetingfactors,weevaluatedthenetworkdelayaveragedoverallthe8010-minutemeasurementintervals,forthe30trafficmatricesroutedoverthe10networksusedinFigure2.Recallthatdifferentnetworkloadswereachievedbyscalinglinkcapacitiesandnottrafficmatrices,hence,preservingtemporaltrafficcharacteristicsacrossexperiments.TheresultsareshowninFigure4.

x 10−3Delay averaged over All Time SlotsMask 0Mask 4Mask 6Mask 82.221.81.61.4Delay1.210.80.60.40.212345% 455% 567 Networks (Decreasing Load)833% 91028% Figure4.DelayAveragedOverTimeSlots.FromcomparingFigure4withFigure2,weimmediatelyobservethatthebenefitsofloweraveragelinkloadsand,therefore,delay,donotalwaystranslateintovisiblybetterperformancewhentimevariabilityistakenintoaccount.Thefigureshowsthedelayaveragedoverthe8010-minuteslotsforthedifferentlevelsoftrafficgranularityunderconsideration,i.e.,masks0,4,6,and8.Weobservethatwhenroutingislimitedtoasinglestream(mask0),performanceispoorevenontheshorter10-minutetimescale.Thisisbecausealthoughlinktrafficmayexhibitsmallershorttermloadvariations,thehigheraveragelinkloadsamplifythosevariationswhenitcomestodelaybecauseofthenon-linearnatureofthecurve.Astrafficgranularitydecreases,i.e.,tomasks4or6,weobservethattheresultingloweraveragelinkloadsmanagetoalso

improveshorttermperformance.Thisisbecause,despitethepotentiallylargershorttermtrafficfluctuations,theloweroverallaveragelinkloadssufficientlydampentheimpactofthosevariationsonshorttermdelay.However,thisimprovementdoesnotreadilyextendastrafficgranularitydecreasesfurther.Specifically,weseethatroutingusingmask8streamsoftenresultsinworseaverageshorttermdelaysthanwhenmasks4or6areused.Thisisbecause,asseenfromFigure2,theimprovementinaveragelinkloadsthatmask8streamsafford,ismarginalcomparedtowhatisachievablewithmask4or6.Ontheotherhand,mask8streamsexhibithighershorttermtrafficfluctuationsthatresultindegradedaverageshorttermdelays.Notethatthisbehaviorisobservedeventhough,asshowninTable2,thenumberofpathsusedwithmask8issimilartowhatisusedwithmasks4and6.Thisindicatesthatalthoughthenumberofpathsissimilar,theassignmentoftraffic(streams)tothemisdifferent.

ThefindingsofFigure4indicatetheexistenceofatrade-offbetweenshort-termandlong-termperformance,whendecreasingtrafficgranularitytoachieveloweraveragelinkloads.Thefiguresuggestsusingthecoarsestpossibletrafficgranularitythatachievesa“significant”de-creaseinaveragelinkloads,e.g.,amaskof4inthecurrentenvironment.Furtherreductionsintrafficgranularityimproveaverageloadsonlymarginally,andthegreatershorttermtrafficvariabilitytheyinduceoftenbecomesthedominanteffect,worseningshorttermperformance.

5.Conclusion

WehaveinvestigatedanewaspectoftrafficawareroutinginIPnetworks,namely,theimpactoftrafficandtimegranularityonroutingperformance.Ourperformancemeasurewasbasedonatraditionaldelaybasedcostfunction,butweexpectcomparablefindingswithothercostfunctions.TheinvestigationwascarriedoutusingactualtrafficandflowdatacollectedonanoperationalInternetbackbone.

Themaincontributionsofthepaperconsistof:(1)quantifyingtheimpactoftrafficgranu-larityonroutingperformance,andinparticularthatthebulkoftheimprovementoccurswitharelativelysmallnumberofstreams;(2)designingandevaluatingaroutingheuristic(Heuristic2)thatapproximatestheperformanceof“optimal”routingreasonablywell,whileincorporat-ingtrafficgranularityconstraints;(3)observingthatwhilefinergranularityroutingimprovesaverageperformance,thisdoesnotalwayscarryovertosmallertimescales,wherethegreatervariabilityoffinergraintrafficcanoffsetmostoftheresultingperformanceimprovements.Thishasbeenapreliminaryinvestigationintothepotentialbenefitsandtrade-offsrelatedtotrafficaggregation.Wearecurrentlycollectingmorenetworktracesthatspanoverafewdaysratherthanhourstofurtherinvestigatethistopicandbaseourfindingsonafirmerfooting.Specifically,weintendto:(1)verifythestabilityofthetrafficmatrix(whichaffectsroutingcomputation)overalargeenoughtimescale;(2)Explorethetrade-offbetweenlong-termandshort-termperformanceoverasufficientlybigdataset;(3)extendtheaggregationschemetouseroutingprefixeswhichisapracticalanddeployablealternative.

Acknowledgements

TheauthorswouldliketothankJordiCastroforhishelpinusingthePPRNsoftwarepackageandapplyingittotherelativelylargeoptimizationproblemsofthispaper.

REFERENCES

1.G.Apostolopoulos,R.Gu´erin,S.Kamat,andS.Tripathi.Quality-of-servicebasedrout-ing:Aperformanceperspective.InProceedingsofSIGCOMM,pages17–28,Vancouver,

Ontario,CANADA,September1998.

2.D.Awduche,J.Malcolm,J.Agogbua,M.O’Dell,andJ.McManus.Requirementsfor

trafficengineeringoverMPLS.RequestForComments(Informational)RFC2702,InternetEngineeringTaskForce,September1999.

3.D.BertsekasandR.G.Gallager.DataNetworks.PrenticeHall,EnglewoodCliffs,NJ,2nd

edition,1992.

4.S.ChenandKNahrstedt.Anoverviewofquality-of-serviceroutingfornextgeneration

high-speednetworks:Problemsandsolutions.IEEENetworkMagazine,SpecialIssueonTransmissionandDistributionofDigitalVideo,12(6):–79,November/December1998.5.B.FortzandM.Thorup.InternettrafficengineeringbyoptimizingOSPFweights.In

ProceedingsofINFOCOM’2000,TelAviv,Israel,March2000.

6.C.Fraleigh,C.Diot,B.Lyles,S.Moon,P.Owezarski,D.Papagiannaki,andF.Tobagi.

Designanddeploymentofapassivemonitoringinfrastructure.InPassiveandActiveMea-surementWorkshop,Amsterdam,April2001.

7.B.GavishandS.Hantler.AnalgorithmforoptimalrouteselectioninSNAnetworks.IEEE

Trans.Commun.,COM-31(10),October1983.

8.M.KodialamandT.V.Lakshman.Minimuminterferenceroutingwithapplicationsto

MPLStrafficengineering.InProceedingsofINFOCOM’2000,TelAviv,Israel,March2000.

9.T.LiandY.Rekhter.Aproviderarchitecturefordifferentiatedservicesandtrafficengi-neering(PASTE).RequestForComments(Informational)RFC2430,InternetEngineeringTaskForce,October1998.

10.A.Sridharan,S.Bhattacharyya,C.Diot,R.Gu´erin,J.Jetcheva,andN.Taft.Ontheimpact

ofaggregationontheperformanceoftrafficawarerouting.Technicalreport,UniversityofPennsylvania,July2000.Availableathttp://www.seas.upenn.edu/guerin.

11.N.Taft,S.Bhattacharyya,J.Jetcheva,andC.Diot.Understandingtrafficdynamicsata

backbonePOP.TechnicalReportTR01-ATL-020201,SprintLabs,February2001.Avail-ableathttp://www.sprintlabs.com/PEOPLE/nina/papers.html.

12.K.S.Vastola.Anumericalstudyoftwomeasuresofdelayfornetworkrouting.M.S.

Thesis,U.Illinois,Dept.Elec.Eng.,Urbana,IL,1979.