Outline Why does BGP exist What is interdomain routing and why do we need it Why does BGP look the way it does Interdomain Routing How does BGP work Reading Sections P D 4 3 3 4 Boring details Yuck EE122 Intro to Communication Networks Fall 2006 MW 4 00 5 30 in Donner 155 Vern Paxson pay more attention to the why than the how TAs Dilip Antony Joseph and Sukun Kim http inst eecs berkeley edu ee122 Materials with thanks to Jennifer Rexford Ion Stoica and colleagues at Princeton and UC Berkeley 1 3 Routing Internet is more complicated Provides paths between networks Internet not just unstructured collection of networks Previous lecture presented two routing designs Internet is comprised of a set of autonomous systems ASes link state distance vector independently run networks some are commercial ISPs currently around 20 000 ASes Previous lecture assumed single domain all routers have same routing metric shortest path no privacy issues no policy issues ASes are sometimes called domains hence interdomain routing 4 Internet a large number of ASes 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 Large ISP Large ISP Stub Need a protocol to route between domains Small ISP Dial Up ISP Stub BGP is current standard Access Network Different kinds of unification IP unifies network technologies BGP unifies network organizations Stub 6 7 1 Purpose of BGP Who speaks BGP you can reach net A via me AS2 BGP AS1 R3 R2 AS1 R1 border router R BGP traffic to A internal router AS2 R3 R2 R1 A table at R1 dest next hop A R2 Two types of routers Border router Edge Internal router Core border router R internal router Share connectivity information across ASes 8 9 In more detail I BGP and E BGP IGP Intradomain routing Example OSPF I BGP R2 R3 IGP A AS1 E BGP 6 announce B AS2 3 4 3 R1 AS3 R5 R4 R 2 border router internal router B 10 Rest of lecture 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 11 1 ASes are autonomous Want to choose their own internal routing protocol different algorithms and metrics Motivate why BGP is the way it is driven by two salient aspects of AS structure Want freedom to route based on policy Discuss some problems with interdomain routing 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 Discuss briefly what a new BGP might look like Want to keep their connections and policies private would reveal business relationships network structure Explain some of BGP s details not fundamental just series of specific design decisions 12 13 2 AS level topology 2 ASes have business relationships Three kinds of relationships between ASes Destinations are IP prefixes e g 12 0 0 0 8 Nodes are Autonomous Systems 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 internals are hidden Links are connections business relationships Business implications customer pays provider peers don t pay each other 4 3 5 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 What routing algorithm can we use 2 1 6 7 Client Web server 15 What about distance vector Key issues are policy and privacy Does not reveal any connectivity information Can t use shortest path But is designed to compute shortest paths domains don t have any shared metric policy choices might not be shortest path Extend distance vector to allow policy choices Can t use link state would have to flood policy preferences and topology would violate privacy 16 Path Vector Routing Faster Loop Detection Extension of distance vector routing Node can easily detect a loop Support flexible routing policies Faster loop detection no count to infinity Look for its own node identifier in the path E g node 1 sees itself in the path 3 2 1 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 2 data traffic 17 Node can simply discard paths with loops E g node 1 simply discards the advertisement 3 1 d path 2 1 d path 1 2 1 data traffic d 18 d path 3 2 1 19 3 Flexible Policies Selection vs Export Selection policies Each node can apply local policies determines which paths I want my traffic to take Path selection Which path to use Path export Which paths to advertise Export policies Examples determines whose traffic I am willing to carry 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 Notes any traffic I carry will follow the same path my traffic takes so there is a connection between the two 3 from a protocol perspective decisions can be arbitrary 1 20 Illustration Route advertisement can depend on entire path advantage of PV approach 21 Examples of Standard Policies Route selection Transit network Selection prefer customer to peer to provider Export only export customer s routes to peers Customer Primary Multihomed nontransit network Competitor Export Don t export routes for other domains Selection pick primary over backup Backup Selection controls traffic out of the network Export controls traffic into the network 22 Any Questions 23 Issues with Path Vector Policy Routing Reachability Security Performance Lack of isolation 24 Policy oscillations 25 4 Reachability Security In normal routing if graph is connected then reachability is assured 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 With policy routing this does not always hold Fixable make ASes prove they have a path 26 Performance 27 Lack of Isolation BGP designed for policy not performance If there is a change in the path the path must be re advertised to every node upstream of the change Hot Potato routing common but suboptimal AS wants to hand off the packet as soon as possible Distance vector provides more isolation 20 of paths inflated by at least 5 router hops Not clear this is a significant problem 28 Persistent Oscillations due to Policies focus of much recent research 1 If there is no global
View Full Document
Unlocking...