CS551Delayed Internet RoutingConvergence[Labovitz00]Bill Chenghttp://merlot.usc.edu/cs551-f121 Computer Communications - CSCI 551 Copyright © William C. Chengbut poorly understoodBGP widely deployed in the Internet2Context Computer Communications - CSCI 551 Copyright © William C. ChengBGP Problems: Delayed ConvergenceHow long does it take for a route to fail-over?Question:experimental methodologyHow to answer this question:explanation of observation using simple modelISP’s don’t tell you what they are doingConvergence time takes longer than we expectedsimulationStudy and understand BGP convergence time3Key Idea Computer Communications - CSCI 551 Copyright © William C. ChengmeasurementSuggests bounds of O(n!) worst case for BGP convergence,O((n-3)*30s), where n is the number of AS’sObserves 2-3 minute convergence times (6x longer thanexpected), BGP timer goes off every 30 secondsPSTN (telephone) fail-over times are in millisecondsRobustness4Why Is Convergence Important? Computer Communications - CSCI 551 Copyright © William C. ChengInternet fail-over times are in 10s of secondsopen problem: how can Internet do much better?but for only their AS, of course!Two years of traces5Methodology Computer Communications - CSCI 551 Copyright © William C. ChengIntroduce artificial faults across InternetTup: time for good news to propagateMeasure:failures, repairs, fail-overAnalysis: helps understand worst case boundsSimluation to study worst case behaviorTdown: time for bad news to propagateTshort: time to switch from a longer route to a shorter oneTlong: time to switch from a shorter route to a longer oneIn general, want bad news to travel fast, good news totravel slowlyInternet-scale experimentation6Methodology Computer Communications - CSCI 551 Copyright © William C. ChengWhat kind of complexities/errors can arise?InternetStub ASFault Injection ServerUpstreamISP2ISP3ISP4ISP5ISP6UpstreamISP1BGP FaultBGP FaultStub ASRouteViewsDataConnectionProbeBGPBGPBGPBGPICMPechosHow do you deal with these errors on real routes?7Observed Convergence Latency Computer Communications - CSCI 551 Copyright © William C. ChengSeconds Until ConvergenceCumulative Percentage of EventsLess than half of Tdown events converge within two minutesLong tailed distribution (up to 15 minutes)TupTshortTlongTdownFailureShort->Long Fail-OverNew RouteLong->Short Fail-overTup and TshortIn general, want bad news to travel fast andgood news to travel slowlyNo correlation between network distance (latency, router,or AS hops) and convergence timesWhy is long convergence bad?8Other Observations Computer Communications - CSCI 551 Copyright © William C. Cheng9Impact on Traffic Computer Communications - CSCI 551 Copyright © William C. ChengTshortTlongPercentage Packet LossOne Minute Bins Before and After FaultFault05101520253035-9 -8 -7 -6 -5 -4 -3 -2 -1 0 1 2 3 4 5 6 7 8 9Why does loss go up?Because there are route loopsin the net causing packet drops.Figure 4a of [Labovitz00a]Some people use old paths,result in routing loopsmodel one router per ASSimulate BGP10How To Tell What’s Going On? Computer Communications - CSCI 551 Copyright © William C. Chengassume full routing meshignore latencysynchronous processing via global queuesimple model that captures key detailsBGP can try all paths of length 2, then 3, then 4⇒ O(n!) stepsThere are many possible routes (indirect through other AS’s)and it takes a long time with BGP to figoure out that nonework11What’s Going On? Computer Communications - CSCI 551 Copyright © William C. Chengeven with MinRouteAdver timers it still can take O(n)steps (13 steps vs. 48 steps originally)12BGP Convergence Example Computer Communications - CSCI 551 Copyright © William C. ChengAS0BBBRRRvia 3via 1 3via 2 3*AS1BBBRRRvia 3via 0 3via 2 3*AS2BBBRRRvia 3via 0 3via 1 3*AS2AS0AS3AS1R13BGP Convergence Example Computer Communications - CSCI 551 Copyright © William C. ChengAS0BBBRRRvia 3via 1 3via 2 3*AS1BBBRRRvia 3via 0 3via 2 3*AS2BBBRRRvia 3via 0 3via 1 3*AS2AS0AS3AS1R14BGP Convergence Example Computer Communications - CSCI 551 Copyright © William C. ChengAS0BBBRRRvia 3via 1 3via 2 3*AS1BBBRRRvia 3via 0 3via 2 3*AS2BBBRRRvia 3via 0 3via 1 3*AS2AS0AS3AS1R15BGP Convergence Example Computer Communications - CSCI 551 Copyright © William C. ChengAS0BBBRRRvia 3via 1 3via 2 3**AS1BBBRRRvia 3via 0 3via 2 3**AS2BBBRRRvia 3via 0 3via 1 3**AS2AS0AS3AS1R0x2z1x0y0z1y1z2y2x3y3x3z16BGP Convergence Example Computer Communications - CSCI 551 Copyright © William C. ChengAS0BBBRRRvia 3via 1 3via 2 3**AS1BBBRRRvia 3via 0 3via 2 3**AS2BBBRRRvia 3via 0 3via 1 3**AS2AS0AS3AS1RR:0z (0 1 3)R:0x (0 1 3)WithdrawUpdate17BGP Convergence Example Computer Communications - CSCI 551 Copyright © William C. ChengAS0BBBRRRvia 3via 1 3via 2 3**AS1BBBRRRvia 3via 0 3via 2 3**AS2BBBRRRvia 3via 0 3via 1 3**AS2AS0AS3AS1RR:1z (1 0 3)R:1y (1 0 3)WithdrawUpdate18BGP Convergence Example Computer Communications - CSCI 551 Copyright © William C. ChengAS0BBBRRRvia 3via 1 3via 2 3**AS1BBBRRRvia 3via 0 3via 2 3**AS2BBBRRRvia 3via 0 3via 1 3**AS2AS0AS3AS1RR:2z (2 0 3)R:2y (2 0 3)WithdrawUpdate19BGP Convergence Example Computer Communications - CSCI 551 Copyright © William C. ChengAS0BBBRRRvia 3via 1 3via 2 3**AS1BBBRRRvia 3via 0 3via 2 0 3***AS2BBBRRRvia 3via 0 1 3via 1 0 3**AS2AS0AS3AS1RWithdrawUpdate20BGP Convergence Example Computer Communications - CSCI 551 Copyright © William C. ChengAS0BBBRRRvia 3via 1 3via 2 3**AS1BBBRRRvia 3via 0 3via 2 0 3***AS2BBBRRRvia 3via 0 1 3via 1 0 3**AS2AS0AS3AS1RWithdrawUpdate21BGP Convergence Example Computer Communications - CSCI 551 Copyright © William C. ChengAS0BBBRRRvia 3via 1 3via 2 3**AS1BBBRRRvia 3via 0 3via 2 0 3***AS2BBBRRRvia 3via 0 1 3via 1 0 3***AS2AS0AS3AS1R22BGP Convergence Example Computer Communications - CSCI 551 Copyright © William C. ChengAS0BBBRRRvia 3via 1 3via 2 3**AS1BBBRRRvia 3via 0 3via 2 0 3***AS2BBBRRRvia 3via 0 1 3via 1 0 3***AS2AS0AS3AS1RWithdrawUpdate23BGP Convergence Example Computer Communications - CSCI 551 Copyright © William C. ChengAS0BBBRRRvia 3via 1 3via 2 3**AS1BBBRRRvia 3via 0 3via 2 0 3***AS2BBBRRRvia 3via 0 1 3via 1 0 3***AS2AS0AS3AS1RWithdrawUpdate24BGP Convergence Example Computer Communications - CSCI 551 Copyright © William C. ChengAS0BBBRRRvia 3via 1 3via 2 3**AS1BBBRRRvia 3via 0 3via 2 0 3***AS2BBBRRRvia 3via 0 1 3via 1 0 3***AS2AS0AS3AS1R25 Computer Communications - CSCI 551 Copyright © William C. Cheng Why Does This Happen?O(n!) such pathsIn
View Full Document
Unlocking...