This preview shows page 1-2-3-4-5-6-7-8-58-59-60-61-62-63-64-65-66-118-119-120-121-122-123-124-125 out of 125 pages.
An Introduction to Interdomain Routing and BGPAcknowledgementsCommon View of the Telco NetworkCommon View of the IP Network (Layer 3)What This Tutorial Is AboutGoalOutline Part IOutline Part IIBest Effort ConnectivityRouting vs. ForwardingHow Are Forwarding Tables Populated to implement Routing?Routers Talking to RoutersBefore We Go Any Further …Autonomous Routing DomainsAutonomous Systems (ASes)AS Numbers (ASNs)Architecture of Dynamic RoutingPowerPoint PresentationThe Gang of FourMany Routing Processes Can Run on a Single RouterIPv4 Addresses are 32 Bit ValuesClassful AddressesRFC 1519: Classless Inter-Domain Routing (CIDR)Which IP Addresses are Covered by a Prefix?CIDR = Hierarchy in AddressingClassless ForwardingIP Address Allocation and Assignment: Internet RegistriesNontransit vs. Transit ASesSelective TransitCustomers and ProvidersCustomers Don’t Always Need BGPCustomer-Provider HierarchyThe Peering RelationshipPeering Provides ShortcutsPeering WarsBGP-4BGP Operations (Simplified)Four Types of BGP MessagesBGP AttributesAttributes are Used to Select Best RoutesTwo Types of BGP Neighbor RelationshipsiBGP Peers Must be Fully MeshedBGP Next Hop AttributeJoin EGP with IGP For ConnectivityNext Hop Often Rewritten to LoopbackImplementing Customer/Provider and Peer/Peer relationshipsImport RoutesExport RoutesHow Can Routes be Colored? BGP Communities!Communities ExampleBlackholesMars Attacks!Import Routes (Revisited)So Many ChoicesBGP Route ProcessingTweak Tweak TweakRoute Selection SummaryBack to Frank …Implementing Backup Links with Local Preference (Outbound Traffic)Multihomed Backups (Outbound Traffic)ASPATH AttributeInterdomain Loop PreventionTraffic Often Follows ASPATH… But It Might NotShorter Doesn’t Always Mean ShorterShedding Inbound Traffic with ASPATH Padding HackPadding May Not Shut Off All TrafficCOMMUNITY Attribute to the Rescue!Hot Potato Routing: Go for the Closest Egress PointGetting Burned by the Hot PotatoCold Potato Routing with MEDs (Multi-Exit Discriminator Attribute)Slide 72Policies Can Interact Strangely (“Route Pinning” Example)News At 11:00What Problem is BGP solving?Separate dynamic and static semanticsAn instance of the Stable Paths Problem (SPP)A Solution to a Stable Paths ProblemAn SPP may have multiple solutionsBAD GADGET : No SolutionSURPRISE : Beware of Backup PoliciesPRECARIOUSPart IIBig and Getting BiggeriBGP Mesh Does Not ScaleRoute ReflectorsBGP ConfederationsBGP Table GrowthLarge BGP Tables Considered HarmfulDeaggregation Due to Multihoming May be a Leading CauseHow Many ASNs are there?When will we run out of ASNs?What is to be done?Multihomed and “Private”! (draft-jhaas-ase-00.txt)BGP Routing TablesAS Graphs Can Be FunAS Graphs Depend on Point of ViewAS Graphs Do Not Show Topology!BGP DynamicsDaily Update CountWhat is the Sound of One Route Flapping?A Few Bad Apples …Two BGP Mechanisms for Squashing Updates30 Second BurstsHow Long Does BGP Take to Adapt to Changes?Two Main Factors in Delayed ConvergenceWhy is Rate Limiting Needed?Route Flap Dampening (RFC 2439)Route Flap Dampening ExampleQ: Why All the Updates?Slide 111IGP Tie Breaking Can Export Internal Instability to the Whole Wide WorldMEDs Can Export Internal InstabilityImplementation Does Matter!How Long Will Interdomain Routing Continue to Scale?SummaryAddressing and ASN RFCsSelected BGP RFCsTitles of Some Recent Internet DraftsSelected Bibliography on RoutingBGP Stability and ConvergenceAnalysis of Interdomain RoutingInternet Route RegistriesSome BGP TheoryThank You!1An Introduction to Interdomain Routing and BGPTimothy G. Griffin [email protected]://www.research.att.com/~griffin/interdomain.htmlSIGCOMM 2001 Tutorial SessionAugust 28, 2001AcknowledgementsThanks to Jay Borkenhagen, Randy Bush, Anja Feldmann, Matt Grossglauser, Madan Musuvathi, Jennifer Rexford, Shubho Sen, and Jia Wang for many helpful commentsMy opinions should not be taken torepresent AT&T policyErrors are my ownCommon View of the Telco NetworkBrickCommon View of the IP Network (Layer 3)What This Tutorial Is AboutroutingGoalUnderstand how layer 3 connectivity is maintained in the global InternetThis tutorial will not say much about the applications that exploit this connectivity.It will be restricted to IPv4 unicast routing.•Part I : The basics of interdomain routing and BGP•Part II : BGP in practice: Issues of ScaleOutline Part I•Forwarding vs. Routing•IP addressing•Autonomous Systems (basic units of interdomain routing)•The Border Gateway Protocol (BGP)–BGP fundamentals –BGP route attributes–Implementing policy with BGP –A wee bit of theoryOutline Part II•Scaling internal BGP•BGP table growth–Address aggregation vs. Multihoming• Growth in number of autonomous systems•Dynamics of BGP–Route flapping –BGP convergence–Rates of BGP updatesBest Effort Connectivity This is the fundamental service provided by Internet Service Providers (ISPs) All other IP services depend on connectivity: DNS, email, VPNs, Web Hosting, …IP traffic135.207.49.8 192.0.2.15310Routing vs. ForwardingRRRABCDR1R2R3R4R5ENet Nxt HopR4R3R3R4DirectR4Net Nxt Hop A B C D EdefaultR2R2DirectR5R5R2Net Nxt Hop A B C D EdefaultR1DirectR3R1R3R1Default toupstreamrouter A B C D EdefaultForwarding: determine next hopRouting: establish end-to-end pathsForwarding always worksRouting can be badly broken11How Are Forwarding Tables Populated to implement Routing?Statically DynamicallyRouters exchange network reachability information using ROUTING PROTOCOLS. Routers use this to compute best routesAdministrator manually configuresforwarding table entries In practice : a mix of these.Static routing mostly at the “edge”+ More control+ Not restricted to destination-based forwarding - Doesn’t scale- Slow to adapt to network failures+ Can rapidly adapt to changes in network topology+ Can be made to scale well- Complex distributed algorithms- Consume CPU, Bandwidth, Memory- Debugging can be difficult- Current protocols are destination-basedRouters Talking to RoutersRouting infoRouting info•Routing computation is distributed among routers within a routing domain•Computation of best next hop based on routing information is the most CPU/memory intensive task on a router•Routing messages are usually not routed, but exchanged via layer 2 between physically adjacent routers (internal BGP and multi-hop external BGP are exceptions)Before We Go
View Full Document
Unlocking...