Interdomain Routing Reading Sections K R 4 6 3 EE122 Intro to Communication Networks Fall 2007 WF 4 00 5 30 in Cory 277 Guest Lecture by Brighten Godfrey Instructor Vern Paxson TAs Lisa Fowler Daniel Killebrew Jorge Ortiz http inst eecs berkeley edu ee122 Materials with thanks to Scott Shenker Jennifer Rexford Ion Stoica and colleagues at Princeton and UC Berkeley 1 Outline Why does BGP exist What is interdomain routing and why do we need it Why does BGP look the way it does How does BGP work Boring details Yuck pay more attention to the why than the how 2 Routing Provides paths between networks Previous lecture presented two routing designs link state distance vector Previous lecture assumed single domain all routers have same routing metric shortest path no privacy issues no policy issues 3 Internet is more complicated Internet not just unstructured collection of networks Internet is comprised of a set of autonomous systems ASes independently run networks some are commercial ISPs currently around 20 000 ASes ASes are sometimes called domains hence interdomain routing 4 Internet a large number of ASes Large ISP Large ISP Stub Small ISP Dial Up ISP Stub Access Network Stub 5 This adds another level in hierarchy Three levels in logical routing hierarchy networks reaches individual hosts intradomain routes between networks interdomain routes between ASes Need a protocol to route between domains BGP is current standard BGP unifies network organizations 6 Who speaks BGP AS2 BGP AS1 R3 R2 R1 border router R internal router Two types of routers Border router Edge Internal router Core 7 Purpose of BGP you can reach net A via me AS2 BGP AS1 R3 R2 traffic to A R1 table at R1 dest next hop A R2 A R border router internal router Share connectivity information across ASes 8 I BGP and E BGP IGP Intradomain routing Example OSPF I BGP R3 IGP R2 A AS1 E BGP announce B AS2 R1 AS3 R5 R4 R border router internal router B 9 In more detail 6 2 3 4 3 9 2 1 Border router Internal router 1 2 3 4 Provide internal reachability IGP Learn routes to external destinations eBGP Distribute externally learned routes internally iBGP Select closest egress IGP 10 Rest of lecture Motivate why BGP is the way it is Discuss some problems with interdomain routing Discuss briefly what a new BGP might look like Explain some of BGP s details not fundamental just series of specific design decisions 11 Why BGP Is the Way It Is 12 1 ASes are autonomous Want to choose their own internal routing protocol different algorithms and metrics Want freedom to route based on policy my traffic can t be carried over my competitor s network I don t want to carry transit traffic through my network not expressible as Internet wide shortest path Want to keep their connections and policies private would reveal business relationships network structure 13 2 ASes have business relationships Three kinds of relationships between ASes AS A can be AS B s customer AS A can be AS B s provider AS A can be AS B s peer Business implications customer pays provider peers don t pay each other Policy implications When sending traffic I prefer to route through customers over peers and peers over providers I don t carry traffic from one provider to another provider 14 AS level topology Destinations are IP prefixes e g 12 0 0 0 8 Nodes are Autonomous Systems ASes internals are hidden Links are connections business relationships 4 3 5 2 1 7 Client 6 Web server 15 What routing algorithm can we use Key issues are policy and privacy Can t use shortest path domains don t have any shared metric policy choices might not be shortest path Can t use link state would have to flood policy preferences and topology would violate privacy 16 What about distance vector Does not reveal any connectivity information But is designed to compute shortest paths Extend distance vector to allow policy choices 17 Path Vector Routing Extension of distance vector routing Support flexible routing policies Faster loop detection no count to infinity Key idea advertise the entire path Distance vector send distance metric per dest d Path vector send the entire path for each dest d 3 d path 2 1 d path 1 1 2 data traffic data traffic d 18 Faster Loop Detection Node can easily detect a loop Look for its own node identifier in the path E g node 1 sees itself in the path 3 2 1 Node can simply discard paths with loops E g node 1 simply discards the advertisement 3 d path 2 1 d path 1 1 2 d path 3 2 1 19 Flexible Policies Each node can apply local policies Path selection Which path to use Path export Which paths to advertise Examples Node 2 may prefer the path 2 3 1 over 2 1 Node 1 may not let node 3 hear the path 1 2 2 3 1 20 Selection vs Export Selection policies determines which paths I want my traffic to take Export policies determines whose traffic I am willing to carry Notes any traffic I carry will follow the same path my traffic takes so there is a connection between the two from a protocol perspective decisions can be arbitrary can depend on entire path advantage of PV approach 21 Illustration Route export Route selection Customer Competitor Primary Backup Selection controls traffic out of the network Export controls traffic into the network 22 Examples of Standard Policies Transit network Selection prefer customer to peer to provider Export Let customers use any of your routes Let anyone route through you to your customer Block everything else Multihomed nontransit network Export Don t export routes for other domains Selection pick primary over backup 23 Any Questions 24 Issues with Path Vector Policy Routing Reachability Security Performance Lack of isolation Policy oscillations 25 Reachability In normal routing if graph is connected then reachability is assured With policy routing this does not always hold Provider AS 1 AS 3 AS 2 Provider Customer 26 Security An AS can claim to serve a prefix that they actually don t have a route to blackholing traffic problem not specific to policy or path vector important because of AS autonomy Fixable make ASes prove they have a path 27 Performance BGP designed for policy not performance Hot Potato routing common but suboptimal AS wants to hand off the packet as soon as possible Even BGP shortest paths are not shortest Fewest AS s Fewest number of routers 20 of paths inflated by at least 5 router hops Not clear this is a significant problem 28 Performance example AS path length can be misleading An AS may have many router level hops BGP says that path
View Full Document
Unlocking...