Outline Why does BGP exist EE 122 Interdomain Routing Protocol BGP Ion Stoica TAs Junda Liu DK Moon David Zats What is interdomain routing and why do we need it Why does BGP look the way it does How does BGP work Path vector algorithm and many boring details http inst eecs berkeley edu ee122 fa09 pay more attention to the why than the how Materials with thanks to Vern Paxson Jennifer Rexford and colleagues at UC Berkeley 1 BGP Routing Provides paths between networks 2 Internet is more complicated Internet not just unstructured collection of networks Internet is comprised of a set of autonomous systems ASes 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 4 independently run networks some are commercial ISPs currently around 30 000 ASes ASes are sometimes called domains hence interdomain routing 1 Internet a large number of ASes Who speaks BGP AS2 BGP AS1 Large ISP Large ISP R3 R2 R1 Stub Small ISP Dial Up ISP Stub border router R Access Network internal router Two types of routers Stub Border router Edge Internal router Core 5 6 Purpose of BGP I BGP and E BGP you can reach net A via me BGP AS1 R1 R2 R3 R2 traffic to A IGP Intradomain routing Example OSPF I BGP AS2 A R3 IGP A AS1 E BGP announce B AS2 R1 table at R1 dest next hop A R2 R border router AS3 internal router R Share connectivity information across ASes 7 R5 R4 border router internal router B 8 2 In more detail 6 2 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 3 4 3 9 2 1 Border router Internal router 1 2 3 4 9 Provide internal reachability IGP Learn routes to external destinations eBGP Distribute externally learned routes internally iBGP Select closest egress IGP 10 1 ASes are autonomous Want to choose their own internal routing protocol 5 Minute Break Want freedom to route based on policy Questions Before We Proceed 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 11 different algorithms and metrics would reveal business relationships network structure 12 3 2 ASes have business relationships Relations between ASes customer provider peer peer Business Implications Customer pay provider Peers don t pay each other 2 ASes have business relationships traffic allowed 13 AS level topology Destinations are IP prefixes e g 12 0 0 0 8 Nodes are Autonomous Systems ASes Peers provide transit between their customers Peers do not provide transit to each other 14 What routing algorithm can we use Key issues are policy and privacy Can t use shortest path internals are hidden Links are connections business relationships 4 3 5 2 1 15 traffic not allowed Client 7 6 Can t use link state Web server domains don t have any shared metric policy choices might not be shortest path would have to flood policy preferences and topology would violate privacy 16 4 Path Vector Routing What about distance vector Does not reveal any connectivity information But is designed to compute shortest paths Extend distance vector to allow policy choices 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 d path 2 1 d path 1 3 1 2 data traffic 18 Faster Loop Detection Flexible Policies 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 Each node can apply local policies Node can simply discard paths with loops E g node 1 simply discards the advertisement 3 19 d path 1 2 d path 3 2 1 Path selection Which path to use Path export Which paths to advertise Examples d path 2 1 data traffic d 17 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 1 5 Selection vs Export Selection policies Route export Route selection determines which paths I want my traffic to take Export policies Illustration Customer determines whose traffic I am willing to carry Competitor 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 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 23 Selection controls traffic out of the network Export controls traffic into the network 22 Examples of Standard Policies Backup can depend on entire path advantage of PV approach 21 Primary Export Don t export routes for other domains Selection pick primary over backup Issues with Path vector Policy Routing Reachability Security Performance Lack of isolation Policy oscillations 24 6 Reachability Security In normal routing if graph is connected then reachability is assured With policy routing this does not always hold Peers don t provide transit to each other Customer doesn t provide transit for provider Provider AS 1 X AS 3 An AS can claim to serve a prefix that they actually don t have a route to blackholing traffic Provider Even worse snoop on all traffic to almost any destination AS 2 25 Customer Performance 26 BGP designed for policy not performance Fixable make ASes prove they have a path but not used in today s Internet AS path length can be misleading An AS may have many router level hops BGP says that path 4 1 is better than path 3 2 1 Hot Potato routing common but suboptimal without anyone realizing that anything is wrong Performance example problem not specific to policy or path vector important because of AS autonomy AS wants to hand off the packet as soon as possible Even BGP shortest paths are not shortest AS 4 Fewest AS s Fewest number of routers AS 3 20 of paths inflated by at least 5 router hops Not clear this is a significant problem 27 AS 2 28 AS 1 7 Lack of isolation routing table size Lack of Isolation dynamics If there is a change in the path the path must be re advertised to every node using the path BGP updates per hour per prefix Each BGP router must know path to every other IP prefix but router memory is expensive and thus
View Full Document
Unlocking...