TheImpatofInternetPoliyandTopologyonDelayedRoutingConvergeneCraigLabovitz,RogerWattenhofer,SrinivasanVenkataharyMirosoftResearhflabovit,rogerwa,heenugmirosoft.omAbhaAhujaMeritNetwork,In.ahujamerit.eduJuly2000TehnialReportMSR-TR-2000-74MirosoftResearhMirosoftCorporationOneMirosoftWayRedmond,WA98052’ssustainedexponentialgrowthandtheontinuedemergeneofnewandvariednetworkappliationsprovidestestamenttothesalabilityofthebakboneinfrastrutureandprotools.TheoriginalTCP/IPdeisiontoplaenetworkintelligeneandstatealmostexlusivelyonend-nodeshasenabledadiverseprogenyofappliationsrangingfromMP3 leexhangetoollaborativelearning.Thissalability,however,omesataprie.Sineitsommerialin-eptionin1995,theInternethaslaggedbehindthepubliswithedtelephonenetwork(PSTN)inavailability,reliabilityandqualityofservie(QoS).Thisrel-ativelakofreliabilitystemsinpartfromtheabseneofintermediatebakbonestateandsynhronizationbetweenrouters.Despitetheremarkabletoleranedemonstratedbytoday’send-usersforfailuresanddelaysinemailandwebservies,therelativelakofInternetbakbonereliabilityposesasigni anthallengeforemergingtransation-orientedandinterativeappliationslikeIn-ternettelephony,onlinebusinessandollaboratories.AlthoughreentadvanesintheIETF’sDi erentiatedServiesworkinggrouppromisetoimprovetheperformaneofappliation-levelservieswithinsomenetworks,arossthewide-areaInternettheseQoSalgorithmsareusuallyprediatedontheexisteneofastableunderlyingforwardinginfrastruture.Inreentwork,weshowedthattheInternetlakse etiveinter-domainpathfail-over[1℄.Spei ally,wefoundthatmulti-homedInternetsitesmayexpe-rieneperiodsofdegradedperformaneaswellasompletelossofonnetivitypersisting fteenminutesormoreafterasinglefault.WeshowedthatmostofthelatenyinInternetfail-overstemsfromdelayedonvergene,orthetemporaryroutingtableosillationsformedduringtheop-erationofthepathseletionproessonInternetbakboneroutersafterafault.Unlikeswithesinthepublitelephonynetworkwhihexhibitfailoverontheor-derofmilliseonds,ouranalysisfoundthatinter-domainroutersinthepaketswithedInternetmaytakeseveralminutestoreahaonsistentviewofthenetworktopologyafterafault.TheurrentInternetinter-domainroutingprotool,BGP,evolvedfromear-lierdistanevetorroutingalgorithms.Theseprotools,inludingRIP[2℄,su erfromanumberofwell-doumentedproblems,inludingslowonvergenetimes[3℄.Distanevetorroutingrequiresthateahnodemaintainthedis-tanefromitselftoeahpossibledestinationandthevetor,orneighbor,tousetoreahthatdestination.Wheneverthisonnetivityinformationhanges,theroutertransmitsitsnewdistanevetortoeahofitsneighbors,allowingeahtorealulateitsroutingtable.Theount-to-in nityproblem[2℄providestheanonialexampleusedtoillustratetheslowonvergeneindistanevetorrouting.TheadoptionofthepathvetorinBGPiswidelyandinorretlybelievedtohave\solvedtheroutingtableosillationproblemsexhibitedbyRIP.Instead,weshowedin[1℄thattheadoptionofthepathvetorexponentiallyexaerbates1thenumberofpotentialroutingtableosillations.Spei ally,wefoundthatadefaulton guration(i.e.onewithoutadditionaladministrativelyaddedpoli-iesor lters)ofnBGPautonomoussystemsonnetedinaompletegraphmaypotentiallyexploren!routes,orallpossiblepathsofallpossiblelengthsbetweeneahASafterafault.ThisuppertheoretiboundonBGPonvergeneomparespoorlywithearlierroutingprotools,suhasRIPwhihhavebeenshowntohaveO(n3)omputationalomplexity[4℄.Webasedourearlieranalysisonasimpli ed,abstratmodelofBGPinter-onnetivity.Thismodelnegletedtheimpatofroutingpoliies,morerealistitimingassumptionsandinter-ASonnetivityontheproessofdelayedonver-gene.AlthoughourinitialmodelprovidesausefultheoretiupperboundonBGPdistributedomputation,wenotethatthisboundisunlikelytoourinpratie.Inthiswork,weexpandonourearliere ortbyexploringthemeasuredonvergenebehaviorsof\realtopologies,inludingmorethan20uniqueBGProuteadvertisementsbetweenmorethan200pairsofInternetservieproviders(ISPs).WealsoprovideanalysisofBGPbehavioringeneralnetworktopologiesandunderothermorerealistiassumptions.Ourmajorresultsinlude: ThetimeomplexityforInternetfail-overonvergeneis30 (n)seonds,wherenisthelengthofthelongestbakuppathbetweenthesoureandanydestinationautonomoussystemforaroute. Onaverage,routesfromustomersoflargerISPsexhibitfasteronver-genethanroutesannounedbyustomersofsmallerInternetproviders. Errantpathsarefrequentlyexploredduringdelayedonvergene.These\vagabondpathslikelystemfrommison gurationorsoftwarebugs. MostInternetroutesexhibitmultiplebakuppathswhihtransitseveraltimesthenumberofInternetprovidersassteadystatepaths.Theremainderofthispaperisorganizedasfollows:InSetion0.2,wepro-videsomebakgroundandrelatedwork.Setion0.3disussesourexperimentaldataolletioninfrastruture.InSetion0.4,wepresentsurveyresultsonISPspoliymehanismsanddisusstheimpatofthesepoliiesonthe owofrout-inginformation.InSetion0.5,wepresentbothempirialobservationsaswellasquantitativeanalysisoftherelationshipbetweenspei Internettopologialon gurationsandtherateofonvergene.Wedemonstratearelationshipbe-tweentheonvergenedelayofarouteannounedbetweentwoprovidersandthelongestp