The Impact of BGP Dynamics on Intra-Domain Traffic

2020-05-10 来源：飒榕旅游知识分享网

SPRINTATLRESEARCHREPORTRR03-ATL-111377-NOVEMBER20031

TheImpactofBGPDynamicsonIntra-Domain

Trafﬁc

SharadAgarwal

Chen-NeeChuah

CSDivision,

ECEDepartment,UniversityofCalifornia,Berkeley

UniversityofCalifornia,Davissagarwal@cs.berkeley.edu

chuah@ece.ucdavis.edu

Abstract—

Recentworkinnetworktrafﬁcmatrixestimationhasfocusedongen-eratingrouter-to-routerorPoP-to-PoP(Point-of-Presence)trafﬁcmatriceswithinanISPbackbonefromnetworklinkloaddata.However,theseesti-mationtechniqueshavenotconsideredtheimpactofinter-domainroutingchangesinBGP(BorderGatewayProtocol).BGProutingchangeshavethepotentialtointroducesigniﬁcanterrorsinestimatedtrafﬁcmatricesbycausingtrafﬁcshiftsbetweenegressroutersorPoPswithinasingleback-bonenetwork.WepresentamethodologytocorrelateBGProutingtablechangeswithpackettracesinordertoanalyzehowBGPdynamicsaffecttrafﬁcfan-outwithintheSprintIPnetwork.Despiteanaverageof133BGProutingupdatesperminute,weﬁndthatBGProutingchangesdonotcausemorethan0.03%ofingresstrafﬁctoshiftbetweenegressPoPs.Thislimitedimpactismostlyduetotherelativestabilityofnetworkpreﬁxesthatreceivethemajorityoftrafﬁc–0.05%ofBGProutingtablechangesaffectintra-domainroutesforpreﬁxesthatcarry80%ofthetrafﬁc.ThusourworkvalidatesanimportantassumptionunderlyingexistingtechniquesfortrafﬁcmatrixestimationinlargeIPnetworks.

I.INTRODUCTION

TheInternetisaninterconnectionofseparatelyadministerednetworkscalledAutonomousSystemsorASes.EachASisaclosednetworkofendhosts,routersandlinks,typicallyrunninganintra-domainroutingprotocolorIGP(InteriorGatewayPro-tocol)suchasIS-IS(IntermediateSystemtoIntermediateSys-tem)[1]orOSPF(OpenShortestPathFirst)[2].TheIGPdeter-mineshowanetworkentity(endhostorrouter)insidetheASreachesanothernetworkentityinthesameASviaintermediatehops.ToreachentitiesoutsidetheAS,theinter-domainrout-ingprotocolorEGP(ExteriorGatewayProtocol)usedtodayistheBorderGatewayProtocolorBGP[3].EachASannouncesaggregateinformationfortheentitiesinitsnetworkviaBGPtoneighboringASes.Thisisintheformofaroutingannounce-mentorroutingupdateforoneormorenetworkpreﬁxes.AnetworkpreﬁxisarepresentationofasetofIPaddresses,suchas128.32.0.0/16foreveryaddressintherangeof128.32.0.0to128.32.255.255.ThroughthepathvectoroperationofBGP,otherASesﬁndouthowtoreachtheseaddresses.

ApacketthatissentfromanASXtoanIPaddressinadiffer-entASZwilltraverseaseriesoflinksdeterminedbymultipleroutingprotocols.Firstly,theIGPinsideASXwilldeterminehowtosendthepackettothenearestborderrouter.TheborderrouterinsideASXwilldeterminetheinter-ASpathviaBGP,suchas“ASX,ASY,ASZ”.ThepacketwillthenbesenttoASY.ASYwilluseBGPtodeterminethatthenextASisASZ.ASYwilluseitsIGPtosendthepacketacrossitsnetworktotheappropriateborderroutertosendittoASZ.ASZwillthen

ThisworkwasdonewhiletheauthorswereatSprintAdvancedTechnologyLaboratories.

SupratikBhattacharyya

ChristopheDiot

SprintATL,IntelResearch,Burlingame,CA,USACambridge,UKsupratik@sprintlabs.com

christophe.diot@intel.com

useitsIGPtosendittothedestinationinsideitsnetwork.

NetworktrafﬁcengineeringtasksarecriticaltotheoperationofindividualASes.Thesetaskstuneanoperationalnetworkforperformanceoptimization,andincludetrafﬁcloadbalancing,linkprovisioningandimplementinglinkfail-overstrategies.Forexample,loadbalancingtypicallyminimizesover-utilizationofcapacityonsomelinkswhenothercapacityisavailableinthenetwork.Inordertoeffectivelytrafﬁcengineeranetwork,atrafﬁcmatrixisrequired.Atrafﬁcmatrixrepresentsthevolumeoftrafﬁcthatﬂowsbetweenallpairsofsourcesanddestina-tionsinsideanAS.However,duetoavarietyofreasonsinclud-inglimitednetworksoftwareandhardwarecapabilities,detailednetworktrafﬁcinformationisoftenunavailabletobuildatrafﬁcmatrix.Thusavarietyoftechniqueshavebeendeveloped[4],[5],[6],[7]toestimatethetrafﬁcmatrixfrommoreeasilyob-tainablenetworklinkloadmeasurements.However,variationsinBGProuteshavethepotentialtoaddsigniﬁcantvariabilitytothetrafﬁcmatrix,whichthepriorworkhasnotconsidered.Ithasbeenapproximately15yearssinceBGPwasdeployedontheInternet.ThenumberofASesparticipatinginBGPhasgrowntoover15,000today.Thisgrowthhasbeensuper-linearduringthepastfewyears[8].WiththissuddengrowththerehasbeenconcernintheresearchcommunityabouthowwellBGPisscaling.Inparticular,ithasbeennotedthatthereissignif-icantgrowthinthevolumeofBGProuteannouncements(orrouteﬂapping)[9]andinthenumberofBGProuteentriesintheroutersofvariousASes[8].Thishasthepotentialtosigniﬁ-cantlyimpactpacketforwardingintheInternet.

Iftheinter-domainpathforreachingaparticulardestinationkeepschanging,thenpacketswilltraverseadifferentsetofASesaftereachchange.Further,foranintermediateASthatpeerswithmultipleASesatdifferentborderroutersinitsnetwork,changesintheinter-domainpathwillcausepacketstotraversedifferentpathsinsideitsnetworktodifferentborderrouters.ThishasseveralimplicationsfortheintermediateAS.PacketdeliverytimesorlatencywithinthatAScanvarysincethepathsinsideitsnetworkkeepchanging.Latencysensitiveapplicationssuchasvoice-over-IPcanbeadverselyaffected.Iftheintra-domainpathsvary,thenthetrafﬁcdemandsfordifferentlinksinthenetworkwillvary.Thisvariabilityinturnwillimpactthetrafﬁcmatrixandmakeit’sestimationmoredifﬁcult.

Inthispaper,weanswerthequestion“DoBGProutingta-blechangesaffecthowtrafﬁctraversestheSprintIPnetwork?”.Sprintmaintainsa“tier-1”ISPthatconnectstoover2,000otherASes.AsigniﬁcantpercentageofInternettrafﬁctransitsthisnetwork.Forthesereasons,webelievethatitisasuitablepoint

SPRINTATLRESEARCHREPORTRR03-ATL-111377-NOVEMBER2003forstudyingtheimpactofBGPontrafﬁcinsideanAS.Weex-amineBGPdatafrommultipleroutersinthenetwork.Wecorre-latethiswithpackettracescollectedonseveraldifferentdaysatdifferentlocationsinsideSprint.Thecontributionsofourworkare:

•routeWeannouncementsdevelopamethodologyontrafﬁcforinsideanalyzinganAS.theItseparatesimpactofinher-BGPenttrafﬁcdynamicssuchastime-of-dayeffectsfromegressPoPshiftsduetoBGProutingchanges.

•fromWeanpresentoperationalresultsnetworkfromthewithcorrelationiBGPdata.ofWecapturedﬁndthatpacketsasig-niﬁcantnumberofroutingchangescontinuouslyoccur.How-ever,forthelinksthatwemeasure,weexperimentallyconcludethatthesechangesdonotsigniﬁcantlyimpactthepathsofmostpackets.Priorwork[10]hasfoundthatonlyasmallnumberofBGPannouncementsaffectmostofthetrafﬁc.However,evenafewBGPchangescanpotentiallysigniﬁcantlyimpactmostofthetrafﬁc.WeaddresswhatimpactthesefewBGPannounce-mentshavewithinSprint.

Thepaperisorganizedasfollows.WebeginwithrelatedworkinSectionIIfollowedbySectionIIIthatexplainstheprob-lemweaddressinthiswork.WeexplainourmethodologyfortacklingthisprobleminSectionIV.WedescribethedatausedinSectionVandpresentourresultsinSectionVI.InSectionVII,weanalyzetheroutingdataandpackettracesfurthertojustifyourﬁndings.WeendwithconclusionsinSectionVIII.

