Achieving convergence-free routing using failure-carrying packets

Karthik Kalambur LakshminarayananMatthew Chapman CaesarMurali RanganThomas AndersonScott ShenkerIon Stoica

Electrical Engineering and Computer SciencesUniversity of California at Berkeley

Technical Report No. UCB/EECS-2007-28

http://www.eecs.berkeley.edu/Pubs/TechRpts/2007/EECS-2007-28.html

February 22, 2007

Copyright © 2007, by the author(s).

All rights reserved.

Permission to make digital or hard copies of all or part of this work forpersonal or classroom use is granted without fee provided that copies arenot made or distributed for profit or commercial advantage and that copiesbear this notice and the full citation on the first page. To copy otherwise, torepublish, to post on servers or to redistribute to lists, requires prior specificpermission.

AchievingConvergence-FreeRoutingusing

Failure-CarryingPackets

K.LakshminarayananM.CaesarM.RanganT.AndersonS.ShenkerI.Stoica

UniversityofCalifornia,BerkeleyandUniversityofWashington

Abstract

Currentdistributedroutingparadigms(suchaslink-state,distance-vector,andpath-vector)involveaconvergencepro-cessconsistingofaniterativeexplorationofintermediateroutestriggeredbycertaineventssuchaslinkfailures.Theconvergenceprocessincreasesrouterload,introducesout-agesandtransientloops,andslowsreactiontofailures.Weproposeanewroutingparadigmwherethegoalisnottore-ducetheconvergencetimesbutrathertoeliminatethecon-vergenceprocesscompletely.Tothisend,weproposeatech-niquecalledFailure-CarryingPackets(FCP)thatallowsdatapacketstoautonomouslydiscoveraworkingpathwithoutrequiringcompletelyup-to-datestateinrouters.Oursimula-tions,performedusingreal-worldfailuretracesandRocket-fueltopologies,showthat:(a)theoverheadofFCPisverylow,(b)unliketraditionallink-staterouting(suchasOSPF),FCPcanprovidebothlowloss-rateaswellaslowcontroloverhead,(c)comparedtopriorworkinbackuppathpre-computations,FCPprovidesbetterroutingguaranteesunderfailuresdespitemaintaininglesserstateattherouters.

1Introduction

Recentlarge-scaledeploymentsofdelayandloss-sensitiveapplicationshaveledtostringentdemandsonrouting.LostordelayedpacketsinapplicationssuchasVoiceoverIP(VoIP),streamingmedia,gaming,andtelecommuting/videoconferencingapplicationscanresultinsignificantperfor-mancedegradation.ISPshencehavestrongincentivestore-ducedelayandlossontheirnetworks,astheseareoftenkeymetricsusedwhennegotiatingService-LevelAgreements(SLAs)associatedwithsuchapplications.Routingconver-genceisoneofthekeyimpedimentstomeetingstrictSLAs.Traditionalroutingparadigms—distance-vector,path-vector,andlink-state—differsubstantiallyinthenatureofthestatemaintainedbyandexchangedbetweenrouters.However,alltheseparadigmsrelyonprotocolmessagestoalertroutersaboutchangesinthenetworktopology.Itisonlyafterthenewsofatopologychangehasreachedallrouters,directlyinthecaseoflink-stateandindirectlyinthecasedistance-vectorandpath-vector,thattheprotocolcanensurethattheforwardingtablesdefineconsistentroutesbetweenallpairsofnodes.Thus,allsuchroutingprotocolsexperi-enceaconvergenceperiod—afterthechangehasbeende-1

tectedandbeforeallrouterslearnaboutthechange—duringwhichtheroutingstatemightbeinconsistent.

Whiletheconvergenceprocessisinvokedwheneverlinkcostschange,linkandrouterfailuresaretheeventsthatcausethemostseriousproblems.Theycancauselosses[3]and,insomecases,triggerLSAstorms,resultinginhighCPUandmemoryutilizationinroutersandincreasednetworkinsta-bility[10].Thoughtheconvergenceperiodfundamentallydependsonnetworkpropertiessuchasthediameterofthenetwork,itisexacerbatedinpracticeduetosystem-levelis-suessuchasprotocoltimers.

Theattemptstosolvethisproblemintheliteraturecanberoughlyclassifiedintothreecategories:(a)designingloop-freeconvergenceprotocols,(b)reducingtheconvergencepe-riodofprotocols,and(c)usingprecomputedbackuppathstoroutearoundfailures.Thefirstcategoryofproposalsin-volvesprotocolchanges(suchasorderingofLSAs[15])toensurethattheconvergenceprocessdoesnotcausetran-sientloops.Thesecondcategoryinvolvesreducingconver-genceperiodbytweakingprotocolparameters(suchasLSApropagationtimersandperiodicityofHELLOmessages)[3].Thesemechanismsoftenachievelowerconvergencetimesbutattheexpenseofadditionaloverhead,andlowerstability(asweshowinsomeofourexperiments).Thethirdcate-gorydealsspecificallywithlinkfailuresalonebyprecom-putingbackuppathsforlinkswhichcanbeusedwhenthelinkinquestionfails[18,19,27].Morerecently,R-BGP[20]proposesusingasimpleprecomputation-basedbackupforfast-failoverduringBGPconvergence;R-BGPalsoprovidesprovableguaranteessuchasloop-prevention.Thesebackupmechanismstypicallydealwiththefailureofsinglelinksgracefully;however,inordertoprovideguaranteesforsi-multaneousfailuresofmultiplearbitrarylinks,thenumberofprecomputedpathsneededisextremelyhigh.

Usingthestate-of-the-arttechniques,theconvergencepe-riodcanbeeliminatedforsinglefailures,andmoregenerallythedurationandimpactoftheconvergenceperiodcanbereduced.Whilethesechangesarequantitativelybeneficial,theydonotchangethequalitativefactthattheseprotocolscould(duetomultiplefailures)endureaconvergenceperiodduringwhenitishardtoprovideroutingguarantees.

Inthispaper,weproposeadifferentroutingparadigm,calledFailure-CarryingPackets(FCP)thateliminatestheconvergenceperiodaltogether.Onceafailureisdetectedlo-

cally,packetsareguaranteedtoberoutedtotheirdestinationaslongasapathtothedestinationexistsinthenetwork.FCPtakesadvantageofthefactthatnetworktopologyintheInternetdoesnotundergoarbitrarychanges.Inintrado-mainISPnetworksandintheAS-levelInternetgraphthereisawell-definedsetofpotentiallinks(i.e.,thosethataresupposedtobeoperational)thatdoesnotchangeveryoften.Thesetofthesepotentiallinksthatareactuallyfunctioningatanyparticulartimecanfluctuate(dependingoflinkfail-uresandrepairs),butthesetofpotentiallinksisgovernedbymuchslowerprocesses(i.e.,decommissioningalink,in-stallingalink,negotiatingapeeringrelationship).Thus,onecanusefairlystandardtechniquestogiveallroutersacon-sistentviewofthepotentialsetoflinks,whichwewillcalltheNetworkMap.FCPhenceadoptsalink-stateapproach,inthateveryrouterhasaconsistentnetworkmap.

Sinceallroutershavethesamenetworkmap,allthatneedstobecarriedbythepacketsisinformationaboutwhichoftheselinkshavefailedatthecurrentinstant.Thisfailure-carryingpacketsapproachensuresthatwhenapacketarrivesatarouter,thatrouterknowsaboutanyrelevantfailuresonthepacket’spreviouspath.Thiseliminatestheneedfortheroutingprotocoltoimmediatelypropagatefailureinforma-tiontoallrouters,yetallowspacketstoberoutedaroundfailedlinksinaconsistentloop-freemanner.WealsopresentavariantcalledSource-RoutingFCP(SR-FCP)thatprovidessimilarpropertiesevenifthenetworkmapsareinconsistent,attheexpenseofadditionaloverheadinpacketheaders.ThoughweprimarilypresentFCPtointroduceanewrout-ingparadigmthatisqualitativelydifferentfrompreviousap-proaches,weshowthroughsimulationthatithasthepoten-tialtoprovidequantitativebenefitsaswell.Usingreal-worldISPtopologiesandfailuredata,weshowthattheoverheadofusingFCP—intermsofcomputation,overheadinpacketheadersandstretchincurred—isverysmall.Wealsocom-pareFCPwithOSPFandshowthat,unlikeOSPF,FCPcansimultaneouslyachievebothlowlossandlowoverhead.Fi-nally,weshowthatcomparedtopriorworkinbackuppathprecomputations,FCPprovidesmuchlowerloss-rateswhilemaintaininglessstateattherouters.

WepresentFCPprimarilyasalink-stateprotocol,andhenceappliesdirectlytointradomainandenterpriserouting.However,webelievethatthesameideacanbeusedinthecontextofinterdomainroutingaswell.Tothisend,weout-lineastrawmanproposalforapplyingFCPtointerdomainroutinginSection7;weleaveacompletestudyofapplyingFCPtotheinterdomaincontextforfuturework.

Initialization:pkt.failedlinks=NULLPacketForwarding:while(TRUE)

path=ComputePath(M−pkt.failedlinks)if(path==NULL)

abort(“Nopathtodestination”)elseif(path.nexthop==FAILED)pkt.failedlinks∪=path.nexthopelse

Forward(pkt,path.nexthop)return

Figure1:BasicFCPprotocol.

workMap,whichrepresentsthelink-stateoftheentirenet-work;wewillrelaxthemapconsistencyassumptioninSec-tion2.2.Intheabsenceoffailures,FCPreducestoalink-stateprotocol;whentherearefailures,FCPbehavesquitedifferently,aswenowexplain.Forthepurposeofourdiscus-sion,weassumethatallnodesknowthenetworkmap,and,unlessotherwisespecified,weassumethatthismapdoesnotchange.WediscusshowthenetworkmapisdisseminatedandupdatedinSection4.

