Slide 1BGP ComplexityBGP Pitfalls and ProblemsFavorite Scapegoat!Misconfiguration [Mahajan02Sigcomm]MisconfigurationInteresting ObservationsEffects and CausesBGP Convergence [Labovitz00Sigcomm]End-to-End Routing Behavior [Paxson96Sigcomm]Inefficiencies in BGP & Internet RoutingInefficiency of Routes [Spring03Sigcomm]Path Inflation SummaryInternet BottlenecksWide-Area BottlenecksMeasurement Tool: BFindSlide 17Results: LocationResults: Available BandwidthPerformance: End-to-End PerspectiveQuantifying Performance Loss [Savage99Sigcomm]Bandwidth EstimationPossible Sources of Alternate PathsOverlay NetworksFuture of OverlayOverlay ChallengesNumber of Route ChoicesRoute Selection MechanismOverlay Routing vs. Multihoming Route ControlBGP InefficienciesSupplemental slides02/14/2007Aditya AkellaBGP Complexity•BGP is a very complicated protocol–Too many knobs–Need to accommodate (sub-optimal) ISP policies–Requires complex, human configuration•For all its complexity, BGP offers no guarantees–Performance??–Reliability??–Correctness??–Reachability??•All of BGPs complexity begets…Headache!BGP Pitfalls and Problems•Pitfalls and problems–Misconfiguration–Convergence–Performance–Reliability–Stability–Security–And the list goes on…Favorite Scapegoat!BGPNetworkingcommunityMisconfiguration [Mahajan02Sigcomm]•Origin misconfiguration: accidentally inject routes for prefixes into global BGP tablesOld Route New RouteSelf deaggregation(failure to aggregate)a.b.0.0/16 X Y Z a.b.c.0/24 X Y ZRelated origin(likely connected to the network– human error)a.b.0.0/16 X Y Z a.b.0.0/16 X Ya.b.0.0/16 X Y Z Oa.b.c.0/24 X Ya.b.c.0/24 X Y Z OForeign origin(address space hijack!)a.b.0.0/16 X Y Z a.b.0.0/16 X Y Oa.b.c.0/24 X Y Oe.f.g.h/i X Y OMisconfiguration•Export misconfiguration: export route to a peer in violation of policyExport Policy ViolationProvider  AS  ProviderRoute exported to provider was imported from a providerProvider  AS  PeerRoute exported to peer was imported from a providerPeer  AS  ProviderRoute exported to provider was imported from a peerPeer  AS  PeerRoute exported to peer was imported from a peerInteresting Observations•Origin misconfig–72% of new routes may be misconfig–11-13% of misconfig incidents affect connectivity•Pings and e-mail checks–Self de-aggregation is the main cause•Export misconfig–Upto 500 misconfiguration incidents per day–All forms are prevalent, although provider-AS-provider is more likelyEffects and Causes•Effects–Routing load–Connectivity disruption–Extra traffic–Policy violation•Causes (Origin misconfig)–Router vendor software bugs: announce and withdraw routes on reboot–Reliance on upstream filtering–New configuration not saved to stable storage (separate command and no autosave!)–Hijacks of address spaces–Forgotten to install filter–Human operators and poor interfaceP1 P2AC•Intended policy: Provide transit to C through link A-C•Configured policy: Export all routes originated by C to P1 and P2•Correct policy: export only when AS path is “C”Export MisconfigBGP Convergence [Labovitz00Sigcomm]•Conventional beliefs–Path vector converges faster than traditional DV (eliminates the count to infinity problem)–Internet path restoration takes order of 10s of seconds•Convergence–Recovery after a fault may take as much as ten minutes–Single routing fault could result in multiple announcements and withdrawals–Loss and RTT around times of faults are much worse•Upon route withdrawal, explore paths of increasing length–In the worst case, could explore n! paths–Depends which messages are processed and when•Limit between update message could reduce messages–Forces all outstanding messages to be processedEnd-to-End Routing Behavior [Paxson96Sigcomm]•Large scale routing behavior as seen by end-hosts, based on analysis of traceroutes•Pathologies: persistent routing loops, routing failures and long connectivity outages•Stability: 9% or routes changed every 10s of minutes, 30% about ~6hrs and 68% took a few days•Symmetry: more than half of paths probed were asymmetric at router levelInefficiencies in BGP &Internet Routing•Route convergence and oscillations•Poor reliability–No way to exploit redundancy in Internet paths•Inefficiency: sub-optimal RTTs and throughputs–What are some of the causes?•Policies in routing: Inter-domain and Intra-domain•Lack of direct routes, “sparseness” of the Internet graphInefficiency of Routes [Spring03Sigcomm]•Three classes of reasons for poor performance (“inflation”)–Intra-domain topology and policy•Topology: no direct link between all cities•Routing policy: “shortest paths” may be avoided due to engineering–ISP Peering•Peeering topology: limited peering between ISPs•Peering policy: hot-potato routing or early-exit routing–Inter-domain•Topology: AS graph is sparse•Inter-domain policies: policies are policiesPath Inflation SummaryInternet BottlenecksHigh-speed “core”High-speed “core”Slow, flaky home connectionBig, fatPipe(s) Last-mile, slow access links limit transfer bandwidthMost bottlenecks are last-mileAs access technology improves…Non-access or Wide-Area Bottlenecks?100Mbps homeconnectionWide-Area BottlenecksWide-Area Internet/High-speed “core”Wide-Area Internet/High-speed “core”SmallISPSmallISPSprintSprintATTATTVery Small ISPVery Small ISPVery Small ISPVery Small ISPTiny ISPTiny ISPTiny ISPTiny ISPSmallISPSmallISPTiny ISPTiny ISPVery Small ISPVery Small ISPUUNetUUNetSmallISPSmallISPSmallISPSmallISPSmallISPSmallISPUnconstrained TCP flowLink with the least available bandwidthNot the “traditional” bottlenecks  may not be congestedWide-area bottleneck  where an unconstrained TCP flow sees delays and lossesMeasurement Tool: BFindMonitor queues, identify where queues build up bottlenecksourcedestIdeally…But no control over destinationEmulate the whole processfrom the source!Measurement Tool: BFindsourcedestRate controlled UDP streamRounds ofTraceroutesMonitor links forqueueingReport toUDP process1MbpsRound j:Queueing on #2! Rate for round 2:1+MbpsRate for round 3: 1+2MbpsFlag #2, keep curent rate for round j+1 force queueingRound 1:No queueing!If #2 flagged too many times  quit. Identify #2 as bottleneckRound 2:No queueing!Round 1Round 2Round j•BFind functions like TCP: gradually increase send rate until hits