II.RELATEDWORK

Duetothedifﬁcultyincollectingdetaileddataforalltraf-ﬁcinalargenetwork,statisticalinferencetechniqueshavebeendeveloped[4],[5],[6],[7]toobtaintrafﬁcmatrices.Thesetech-niquesattempttoinferthebytecountsfororigin-destinationpairswithinanetworkbasedonlinkbytecounts.Thetrafﬁcmatrixthatisestimatedisonewheretheoriginsanddestinationsareroutersinsidethelocalnetwork.Inreality,forISPnetworks,mostoftheoriginsanddestinationsareendhostsoutsidethelo-calnetwork.Thusinter-domainroutechangesbetweentheendhostscanchangetheoriginanddestinationroutersinsidethelocalnetwork.Thishasthepotentialtoreducetheaccuracyofthesetechniquesandtherebyimpactthetrafﬁcengineeringtasksbasedontheestimatedtrafﬁcmatrices.Zhangetal.[7]identifythisproblembutassumeittobenegligiblebasedontheirexpe-rienceintheproposedgeneralizedgravitymodel.WecorrelateBGPdatawithtrafﬁcmeasurementstoquantifythiseffect.Muchofthepriorworkininter-domainroutinghasbeeninanalyzingaggregatestatisticsofeBGP(externalBGP)tablesandupdates.Toourknowledge,littlepriorworkhasfocusedoniBGP(internalBGP)behavior.Also,westudyiBGPdynam-icsonthepacketforwardingpathinanoperational“Tier-1”ISP,insteadofpriorworkthatstudiedrelatedissuesthroughsim-ulationsorcontrolledexperiments.Weareawareofonlytwostudies[11],[10]thathavecorrelatedtrafﬁcmeasurementswithBGPdatafromanoperationalnetwork.

UhligandBonaventure[11]usesixsuccessivedaysoftraf-ﬁcmeasurementsandasinglesnapshotofaBGProutingtabletostudythedistributionandstabilityoftrafﬁc.TheyﬁndthattrafﬁcisnotevenlydistributedacrossASesintermsofhopdis-tancefromthemeasurementpoint.Theyshowthatunder10%

ofASessentabout90%ofthetrafﬁc.ThelargestASesintermsoftrafﬁccontributionremainedthelargestfromdaytoday.Rexfordetal.[10],theauthorsassociatethenumberofBGPupdateswithtrafﬁcbehaviorinAT&T’snetwork.TheyﬁndthatasmallnumberofpreﬁxesreceivemostoftheBGPupdatesandthatmosttrafﬁctravelstoasmallnumberofpreﬁxes.TheyﬁndthatthepreﬁxesthatcarrymostofthetrafﬁcdonotreceivemanyBGPupdates.Theseresultsmightleadonetoconjec-turethatBGProutingupdatesdonotcausesigniﬁcanttrafﬁcshifts.However,evenifthepreﬁxesthatcarrymostofthetraf-ﬁcreceivefewBGPupdates,thesefewupdatescanstillcausesigniﬁcantegressborderrouterchanges.TheseresultsdonotspeciﬁcallydemonstratetheextenttowhichBGPupdatescauseshiftsinintra-domaintrafﬁcbecausethenumberofupdatesit-selfisnotsufﬁcienttounderstandthisissue.EveryBGPan-nouncementcanpotentiallychangetheattributethatdeterminestheegressborderrouter.ThusthenumberofBGPupdatesdoesnotdirectlytranslateintotheamountoftrafﬁcthatshifts.Inourwork,wedevelopanentirelydifferentmethodologythanusedbyRexfordetal.[10].WeperformathoroughstudyofhowBGPupdatescanaffecttheintra-domaintrafﬁcmatrix.WegobeyondcountingthenumberofBGPmessagesassociatedwithpopularpreﬁxestoactuallyaccountingforhoweverypacketisaffectedbyeveryBGPchange.Wemeasuretheimpactintermsoftrafﬁcvariabilityinbackbonelinksandquantifyvolumesoftrafﬁcshifts.Weﬁndthatforsometrafﬁc,afewBGPupdatesdochangetheegressrouteraddressandcausethetrafﬁctoshiftbetweenintra-domainpaths.However,mostofthetrafﬁcisun-affected.Thetrafﬁcwemeasurecontainslargeﬂowsthatre-ceiveBGPupdatescarryingfeweregressrouterchangesthanthoseforotherﬂows,whichwasnotexploredinthepriorwork.

III.PROBLEMDESCRIPTION

BGPisapathvectorroutingprotocolthatexchangesroutesforIPaddressrangesorpreﬁxes.Eachrouteannouncementhasvariouscomponents,suchasthelistofpreﬁxesbeingwith-drawn,orthepreﬁxbeingadded,theASpathtobefollowedinreachingthepreﬁx,andtheaddressofthenextrouteralongthepath.EveryASthatreceivesarouteannouncementwillﬁrstapplyitsimportpolicies[3]andthenBGP“best”routeselec-tion,whichtakesintoconsiderationpreferenceslocaltotheAS,theASpathlength,andthebestIGPpathtotheborderrouter,amongothers.Iftherouteisselected,thenithasthepotentialtobepassedontootherneighboringASes.Exportrulesorpoli-ciesdeterminewhichASmayreceivethisannouncement.ThecurrentASwillbeaddedtotheASpathandthenexthoprouterwillbechangedtooneofthisAS’sborderrouters.

ManyASesconnectviaBGPtomultipleupstreamASesorISPs,andevenatmultiplepointstothesameISP.Thistrend,knownasmultihoming,hasbecomeverypopularoverthepastfewyears,asindicatedbythetremendousgrowthinBGPpar-ticipation[12].Asaresult,anintermediateASmayreceivemultipleroutesinBGPforthesamedestinationaddresspreﬁx.ThismaycausetheintermediateAStokeepchangingtherouteitusestoreachthisdestination.Thiscanoccurduetomanyrea-sons.EachASalongapathapplieslocalpoliciesinacceptingsomeroutesandnotothers.BGProuteselectionisusedtopickthe“best”oftheremainingroutesvia13steps[13].Infact,each

SPRINTATLRESEARCHREPORTRR03-ATL-111377-NOVEMBER2003TrafficPoP 10󰀀fficTraSprint Network󰀀PoP 20󰀀ciffarTBGP UpdatePoP 30󰀀Customer󰀀Fig.1.Intra-domainrouteandtrafﬁcthroughtheSprintnetwork

ASmayhavemultipleBGProutersconnectedviainternalBGPoriBGP[3],anddifferentpartsoftheASmaybeusingdiffer-entroutestoreachthesamedestination.TheconcatenationofsuchroutepolicyandselectionrulesacrossmultipleroutersineachofmultipleASesalongaparticularASpathtoadestina-tionleadstoaverycomplexroutingsystem[14].Anyportionofthissystemcancontributetoroutechangeswhenfacedwithmultiplechoicestoreachadestination.Rapidchangescanmakeroutingforadestinationpreﬁxunstable[15].Inaddition,rapidchangescanalsosigniﬁcantlyimpacttrafﬁcpatternswithinanAS.

TheSprintnetworkconnectstomultipleotherASes,inmul-tiplegeographicallydistinctlocationscalledPoPsorPointsofPresence(alsoknownasswitchingcenters).SuchanISPhasalargeandcomplexnetworkofroutersandlinkstointer-connectthesePoPs.Further,eachPoPisacollectionofroutersandlinksthatprovideconnectivitytocustomerASesorpeerASesinalargemetropolitanarea.RouterswithinandacrossPoPsuseiBGPtodistributeBGProutes.iBGPistypicallyusedinnet-workswithmultipleroutersthatconnecttomultipleASes.ItmaynotbepossibletodistributetheBGProutingtableinIGPinascalablefashiontoallrouterswithinlargeASes[3].ThusiBGPisusedtoexchangeBGProutesamongtheseroutersandIGPisusedtoexchangeroutesforlocaladdresseswithintheAS.AnASnetworkmaybedesignedunderseveralconstraintssuchastheaveragelatencyorjitterinsidethenetwork.Thus,theISPwillhaveto“engineer”itsnetworktoensurethatlossanddelayguaranteesaremet.ThetaskoftrafﬁcengineeringmayincludesettingIS-ISorOSPFlinkweightssothattrafﬁctravelsalongtheshortestpathsintheAS’snetworkandcongestionislimited.Overtime,thetrafﬁcexchangedwiththeseneighbor-ingASesmaychange.Asaresult,thelinkweightswillhavetobeupdated.Furthermore,thetrafﬁcexchangedwiththeseASesmaygrowandmorecustomerASesmayconnecttotheISP.Asaresult,morelinkswillhavetobe“provisioned”intothenet-work.Thesetasksareusuallyperformedbyﬁrstgeneratinga“trafﬁcmatrix”[16]whichshowsthetrafﬁcdemandsfromanypointinthenetworktoanyotherpoint.Itcanbecreatedatdif-ferentlevels-eachroworcolumnofthematrixcanbeaPoPorASorrouteroringress/egresslink.PoP-to-PoPtrafﬁcmatricesareimportantforprovisioningandtrafﬁcengineeringinter-PoPlinks,whichtypicallyrequirethemostcriticalengineering.