2.1BasicFCPdesign

2Failure-CarryingPackets

Inthissection,weintroducetheFCPalgorithmanditsprop-ertiesusingasimplenetworkmodel,similartomanyintrado-mainsettings,whereroutersuselink-staterouting.

WithFCP,allnodes(wewillusethetermsrouterandnodeinterchangeably)inthenetworkmaintainaconsistentNet-2

ThemainintuitionbehindFCPisthatitisenoughforaroutertoknowthelistoffailedlinksinthenetwork,inadditiontothenetworkmap,tocomputethepathtoadestination.FCPusesthepacketheadertogatherandcarrythelistoffailedlinksrequiredforroutingthatpacket.Asweshowlater,thepacketneedonlycarrythefailedlinksthatthepackethassofarencounteredalongitspath,notallfailedlinksinthenet-work,inorderforthistowork.Thus,thenumberoffailurescarriedinanypacketheaderistypicallyverysmall.

Figure1showsthepseudocodeofthebasicFCPprotocol.Whenapacketarrivesatarouter,itsnext-hopiscomputedusingthenetworkmapminusthefailedlinksintheheader.Ifthisnext-hopwouldsendthepacketoutaninterfacethathasafailedlink,thentherouter:(1)insertsthefailedlinkintothepacketheader,(2)recomputestherouteusingthisnewfailureinformation,and(3)returnstosteponeifthenewnext-hopalsoincursafailureor,ifnot,forwardsthepackettoitsnext-hop.Notethateachpacketistreatedseparately,thefailureinformationcontainedinapacketisnotincorporatedintotheroutingtables.

TounderstandFCPbetter,considertheexampleinFig-ure2.AssumeN1sendsamessagetoNd,andthatlinksN3−NdandN5−N7aredown.Sinceonlynodesadja-centtothefailedlinksknowaboutthefailure,thepacketisforwardedalongtheshortestpathintheoriginalgraph,(N1,N2,N3,Nd),untilitreachesthefailedlinkN3−Nd.Atthispoint,N3computesanewshortestpathtoNdbasedonthemapminuslinkN3−Nd,andincludesthefailed

