BGP: Inter-Domain Routing ProtocolThe need for routing in the InternetExternal and internal gateway protocolsDistance vector protocolsClassless inter-domain routingBGP communicationBGP attributesInternal-BGPRoute Information Propagation In the Internet Using BGPIntroductionOutlineStructure of ASsAS BGP PoliciesSlide 14AS BGP Policy DetailsHow does it work?Now, Does it Really Work?Route Instability StudyInitial Instability FindingsMany Problems due to Router Software ImplementationFollow-up ResultsRoute ConvergenceConvergence FindingsConclusionsReferencesBGP: Inter-Domain Routing ProtocolNoah TreuhaftU.C. BerkeleyThe need for routing in the Internet•Need to get packets from source to destination•How do you do this?–Network is a collection of point-to-point links connected by routers–Routers’ decisions determine which links you transit–Routing proceeds hop by hop (contrast with source routing)–How do you determine the next hop?•Could configure it statically•But the Internet needs a routing system and protocol to exchange complex and changing routing infoExternal and internal gateway protocols•Autonomous System (AS) – a single administrative domain (ISP, customer)•External Gateway Protocols exchange routing information between routers of different AS’s.–Goal: support routing policies, scale•Internal Gateway Protocols exchange routing information among an AS’s own routers–Goal: optimize route takenDistance vector protocols•<destination, metric> messages relative to sender–Essentially a routing table•Contrast with link state protocols–<source, destination, metric> messages “flooded” to all nodes–Shortest path first (Dijkstra) algorithm builds routing tableClassless inter-domain routing•Internet routing was once based on network classes•Trading classes for variable-length prefixes allows aggregation–Greater flexibility in address allocation–Less routing information requiredBGP communication•A Border Gateway Protocol (BGP) session consists of a TCP connection between two routers–If connection fails, associated state is dropped.•Message types: OPEN, UPDATE, NOTIFICATION, KEEPALIVE•UPDATE format: <withdrawn routes, attributes, valid routes>BGP attributes•ORIGIN – BGP speaker’s unique identifier•AS-PATH – AS’s that relayed this message•NEXT-HOP•MULTI-EXIT-DISCRIMINATOR (MED) – metric for multiple paths between 2 AS’s•LOCAL-PREF – metric for multiple paths to same prefix•COMMUNITY – update categorizationInternal-BGP•Same messages, attributes as External-BGP•Different rules for readvertising prefixes–Does not readvertise routes from one I-BGP speaker to another–Prevents looping (E-BGP uses the ASN and AS-PATH for this)•Route reflection: adding hierarchy for scalability•AS confederation: subdivision of a logical AS into multiple AS’sRoute Information PropagationIn the Internet Using BGPMatthew DennyU.C. BerkeleyIntroduction•Internet consists of different Autonomous Systems (ASs), which consist of admin. defined domains of hosts (e.g. ISPs, universities, companies, etc.)•Hosts in each AS must be able to send packets to any other host on the Internet•ASs have routers which exchange routing info. with other ASs using BGP–How do ASs ensure “full reachability” of the Internet, given no central authority?–How well does the current route information propagation scheme perform?Outline•Introduction•Structure of ASs•BGP policies of ASs•Why does it work?•Now, does it really work?Structure of ASs•Somewhat hiearchical (but becoming less so)•3 Types of relationships–Customer-Provider: customer AS pays provider AS for access to rest of Internet: provider provides transit service•End customers pay ISPs, and ISPs in lower “tiers” pay ISPs in higher tiers–Peers: ASs that allow each other transit service •ISPs on same tier, usually involves no fees–Customer-Backup Provider: Provider if primary provider fails. May be peers otherwise•Use BGP to communicate route info. at Network Exchange Points (NAPs) and private peering pointsAS BGP Policies•Customers export all of their routes and routes of their customers to providers, but not routes from peers or other providers•Peers export their routes and routes of their customers to other peers, but not routes from peers or other providers•Providers export all of their routes to customers•Usually, backup providers “promoted” to provider from peer upon failure of primary•If an AS recieves 2 routes for same prefix, usually exports the best by some path selection algorithmAS BGP PoliciesAS1 AS2AS3 AS4192.168.0.0/26192.168.0.64/26 192.168.0.128/26192.168.0.192/26192.168.0.0/26192.168.0.192/26192.168.0. 0/25192.168.0. 128/25192.168.0. 64/26192.168.0. 128/25192.168.0. 128/26192.168.0. 0/25192.168.64. 0/26192.168.0. 128/25192.168.0. 0/26192.168.0. 192/26192.168.0. 128/26192.168.0. 64/26192.168.0. 64/26192.168.0. 128/25192.168.0. 64/26AS BGP Policy Details•Export Policy–To indicate priority of route, most ASs use communities [Labovitz 2000b]•Import Policy–AS Path loop detection, not usually selective. Use communities to infer local pref•Path Selection–If AS has multiple routes for same prefix, best route decided by local pref; AS Path and MED are tiebreakersHow does it work?•Full Reachability–Provider/Customer relationships form a DAG•Assumes everyone below tier 1 has a provider•Convergence–Can diverge, and checking for convergence is an NP Complete Problem [Griffin 99]–Assuming strict preferences on route selection and the above structure, [Gao 2000] proves that BGP systems will converge–Will this hold as peering becomes more common?Now, Does it Really Work?•Potential Problems–Route Instability•Large number of unneeded messages leads to router CPU flooding–Routers lose Keep-Alive messages go “down” •“Route Flap” Problem–Route Convergence•Routes that change (e.g. failover to a backup provider) may take a long time to propagate correctly through system•Can cause intermittent loss of connectivityRoute Instability Study•Labovitz et. al. performed a study to measure instability in BGP Updates [Labovitz 1997, 1999]–Logged BGP update messages at 5 NAPs 1996-1998, and analyzed instability events•Routes withdrawn that are re-announced, and “pathological” withdraws•Some events due to route or policy instability, or pathological behaviorInitial Instability
View Full Document
Unlocking...