cTraffiPoP 10󰀀ciffarTSprint Network󰀀PoP 20󰀀TrafficPoP 30󰀀Customer󰀀Fig.2.Intra-domainrouteandtrafﬁcthroughSprintafterBGPchange

Iftheinter-domainBGProuteforadestinationpreﬁxchanges,thenthepathoftrafﬁctooneofthesedestinationhoststhroughtheSprintnetworkmaychange.ConsidertheexampleinFigure1wheretrafﬁcdestinedtothecustomerASenterstheSprintnetworkthroughPoP10.ThecurrentBGPannounce-mentfromthecustomerdeterminesthatthe“egress”orexitPoPforthistrafﬁcisPoP20.EachBGPannouncementhasanexthopattributethatindicatestheegressBGProuterthattrafﬁctothedestinationaddresscanbesentto.ThustheannouncementfromthecustomerwouldindicatethatthenexthopistheegressBGProuterinPoP20.IfanewBGPannouncementisheardthatchangesthenexthoproutertooneinPoP30,thenthistraf-ﬁcwilltraveltoPoP30instead,asshowninFigure2.Asaresult,thetrafﬁcisnowtravelingbetweenPoPs10and30in-steadofPoPs10and20.ThepathtakenbythistrafﬁcinsidetheSprintnetworkmaybeverydifferent,andifthishappensfrequently,thetrafﬁcengineeringandnetworkprovisioningforthisnetworkmaynolongerbeaccurate.ThelinksbetweenPoPs10and20willhavelessloadandthelinksbetweenPoPs10and30willhavemore.Congestionmayoccurandfuturegrowthofthenetworkmaybeimpacted.Further,duetothischange,thistrafﬁcwillnowexperienceadifferentlatencybecauseittra-versesadifferentpath.Latencysensitiveapplicationssuchasvoice-over-IPmaybeadverselyaffectedifsuchchangesoccuroften.

Ifthishappensfrequently,estimatingtrafﬁcmatricesforthisnetworkmaybemorechallengingthanpreviouslyassumed.Ifﬂowsbetweenendhostskeepchangingtheoriginanddestina-tionpointsinsidethelocalnetwork,thenthebytecountsbe-tweenthesepointswillkeepchanging.Withouttrafﬁcmatricesthatcanaccountforandrepresentsuchvariability,trafﬁcengi-neeringwillbecomeharder.Thereissigniﬁcantpotentialforsuchchangestooccur.Oftheover2,100ASesthatconnectdi-rectlytotheSprintnetwork,over1,600haveadditionalindirectpathsviaotherASestoreachthenetwork.Ingeneral,overhalfofthenon-ISPASesontheInternethavemultiplepathstothe“tier-1”ISPsoftheInternet[12].

Notethatinthiswork,weonlyaddresstheimpactontrafﬁcinrelationtopathchangesinsidetheSprintnetwork.SomeofthesechangesmayalsobeassociatedwithpathchangesinsideotherASesandintheinter-ASpath.Thismayresultinchangestothecongestionorpacketdelayexperiencedbytrafﬁc,which

SPRINTATLRESEARCHREPORTRR03-ATL-111377-NOVEMBER2003Sprint NetworkAS Z1.1.1.0/24packet1.1.1.1RouterRouter2.2.2.2AS XPoP ABGP TableDestNextHopPoP B1.1.1.0/248.8.0.0/162.2.2.23.3.3.3Fig.3.DatapacketandBGPcorrelationexample

mayevencausecongestioncontrolreactionsorenduserbehav-iortochange.Weaccountfortheseeffectsduetorealroutingchangesinourmethodologybycollectingandusingrealback-bonetrafﬁc.However,weareunabletoaccountforhowtheenduserbehaviorwouldhavebeenhadtherebeennoroutingchanges.

IV.ANALYSISMETHODOLOGY

A.IngressPoPtoEgressPoPTrafﬁcMatrix

Sincewewishtodeterminetheimpactofroutingchangesfortrafﬁcengineeringandnetworkcapacityplanning,weareonlyconcernedwithinter-PoPvariationsintrafﬁc.Typically,eachPoPishousedwithinasinglebuilding,andisacollec-tionofroutersandlinksbetweenthem.Ittendstohaveatwo-levelhierarchicalroutingstructure.Atthelowerlevel,customerlinksareconnectedtoaccessrouters.Theseaccessroutersareinturnconnectedtoanumberofbackbonerouters.ThebackboneroutersprovideconnectivitytootherPoPsaswellasotherlargeISPs.InstallingadditionalcapacitywithinaPoP(betweenac-cessroutersandbackboneroutersinthesamePoP)isrelativelylessexpensiveandrequireslessplanningandtimecomparedtocapacityupgradesbetweenPoPs(betweenbackboneroutersindifferentPoPs).Thuswebelievethatintra-PoPlinksarerarelycongestedandintra-PoPvariationsareunlikelytocausesigniﬁ-cantlatencyvariation.

Ifweareonlyconcernedwithvariationsintheinter-PoPpathsthattrafﬁctakesacrosstheSprintnetwork,weneedtoconsiderbothtrafﬁcinformationandroutinginformationatthegranular-ityofPoPs.Foraparticularpacket,aningressPoPisthePoPinSprintwherethepacketentersthenetwork,whiletheegressPoPisthePoPwherethepacketleavesthenetwork,presumablyto-wardthedestinationaddress.WeneedtodetermineiftheegressPoPforanypacketchangesduetoBGProutechanges.Thus,weneedtoconstructaPoP-to-PoPtrafﬁcmatrix.EachcolumnofthematrixcorrespondstoanegressPoPandeachrowcorre-spondstoaningressPoP.AnentryinthismatrixindicateshowmuchofthetrafﬁcenteringthecorrespondingingressPoPex-itstheSprintnetworkatthecorrespondingegressPoP.ChangesovertimeinthiskindoftrafﬁcmatrixindicateschangesintrafﬁcpatternsbetweenPoPswhileignoringchangesintrafﬁcpatternsbetweenlinksinsideanyPoP.

Togeneratethismatrix,weneedBGProutinginformationandpacketheaders.Foreverypacket,weneedtodeterminewhichPoPitwillexitthenetworkfrom.Thedestinationad-

dressinthepacketheaderindicateswherethepacketshouldﬁnallygoto.TheBGProutingtableentryforthisdestinationaddressgivesthelasthoprouterinsideSprintthatwillsendthepackettoaneighboringAS.WeuserouteraddressallocationsandroutinginformationspeciﬁctotheSprintnetworktodeter-minethePoPthateveryegressrouterbelongsto.Inthisfashion,wecandeterminetheegressPoPforeverypacket.Forexample,considerFigure3.Attimet,apacketwithdestinationaddress1.1.1.1enterstheSprintnetworkatPoPA.WeusetheBGPta-blefromtheingressrouterinthisingressPoPtoﬁndthedestina-tionaddress1.1.1.1.Thistableindicatesthattheroutingpreﬁxis1.1.1.0/24andthenexthoprouteris2.2.2.2.Thismeansthatrouter2.2.2.2insidetheSprintnetworkwilldeliverthispackettoaneighboringASitandwilleventuallyreachthedestinationpreﬁx1.1.1.0/24.UsingourknowledgeofrouterlocationsandroutinginformationspeciﬁctotheSprintnetwork,wedeterminethat2.2.2.2isinPoPB.Thusweaddthesizeinbytesofthispackettothe(A,B)entryinthetrafﬁcmatrixfortimet.Moredetailsofthistechniquecanbefoundin[17].B.VariabilityduetoBGP

Fortrafﬁcengineeringandcapacityprovisioning,thetrafﬁcmatrixneedstobeconsidered.Ifthismatrixvariesalot,itbe-comeshardertocalculateitaccuratelyandappropriatelyengi-neerthenetwork.Ashasbeenobservedinmuchpriorwork,Internettrafﬁchasinherentvariability,duetoend-userbehav-ior,congestioncontrolandotherreasons.However,therecanbeevenmorevariabilityduetoBGProutingchanges.WewanttoidentifythevariabilityduetoBGP,nottheinherenttrafﬁcvariability.Bycarefullyusingfreshversusstaleroutingdatatocalculatethetrafﬁcmatrices,wecanidentifythevariabilitythatisduetoBGProutingchanges.

