A Whirlwind Tour of Interdomain RoutingOverviewThe Need for Routing DomainsChallenges of Interdomain RoutingBorder Gateway Protocol (BGP): OverviewBGP Operation: A High-Level ExampleBGP Operation: MessagingBGP Operation: A Low-Level ExampleBGP Operation: Choosing RoutesSlide 10(Non)convergence of BGPKey PointsPowerPoint PresentationInterdomain Routing by the numbersWhen does a network become an AS?Nonconvergence of BGP: An ExampleSlide 17Classless InterDomain Routing (1991)CIDR: An ExampleCIDR, cont.ReferencesBGP Traffic: StatusA Whirlwind Tour of Interdomain RoutingAaron [email protected] 122 ClassFebruary 9, 20012Overview•What I hope you will learn in the next half-hour:–What interdomain routing is and how it came to be–What BGP is and how it works–BGP’s strengths and weaknesses3The Need for Routing Domains •Prior to 1982, the Internet used a single routing protocol (GGP).•This architecture had disadvantages:–Wasteful to store complete routing table in every router–Routing traffic became excessive as the Internet grew•In 1982, the Internet split into “Autonomous Systems” (AS’s) or “Routing Domains”: collections of routers and hosts under common administration.•An AS uses an intradomain (RIP, OSPF) protocol of its choice for routing within the AS.•A common interdomain (EGP, then BGP) protocol is used for routing between AS’s.4Challenges of Interdomain Routing•“Link costs” cannot be compared between different AS’s.–How to avoid routing loops?•The scale of the problem is larger than the intradomain one:–Larger routing tables–Routers separated by greater distances: higher delays and lower reliability for messages passed•Different AS’s may have conflicting routing objectives…… due to prior business agreements.… due to different approaches to the speed vs. reliability tradeoff.5Border Gateway Protocol (BGP): Overview•BGP is the currently-deployed interdomain routing protocol.–First introduced in 1989. Many modifications since.•BGP is a path-vector protocol: route announcements include the complete list of AS’s to reach the destination (AS-path).–Makes loop suppression very simple– Avoids comparisons of metrics between different AS’s6BGP Operation: A High-Level ExampleAbileneAS 556UCBAS 25CALRENAS 11537128.32/16128.32/16 25128.32/16 25128.32/16 11537 25128.32/16 11537 25128.32/16 556 11537 25128.32/16 556 11537 25128.32/16 X 556 11537 25AS X7BGP Operation: Messaging•Each AS has one or more BGP speakers.–Speakers learn of internal routes through the intradomain routing protocol.–Speakers inform BGP speakers in neighboring domains of local destinations.–Other routers in the domain can send traffic destined outside the domain to a speaker: they do not need a complete routing table.•BGP speakers exchange entire routing table only once. Thereafter, updates (announcements and withdrawals)•BGP speakers communicate using TCP (port 179)(+) Keeps retransmission and reordering of updates out of protocol(–) Routing updates “back off” during congestion•Speakers send “keep-alive” messages at regular intervals.8BGP Operation: A Low-Level ExampleR1R4R2R3ded R4d R4e R3 Ce R3 Ce R2 B Ce R2 B CAS AAS BAS CBGP SpeakersOther RoutersBGP SessionData Linkd R2 Bd R2 Bd R2 Bd R2 B9BGP Operation: Choosing Routes•Each AS defines a mapping from routes to nonnegative numbers: speakers use it to choose routes.•The number to which a route is assigned is called its “local-preference.”•When a BGP speaker receives two routes to a destination:–It chooses the one with higher local-preference, if possible.–Otherwise, it chooses the one with shorter AS-path, if possible.…–Ties are broken using the IP address of the next-hop router.•A speaker may advertise at most one route per destination to other speakers, so the last step always breaks a tie.10BGP Operation: Choosing Routes•Sample mapping from routes to local-preferences:If 556 is in AS-Path, return 200.Else if destination is 128.32/16 and AS-Path does not contain 556, return 150.Otherwise, return 100.•BGP speakers can be programmed to exclude certain routes from consideration.–Examples:•CALREN excludes routes from UCB with destinations other than 128.32/16, 169.229/16, and 136.152/16.11(Non)convergence of BGP•We say a routing protocol converges if routers settle on a set of routes and no new routing updates are sent.•One can prove that distance-vector and link-state routing protocols will always converge.•It was recently discovered (1996) that BGP does not necessarily converge.12Key Points•The Internet is too large for a flat routing architecture.•So, the Internet is split into Autonomous Systems (AS’s)–Routing problem separated into inter- and intradomain routing.•Interdomain routing presents unique challenges over intradomain.•The current interdomain routing protocol is the Border Gateway Protocol (BGP), a path-vector protocol.•Unlike other routing protocols, BGP does not necessarily converge.Buzzwords: Interdomain Routing, BGP, BGP Speakers, AS, AS Path, Local Preference, Path Vector Routing Protocol.13Extra Slides14Interdomain Routing by the numbersNumber of registered AS’s18633Number of IP addresses “assigned”About 89 millionAverage AS size (IP addresses)About 4780Statistics on the Internet at Large Statistics on one BGP SpeakerNumber of routes storedAbout 91000Average AS- path length4.3Maximum AS- path length10From www.telstra.net/ops/bgptable.html, 9/23/00From rs.arin.net and www.netsizer.com, 9/23/0015When does a network become an AS?•To receive an AS number, a network must–Be multi-homed (i.e. have more than one connection to the rest of the network)–Be capable of running BGP –Pay 500 USD There is no minimum network size to become an AS.•Example: a small company with a single provider is considered part of the provider’s AS.16Nonconvergence of BGP: An Example•Consider an internet with 4 AS’s, •Focus on a destination d in AS 0.•AS 1 will accept routes 10 and 120 to d, but prefers 120.•AS 2 will accept routes 20 and 230 to d, but prefers 230.•AS 3 will accept routes 30 and 310 to d, but prefers 310.12 3017Nonconvergence of BGP: An Example012 3012 3012 3012 3012 3012 3…d 2 0d 1 0d 3 1 0d 2 0d 2 3 0d 3 018Classless InterDomain Routing (1991)•A temporary solution to two immediate dangers: 1. Class-B address space exhaustion–Class-A allows 16,777,216 hosts: “too
View Full Document
Unlocking...