A Whirlwind Tour of Interdomain Routing Aaron Wagner awagner eecs berkeley edu EE 122 Class February 9 2001 Overview 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 weaknesses 2 The 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 3 Challenges 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 4 Border 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 s 5 BGP Operation A High Level Example UCB AS 25 128 32 16 25 CALREN AS 11537 128 32 16 25 128 32 16 128 32 16 X 556 11537 25 128 32 16 11537 25 AS X 128 32 16 556 11537 25 128 32 16 556 11537 25 Abilene AS 556 128 32 16 11537 25 6 BGP 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 7 BGP Operation A Low Level Example BGP Speakers R1 d R2 B e R2 B C Other Routers Data Link BGP Session de R2 B C AS A R2 d R4 R4 d R4 e R3 C d R2 B R3 de R3 R2 C B e d AS B AS C 8 BGP 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 9 BGP 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 ASPath 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 10 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 11 Key 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 12 Extra Slides 13 Interdomain Routing by the numbers Statistics on the Internet at Large Statistics on one BGP Speaker Number of registered AS s 18633 Number of IP About 89 addresses assigned million Average AS size IP addresses About 4780 From rs arin net and www netsizer com 9 23 00 Number of routes stored About 91000 Average ASpath length 4 3 Maximum ASpath length 10 From www telstra net ops bgptable html 9 23 00 14 When 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 15 Nonconvergence of BGP An Example 1 0 2 3 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 16 Nonconvergence of BGP An Example 1 d20 1 0 2 2 1 2 d230 0 3 0 1 d30 3 2 1 d10 3 d310 3 1 d20 0 2 0 3 2 0 3 17 Classless InterDomain Routing 1991 A temporary solution to two immediate dangers 1 Class B address space exhaustion Class A allows 16 777 216 hosts too large Class C allows 255 hosts too small Class B allows 65 536 hosts just right Only 16384 class B network numbers available Last Class B address would have been assigned in March 1994 2 Routing table explosion Idea assign multiple consecutive Class C addresses in place of Class B and aggregate 18 CIDR An Example 197 8 2 24 197 8 0 24 AS W 197 8 0 24 W 197 8 0 22 Y W X 197 8 1 24 X 197 8 1 24 AS X 197 8 3 24 AS Z AS Y Assign IP addresses to maximize aggregation 19 CIDR cont Imperfect technique old addresses multihoming changing providers etc 20 From www telstra net ops bgptable html 9 23 00 References http rs arin net regserv asnguide htm http www netsizer com http telstra net ops bgptable html Labovitz C Malan G Jahanian F Origins of Internet routing instability Proceedings of
View Full Document
Unlocking...