Intheﬁrstscenario,weattempttoaccuratelyaccountforwhathappensintheSprintnetwork.WemaintainthelatestBGPtableforeverypointintimeforarouterbyapplyingtheBGPupdatesastheyarereceivedattherouter.WecallthisthedynamicBGPtable.Foreverypacketthatisreceived,wecheckthisBGProut-ingtabletoﬁndtheegressPoPforthatdestinationandupdatethetrafﬁcmatrix.Inthisway,wecancalculatetheactualtime-varyingtrafﬁcmatrixfortheSprintnetworkthataccountsforthecombinedeffectofinherenttrafﬁcvariabilityandchangesduetoBGPannouncements.

Inthesecondscenario,weconsiderwhatwouldhappenifBGPchangesdidnotoccur.Wecreateanewtime-varyingtraf-ﬁcmatrix.However,foreverypacket,weusetheBGProutingtablethatexistedatsomepreviouspointintime.WeusethesamestaticBGProutingtableforthewholetimeperiodofmea-surement.Thistime-varyingtrafﬁcmatrixonlyaccountsfortheinherenttrafﬁcvariability.Wecallthisthe“stale”trafﬁcmatrix.Wethensubtractthesetwotime-varyingtrafﬁcmatricestoobtainthechangestothetrafﬁcmatrixthatwereonlyduetoBGPannouncements.Wecallthisthe“difference”matrix.Sup-posethatattimet,acellat(A,C)inthedifferencematrixhasvaluez.Thismeansthatatt,anextrazbytesfromPoPAegressedatPoPCduetooneormoreBGProutingchanges.Thereshouldbeacorresponding−zbytesforsomeothercellintheArow.

ThiscanoccurinthefollowingscenarioasinFigures1and2.

SPRINTATLRESEARCHREPORTRR03-ATL-111377-NOVEMBER2003Supposethatatthestartofourstudy,theegressPoPforthedestinationpreﬁx1.1.1.0/24wasPoP20.Supposembytesofpacketstraveltothisdestinationpreﬁxattimet−2,andattimet−1aroutingchangeoccurschangingtheegressPoPtoPoP30.Attimet,zbytesofpacketstraveltothisdestinationpreﬁx.The“stale”trafﬁcmatrixwillshow(10,20)=m,(10,30)=0attimet−2and(10,20)=z,(10,30)=0attimet.Thetrafﬁcmatrixwithroutingchangeswillshow(10,20)=m,(10,30)=0attimet−2and(10,20)=0,(10,30)=zattimet.The“difference”matrixwillshow(10,20)=0,(10,30)=0attimet−2and(10,20)=−z,(10,30)=zattimet.

Notethathereweareonlyconcernedwithintra-ASchangesduetoBGP-i.e.,shiftsintheegressPoPwithinSprint.BGPchangesmaycauseinter-domainpathstochange.Thediffer-encematrixremovestheimpactofinter-domainchangesontraf-ﬁcandonlyfocusesontheimpactduetointra-domainchanges.

V.ANALYSISDATA

WenowdescribethepacketandBGProutingdatathatwecollectfromtheSprintnetworktounderstandifBGProutingchangesimpacthowtrafﬁctraversesthenetwork.A.PacketTraceCollection

TobuildanaccuratePoP-to-PoPtrafﬁcmatrixforanysignif-icantamountoftime,weneedatremendousamountofdata.Sprinthasover40PoPsworldwide,andweneedtocreateap-proximatelya40X40matrix.SomePoPshavehundredsofingresslinks.Thuswewouldneedtocapturepacketheadersfromthousandsofingresslinks.Thisiscurrentlyinfeasible,duetomultiplereasonsincludingcollectionlogistics,storagelimitsandcomputationtimelimits.Instead,wecapturepackettracesfrommultipleingresslinksforseveralhoursatdifferenttimes,asshowninTableI.Weanalyzeourproblemforeachpackettraceindividually.ThusinsteadofbuildingPoP-to-PoPtrafﬁcmatrices,webuildaningresslinktoegressPoPvectorforeachpackettrace,whichwerefertoasatrafﬁcfanout.ThesumofallthetrafﬁcfanoutsfromalltheingresslinksinaPoPformsarowofthetrafﬁcmatrix.IfeachofthetrafﬁcfanoutsisnotaffectedbyBGPchanges,thenthetrafﬁcmatrixisunaffected,whichmakesiteasiertoengineerthenetwork.

Wecapturepackettracesusingthepassivemonitoringinfras-tructuredescribedin[18].Weuseopticalsplitterstotapintoselectedlinksandcollectionsystemsthatstoretheﬁrst44bytesofeverypacket.EverypacketisalsotimestampedusingaGPSclocksignal,whichprovidesaccurateandﬁne-grainedtiminginformation.WepickmultipleingresslinksasshowninTableIinanattempttoobtainpackettracesrepresentativeofthetraf-ﬁcenteringtheSprintnetworkfromasingleingressPoP.ThecategorizationoftheneighboringASesinto“tiers”isbasedontheclassiﬁcationin[19].Theinformationinthistableandtheresultsthatwepresentinlatersectionshavebeenanonymized.ThetracescannotbemadepubliclyavailabletopreservetheprivacyofSprint’scustomersandpeers.However,theyhavebeenmadeavailabletoacademicresearcherswhileatSprinttoperformmanystudies,suchasthisone.Statisticalinformationaboutthesetracesandtheresultsofthesestudiescanbefound

ontheInternet1.B.Approximations

Asigniﬁcantamountofcomputationtimeisrequiredfortheanalysisofthesetraces.Forexample,traceDinTableIrepre-sentsover2.5billionpacketsandconsumes162GBofstorage.Inordertokeepcomputationtimeslow,weemployonesimpli-ﬁcationtechniqueandtwoapproximations.

Intheﬁrstapproximation,insteadofcalculatingandstoringaseparatetrafﬁcfanoutforeveryinstantintimeduringatrace,wecreateafanoutforevery20minuteperiod.Thatis,weaggregateallthepacketsreceivedinevery20minutewindowandcalcu-latethetrafﬁcfanoutduetothosepackets.Thesimpliﬁcationtechniquehereisthatwedonottreatpacketsindividually,butrathertreatthemasaﬂowaggregate.Forevery20minutewin-dow,wegrouppacketsbythedestinationaddress,andlookuptheegressPoPforthisdestinationaddressonce.Thissavesustheoverheadoflookingupthesameaddressmultipletimeswithnolossinaccuracy.Incalculatingthetrafﬁcmatrixwithrout-ingchanges,weuseafreshBGPtableatthestartofevery20minutewindow.Webatchtheroutingtablechangesandcom-puteanewtableevery20minutes.Thustheremaybesomeout-of-dateroutinginformationfromonewindowtothenext.Whilewechoose20minutesarbitrarily,wehaveexperimentedwithdifferentvaluesdownto1minuteintervals.Weﬁndthatthiswindowsizeintroducesnegligibleerrorsinthetrafﬁcfan-outcalculationwhilesmallervaluessigniﬁcantlyslowdownthecomputation.

Thesecondapproximationisthatweonlyconsider99%ofthetrafﬁc.Morespeciﬁcally,weonlyconsiderthelargestﬂows(packetsgroupedbythedestinationaddress)thataccountforatleast99%ofthetrafﬁc.Wehaveobservedthephenomenonthatthereareafewﬂowsthataccountforthemajorityoftrafﬁcandmanyﬂowsthatcontributeaninsigniﬁcantamountoftraf-ﬁc[20].Byignoringthesmallestﬂowsthatcontributeatotalofatmost1%ofthetrafﬁcinany20minutewindow,wesigniﬁ-cantlyreducethecomputationoverhead.Forexample,intraceD,only30,000outof200,000destinationaddressescarry99%ofthetrafﬁc.Thus,ineach20minutewindow,weonlylookup30,000addressesintheroutingtable,insteadofalmost10timesasmany.Thereforethisapproximationmakesthefan-outcom-putationsigniﬁcantlyfasteratthecostofignoringonly1%ofthetotaltrafﬁc.

C.BGPRoutingCollection

TodeterminewhichegressPoPapacketissentto,weneedtocorrelatethepacketheaderswithBGProutinginformation.WecollectBGPdatafromPoPs8and10.WeusetheGNUZebra2routingsoftwaretoconnecttoeachofthesePoPsandcollectroutingupdates.InthecaseofPoP8,weconnecttothesamerouterthatwecollectpackettracesfrom.TheZebralis-tenerconnectsasaniBGProutereﬂectorclientandstoresallrouteupdatesthatarereceived.ForPoP10,theZebralistenerconnectsasacustomerASinaneBGPsession.Eachoftheup-datesistimestampedtoallowcorrelationwiththepackettraces

1Sprint

ATLIP-MonitoringProject,http://ipmon.sprintlabs.com/2GNUZebraRoutingSoftware,http://www.zebra.org/

SPRINTATLRESEARCHREPORTRR03-ATL-111377-NOVEMBER20036

TABLEIPACKETTRACES