F = {} F ={}N2d}-N3 {NF =N3Inordertoreduceconfusion,mostofourdiscussionwillfocusonbasicFCP,andthenwewilldiscussbrieflythepropertiesofthisalternateapproach.

F = {N3-Nd}N1N4N72.3

DestinationdN3- {N =7}N5-, NProperties

SourceN5F = {N3-Nd, N5-N7}N6FFigure2:AnexampleillustratingFCProuting.

linkN3−Ndintheheader.Letusassumethatthispathis(N4,N5,N7,Nd).WhenthepacketreachesN5,N5addsthefailedlinkN5−N7totheheader,andcomputesanewshort-estpaththatdoesnotincludethetwofailedlinks.Eventuallythepacketreachesthedestination,Nd,alongthispath.

Ingeneral,therearetwopossibilitieswhenapackethitsafailedlink:eitherthereisnopathtothedestination,inwhichcasethepacketisdropped,orthereissomepathtothedes-tinationinwhichcasethegraphonwhichrouterscomputethepathbecomessmaller(i.e.,becauseitdoesnotincludethefailedlink).1Witheverynewfailedlinkinsertedinthepacketheader,thegraphoverwhichthepacketisroutedbe-comesmonotonicallysmaller.

WepresenttwokeypropertiesofFCP:guaranteedreacha-bilityandpathisolation.Informally,thereachabilityprop-ertysaysthataslongasthenetworkisconnectedandtherearenopacketlossesduetocongestion,everypacketisguar-anteedtoreachitsdestinationdespiteanylinkfailures.Thepathisolationpropertysaysthatamaliciousnodecannotim-pactthepathfollowedbyapacketunlessitisalreadyonthatpath.Finally,weshowthatSR-FCPcanprovidetheseprop-ertiesevenwhenthenodemapsareinconsistent.

Sinceafailednodecanberepresentedasnodewhosealllinkshavefailed,intheremainderofthissectionwecon-sideronlylinkfailures.Furthermore,unlessotherspecified,weconsideronlyfail-stopfailures,andassumethatFCPem-ploysshortestpathrouting.TostateFCP’spropertiesmoreprecisely,westartwiththefollowingdefinition.

Definition1.LetMbethenetworkgraph(map).DefinethelivenessgraphLG(t1,t2)asthemaximalgraphconsistingofonlynodesandlinksofMthatarealiveatalltimesduringtheclosedtimeinterval[t1,t2].

Notethatoncealinkgoesdownduring[t1,t2],itisremovedfromLG(t1,t2)irrespectiveofwhetherthelinkcomesbackagainornot.Thisaspectcapturesthefactthat,inFCP,onceafailedlinkisaddedtothepacketheader,itisneverremovedfromtheheader.2

Next,wegivesufficientconditionsthatguaranteepacketdeliveryinFCP.

Lemma1.GuaranteedReachability:ConsiderpacketpenteringnetworkMattimet1.Assumelinkfailuresarede-tectedinstantaneously,therearenopacketlossesduetonet-workcongestion,andthepropagationdelayoveranylinkisonetimeunit.Letd(G)denotethediameterofgraphG.Then,FCPguaranteesthatpwillbedeliveredtothedes-tinationbytimet2,wheret2isthesmallesttime,ifany,suchthatthefollowingtwoconditionshold:

1.thereareatmostffailuresduring[t1,t2],wheref≤(t2−t1)/d(LG(t1,t2))−12.LG(t1,t2)isconnectedandspans(allnodesof)MProof.Themainpartoftheproofistoshowthatpacketpisdeliveredtoitsdestinationbysometimet2thatsatisfiescon-ditions(1)and(2).Fromhereitfollowstriviallythatpacketpwillbedeliveredbythesmallestvalueofsucht2.

Theproofisbycontradiction.Assumepisnotdeliveredtothedestinationbyatimet2thatsatisfiesbothconditions(1)and(2).

2

2.2Source-RoutingFCP(SR-FCP)

BasicFCPassumesthatallnodeshavethesamemap.Wenowrelaxthisassumption,bypresentinganalternatede-signthatemployssource-routing.Withsource-routingFCP(SR-FCP),thefirstrouteronthepacketpathinsertstheen-tireroutetothedestinationinthepacketheader.Subsequentrouterssimplyforwardthepacketbasedonthesourcerouteinthepacketheaderuntilthepacketeitherreachesthedesti-nationorencountersafailedlink.Inthelattercase,thenodeaddsthefailedlinktothepacketheader(exactlylikeba-sicFCP),andreplacesthesourcerouteintheheaderwithanewlycomputedroute,ifanyexists,tothedestination.

ThemainadvantageofSR-FCPoverFCPisthatitworkscorrectlyevenwhennotallnodeshavethesamenetworkmap.Thus,SR-FCPdoesnotrequirethatallnodeshavethesamemap.Asecondadvantageisthat,unlessthereisalinkfailure,packetforwardingdoesnotrequirealookupopera-tion,andthuscanbeimplementedmuchfasterinpractice.Onthedownside,SR-FCPincreasesthepacketoverhead,byrequiringeachpackettocarrythesourceroute.Further-more,theinconsistencyacrossmapscansignificantlyin-creasethelistoffailedlinks,asanylinkthatdoesnotappearinallmapscanbepotentiallymarkedasafailedlink.

Thereisathirdpossibilitythatarisesduetocongestion:iftheroutercannotholdontothepacketduetoresourcelimitations,packetsmightbedropped.

1

FCPdoesnotreusefailedlinkstoavoidcycles.

3

Westartwithtwoobservations.Thefirstobservationisthatapacketwillnotencounterthesamefailedlinktwice.Thisfollowsfromthefactthatonceapacketencountersafailedlinkl,thislinkiscarriedinthepacketheader,andeachsubsequentpathcomputationwillavoidl.

Thesecondobservationisthatanypacketforwardeddur-ing[t1,t2]willtakeatmostd(LG(t1,t2))timetoeitherreachthedestination,orencountera(new)failedlink.Thisisbecause,unlessanewfailureisencountered,everynodeusesthesamemapandfailedlinklist(i.e.,theonecarriedbythepacket)toforwardthepacketalongtheshortestpath.Furthermore,atanytimet∈[t1,t2),theshortestpathisatmostd(LG(t1,t)).Thisisbecause,fromcondition(2)anddefinition1,bothLG(t1,t2)andLG(t1,t)spanM,andLG(t1,t)includesalllinksofLG(t1,t2),whichyieldsd(LG(t1,t2))≥d(LG(t1,t)),∀t∈(t1,t2).

Letkbethenumberoflinkfailuresencounteredbypacketpduringinterval[t1,t2],wherek≤fbyhypothesis.Afterencounteringthekthfailure,thepacketisroutedalongshort-estpathtodestination.Sincetherearenopacketlosses,theonlyreasonpmaynotreachdestinationiseitherbecause(a)pencountersanotherlinkfailure,orbecause(b)somenodeA,triestoforwardpbutdoesnothavearoutetoDinthenet-workmapminusthelistoffailedlinks.However,(a)cannotbetrue,sincebythesecondobservation,pwouldencounterthe(k+1)thfailurebytimet1+(k+1)×d(LG(t1,t2))≤t1+(f+1)×d(LG(t1,t2))≤t2,whichviolatescondi-tion(1).Similarly,(b)cannotbetrueasitimpliesthatthelivenessgraphisdisconnectedatsomepointduringthein-terval[t1,t2],whichviolatescondition(2).Thiscompletestheproof.

NotethatFCPcanfailevenifthereisaviablepathinLG(t1,t2),butthiscanonlyoccuriftheLG(t1,t2)isdis-connectedandthepacket-in-flightgetsstrandedonadiscon-nectedcomponent.Asanexample,considerFigure1.Asbe-fore,N1initiallysendsthepackettoN2.However,atthisinstant,letthelinksN1−N2,N3−NdandN3−N4allgodown.SinceN2andN3aredisconnectedfromthedestina-tiontheycannotroutethepackettoNddespitethefactthatthepathN1−N5−N6−N7wasalwaysactive.Notethatcon-dition(2)intheaboveLemmafiltersoutthisscenario,asitrequiresLG(t1,t2)tospantheentiregraph.

Intoday’sprotocols,maliciousrouterscansendfakerouteupdates,andhencesubvertanetworktocausemorepack-etstoflowthroughthem[17,30].InFCP,oncethemapisuploadedtoeachnode,therearenodynamiclinkupdatesthatnodesexchangetomodifythismap.Furthermore,eachpacketistreatedindependentlyofotherpackets—onlyfail-uresthatthepacketencountersaretakenintoaccountforcomputingthepaths.Hence,anodewhichisnotonthepacket’spath,ascomputedbyFCP,cannotaffectthefateofthepacket.Thenextlemmastatesthisproperty.

Lemma2.Pathisolation:Assumingthemapdistributionissecure,maliciousnodescannotperformoff-pathattacks.Proof.Theprooffollowsdirectlyfromthefactthatanoff-pathnodehasnowaytocontaminatetheroutingstateofthenodesalongpacket’spath,athesenodescomputethepacketroutesolelybasedonthedisseminatedmapandthelistoffailedlinksinthepacketheader.

Themainassumptionwemakehereisthatthemapdis-seminationismuchlessfrequentthanrouteupdatesinto-day’sroutingprotocols,andthuswecanaffordtoimprovethesecurityofthemapdisseminationoperation,evenattheexpenseofanincreasedoverhead.

Notethatthepathisolationpropertydoesnotprovidese-curityguaranteesagainstarbitraryattacks.Forexample,amaliciousnodecanstillmountdenialofserviceattacksbysendingspuriouspacketswithlargelistsoffakefailedlinksinthehopeofoverloadingtheCPUsofitsneighbors.Thisattackissimilartoamaliciousnodesendingalargenumberoffakeroutingupdatestoitsneighbors.

ThenextresultshowsthatSR-FCPisabletoprovidetheseproperties,eveninthepresenceofinconsistentmaps.Inthiscase,thepropertiesapplytothegraphdefinedbytheinter-sectionofallmapsinthesystem.Intuitively,thisisbecauseSR-FCPpotentiallytreatsanylinkthatisnotinallmapsasafailedlink.Inparticular,ifalinklinapacket’ssourcerouteisnotinthemapofanodeAthatforwardsthepacket,Asimplyaddsltothelistoffailedlinks.

Lemma3.Consideranetworkwherethemapsmaintainedbynodesarenotnecessarilyconsistent.Redefinethenotionoflinkfailuretoincludeeverylinkthatdoesnotbelongtoallnodemaps.

Usingthenewdefinitionoflinkfailure,SR-FCPachievesboththeguaranteedreachabilityandthepathisolationprop-erties,asstatedbyLemmas1and2,respectively.

Proof.TheproofforguaranteedreachabilityissimilartotheproofofLemma1.Theonlydifferenceisthat,inthiscase,nodesmayhavedifferentmaps.However,byusingsourcerouting,weensurethatthetwoobservationsinLemma1arestilltrue.LetAbethenodethathascomputedandinsertedthesourcerouteinagivenpacketp.Since,intheroutecom-putation,Aeliminatesthefailedlinksencounteredbypsofar,thisensuresthatpwillnotencounterthesamefailedlinktwice.Furthermore,everysubsequentnodealongp’spathusesthesourcerouteinsertedbyAtoroutepacketpuntileitherpreachesitsdestinationorencountersanotherfailedlink.SincethemapusedbyAtocomputethesourcerouteofpisasupersetofLG(t1,t2)(wheretimest1andt2areasdefinedinLemma1)3,itfollowsthatittakespatmostd(LG(t1,t2))toreachthedestinationorthenextfailedlink.

BythedefinitionoflinkfailureinLemma3,LG(t1,t2)doesnotcontainanylinkunlessthelinkispresentinallmaps,includingtheA’smap

3

4

Theproofofthepathisolationpropertyfollowsagainfromthefactthatanoff-pathnodehasnowaytocontam-inatetheroutingstateofthenodesalongpacket’spath.

No recomputationneededDefault path = {Nd}, Backup path = {N4,N5,N7,Nd}F = {} {}F =N2d}3-NN{ F =N32.4Challenges

N1SourceF = {N3-Nd}Wehavedescribedthebasicalgorithmanditsfundamentalproperties.Intherestofthepaper,weaddressthemainchal-lengesofrealizingFCP.

•Computationaloverhead(Section3):Wheneverapacketcarryingfailureinformationarrivesatarouter,therouterneedstocomputenewroutes.Wepresentmechanismstoreducethecomputationoverheadsig-nificantly.

•Mapdisseminationandupdates(Section4):FCPreliesonallroutershavingaconsistentviewofthenetworkmap,whichrequiresamapdisseminationandupdateprotocol.

•Quantitativeperformance(Section5):WhileFCP’scor-rectnesspropertiesmightbetheoreticallyappealing,tohaveanypracticalrelevanceFCPmustbecomparedquantitativelytocurrentOSPFperformance,aswellasbackuppathtechniquesthatarecommonlyusedinop-erationalnetworkstoday.

•Deployment(Section6):ForFCPtohavepracticalim-plications,themechanismsshouldbedeployablewithminimalchangestocurrentinfrastructure.Wediscusshowwecanleveragecurrentlydeployedmechanisms(suchasMPLS),andseveralearlierproposals(suchasRCP)toachieveourgoals.

•FCPextensions(Section7):SincemuchofthepaperdiscussesFCPasalink-stateroutingprotocol,itisdi-rectlyapplicableonlyintheintradomaincontext.WediscusshowFCPcandealwithincompletemapsandwithpolicyconstraintsneededforinterdomainrouting.

N4N7DestinationdN3-N{= F 7}N5-, NN5N6F = {N3-Nd, N5-N7}No recomputationneeded even for multiple failuresDefault path = {N7,Nd}, Backup path = {N6,Nd}Figure3:Anexampleinwhichapacketexperiencesmultiplelink

failuresbutrecomputationisnotnecessary.

Lemma4.IfapacketpencountersafailedlinklatnodeN,andtheprecomputedpathPltothedestination(usingtheconsistentmapminusl)doesnotcontainalinkthatbelongstothesetoffailedlinksthatpcarries,thenPlcanbeusedtorouteptothedestination,andnorecomputationisnecessary.Proof.Prooffollowsfromthefactthatashortestpathisun-affectedbyremovingalinknotcontainedinthatpath.Figure3illustratestheintuitionbehindtheabovetech-nique.WhenthepacketreachesnodeN5,multiplefailuresareencountered.ButsincethebackuppathatN5forthefailedlinkN5−N7doesnottraverseN3−Nd,recomputationisnotnecessary.Hence,whenthefractionoffailedlinksissmall,thechancethatarecomputationistriggeredislow.

3.2Reducingrecomputationtime

3ReducingOverheadofFCP

BasicFCPrequirescomputationforeverypacketthaten-countersafailureateverynodethatthepackettraverses.Wepresentseveralmechanismsthatreducetheoverheadsignif-icantlybyaddingonlyasmalloverheadtorouterstate.

3.1Reducingper-packetroutecomputation

Toreduceper-packetcomputationatnodeswherefailuresareencountered,nodesperformsomeprecomputation.Eachnode(inadditiontothedefaultforwardingtable),foreveryadjacentlinkl,computestheforwardingtableusingthecon-sistentmapminusl;thistableisusedwhenlisfailed.How-ever,intermsofactualforwardingstate,suchaprecompu-tationonlydoublesthememoryrequirement:foreachdesti-nation,inadditiontothedefaultpathPcomputedusingthemap,weneedtostoretheprecomputedpathcomputedusingmapminuslP,wherelPisfirsthopinP.

5

Eachnodemaintainsacacheofthepathsthatitcomputesbasedonfailuresseeninpackets.Foreachcombinationoffailures,anodeperformscomputationtofindshortestpathsonlyonce.Thisisbecauseperformingashortestpathcom-putationonM\\F,whereMisthemap,andFisthelistoffailedlinks,yieldsshortestpathstoalldestinations.

Forperformingrecomputation,weborrowfromtheliter-atureonincrementalrecomputation[13,25].Priorresearchhasshownthatincrementalrecomputationcanbeperformedwithintheorderoffewmillisecondsevenforgraphswithathousandnodes[3].Performingrecomputationwithinafewmillisecondsisveryreasonable;sincefailuredetectionitselfcouldtakethatmuchtime,recomputationdoesnotsubstan-tiallyworsenthevulnerabilityperiod.

Furthermore,sincemanyoftheincrementalalgorithmsconstructshortest-pathtrees,therecomputationstepyieldspathstoalldestinations.Hence,bysavingthisinformation,thenodecanavoidrecomputationforallfuturepacketswiththesamesetoffailedlinksirrespectiveofthedestination.

3.3Reducingpacketoverhead

Wenowpresentamechanismtoreducepacketoverheadfur-therattheexpenseoflocalmappingstateatthenodes.Con-sideranodeN1sendingafailureheader(thatincludesasetoffailedlinks)FtonodeN2.WiththefailureheaderFthenodeN1associatesalabellf,andincludesthemappinglf→FwhenitsendsthepackettoN2.AfterN1receivesanacknowledgmentfromN2aboutthemapping,N1includesonlythelabellfratherthantheentirefailureheaderF.La-belsdon’thaveglobalmeaningbutarespecifictoapairofnodes.Forrobustness,atime-to-livevalueTcanbeassoci-atedwithalabel;ifnopacketwithaparticularlabelisseenforperiodT,thelabelisremoved.

•Howdowedecidewhenthenodesswitchtoanewver-sionofthemap?Howdoesroutinghappenduringthewindowofswitchingmapswhennotallnodesrouteonthesameversion?

•Howdowemakethecoordinatorresilienttofailures?

4.3Transitioningtonewmap

4DisseminationofNetworkMaps

Wenowturntotheproblemofdisseminatingtheglobalnet-workmaptoallnodesperiodically.Thepurposeofthemapistoprovideallrouterswithaloosely-synchronizedbutglob-allyconsistentviewofnetworkstate.

4.1Networkmapinformation

Toreduceoverheadaswellasreactquicklytochanges,thenetworkmapdoesnotincludetransientchangestothenet-work.Forinstance,ifalinkfailstemporarilyforashortdura-tion,itisnotremovedfromthemap.Rather,onlylong-termupdatessuchasplannedoutagesandnewlyprovisionedlinksarepublishedinthemap(short-termupdatesarehandledbytheFCPprotocoldescribedinprevioussections).Inordertoreducebandwidthconsumption,onlythedifferencefromthepreviousversionofthemapcanbedisseminated.

Wefirstpresentaprotocolthattriestoensurethatallnodesrouteusingthesamemap.Then,wedescribeamechanismthatensurescorrectroutingevenwhentheprotocolfailstotransitionallnodestothenewmapsimultaneously.

Wheneachnodereceivesanewmap,itsetsalocaltimerthatexpiresafteraperiodTlp,whereTlpisaconservativees-timateofthediameterofthenetwork.Anodeswitchestoanewmapeitherwhen:(a)thetimerexpires,or(b)itreceivesapacketthatisroutedusinganewmap.Intuitively,whenthetimeratthefirstnodethatreceivesthemapexpires,allnodeswouldhavereceivedthenewnetworkmapcompletely.Hence,whenitstartsroutingusingthenewmap,allnodesthatroutepacketswouldswitchtothenewmap.Thiscascad-ingprocessquicklyresultingintheentirenetworkswitchingtothenewmapdependingontheamountoftrafficflowinginthenetwork.Intheworst-case,allnodeswouldswitchtothenewmapwithinTlpofeachother.

Inpractice,foranintradomaintopologyspanninganentirecontinent,weexpectthethatthelongestshortest-pathinthenetworkwouldbenolargerthanafewhundredsofms(forcomparison,one-waydelaysforcontinentalUnitedStatesisroughly50ms).Hence,Tlpcanbeconservativelychosentobeafewsecondstoaccountforprocessingdelaysateachnodeaswell.

4.2Basicmapdissemination

ThemapisdisseminatedbyanRCP-likecoordinator[9]us-ingreliableflooding.ThecoordinatorsendsthemapviaTCPtoasetofnodes,whichinturnsendsthemaptotheirneigh-borsalongtheoutgoinglinksinthemap,andsoon.Toavoidreceivingthemapmultipletimesformitsneighbors,anodecanaskaneighbortocancelthemaptransmissiononcethenodegetsthemapfromanotherneighbor.Ifanodeisdownduringthemapdistribution,thenodewillgetthemapfromitsneighborsonceitcomesup.

Toensurepathisolationproperty(seelemma2),weusepublickeycryptography,wherethecoordinatorsignseachmapwithitsprivatekey.Thecoordinator’spublickeyisdis-tributedtoallnodesinthenetworkeitherout-of-band(e.g.,manually)orviaapublic-keyinfrastructure(PKI),ifavail-able.Sincemapdisseminationisarelativelyrareevent,webelievethattheoverheadimposedbythesignatureopera-tionswillbeacceptable.Furthermore,sincetheoverheadonthecoordinatorisrelativelyindependentonthenetworksize,weexpectthecoordinatortoscaletolargenetworksizes.Whilewehavedescribedhowmapsaredisseminated,thefollowingchallengesremain,whichweaddressnext:

6

4.3.1Packetforwardingduringmaptransitions

Wenowpresentapracticalpacketroutingmethodusingthemapupdateprocessthatworkseveninthecasewhenthemap-disseminationexceedsTlp.Here,weassumethateverynodemaintainsnotonlythelatestmap,butthepreviousver-sionofthemap,aswell.Thebasicideaistodowngradeapackettousingthepreviousversionofthemapifthenewmapisnotcompletelydisseminated.

Eachforwardedpacketcontainsasequencenumberthatindicatesthesequencenumberofthemapusedtoroutethatpacket.Whenanodestartsroutingapacket,itscurrentactivenetworkmap(whichiseitherthemostrecentmapithasre-ceivedorthepreviousversion).Letanodenreceiveapacketfromn󰀁.Letthesequencenumbercontainedinthepacketbes󰀁,thesequencenumberoftheactivemapatthecurrentnodebes,andthelargestreceivedsequencenumberreceivedatthecurrentnodebesmax(smax≥s).

Case(a)s󰀁Usingthisprotocol,originatorstartsforwardingthepacketpusingitsactivemap.Intheworstcase,pisdemotedtous-ingthepreviousmapifthelatestmapisnotfullydissem-inated.Notethatmapdemotionwouldhappenonlywhenthetimerexpiresbeforeallnodesgetthemap,andshouldnothappenwithconservativelychosentimeouts.Evenifapacketisdemotedtousingthepreviousmap,theprotocol’sbasiccorrectnessisnotaffected.Duringmaptransition,allnodeswouldnotswitchversionnumbersexactlyatthesametime.However,eventuallyallnodeswouldupdatetothenewmap,andeventuallyroutingconsistencyisguaranteed.Asnotedearlier,ifanodenreceivesapacketwithanewse-quencenumbersmaxbeforeitstimerforsmaxexpires,thennupdatesstosmax.

encefromthepreviousnetworkmaptosavebandwidthre-sources.Theonlylimitationistheoverheadtosignthemap.

5EvaluationofFCP

Wefirstpresentourexperimentalmethodology,thedatasetsweused,andprotocolconfigurationsweusedforcompari-sonpurposes.Wepresentresultsintwoparts.Inthefirstpart,wepresentresultsthatshowthattheoverheadofFCPisverysmall.Inthesecondpart,wecompareFCPwithOSPFaswellasbackupcomputationtechniques.Finally,wepresenttheoverheadinvolvedinusingSR-FCPasafunctionofde-greeofinconsistencyinthemapsattherouters.Tosumma-rizeourresults:

•TheoverheadofFCPisverylowbothintermsofcom-putationoverheadandpacketheaderoverhead.

•Unliketraditionallink-staterouting(suchasOSPF),FCPcanprovidebothlowloss-rateaswellaslowcon-troloverhead,

•Comparedtopriorworkinbackuppathpre-computations,FCPprovidesbetterroutingguaranteesunderfailuresdespitemaintaininglesserstateattherouters.

4.4Coordinatorfault-tolerance

Wenowdescribeamechanismforreplicatingthecoordi-natortoimprovefaulttolerance.Themainideaistousereplicatedcoordinators(muchlikehowRCPdoes)withreplicahavingareplicanumberthatdenotestheorderingofthereplica.4Forexample,replica1ismoreimportantthanreplica2.EachreplicaindependentlychoosesamapM(allofthemexecutethesamealgorithm,andhenceshouldpickthesamemap,thoughtheymaynotbesynchronized),anddisseminatesMskewedintimesuchthatreplica1sendsthemapupdateattimet=0,replica2sendstheupdateattimet=T/n,replica3attimet=2T/nandsoon,whereTistheperiodicityofupdatesthateachreplicasends,andnisthenumberofreplicas.EachnodefloodsonlythemapofthereplicawiththelowestsequencenumbersuchthatthemapisnoolderthantimeT+c,wherec>0isthemaximumtimeforthemaptogetdisseminatedacrossthenetwork;theothermapsitreceivesaresuppressedtosavebandwidthresources.Forrouting,eachnodeinthesystemwouldusethemapfromthelowestnumberedreplicawiththehighestsequencenumbersuchthatthatthemapisnoolderthantimeT+c,wherecisdefinedasabove.Eveniftherearenetworkparti-tions,withinallconnectedcomponents,theeventualroutingconsistencywouldhold.Partitionshealatthenetworklayerduringsubsequentupdates.

5.1Methodology

4.5Periodicityofmapupdates

Themapupdationperiodwoulddependonhowfrequentlylinksaredecommissionedoraddedtothenetwork,plannednetworkoutages,andfrequencyatwhichlinkcostschange(sayfortrafficengineeringreasons).Intheextremecase,onecouldjustdisseminatethemapasfrequentlyasthedefaultOSPFLSAgenerationperiod(whichistypically30sec-onds).UnlikeOSPF,thecoordinatorcansendonlythediffer-Inpractice,sincethecoordinatorperformstasksonlyatcoarsetimescales,havingasmallnumberofreplicasforthecoordinatormightsuffice.

4

Protocols:WecomparedFCPwithtwoalternatestrategies:theOSPF[23]link-stateprotocol,andanMPLS-likeproto-colthatprecomputesbackup-paths.TocomparewithOSPF,weleveragedtheOSPFDsoftwarerouterdevelopedbyJohnMoy[24],whichcompletelyimplementstheOSPFprotocolasspecifiedbyRFCs2328and1765[22,23].WeconfiguredOSPFDfollowingthemillisecond-convergencerecommen-dationsgivenin[3],includingtheincrementalDijkstra’sal-gorithmdescribedin[25].

OSPFDalsocontainsanetworkemulationtoolkitforeval-uatingdeployments,whichweextendedtosupportFCPandbackup-pathsimplementations.Tocomparewithbackup-pathprecomputation,inourresults,weusethesampleselec-tionalgorithmusedbyJuniperNetworks[19].Althoughal-gorithmsexisttocompute“optimal”backuppathswefoundthatsuchalgorithmsinvolvedsubstantialcomputationtime,whichledtopoorresultswhenappliedtothedynamicallychangingnetworksweconsiderhere.

Configuration:ToconfigureOSPFD’stimers,wecon-ductedasimulationstudytodeterminesettingsthatper-formedwellonourworkloads.Bydefault,weconfiguredOSPFDtosendoneprobeevery400ms,andtoconsideralinkdownifnoprobesarereceivedafter2seconds.Tore-ducesensitivitytoflappinglinks,weconfiguredOSPFDto“treatbadnewsdifferentlyfromgoodnews”bypropagatinglinkfailuresimmediatelybutdelayingpropagationoflinkarrivalsforfiveseconds.GiventhatFCPandtheBackup-pathschemedonotpropagatefailureinformationglobally,7

Table1:Protocolconfigurationparameters

Parameterhello-intervaldead-intervalretransmit-intervalthrottle-intervalOSPFD400ms2sec2sec2secFCP/Backupcomputations50ms250msn/an/aOSPFDdefault1sec5sec5sec5secCumulative fractionweconfiguredthemwithfasterprobingtimes(onehelloev-ery50ms).Eachroutersendspingstoallotherrouters,withonepingevery15seconds5.Finally,tofullystressFCProut-ing,thenetworkmapsareneverupdatedintheexperimentswepresent.

Data:LinkfailuresandarrivalsweredrivenbyISIStracescollectedontheAbileneInternet2backbone[1].ThesetracescontaintimestampedLinkStateAdvertisements(LSAs).Wemodifiedthenetworkemulatortodrivelinkfailuresbyplay-ingbackLSAsbasedontheirtimestamps.Toevaluatelargernetworksandawiderrangeofparameters,wealsousedRocketfuel[28]topologiesandusedashiftedParetodistri-butiontodrivethetime-to-failuredistributionforeachlink.ThoughwehadsixAStopologiesfromtheRocketfueldata,wereportresultsfromAS1239(Sprint)Rocketfueltopologyasarepresentativesample.TheSprintAStopologyhas283nodesand1882links.

1 0.995 0.99 0.985 0.98 0.975 0.97 0.965

0

1

10 fails/sec4 fails/sec0.5 fails/sec

2

3

4

Packet header overhead [bytes]

Figure5:PacketoverheadofFCP.

5.2OverheadofFCP

FCPintroducesextraoverheadonlyforpacketsthaten-counterafailedlink.Theoverheadcanbeclassifiedinto:(a)networkoverhead,i.e.,stretchofroutingthepacket,(b)packetheaderoverhead,and(c)recomputationoverhead.

1

Cumulative fraction 0.995 0.99 0.985 0.98

10 fails/sec4 fails/sec0.5 fails/sec

1

1.2

1.4

1.6

1.8

2

Stretch

showstheCDFofstretchoverallpairsofsourcesanddes-tinationsforincreasingfailurerates(wherefailurerateismeasuredbythenumberoflinksthatfailpersecondinthenetwork).Wefoundthattheaveragestretchwasverylow(1.0012),andtheworst-casestretchwasunder1.8.However,forincreasingfailurerates,theaveragestretchincreasedto1.0026,withaworst-casestretchof1.83.Thishappensbe-causethenumberoffailedlinksapacketencountersin-creaseswithincreasingfailurerates.Hence,FCPisforcedtoreroutepacketsmultipletimeswhichreducesthechancesthattheoptimalend-to-endpathistaken.However,asshownlater,wefoundthisstretchwascomparabletothebackup-pathselectionstrategythatwecomparedagainst.

Packetheaderoverhead:Figure5showstheCDFofmin-imumpacketoverheadincurredbythefailureheaderwithFCP,usingtheOC48tracefromCAIDA[2]togeneratereal-istictrafficworkloads.FortheAbilenefailuretrace[1],FCPinflatestheaveragepacketsizebyanegligibleamount.Themaximumheadersizeduringtherunis4bytesperpacket,assumingeachfailureheadertakes2bytes.Althoughheadersizescanpotentiallybelargerinnetworkswithmoresimul-taneousfailures,wecanreducethebyteoverheadbyus-ingthelabeloptimizationdescribedin3.3.Itisimportanttonotethatheadersareonlyaddedonlinkfailure,unlikeMPLS,whichappendsalabel(orstackoflabels)toeverydatapackettraversingalabel-switchedpath.

Recomputationoverhead:Figure6(a)showsaCDFofthenumberofrecomputationsperpacketinanetworkwith0.5linkfailurespersecond.Roughly0.2%ofpacketsrequirerecomputationtobeperformedunderthevanillaFCPimple-8

Figure4:Stretchforvaryingmeanfailureinter-arrivaltimes(in

seconds).FCPincursastretchpenalty,butthispenaltyissmallevenathighlinkfailurerates.

Stretch:Afterfailure,FCPdoesnotnecessarilydiscoverthenext-shortestpath,incurringastretchpenalty.Figure4

WefoundthatsendingpingsatafasterratecouldoverloadtheOSPFDimplementation.

5

1

Cumulative fractionCumulative fraction 0.9995 0.999 0.9985 0.998

no cachecaching

precomputation

0 1 2 3 4 5 6 7 8

Recomputations per packet

1 0.8 0.6 0.4 0.2 0

10

AS1221AS1239AS1755AS3257AS3257AS3257 100

Time [microseconds]

1000

(a)(b)

Figure6:RecomputationcostsofFCP:(a)Numberofrecomputations.(b)Recomputationtimes.

mentation.Thisvaluedecreasesto0.01%whenroutesoncecomputedarecached.Figure6(b)showsthetimetorecom-putepathsafterlinkfailureasmeasuredona3GHzIntelPentiumprocessorwith2GBofRAM.Recomputationtimeisbelowonemillisecondonalltopologies.

thelossrateandoverhead.Forawidevarietyoffailurerates,FCPoutperformsOSPFbyanorderofmagnitude,whilesi-multaneouslymaintainingalowercontroloverhead.NotethatOSPF’soverheadbeginsdecreasingasthefailurerateincreasespasttheabilityoftheprobingprotocoltokeepupwithlinkevents.

InFigure8(b),wevarytheprobingrateandplotthefrac-tionincreaseinlossrateofOSPFoverthelossrateofFCPforvarioustopologies.Althoughtheamountofimprovementvariesacrosstopologies,FCPprovidesmorethanaorderofmagnitudelowerlossratethanOSPF.AsshowninFig-ure8(c),FCPalsoreducescontroloverhead.Ingeneral,wefoundthatdensertopologies(e.g.AS1221,withanaveragedegreeof6.2)hadlessbenefitfromFCPthansparsertopolo-gies(e.g.AS3257,withanaveragedegreeof3.7).Thishap-pensbecauseindensertopologiesOSPFhasalargernumberofpathstochoosefrom,andishencemorelikelytodiscoveraworkingpath.

5.3BenefitsofFCP5.3.1ComparisonwithOSPF

InFigure7(a),wevarytherateatwhichOSPFDsendsHELLOpacketstoneighbors,andmeasuretheresultingef-fectoncontroloverheadandthefractionofdatapacketsde-livered.Asmentionedpreviously,wetuneFCPwithafastprobingrate,sincefasterprobingdoesnotincurapenaltyincontroloverheadintermsofLSAsdisseminatedsincenoneofthelinkfailuresdetectedareannounced.AstheHELLOprobingrateisincreased,thenumberofdatapacketslostde-creases,sincefailuresarereactedtomorequickly.However,probingatafasterratealsocausesmoreshort-termfailurestobedetectedandpropagated,increasingcontroloverhead.Ontheotherhand,FCPundergoesonlyaverysmall(yetnon-zero)loss-rateoflessthan0.1%;thelossofFCPinourexperimentsisnon-zerosincelinkfailuredetectiontakesafi-nitetimeandduringthisperiod,allpacketstryingtousethatlinkwillbedropped.AlthoughFCPexhibitssimilarbehav-iortoOSPFintermsofstretchandlossratewhilevaryingtheprobingrate(Figure7(b)),itscontroloverheadisnotafunctionoflinkfailurerate,andhenceitsprobingratecanbeincreasedwithoutinflatingcontroloverhead.WefounditwaspossibletotuneOSPFtoachievethisloss-rate,butonlyattheexpenseofaincreasingitscontroltraffictoabove300messagespersecondperlink.

Figure7(c)whichplotstheaveragestretchshowsasimilarphenomenonaswell;astheprobingratedecreases,ittakeslongertodetectlinkrepairs,andhencealargerfractionofworkingpathsarenotdiscoveredbyapacket.SincewecankeeptheFCPprobingratehighwithoutcompromisingover-head,FCPhasmuchlowerstretchthanOSPF.

5.3.3Comparisonwithbackup-pathselection

5.3.2Effectofvaryingparameters

InFigure8(a),wevarythemeaninterarrivaltimeforlinkfailures,butfixOSPF’sprobingintervalat400ms,andplot

9

UnlikeOSPF,thebackup-pathstrategyweusedcanattainveryfastfailovertimeswithoutasignificantincreaseincon-troloverhead.However,tominimizelossrates,thebackup-pathstrategyneedstoaccountforeveryfailurecontingency,andhencerequiresasubstantialnumberofbackuppaths.Precomputingalargenumberofbackuppathstoaccountfordifferentcombinationsofmultiplelinkfailuresincreasesstateperrouter.ThistradeoffisshowninFigure9a.Forex-ample,with8backuppathsperlink,thebackuppathstrategyrequires4210entriesperrouter,andexperiencesaloss-rateof0.05%.Howeveronthesameworkload,FCPrequiresonly255entriesyetattainsalossrateoflessthan0.002%.More-over,unlikeFCP,thedistributioninstateacrossroutersisnotuniform,andhencethetop1%ofroutersrequiremorethan20,285entries.However,forswitchingbetweenmaps,FCPmusttemporarilymaintainasecondcopyofitsroutingstate.Althoughthisstateisonlymaintainedforashortperiod,andcanbestoredasdeltas(differencesfromthecurrentmap),intheworstcasethiscoulddoubleFCP’sstaterequirements(to510inthisexample).

Figure9(b)showstheperformanceinthepresenceofsi-

Overhead [msgs/sec per link] 500 400 300 200 100 0

OSPF-overheadOSPF-lossrateFCP-lossrate 1.4 1.2

Loss rateLoss rate 1 0.8 0.6 0.4 0.2

0.5 0.4 0.3 0.2 0.1 0

FCP-lossrateFCP-stretch

1.8 1.7

StretchStretch 1.6 1.5 1.4 1.3 1.2 1.1 1

3 2.5 2 1.5 1

OSPF-stretchFCP-stretch

0

10 100 1

OSPF hello interarrival time [sec]

1 10 100 0.1

FCP hello interarrival time [sec] 10 100 1

OSPF hello interarrival time [sec]

(a)(b)(c)

Figure7:ComparisonwithOSPF:(a)UnlikeFCP,OSPFcannotsimultaneouslyprovidelowcontroloverheadandhighavailability,(b)

ReducingFCP’sHELLOtimerreducesstretchandlosswithoutincreasingcontroloverhead,(c)OSPF’smapbecomesinconsistentwiththetopologyatlowprobingrates,resultinginastretchpenalty.

Overhead [msgs/sec per link]Overhead [msgs/sec per link]Ratio reduction in lossrate 0.04 0.035 0.03 0.025 0.02

60 50 40 30

10000 1000 100 10 1

AS1221AS1755AS3257AS3967

10 100 1000 10000 1

OSPF hello interarrival time [sec]

16 14 12 10 8 6 4 2 0

FCP-lossrateOSPF-lossrateOSPF-overhead

Loss rateAS1755AS3257AS3967AS61

0.015

20

0.01

10 0.005

0

1 10 0.1

Avg. failures per second

1 10 100 1000 10000

OSPF hello interarrival time [sec]

(a)

oncontroloverhead.

(b)(c)

Figure8:Effectofvaryingparameters:(a)failurerateoncontroloverheadanddatapacketlossrate.(b)topologyonlossrate.(c)topologymultaneousfailuresontworepresentativetopologies.Wefixthenumberofbackuppathstotwo,andvarythenumberofrandomlyselectedlinkstosimultaneouslyfail.Onbothtopologies,thebackupstrategyandFCPhaveroughlyequalloss-ratesduringsinglefailures.However,whenmorethanonefailureoccurs,FCPhassignificantlylowerlosses.(NotethatFCPhasnon-zerolosssincethefailuredetectionisnotinstantaneous.)Thishappensbecauseasthefailureratein-creases,itbecomesmorelikelythebackup-pathstrategywillencounterasetoffailuresnotcoveredbyanyoneofthebackuppaths.Finally,Figure9(c)showsthatthebackup-pathsstrategyincursastretchpenaltyduringlinkfailures.Thishappensbecausethebackup-pathsstrategyattemptstofindlink-disjointpathsasbackups,whichtendtobelongerthanthepathFCPfindsaroundthefailure.

10 9

1.025

8 7 1.02

6

1.015 5

4

1.01 3

2 1.005

1

1 0 0 0.05 0.1 0.15 0.2 0.25 0.3Map inconsistency factor (d)

StretchOverhead

Avg. overhead [bytes/packet] 1.03

Figure10:Effectofinconsistencyinnetworkmapsontheover-headincurredbySR-FCP.

5.3.4Effectofinconsistentmaps

Sofar,wehaveassumedthatallnodeshaveaconsistentstateofthenetworkmap.Here,weinvestigatetheoverheadin-curredbySR-FCP—intermsofaverageroutingstretchandper-packetoverhead—asafunctionofmapinconsistencyfactor(seeFigure10).Specifically,forachosenmapincon-sistencyfactord,weinstantiatethenetworkmapMnateachnodenbypickinglinksrandomlyfromtheactualnetworkmapM,suchthattheintersectionofmapsatallnodesformsaspanningandconnectedsubgraphofM,whichcontains

10

onlyafraction(1−d)oflinksinM(withhighprobability).Thex-axisiscappedat0.3sincethatisthelargestfractionofinconsistencyforwhichtheintersectionofmapsatallnodesformsaspanningsubgraph.

Theplotshowsthatthestretchandpacketoverheadaresmallevenwhenmapsarehighlyinconsistent.Evenwhentheinconsistencyfactoris0.3,theaveragestretchislessthan1.03,andtheaveragesizeofapacketheaderisunder10bytes(assuming2bytespernodeforsourceroutesandfailures).ThereasonSR-FCPperformssowellisbecauseSR-FCPpaysapenaltyonlyifthesourcenodeperformingaroutecomputationmissessomelinksthatcouldhaveresultedinsignificantlyshorterpaths;anintermediatenodejustfor-

Stretch 0.03 0.025Loss rate 0.02 0.015 0.01 0.005

0 1

State [entries per router]Loss rate 20000 10000 0

0.002 0.001

0

0 0.5 1 1.5 2 2.5 3Number of simultaneous failures

StretchFCP-lossrateBkup-lossrate

FCP-stateBkup-state-avgBkup-state-99pc

50000 40000 30000

0.005 0.004 0.003

FCP-AS1755Bkup-AS1755FCP-AS3275Bkup-AS3275

1.05 1.04 1.03 1.02 1.01 1 0

num-bkups=0num-bkups=1num-bkups=2num-bkups=3num-bkups=4

10

Number of backup paths

1 2 3 4 5

Number of simultaneous failures

(a)(b)(c)

Figure9:ComparisonwithBackup-paths:(a)UnlikeFCP,Backup-pathscannotsimultaneouslyprovidelowstateandlowloss-rate.(b)FCP

maintainslowlossforavarietyoffailurerates.(c)Backup-pathsstretchpenaltyforvaryingnumbersofbackuppaths.

wardsapacketbasedonthepacket’ssourcerouteirrespec-tiveofwhetherdownstreamlinksinthatsourceroute(notadjacenttotheintermediatenode)arepresentinthenode’smapornot.

6DeploymentIssues

FCPrepresentsasubstantialdeparturefromtraditionalrout-ingmechanisms,andhenceunsurprisinglyrequiresseveralmodificationstorouterdesignevenfordeploymentatthein-tradomainlevel.Althoughthesechangesarebynomeanstrivial,inthissectionweoutlinehowtheymaybeimple-mentedasextensionstoexistingprotocolsanddesigns.Mapdissemination:TheroleofthecoordinatorisakintothecentralizednodeinthecaseofRCP[9].SuchadesignisamenableincaseofISPnetworkswherethecentralizedadministrativenodecanactasthemapcoordinatorandperi-odicallydisseminatesthenetworkmap.Inaddition,tobetterhandlepacketforwardingduringmaptransitions(seeSec-tion4.3.1),routersmuststoreboththecurrentandthepre-viousmap,insteadofonlythecurrentmapasmostoftheexistingprotocolsdo.

FIBstate:Ifdynamicfailure-basedpathcomputationsarenotcached,theFIBstateisdoubledsinceatthemini-mum,thenexthopinformationshouldbemaintainedforcurrentmapandpreviousmap.Evenifpathcomputationsarecached,theaverageadditionalstaterequiredisnothigh.Withtheprecomputationoptimizationforeachoutgoinglink(describedinSection3.1),theFIBstateisagainonlydou-bledoverall,whichwebelieveisamodestrequirement.Forwarding:IntheoptimizedversionofFCP,routersaddalabelcorrespondingtoalistoffailedlinkstopacketheaders,andperformforwardingbasedonthelabel.AppendingandforwardingbasedonlabelsisaddressedbyMulti-ProtocolLabelSwitching(MPLS)[12].FCPalsoneedstoinvokere-computationfornewfailuresencountered,byinvokingspe-cialprocessingviatheslowpath.

Applicabilityofintradomainroutingcontrols:Sincethenotionofhavingalink-stategraphisretained,thekeyseman-11

ticsofintradomainroutingmapsremainunaffected.FCPcontinuestoprovidecost-basedshortest-pathroutingintheabsenceoflinkfailures.Hence,assignmentofaddressesandaccesscontrols,trafficengineering,andotheraspectsofcon-figuration/maintenanceremainunchanged.Specificallyfortrafficengineering,long-termplanningchangestothelinkcostscanbeintroducedbythecentralcoordinator.Forshort-term,reactivecostchangesintroducedbytheroutersthem-selves,therewouldbeashortdelaysincetheupdatesarenotinstalledinstantaneously,buthavetogothroughthecoordi-natorbeforetheTElink-costchangesbecomeactive.Sincethelink-costchangesgothroughthecoordinator,itcanberatifiedbeforeitisincorporatedintothenetworkmapinor-dertopreservethepathisolationproperty.

7ExtensionstoFCP

WedescribedFCPasalink-stateroutingprotocol,andhenceisdirectlyapplicabletointradomainnetworks.Here,wepresentextensionstoFCPtobroadenthescopeofapplicabil-ity.Specifically,weturntohowFCPcanbeusedtoimproveinterdomainrouting,bothintermsofiBGPandeBGProut-ingstability.

Figure11:MitigatingiBGPdisruptionsusingFCP.

7.1ImprovingiBGPstabilityunderlinkfailures

HotpotatoroutingiscommonlyusedbyISPstoselecttheclosestexitpointamongstmultipleequally-goodinterdo-mainroutes.Failureoflinkswithinthenetwork,failuresofnext-hoplinksgoingoutofthenetworkfromtheborderrouters,aswellassmallperturbationsinintradomaincosts

canleadtohot-potatodisruptions,wherelargeamountsoftrafficoscillatebetweenegresspoints.Suchdisruptionscanleadtoroutingloops,routeroverload,andexternallyvisi-bleBGProutingchanges[32,33].Henceaschemethatcanpreventsuchinstabilityduringchangeofegresspointsisde-sired[31,32].

WepresentasimplemodificationtoFCPtoallowittooperateoveriBGProuteswithinasingledomainforthecaseoffailureoflinks.Weaugmentthelink-statenetworkmapmaintainedbyinternalrouterstotreatanegressroutetoaparticularprefixasavirtuallinkdirectlyconnectedtothedestinationprefix.FCPisagnostictothethenotionofvirtuallinks,asittreatsvirtualandactuallinksequally;weusethetermvirtuallinkonlyforconvenience.Wheneitheranormallinkoravirtuallinkfails,aroutercanuseFCPtoforwardthepackettoanalternateegressconnectedtothesamenext-hopAS.Thisensuresthatroutingtoexternalroutesremainsconsistenteveniffailuresarenotimmediatelypropagated.AsimpleillustrativeexampleisshowninFigure11.ThenetworkmapconsistsofactuallinksE1−R1,E2−R2andR1−R2,andvirtuallinksE1−PandE2−PforprefixP.Initially,letbothroutersR1andR2useegressE1toreachthedestinationprefixP.Whenthelink(R1,E1)(ortheBGPnexthopfromE1towardsP)fails,R1appendsthe(R1,E1)(orthevirtuallink(E1,P))topacketheaderscausingR2toforwardthepacketsviaE2.TraditionaliBGP/OSPFroutingwouldundergoaroutingloopbetweenR1andR2lastinguntilR2’sscanprocess,i.e.visitingtheBGProutingdecisionforeachprefix,completes.

routes,anAScanforcedownstreamASestoforwardtraf-ficattheexpenseofviolatingtheirownpolicies.Wenextpresentasolutiontothischallenge.

Themainideabehindoursolutionistotreatanypolicyviolationasalinkfailure.WeassumethatASesonlyimple-mentpoliciesthatareafunctionoftheneighborfromwhomtheyreceivedtheadvertisementandlocalpolicyconsidera-tions(asopposedto,forexample,policiesdependentonthepresenceofannon-neighborASintheAS-path).Virtuallyalltoday’sBGPpoliciesfallintothiscategory[34].

ConsiderapacketproutedfromsourceASStodestina-tionASD.WhenarouterinthesourceASSstartsrout-ingapacket,itaddstheAS-levelpath(sourceroute)inthepacketheader,justasproposedbySR-FCP.LetarouterRbelongingtoanintermediateASIreceivesthepacketpwithanAS-levelsourcerouteASR(p).LetASR(R,D)repre-senttheAS-levelroutecomputedbyRtothedestinationASD(basedonitsBGProuteselectioncriteria).Finally,letNextHop(Route)representtheAS-levelnext-hopforaroute.Thefollowingcasesarepossible:

1.N=NextHop(ASR(p))=NextHop(ASR(R,D))andnext-hoptoNisalive.Inthiscase,RsimplyforwardsthepackettoN.2.N=NextHop(ASR(p))=NextHop(ASR(R,D))andthatnext-hoptoNisdead.Inthiscase,RinvokesSR-FCPbyaddingtheAS-pathI−N(recallthatIistheintermediateASthatRbelongsto)tothefailureheader.RthenforwardsthepacketalongthebestAS-paththatitknowswhichdoesnothaveanyfailures.3.NextHop(ASR(p))=NextHop(ASR(R,D)).discussthiscasenext.

We

7.2Interdomainpolicyrouting

Interdomainroutingtodaysuffersfromlongoutagesarisingfromaslowconvergenceprocessthatoccursaftercertainroutingevents[21].Inthissection,wediscusshowwecanleverageFCPtoavoidfailuresduringtheconvergencepro-cessofBGP.Inourproposal,weonlyconsiderchangesonthedataplane;wedonotmodifyBGP’srouteannouncementandpropagationprotocol.Next,wediscusstwoofthekeychallengesfacedbyourproposal:(a)howarethenetworkmapsdefinedanddistributed?(b)howarepoliciesrespectedwhenFCPisused?

7.2.1FCPnetworkmap

Unlikethecaseofintradomainrouting,thereisnonaturalcentralizedauthoritytoactasacoordinatorfordistributingAS-levelnetworkmaps.Hence,weassumethatnodesworkwithinconsistentmapsanduseSR-FCP(Section2.2).

AllroutersinthenetworkrunBGPprotocolforexchang-ingroutesastheydotoday.EachrouterdefinestheFCPmapusingthelatestsetofBGPupdatesithasreceivedfromallitsneighbors.

IftheASdecidesthatthesourceroutepresentinthepacketisnotcompatiblewithitschoiceofroutes,itdoesthefollowingoperationsforpreventingtransientloops.First,itaddsNextHop(ASR(p)tothefailureheaderofthepacket.Second,itusesthebestrouteithastothedestinationthatdoesnothaveanyfailedlinks,andaddsthatsourceroutetothepacket.WeleavethedegreetowhichanASallowsroutesthatarenotthemost-preferredtobeusedinthesourcerouteasameta-policydecisionofthatAS.Thismeta-policyrepre-sentsthetradeoffbetweenthedegreetowhichtheASallowsFCPtorecoverfromfailuresandtheextenttowhichpoli-ciesareobeyed.Forinstance,anAScandecidethatitallowsonlythetoptwopreferredroutes.

7.2.3Discussion

7.2.2UsingSR-FCPwithpolicyrouting

NaivelyimplementingSR-FCPwouldhaveadversepol-icyimplications.Thisisbecause,byusingAS-levelsource

12

SinceBGPpropagatesonlyroutesthatcanbepotentiallyuseddownstream,routerswillnotobtaintheentirelink-stateofthenetwork.However,afterBGPconverges,allthenodesshouldhaveconsistentrouteselectioninformation,i.e.,allnodeswillpickthesameAS-levelpathforeachdestinationprefix.Inotherwords,atallnodes,theAS-levelsourceroute

inthepacketheaderwillbeidenticaltoitsmostpreferredroutetothedestination(Case(1)above).

Duringtheconvergenceprocess,routingusingtheabovemodifiedSR-FCPprotocolensuresthatpacketswillnotenterintotransientloops.ThisfollowsfromthefactthatpacketsareroutedusingSR-FCP,henceateverystagethepacketei-thermakesprogressbasedonthesourcerouteorthatalinkisaddedtothelistoffailedlinksinthepacketheader.Eventu-ally,thepacketwillreachthedestinationorwilldiscoverthattherearenomorepaths(basedonlinksinthefailureheader),andwillbedropped.Also,aswementionedabove,theex-tenttowhichFCPwillhelproutearoundfailuresdependsontheflexibilityofthepolicyattheASestousesourceroutesthatarenotthemostpreferred.

Onepracticalchallengeofourschemeisdeployability,asitrequireonetoinserttheASsourcerouteandthelistoffailedlinksinthenetwork(IP)header.WhileonecanuseIPoptionstostorethisstate,acomprehensivesolutiontothischallengeissubjectoffuturework.

overeachotherrouterR󰀁,RprecomputesbackuppathstoalldestinationsassumingthatR󰀁isdown.Fordealingwithlinkfailures,itperformsasimilarprecomputationbyiter-atingoverneighboringlinks.However,thedraftstatesthattheydonotaimtohandlemultiplesimultaneouslink/routerfailures.Nearsidetunneling[7]dynamicallyconstructstun-nelstotheclosestrouteradjacenttothefailure,andforwardtrafficviathetunnelduringtheconvergenceprocess.Asim-plerschemeistosimplyforwardviaaloop-freealternatepathinthepresenceoffailure,ortoforwardtoaU-turnal-ternatewhennoloop-freealternateexists[4].Whiletheseapproachesimprovepropertiesoftheconvergenceprocess,theystillrequireroutingupdatesatthecontrolplane,andarehencesubjecttothecontroloverheadversusavailabilitytradeoffwediscussedinourresults.

ReducingconvergencetimesSomeeffortshaveaddressedfailurerecoverydirectlyatthelevelofroutingprotocol.Forinstance,Alaettinogluetal.[3]proposetomodifyIGPim-plementationstoreduceconvergencetimetoafewmillisec-ondsevenwhenlinksfail,bymodifyingtimers,andim-provingrun-timeoftheroutecomputationalgorithm.How-ever,reducingtimerscanincreasethecontroloverheadandworsennetworkstability,asshownbyourexperimentalre-sults.Ingeneral,therehasbeensubstantialdebateoverwhatparameterstouse,anditisnotclearthatthereisasinglecorrectchoiceofthesetimersoriftheycanbeeliminatedcompletely.

Suchprotocoltweaksarerestrictedbyprotocolcon-straints;forexample,arbitrarilyreducingthetimervaluesfordetectingchangeinlinkstatuscouldpotentiallymakeroutesoscillateduetofalsepositivesindetectingfailedlinks.Fur-thermore,adjustinglinkweightsinOSPFcantemporarilydestabilizethenetwork,evenwithfastconvergence,becauseoftenmultipleweightsneedtobeadjustedsimultaneously.Usingprecomputedbackup-pathsSeveralworks,haveproposedusingprecomputedbackuprouteswhenprimarypathsinthenetworkfail,forexampleIPrestoration[18],andMPLSFast-Reroute[27],andseveralothers[4,6,11,19].Ashortevaluationofthefastreroutetechniquesispresentedin[14].Morerecently,R-BGP[20]proposesusingasimpleprecomputation-basedbackupmethodforfast-failoverdur-ingBGPconvergenceprocessthathassomeprovableguar-anteessuchasloop-preventionandvalley-freerouting.

Backuproutesarepracticalonlywhentherearesmallnumbersofsimultaneousfailures;toachievetheguaranteedreachabilitypropertyofFCPwithmultiplefailures,severalbackuppathswouldbeneeded.Infact,fromourexperi-ments,weseethatevenwithlowfailuresrates,multiplefail-urescansimultaneouslyoccurinrealnetworks.Incontrasttoprecomputedbackuppaths,FCPnotonlyprovidescorrect-nessguaranteesinthefaceofmultiplelinkfailures,butdoessobyrequiringmuchlesserstateattheroutersthanbackuppathcomputationstypicallydo.13

8RelatedWork

Priorworktoaddresstheproblemofroutingconvergenceintheliteratureattheprotocollevelcanberoughlyclassifiedintothreecategories:(a)designingloop-freeconvergenceprotocols,(b)reducingtheconvergenceperiodofprotocols,and(c)usingprecomputedbackuppathstoroutearoundfail-ures.Wedon’tdiscussattemptsataddressingsuchissuesatthehigherlayers,forinstanceusingoverlaystogetaroundunderlyingroutingproblems.

TheideaofcarryinginformationtorouteapacketintheheaderofthepacketitselfisinspiredbyStoica’sworkondy-namicpacketstate[29].FCPissimilarinspirittoLOLS[26]usedforroutinginwirelessadhocnetworks.However,FCPseparatesnetworkmapinformationandtransientfailuresbynotintroducingtransientfailuresintothemap,andhencecanprovidebetterroutingguarantees.

Loop-freeconvergence.Severalapproachesensurethatconvergencetakesplaceinawaythatitobeyscertaincor-rectnessconstraints.Forexample,link-statevectorrout-ing[5]advertisesasubsetoflinks,andusesatermination-detectionalgorithmtobreakloops.Diffusingcomputa-tions[16]achievestheoreticalloop-freeroutingconvergenceusingadistance-vectorparadigm.However,astheauthorsofthatpapernote,theperformanceafternodefailuresandnet-workpartitionsisaconcernbecauseallnetworknodeshavetobeinvolvedinthesamediffusingcomputation.

ReorderingLSAsduringpropagationhasbeenproposedtoensurethattransientloopsareavoided,forthespe-cificcasesofprotectedandplannedlinkfailuresandcostchanges[15]alone.Not-viaaddresses[8]usesamechanismverysimilartotheprecomputationoptimizationpresentedinSection3.1.ConsiderarouterRthatperformsthefollow-ingcomputation:Fordealingwithnodefailures,byiterating

9Conclusion

WeproposedFailure-CarryingPackets(FCP),anewroutingtechniquewhicheliminatestheconvergenceperiodenduredbytraditionalroutingprotocols.ThebasicideabehindFCPissimplebothconceptuallyandpractically:onceallroutershavealoosely-synchronized,consistentviewofthenetwork,itisenoughforaroutertoknowthelistoffailedlinkstocorrectlycomputethepathtoadestination.

ThoughweprimarilypresentFCPtointroduceanewroutingparadigmthatisqualitativelydifferentfromprevi-ousapproaches,wealsopresentsimpleoptimizationsthatmakesFCPfeasibleinpractice.Usingreal-worldISPtopolo-giesandfailuretraces,weshowthatboththecomputationoverheadaswellaspacketoverheadincurredbyFCPisverysmall.WealsopresentcomparisonswithbothOSPF(withtimerscarefullychosen)aswellasacommercially-usedbackuppathtechnique.Intheformercase,weshowthatunlikeOSPF,FCPcanprovidebothlowloss-rate,aswellaslowcontroloverhead.Inthelattercase,weshowsthatFCPprovidesbetterroutingguaranteesunderfailuresdespitemaintaininglessstateattherouters.ThoughthebasicmodelofFCPasalink-stateroutingparadigmisdirectlyapplica-bleonlytointradomainnetworks,wediscusshowFCPcanbeappliedtointerdomainpolicyroutingaswell.StudyingtheapplicabilityofFCPindifferentroutingnetworks(suchasinterdomainrouting,wirelessnetworks,sensornetworks)moredeeplyistopicoffuturework.

References

[1]Abileneobservatorydatacollections.2006.http:

//abilene.internet2.edu/observatory/data-collections.html.

[2]AnonymizedOC48traces,CAIDA.2006.http://data.

caida.org/.

[3]C.Alaettinoglu,V.Jacobson,andH.Yu.TowardsMillisecond

IGPConvergence.IETFDraft,2000.

[4]A.Atlas.U-turnAlternatesforIP/LDPFast-Reroute.Internet

Draftdraft-atlas-ip-local-protect-uturn-03.txt,February2006.[5]J.BehrensandJ.J.Garcia-Luna-Aceves.Distributed,scalable

routingbasedonlink-statevectors.InProc.ACMSIGCOMM,1994.

[6]S.Bryant,C.Filsls,S.Previdi,andM.Shand.IPFastReroute

usingTunnels.Internetdraftdraft-bryant-ipfrr-tunnels-01.txt,Oct2004.

[7]S.BryantandM.Shand.AFrameworkforLoop-freeConver-gence.InternetDraftdraft-bryant-shand-lf-conv-frmwk-03,October2006.

[8]S.Bryant,M.Shand,andS.Previdi.IPFastRerouteUsing

Not-viaAddresses.InternetDraftdraft-bryant-shand-ipfrr-notvia-addresses-03,2006.

[9]M.Caesar,D.Caldwell,N.Feamster,J.Rexford,A.Shaikh,

andJ.vanderMerwe.Designandimplementationofaroutingcontrolplatform.InProc.NSDI,2005.

[10]G.Choudhury.PrioritizedTreatmentofSpecificOSPFVer-sion2PacketsandCongestionAvoidance.RFC4222,Octo-ber2005.

[11]G.Choudhury,A.Atlas,R.Torvi,C.Martin,B.Imhoff,and

D.Fedyk.BasicSpecificationforIPFast-Reroute:Loop-freeAlternates.IETFdraft,2005.

[12]B.DavieandY.Rekhter.MPLS:TechnologyandApplica-tions.InMorganKaufmann,2000.

[13]P.Franciosa,D.Frigioni,andR.Giaccio.Semi-dynamic

shortestpathsandbreath-firstsearchindigraphs.InSTACS,1997.

[14]P.FrancoisandO.Bonaventure.AnevaluationofIP-based

FastRerouteTechniques.InProc.CoNEXT,2005.

[15]P.FrancoisandO.Bonaventure.Avoidingtransientloopsdur-ingIGPconvergenceinIPnetworks.InProc.INFOCOM,2005.

[16]J.J.Garcia-Luna-Aceves.Loop-FreeRoutingUsingDiffus-ingComputations.IEEE/ACMTransactionsonNetworking,1993.

[17]Y.Hu,A.Perrig,andM.Sirbu.SPV:SecurePathVectorRout-ingforSecuringBGP.InProc.ACMSIGCOMM,2004.

[18]G.Iannaccone,C.Chuah,S.Bhattacharyya,andC.Diot.Fea-sibilityofIPRestorationinaTier-1Backbone.IEEENet-works,SpecialIssue,March2004.[19]Juniper-Networks.Configurealternatebackup

pathsusingfate-sharing.2005.http://www.juniper.net/techpubs/software/junos/junos53/swconfig53-mpls-apps/html/mpls-signaled-config37.html.

[20]N.Kushman,S.Kandula,D.Katabi,andB.Maggs.R-BGP:

StayingConnectedinaConnectedWorld.InProc.NSDI,2007.

[21]Z.Mao,R.Govindan,G.Varghese,andR.Katz.RouteFlap

DampingExacerbatesInternetRoutingConvergence.InProc.SIGCOMM,2002.

[22]J.T.Moy.OSPFDatabaseOverflow.RFC1765,March1995.[23]J.T.Moy.OSPFVersion2.RFC2328,April1998.

[24]J.T.Moy.OSPFcompleteimplementation.InAddison-Wesley,NewYork,2001.

[25]P.Narvaez,K.-Y.Siu,andH.-Y.Tzeng.NewDynamicAlgo-rithmsforShortestPathTreeComputation.IEEE/ACMTrans-actionsonNetworking,2000.

[26]S.Nelakuditi,S.Lee,Y.Yu,J.Wang,Z.Zhong,G.-H.Lu,and

Z.-L.Zhang.Blacklist-AidedForwardinginStaticMultihopWirelessNetworks.InProc.ofSECON,2005.

[27]P.Pan,G.Swallow,andA.Atlas.FastRerouteExtensionsto

RSVP-TEforLSPTunnels.RFC4090,May2005.

[28]N.Spring,R.Mahajan,andD.Wetherall.MeasuringISP

TopologieswithRocketfuel.InProc.ofSIGCOMM,2002.[29]I.Stoica.StatelessCore:AScalableApproachforQualityof

ServiceintheInternet.PhDthesis,CarnegieMellonUniver-sity,Dec.2000.

[30]L.Subramanian,R.H.Katz,V.Roth,S.Shenker,andI.Sto-ica.ReliableBroadcastinUnknownFixedIdentityNetworks.InProc.PODC,2005.

[31]R.Teixeira,N.Duffield,J.Rexford,andM.Roughan.Traffic

MatrixReloaded:ImpactofRoutingChanges.InProc.ofPAM,2005.

[32]R.Teixeira,T.Griffin,A.Shaikh,andG.Voelker.Network

SensitivitytoHot-PotatoDisruptions.InProc.ofSIGCOMM,2004.

[33]R.Teixeira,A.Shaikh,T.Griffin,andJ.Rexford.Dynam-icsofHot-PotatoRoutinginIPNetworks.InProc.ofACMSIGMETRICS,2004.

[34]F.WangandL.Gao.InferringandCharacterizingInternet

RoutingPolicies.InProc.IMC,2003.

14