TraceABCDEPoP88888Link22313LinkSpeedOC-12OC-12OC-12OC-12OC-12LinkTypeingressingressingressingressingressNeighborTier-2ISPTier-2ISPTier-3ISPTier-2ISPTier-3ISPDate06Aug200206Aug200206Aug200206Aug200207Aug2002Duration(hours)

6.19.96.422.49.6thatwecollect.EachupdatecorrespondstoanactualchangeintheBGProutingtableattherespectiverouter.ThuswecapturealltheBGProutingchangesthatoccurforthegivenrouter.WhilewepresentdatafromtheeBGPlistenerforcompari-son,weprimarilyfocusonouriBGPdata.iBGPdataisricherthaneBGPdatainmanyaspects.ItreﬂectsbothchangesinBGProuteslearnedfromexternalASesbytheSprintnetwork,andchangestoBGProutesforinternaladdresses.ItidentiﬁestheegressrouterwithinSprintforanydestinationpreﬁx,whileaneBGProutingtablefromaparticularcollectionrouterwouldonlyindicatetheaddressofthatcollectionrouterforalldestina-tionpreﬁxes.iBGPdatareﬂectschangesinIGProutingaswell,becauseiftheIGProutingmetricchangesresultinginachangetothebestnexthopBGProuterforapreﬁx,itwillbeseenasachangetothecorrespondingiBGPtableentry,whichwouldnotbetrueofeBGP.Also,itincludessomeprivateBGPcommu-nityattributesthathelpusdeterminethesourceoftheroutingannouncementswithintheSprintnetwork,whichwouldnotbeseenineBGPdata.

VI.RESULTS

WhilewehaveanalyzedallthetracesinTableI,wewillfocusontheresultsfrompackettraceDforbrevity.Ouranalysisforallthetracesproducedverysimilarresults.WepresenttraceDheresinceitisthelongesttrace.A.StabilityoftheBGPRoutingTable

WebeginbyconsideringhowstabletheBGProutingtableis.Iftheroutingtabledoesnotchangeatall,thenitcanhavenonegativeimpactontrafﬁcwithintheSprintnetwork.InFig-ure4,weshowthenumberofBGProutingtablechangesforatypicalweekinPoPs8and10.Therewere765,776eBGProut-ingtablechangesand1,344,375iBGProutingtablechangesduringthisweek.Eachpointinthegraphsshowsthenumberofroutingtablechangesduringa20minutewindow.WeseethatthetypicalnumberofiBGProutingtablechangesisabout133perminute,whileeBGPchangesoccuratabouthalfthatrate.WeobservethatoccasionalspikesareinterspersedamongthiscontinuousBGP“noise”of133changesperminute.Duringthespikes,theaveragenumberofiBGProutingchangesismuchhigher,upto6,500perminute.

InFigure5,weshowahistogramofthenumberofiBGProutechangesduringatypicalweek.Weaggregateroutechangesinto20minutewindows.Weplotthepercentageofnumberofchangesineachwindowontheverticalaxis,withthehorizontalaxisshowingtheactualnumberofchanges.Inthebottomgraph,therangeofthehorizontalaxisislimitedto10,000inorderto

)nib 0e0tu0n5i1m 02( stn0e0v0E50

1234567

Time (days)

)n0ib0 0e0tu1nim0 0020(6 stnev0E0020

1234567

Time (days)

Fig.4.BGProutingtablechangesfromTuesday06August2002toTuesday

13August2002(iBGPontop,eBGPonbottom)

8)%(6 marg4otsiH2001000020000300004000050000Number of updates per 20 minute bin8)%(6 marg4otsiH200200040006000800010000Number of updates per 20 minute binFig.5.HistogramofiBGProutechangesoveratypicalweek

SPRINTATLRESEARCHREPORTRR03-ATL-111377-NOVEMBER20038)%(6 marg4otsiH2001000020000300004000050000Number of updates per 20 minute bin8)%(6 marg4otsiH200200040006000800010000Number of updates per 20 minute binFig.6.HistogramofiBGProutechangesoveratypicalmonth

52sexif0e2rP fo5 1# ni e0g1nahC5 %0PoPs

Fig.7.ChangesinpreﬁxesateachegressPoPduringtraceD

avoiddistortingtheshapeofthegraphwithoutliers.Thisﬁgureillustratesthenoisecharacteristicofroutechangesmoreclearly.Thenumberof20minuteintervalsduringwhich1,000orfewerchangesoccurredisnegligiblysmall.Ontheotherhandthereare1,000−4,000changesper20minuteintervalforamajor-ityoftheentireweek.Figure6plotsthehistogramofchangesoveratypicalmonth.TheshapeissimilartothatinFigure5whichconﬁrmsthatthedistributionofroutechangesissimi-laronlongertime-scales.Wehaveveriﬁedthisbehavioroveraperiodofseveralmonths.

ThepresenceofcontinuousBGProutingtablechangesindi-catesthattheInternet’sroutinginfrastructureundergoescontin-uouschange.Thismayberelatedtothesize,complexityanddistributedcontroloftheInternet.ThusBGPupdateshavethepotentialtoaffectintra-domaintrafﬁccontinuously,andnotjustduringshortperiodsofinstabilityintheInternet.Theseshortperiodsofupdatespikesarerelativelyinfrequent,butweob-servethattheycancauseaten-foldincreaseintherateofrout-ingchange.Itisdifﬁculttoaccuratelyidentifythecauseofsuchspikes.However,signiﬁcanteventssuchasroutercrashes,BGPsessionrestorationandmaintenanceactivitiesarelikelycauses.IfanunusualeventsuchasthelossofconnectivitytoaPoPoramajorneighboringASoccurs,thensigniﬁcanttrafﬁcshiftwillnaturallyoccur.Inthiswork,wedonotfocusontheserareeventsbutinsteadstudytheimpactofroutingtablechangesdur-ingmoretypicaltimeperiods.WeconﬁrmthatnomajorlossofconnectivityoccurredduringtraceDbypresentingFigure7.

Dynamic BGP2.0e+08Static BGP1.5e+081.0e+08020040060080010001200Time(mins)Fig.8.BytesfromtraceDtoPoP2fordynamicBGPtableandstaticBGPtable5e+06

Dynamic BGP−Static BGP

0e+00

−5e+06

200

400

6008001000

1200

Time(mins)

Fig.9.DifferenceinbytesfromtraceDtoPoP2(dynamicBGP-staticBGP)

WetrackthenumberofdestinationpreﬁxesthatexiteachegressPoP.Inthisﬁgure,weplotthemaximumpercentagechangeinthisnumberforeachPoPthroughoutthedurationofthetrace.Weseethatinmostcases,lessthan10%ofthetotalpreﬁxesex-itingateachPoPwereaddedorremovedfromtheBGProutingtable.Thisistypicalbehaviorduringtheothertracesthatweanalyzed.Thetwocasesof25%and12.5%changewereduetomaintenanceattwonewegressPoPsbeingprovisionedintotheSprintnetwork.NotrafﬁcexitedthosetwoPoPsfromtraceD.B.OverallImpactonIntra-DomainTrafﬁc

WenowinvestigateifthiscontinuousnoiseofBGProutingtablechangesaffectshowtrafﬁcisforwardedintheSprintnet-work.Figure8showsthetrafﬁcvolumeper20minutesforpackettraceDtowardaparticularegressPoPintheSprintnet-

0052y0cn0e5u1qerF00500

20406080100

Percentage Shift

Fig.10.HistogramofegressPoP%trafﬁcshiftfortraceD

SPRINTATLRESEARCHREPORTRR03-ATL-111377-NOVEMBER20038

TABLEII

SUMMARYOFTRACERESULTS

Trace#ofCellsAvgShiftperCellStdDevofShiftCellsWith>5%Shift

VolumeShiftTotalVolume%VolumeShiftA6480.17%1.62B10440.03%0.24C6840.60%7.53D24120.07%2.03E10082.35%15.05work.OnelineindicatesthetrafﬁccomputedwithastaticBGPtablewhiletheotheristhatwithadynamicBGPtable.Theﬂuc-tuationsobservedinbothcasesariseduetothevariabilityinher-entintrafﬁc,suchasduetouserbehavior.Thedifferencebe-tweenthetwolinesshowshowmuchofthistrafﬁcshiftedinsidetheSprintnetworkduetoBGPchanges.Sincethetwolinesareveryclosetoeachother,thisvariabilityisnegligible.Figure9plotsthedifferenceinthenumberofbytestowardtheegressPoPforthetwocases,bysubtractingthevalueforthestaticBGPcasefromthevaluefromthedynamicBGPcase.ThesumofthisdifferenceacrossallingresslinksforeachegressPoPformsthedifferencematrixthatwepreviouslydescribed.Weseethatthereisnodifferenceformostofthetimeintervals.Themaximumdifferenceisabout7MBforany20minutewindow,comparedto120MBoftrafﬁctothisPoPatthattime,whichisonly5.8%.InFigure10weshowahistogramofthenumberoftimeintervalsacrossallPoPsfortraceDbythepercentageshiftintrafﬁc.Weseethatlessthan5%oftrafﬁcshiftoccurredinalmostallcases.

InTableIIwesummarizetheresultsforallthetraces.Thesecondcolumnshowsthetotalnumberofcellsinthetrafﬁcfanout(i.e.,thenumberof20minutetimeperiodsinthetracemultipliedbythenumberofegressPoPs).The“AvgShiftperCell”columnshowsthepercentageoftrafﬁcshiftaveragedacrossallthecellsandthenextcolumnshowsthestandardde-viationofthisvalue.The“CellsWith>5%Shift”columnshowshowmanyofthesecellshadmorethana5%trafﬁcshift.WeﬁndthattheaverageshiftoveralltimeperiodsandPoPsisonly0.07%fortraceD.Inonly2caseswasthepercentageshiftmorethan5%.However,inbothcases,theactualvolumeoftrafﬁcthatshiftedwasonlyseveralMB.FromthelastthreecolumnsinTableII,weshowthatofthe1TBoftrafﬁcvolumeintraceD,only145MBchangedtheegressPoPasaresultofaBGPchange,whichisonly0.01%.

Asshownbythelastcolumn,verysmallpercentagesoftheingresstrafﬁcmovearoundduetoBGPchangesacrossallthetracesthatweanalyzed.However,therearesomecaseswheretrafﬁcfromaningresslinktocertainPoPsforcertaintimeperi-odsshifts.Whilethesedonotrepresentlargevolumesoftrafﬁcthatcanimpacttrafﬁcengineeringdecisions,theycanimpacttheperformanceofindividualapplications.Delay-sensitiveap-plicationssuchasvoice-over-IPmayexperiencedegradedappli-cationqualityduetotrafﬁcshiftsbetweenegressPoPsforindi-vidualpreﬁxes.Forexample,alargevolumeoftrafﬁctowardacustomernetworkP1mayshiftfrequentlybetweentwoegressPoPsAandB,whilethetrafﬁctowardanothercustomernet-workP2mayshiftinthereversedirection.Whilethismaylead

4103MB398GB0.03%058MB791GB0.01%433MB556GB0.01%2145MB1TB0.01%24144MB919GB0.02%AS Y󰀀PoP 2󰀀Sprint Network󰀀PoP 8󰀀PoP 9󰀀AS X󰀀Fig.11.TrafﬁcshiftfromPoPs2and8toPoP9

toverylittlechangeinthetotalvolumeoftrafﬁctowardegressPoPsAandB,customersP1andP2mayexperiencesigniﬁcantdelayﬂuctuationsacrosstheSprintnetwork.Howeverweﬁndthatforourpackettraces,thegreatestnumberofshiftsbetweenegressPoPsacrossallﬂows(asdeﬁnedinSectionV)isonly3.Forexample,intraceD,therewere6720-minutewindows,withanaverageof23,409ﬂowsfor99%ofthetrafﬁcineachwindow.Anaverageof5−6ﬂowsexperiencedashiftintheegressPoPperwindow.Therefore,onlysmallnumbersdelay-sensitiveﬂowsarelikelytoexperienceﬂuctuationsinqualityacrosstheSprintnetwork.

C.SpeciﬁcCasesofEgressShiftsforIntra-DomainTrafﬁcWenowexaminetwoparticularcasesofvariabilityinordertogaindeeperinsightsintosuchoccurrences.IntraceD,about42%ofthetotaltrafﬁcvariabilityinvolvedonlytwodestinationnetworks.ThesetwonetworksconnecttotheSprintnetworkinmultipleplaces,asshowninFigure11.ThisvariabilityoccurredbetweenthreePoPsthatarespreadacrosstheeastcoastoftheUS.WefoundthattrafﬁcgoingtoASXshiftedfromthelongerASpathviaPoP8totheshorterASpathviaPoP9,whiletraf-ﬁctoASYshiftedfromtheshorterASpathviaPoP2tothelongeroneviaPoP9.Ineachcase,theBGPpathchangedonlyoncethroughouttraceD.Thesechangesintheinter-domainpathscausedachangeintheegressPoPforthesedestinationad-dressesbecausedifferentneighboringASespeerwiththeSprint

SPRINTATLRESEARCHREPORTRR03-ATL-111377-NOVEMBER20032e+06

Dynamic BGP−Static BGP

0e+00

−2e+06−4e+06

0200400

60080010001200

Time(mins)

Fig.12.DifferenceinbytesfromtraceDtoPoP8(dynamicBGP-staticBGP)

1e+07

Dynamic BGP−Static BGP

5e+06

0e+00

200

400

6008001000

1200

Time(mins)

Fig.13.DifferenceinbytesfromtraceDtoPoP9(dynamicBGP-staticBGP)

networkindifferentPoPs.InFigures9,12and13,weshowtheshiftintrafﬁcexitingatPoPs2,8and9.WecanseethatthedipsinFigures9and12correspondtothepeaksinFigure13.Thesetwoexamplesaretypicalofthevariabilityinthefan-outtoegressPoPs.

•homedWeobservedestinationtrafﬁcnetworks.

shiftingbetweendifferentpathstomulti-•eachOftentrace.

theBGPpathwillchangeonlyonceortwiceduring•shifts.

OnlyafewnetworksareinvolvedinthemajorityoftrafﬁcVII.LIMITEDIMPACTOFBGPCHANGESONTRAFFICIntheprevioussection,weshowedthatthetrafﬁcfan-outintheSprintnetworkishardlyaffectedbychangesinBGProutes.YetthereisasigniﬁcantamountofBGPactivityallthetime.Inthissection,weexplainthisdiscrepancy.

A.DistributionofBGPChangesandTrafﬁcAcrossASesWebeginbyexaminingwhetherroutingtablechanges,traf-ﬁcandtrafﬁcshiftsaresimilarlydistributedacrossalltheASes.Sincethereareover14,000ASes,wesummarizetheASesinto5distinctcategoriesforsimplicity.ThiscategorizationisbasedonSubramanianetal.[19].Tier-1ASescorrespondtolargeglobalISPssuchasSprint.Tier-2ASestendtobenationalISPs,Tier-3andTier-4areregionalISPs.Tier-5ASesarestubnetworksthatdonotprovideconnectivitytootherASes.Ingen-eral,aTier-nASisacustomerofoneormoreTier-(n-k)ASes.InFigure14,wecompareBGProutechanges,trafﬁcdestina-tionsandtrafﬁcshiftsfortheoriginASes(i.e.,theterminating

70󰀀60󰀀50󰀀All Traffic󰀀Traffic Shift󰀀%󰀀

40󰀀All BGP Updates󰀀30󰀀20󰀀10󰀀0󰀀Tier1󰀀

Tier2󰀀Tier3󰀀Tier4󰀀Tier5󰀀

Origin AS󰀀

Fig.14.iBGProutechanges,trafﬁcandtrafﬁcshiftsduringtraceDbyorigin

80󰀀70󰀀60󰀀All Traffic󰀀50󰀀Traffic Shift󰀀All BGP Updates󰀀%󰀀

40󰀀30󰀀20󰀀10󰀀0󰀀Tier1󰀀

Tier2󰀀

Tier3󰀀

Tier4󰀀

Tier5󰀀

Next AS󰀀

Fig.15.iBGProutechanges,trafﬁcandtrafﬁcshiftsduringtraceDbynextAS

ASalongthepath).Weseethatthemajorityoftrafﬁcisdes-tinedtoTier-5ASes.ThisisconsistentwiththenotionthatthetiersprovideconnectivitytoASesexceptforTier-5stubASesthathousetheendhosts.Weseeasimilartrendwiththenum-berofBGPchanges.MostoftheroutesthatareaffectedaretopreﬁxesterminatinginTier-5ASes.However,weseethatthetrafﬁcshiftsaredisproportionatelymorefrequentfordesti-nationpreﬁxesinTier-4ASes.Thisisduetoafewnetworksbeinginvolvedinthemajorityoftrafﬁcshifts,asweshowedintheprevioussection.

InFigure15,wecomparethesamedistributionsacrossthenextASes(i.e.,theneighboringASthattrafﬁcorpathsgoto).WeseethatmosttrafﬁcleavestheSprintnetworktoTier-2ASes.ThisisconsistentwiththenotionthatSprintbeingaTier-1globalISPprovidesconnectivitytomanyTier-2nationalISPs.However,weseethatthemajorityofBGProutechangesarere-ceivedfromneighboringTier-3ASes.Consistently,themajorityoftrafﬁcshiftsinvolveneighboringTier-3ASes.Again,thisisduetoafewnetworksbeinginvolvedinthemajorityoftrafﬁcshifts,asweshowedintheprevioussection.Tier-1ASesalsoaccountforasigniﬁcantnumberofBGPchanges.SinceSprintpeersdirectlywithTier-1ASes,andsincethesefewASestran-sitmorepreﬁxesthanotherASes,tier-1ASesshowmoreBGPchangesinFigure15thaninFigure14.

ThusweﬁndthatmosttrafﬁcleavestheSprintAStoneigh-boringTier-2ASesandmosttrafﬁcterminatesatTier-5ASes.However,thetrafﬁcshiftsarenotdistributedacrosstheseASesinthesamemannerandtheBGPchangesarenotdistributedin

SPRINTATLRESEARCHREPORTRR03-ATL-111377-NOVEMBER2003e2000tunim 15001/seta1000dpu P500GB #14:00018:0000:0006:0012:00Aug 6, 2002 Aug 7, 2002 (UTC) etu1000nim 1800/sex600iferP400 detc200effA #14:00018:0000:0006:0012:00Aug 6, 2002 Aug 7, 2002 (UTC) Fig.16.iBGProutechangesandpreﬁxesaffectedduringtraceD

seta# of Prefixesdp10,000# of BGP updatesU & sex100iferP00 4 8 121620242832Prefix Length200xAverage # of BGP updates/prefixifer150p/set100adpU50 #0048121620242832Prefix LengthFig.17.iBGProutechangesandpreﬁxlengthduringtraceD

thesamewayastrafﬁcshifts.ThiscanmeanthateithertheBGPchangesfromeachASarenotspreadevenlyacrosstheBGPta-bleortheBGPchangesdonotcauseegressPoPchanges.Wenowexploretheﬁrstpossibilityandthenexplorethesecondpos-sibilityattheendofthissection.

B.DistributionofBGPChangesAcrosstheRoutingTableInFigure16,weshowthenumberofroutingtablechangesandthenumberofpreﬁxesaffected.Weagainseeinthetopgraphthatanaverageof133routingtablechangesoccureveryminute.Inthesecondgraph,weseethatonaverage,roughly70routingtableentriesareaffectedeveryminute.Evenduringthespikeof1,500routingtablechangesearlyinthetrace,only900routingtableentrieswereaffected.Thisshowsthatthesamedestinationpreﬁxcanreceivemultipleroutingchangeswithinashorttimeperiod.

InFigure17,weshowthedistributionofroutechangeswithpreﬁxlength.Fromthetopgraph,weseethatthenumberofchanges(darkverticalbars)doesnotdirectlycorrespondtothenumberofroutingtableentries(lightverticalbars)foreachpre-ﬁxrange.Inthesecondgraph,wenormalizethenumberofchangesbythenumberofentriesforeachpreﬁx.Weseethat/8addressesreceiveanunusuallyhighnumberofchanges./8pre-ﬁxesconstitutelessthan0.01%oftheBGPtable,butaccountfor18%oftheroutechangesreceived./28,/30,/32address

2000etunim1500/seta1000dpu la500toT14:00018:0000:0006:0012:00Aug 6, 2002 Aug 7, 2002 (UTC)e20001500Fig.18.BGProutechangesforallpreﬁxesduringtraceD100015etun500im/10setad14:00018:0000:0006:0012:00pu5 latoT14:00018:0000:0006:0012:00Aug 6, 2002 Aug 7, 2002 (UTC) 15Fig.19.BGProutechangesforheavy-hittersduringtraceD10preﬁxesalso5receiveahighnumberofupdatesperroutingtableentry.Thesemorespeciﬁcentriestypicallyrepresentaddresses14:000internalwithinthe18:00Sprintnetwork00:00andcustomer06:00networks12:00thatdonothaveapublicASnumber.TheyareusuallyrepresentedintheeBGProutingtablebyalargeraddressrange.

ThusweseethatBGProutingtablechangesarenotspreadevenlyacrosstheroutingtable.Someroutingtableentriesre-ceivemultiplechanges,andentriesofcertainpreﬁxlengthsaremorepronethanothers.Thusifmostofthetrafﬁcissunkbydestinationaddressesthatareinthesechange-pronepreﬁxes,thenthereismorepotentialforshift.

C.DistributionofBGPChangesAcrossTrafﬁc

SinceBGProutechangesarenotspreaduniformlyacrosstheroutingtable,andsincesubsequenttrafﬁcshiftsarealsonotproportionatelyspreadacrossneighboringandoriginASes,wenowexaminehowBGProutechangesarespreadacrosstraf-ﬁc.Speciﬁcally,weexaminewhichpreﬁxescarrythemajor-ityofthetrafﬁcandexaminehowtheyareaffectedbyBGProutechanges.Ourpriorwork[17],[20]showedthatthetraf-ﬁcinSprint’snetworkcontainsheavy-hitters-i.e.,asmallsetofdestinationnetworkpreﬁxesthattogethercontributeaverylargeportionoftrafﬁc.Weobservedsimilarheavy-hittersinthepackettracesweanalyzedinthispaper.IntraceD,wefoundthat30,000addressesoutofatotalof200,000inthetraceac-countedfor99%ofthetrafﬁc,whichisabout15%ofthead-dresses.Only1.5%oftheaddressesinthetraceaccountedfor80%ofthetrafﬁc.

InFigure18,weseeagainthenumberofiBGProutechangesduringtraceD,withtheaverageofabout133changesperminute.Incontrast,Figure19showsthenumberofchangesforonlythedestinationpreﬁxesthataccountforatleast80%ofthetrafﬁc.Weseeasigniﬁcantlylowernumberofroutechanges.Themaximumnumberofchangesinanyoneminuteintervalisonly15,whileacrossallpreﬁxes,themaximumnumberis1,600.ThisshowsthatonlyasmallfractionoftheBGProutechangesaffectthemajorityoftrafﬁc.ThisistrueofallthetracesweexaminedinTableI.

1000500SPRINTATLRESEARCHREPORTRR03-ATL-111377-NOVEMBER200314:00018:0000:0006:0012:00Aug 6, 2002 Aug 7, 2002 (UTC)etu2000nim/s1500egnah1000C15 poH500txe10N14:00018:0000:0006:0012:00Aug 6, 2002 5Aug 7, 2002 (UTC)Fig.20.0NexthopBGProutechangesforallpreﬁxesduringtraceD14:0018:0000:0006:0012:00Aug 6, 2002 Aug 7, 2002 (UTC) et15unim/se10gnahC p5oHtxeN14:00018:0000:0006:0012:00Aug 6, 2002 Aug 7, 2002 (UTC) Fig.21.NexthopBGProutechangesforheavy-hittersduringtraceD

However,forourparticularproblem,weareonlyconcernedwithroutechangesthataffectthenexthopattribute.Thenexthopattributedeterminestheegressrouter,andthustheegressPoP,thattrafﬁctoaparticularnetworkpreﬁxwillgoto.OnlychangestothisattributecancauseshiftintheegressPoPfortrafﬁc.InFigure20,weshowthenumberofBGProutechangesthataffectedthenexthopforallpreﬁxes.WeseethatthenumberofeventshasdroppedtoabouthalfofthatseeninFigure18.Further,weareonlyconcernedwithchangestothenexthopforthemajorityoftrafﬁc,whichweshowinFigure21.HereweseeanevensmallernumberofroutechangesthataffectourproblemofegressPoPshift.Only11%oftheBGPchangesforheavy-hitterscausednexthopchanges,while63%oftheBGPchangesforallpreﬁxescausednexthopchanges.

Weconcludethatheavy-hittersreceivefewerroutechangesthanmostpreﬁxes,andfurther,asigniﬁcantlylowernumberofroutechangesforheavy-hitterscausesnexthopchanges.Forourproblem,veryfewofthelargenumberofroutechangesmatter.Only0.05%ofthetotalroutechangesduringtraceDcausednexthopchangesforheavy-hitterdestinationad-dresses.Thesearetheonlyonesthatcanpotentiallyaffecttraf-ﬁcfan-outtowardegressPoPs,althoughinsomecasesthenext-hopchangemaybefromoneroutertoanotherwithinthesameegressPoP.ThisexplainsourﬁndingsthatBGProutechangescausenomorethan0.03%oftrafﬁcvolumetoshifttheegressPoP.

Therecanbetworeasonsforthisphenomenon.First,ifanet-workpreﬁxisunstablethenpackettravelingtowarditmaybefrequentlydisrupted,causingTCPconnectionstobackoffandeventerminate.Second,networksthatattractlargevolumesoftrafﬁcmayhavemoreresourcestoaffordgoodnetworkadmin-istrationandstableBGPconﬁgurationswiththeirpeers.Re-gardlessofthecauseofstabilityofheavy-hitters,thereisasig-niﬁcantamountofinstabilityfornon-heavy-hitters.However,itisdifﬁculttoaccuratelydeterminethecauseoftheinstability.Anyofalargenumberofnetworkevents(fromintra-domainIGPmetricchangestorouterconﬁgurationchangesinaneigh-boringAS)cancauseaBGPchangetooccur.SinceBGPis

apathvectorprotocol,itisdifﬁculttoevendeterminetheAS

thatoriginatedaparticularroutingchange,letalonethecauseofit.Grifﬁn[14]showsthataBGPnetworkcannondeterministi-callychangeroutingeventsincomplexandnon-intuitivewaysastheyarepropagated.WhileitmaybepossibletostudylargenumbersofcorrelatedroutingchangesfrommultipleBGPvan-tagepoints,webelieveitisdifﬁculttoaccuratelydeterminethecausebehindtheinstabilityofindividualdestinationpreﬁxes.

VIII.CONCLUSIONS

RecentstudiesofBGPhaveshownasigniﬁcantgrowthinthesizeanddynamicsofBGPtables.ThishasledtoconcernsaboutwhatimpactthesetrendsinBGPhaveontheInternet.WefocusonthisissueforalargeISPsuchasSprint.LargeISPnetworksaredesignedandmaintainedonthebasisofmet-ricssuchaslatencyandtheneedtoprovisionthenetworkforfuturegrowthandchangesintrafﬁc.Thisengineeringistyp-icallybasedoncalculatingatrafﬁcmatrixtodeterminetrafﬁcdemandsfordifferentpartsofthenetwork.FluctuationsinBGProutescancausethistrafﬁcmatrixtochange,invalidatingtheengineeringeffort.Further,latencysensitiveapplicationscanbeadverselyaffected.

WehavecorrelatediBGProutechangeswithpackettracesinSprint’sIPnetworktomeasurethevariabilityintrafﬁcfan-outfromingresslinkstoegressPoPs.Wehavepresentedamethod-ologythatseparatesthevariabilityinherentintrafﬁcfromthevariabilitythatisduetoBGPchangeswithinanAS.FromouranalysisofseveralpackettracesandassociatedBGPchanges,ourﬁndingsare:

•ingTherechangesiscontinuousperminute.iBGPThisnoiseisinterspersedofmorethanwithahundredrareperiodsrout-ofhighchanges,asmuchasseveralthousandperminute.eBGPchangesoccuratabouthalfthisrate.

•linkHardlythatweanymeasuredfractionofexperiencedthevolumeanofegresstrafﬁcfromPoPshiftanyingressduetoBGPchanges.Atanytime,onlyseveralﬂowsexperiencedanegressPoPshiftoutoftypicallytensofthousandsofﬂowsinatrace.Affectedﬂowsexperiencednomorethanafewshifts.•ofOnlythetrafﬁcfewnetworksshift.Thistendinvolvestobeinvolvedtheinter-domaininasigniﬁcantpathchanging,fractionresultingintheintra-domainpathchanging.

•entriesBGPreceiveroutechangesmultiplearechanges,notdistributedandsomeevenly.aremoreSomelikelyroutetoreceiveachangethanothers.BGPchangesandtrafﬁcseemsimilarlydistributedbyoriginAS,whileBGPchangesandtraf-ﬁcshiftsseemsimilarlydistributedbynextAS.RelativelyfewBGPchangesaffectthemajorityofthetrafﬁc,andevenfewerchangetheegressPoP.

ThetrafﬁcfanoutislargelyunaffectedbyBGProutingchangesforseverallinksthatwehaveconsidered.Iftheselinksarerepresentativeofalltheingresslinks,thenitisreasonabletoassumethatthetrafﬁcmatrixisunaffected.Thereforeitispossibletoperformnetworkengineeringandprovisioningtaskswithoutconcernfortheeffectofglobalroutingchanges.BGPchangesareunlikelytocauselatencyvariationswithinanASformosttrafﬁc.Yet,someopenissuesremain.Areheavy-hittersrelativelyimmunefromchangeduetotheengineeringofnet-worksordoTCPdynamicsdictatethatonlystableroutescan

SPRINTATLRESEARCHREPORTRR03-ATL-111377-NOVEMBER200312

supportheavy-hitters?Unstableroutesmayreﬂectconnectivitythatisundergoingrapidchangesorheavypacketloss,andthatmaycausetheTCPcongestioncontrolalgorithmtocutbackitssendingrate.AnotheropenissueisthatsincethereissomuchBGPchange,thecauseandoriginofsuchupdatesshouldbeun-derstood.However,duetothenon-linkstatenatureofBGP,itisdifﬁculttoaccuratelyidentifythecauseofindividualupdates.CorrelationbetweensuccessiveupdatesfromseverallocationsintheInternetmayprovidebettersuccess.ThisworkexploredaspeciﬁceffectofBGPchangesontheSprintnetwork,i.e.vari-abilityinintra-domaintrafﬁcpatterns,duringnormalnetworkbehavior.Periodicnetworkmaintenanceandlinkfailuresmaycauseadditionalimpactontrafﬁcthatwehavenotexplored.

IX.ACKNOWLEDGEMENTS

OurworkwouldnothavebeenpossiblewithoutthehelpofSprintlinkEngineeringandOperationsincollectingBGPandpackettracesfromthenetwork.Inparticular,wewanttothankDaveMeyer,RyanMcDowellandMujahidKhan.

REFERENCES

[1][2][3][4][5][6][7][8][9][10][11][12][13][14][15][16][17][18][19][20]

D.Oran,“OSIIS-ISintra-domainroutingprotocol,”RFC1142,IETF,February1990.

J.Moy,“OSPFversion2,”RFC1583,IETF,March1994.

J.W.Stewart,BGP4:Inter-DomainRoutingintheInternet.Addison-Wesley,1998.

Y.Vardi,“Networktomography:estimatingsource-destinationtrafﬁcin-tensitiesfromlinkdata,”JournaloftheAmericanStatisticalAssociation,vol.91,no.433,pp.365–377,1996.

C.TebaldiandM.West,“Bayesianinferenceonnetworktrafﬁcusinglinkcountdata,”JournaloftheAmericanStatisticalAssociation,vol.93,no.442,pp.557–576,1998.

J.Cao,D.Davis,S.Wiel,andB.Yu,“Time-varyingnetworktomography:Routerlinkdata,”JournaloftheAmericanStatisticalAssociation,vol.95,pp.1063–1075,2000.

Y.Zhang,M.Roughan,N.Dufﬁeld,andA.Greeberg,“Fastaccuratecom-putationoflarge-scaleIPtrafﬁcmatricesfromlinkloads,”inProc.ACMSIGMETRICS,June2003.

G.Huston,“AnalyzingtheInternet’sBGPRoutingTable,”CiscoInternetProtocolJournal,March2001.

T.Bu,L.Gao,andD.Towsley,“Onroutingtablegrowth,”inProc.IEEEGlobalInternetSymposium,2002.

J.Rexford,J.Wang,Z.Xiao,andY.Zhang,“BGProutingstabilityofpopulardestinations,”inProc.InternetMeasurementWorkshop,2002.S.UhligandO.Bonaventure,“Implicationsofinterdomaintrafﬁccharac-teristicsontrafﬁcengineering,”EuropeanTransactionsonTelecommuni-cations,2002.

S.Agarwal,C.-N.Chuah,andR.H.Katz,“OPCA:Robustinterdomainpolicyroutingandtrafﬁccontrol,”Proc.IEEEInternationalConferenceonOpenArchitecturesandNetworkProgramming,2003.

CiscoSystemsInc.,“CiscoIOSIPandIProutingcommandreference,release12.1.”

T.G.Grifﬁn,“Whatisthesoundofonerouteﬂapping?,”inNetworkMod-elingandSimulationSummerWorkshop,Dartmouth,2002.

Labovitz,Malan,andJahanian,“Internetroutinginstability,”inProc.ACMSIGCOMM,1997.

A.Medina,N.Taft,K.Salamatian,S.Bhattacharyya,andC.Diot,“TrafﬁcMatrixEstimation:ExistingTechniquesandNewDirections,”inProc.ACMSIGCOMM,August2002.

S.Bhattacharyya,C.Diot,J.Jetcheva,andN.Taft,“Pop-levelandaccess-link-leveltrafﬁcdynamicsinatier-1PoP,”inProc.InternetMeasurementWorkshop,2001.

C.Fraleigh,C.Diot,B.Lyles,S.Moon,P.Owezarski,K.Papagiannaki,andF.Tobagi,“DesignandDeploymentofaPassiveMonitoringInfras-tructure,”inPassiveandActiveMeasurementWorkshop,April2001.

L.Subramanian,S.Agarwal,J.Rexford,andR.H.Katz,“CharacterizingtheInternethierarchyfrommultiplevantagepoints,”Proc.IEEEINFO-COM,2002.

K.Papagiannaki,N.Taft,S.Bhattacharyya,P.Thiran,K.Salamatian,andC.Diot,“ApragmaticdeﬁnitionofelephantsinInternetbackbonetrafﬁc,”Proc.InternetMeasurementWorkshop,2002.

因篇幅问题不能全部显示，请点此查看更多更全内容

查看全文

全部栏目

The Impact of BGP Dynamics on Intra-Domain Traffic