Policy-Based Path-Vector Routing Reading: Sections 4.3.3Goals of Today’s LectureInterdomain RoutingChallenges for Interdomain RoutingShortest-Path Routing is RestrictiveLink-State Routing is ProblematicDistance Vector is on the Right TrackPath-Vector RoutingFaster Loop DetectionFlexible PoliciesBorder Gateway ProtocolBGP OperationsIncremental ProtocolBGP RouteASPATH AttributeBGP Path SelectionBGP Policy: Applying Policy to RoutesBGP Policy: Influencing DecisionsImport Policy: Local PreferenceImport Policy: FilteringExport Policy: FilteringExport Policy: Attribute ManipulationBGP Policy ConfigurationAS is Not a Single NodeAn AS is Not a Single NodeInternal BGP and Local PreferenceSlide 27Hot-Potato (Early-Exit) RoutingJoining BGP and IGP InformationJoining BGP with IGP InformationSome Routers Don’t Need BGPSlide 32Causes of BGP Routing ChangesBGP Session FailureRouting Change: Before and AfterRouting Change: Path ExplorationSlide 37BGP Converges Slowly, if at AllConclusions1Policy-Based Path-Vector RoutingReading: Sections 4.3.3COS 461: Computer NetworksSpring 2006 (MW 1:30-2:50 in Friend 109)Jennifer RexfordTeaching Assistant: Mike Wawrzoniak http://www.cs.princeton.edu/courses/archive/spring06/cos461/2Goals of Today’s Lecture•Challenges of interdomain routing–Scale, privacy, and policy–Limitations of link-state and distance-vector routing•Path-vector routing–Faster loop detection than distance-vector routing–More flexibility than shortest-path routing•Border Gateway Protocol (BGP)–Incremental, prefix-based, path-vector protocol–Programmable import and export policies–Multi-step decision process for selecting “best” route•Multiple routers within an AS•BGP convergence delay3Interdomain Routing•AS-level topology–Destinations are IP prefixes (e.g., 12.0.0.0/8)–Nodes are Autonomous Systems (ASes)–Links are connections & business relationships1234567Client Web server4Challenges for Interdomain Routing•Scale–Prefixes: 150,000-200,000, and growing–ASes: 20,000 visible ones, and growing–AS paths and routers: at least in the millions…•Privacy–ASes don’t want to divulge internal topologies–… or their business relationships with neighbors•Policy–No Internet-wide notion of a link cost metric–Need control over where you send traffic–… and who can send traffic through you5Shortest-Path Routing is Restrictive•All traffic must travel on shortest paths•All nodes need common notion of link costs•Incompatible with commercial relationshipsRegional ISP1Regional ISP2Regional ISP3Cust1Cust3Cust2National ISP1National ISP2YESNO6Link-State Routing is Problematic•Topology information is flooded –High bandwidth and storage overhead–Forces nodes to divulge sensitive information•Entire path computed locally per node–High processing overhead in a large network•Minimizes some notion of total distance–Works only if policy is shared and uniform•Typically used only inside an AS–E.g., OSPF and IS-IS7Distance Vector is on the Right Track•Advantages–Hides details of the network topology–Nodes determine only “next hop” toward the dest•Disadvantages–Minimizes some notion of total distance, which is difficult in an interdomain setting–Slow convergence due to the counting-to-infinity problem (“bad news travels slowly”)•Idea: extend the notion of a distance vector8Path-Vector Routing•Extension of distance-vector routing–Support flexible routing policies–Avoid count-to-infinity problem•Key idea: advertise the entire path–Distance vector: send distance metric per dest d–Path vector: send the entire path for each dest d321d“d: path (2,1)”“d: path (1)”data trafficdata traffic9Faster 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 advertisement321“d: path (2,1)”“d: path (1)”“d: path (3,2,1)”10Flexible 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”23111•Interdomain routing protocol for the Internet –Prefix-based path-vector protocol–Policy-based routing based on AS Paths–Evolved during the past 15 years•1989 : BGP-1 [RFC 1105]–Replacement for EGP (1984, RFC 904) •1990 : BGP-2 [RFC 1163]•1991 : BGP-3 [RFC 1267]•1995 : BGP-4 [RFC 1771] –Support for Classless Interdomain Routing (CIDR) Border Gateway Protocol12BGP OperationsEstablish session on TCP port 179 Exchange all active routes Exchange incremental updatesAS1AS2While connection is ALIVE exchangeroute UPDATE messagesBGP session13Incremental Protocol•A node learns multiple paths to destination–Stores all of the routes in a routing table–Applies policy to select a single active route–… and may advertise the route to its neighbors•Incremental updates–Announcement Upon selecting a new active route, add node id to path… and (optionally) advertise to each neighbor–WithdrawalIf the active route is no longer available… send a withdrawal message to the neighbors14BGP Route•Destination prefix (e.g,. 128.112.0.0/16)•Route attributes, including–AS path (e.g., “7018 88”)–Next-hop IP address (e.g., 12.127.0.121)AS 88Princeton128.112.0.0/16AS path = 88Next Hop = 192.0.2.1AS 7018AT&T AS 12654RIPE NCCRIS project 192.0.2.1128.112.0.0/16AS path = 7018 88Next Hop = 12.127.0.12112.127.0.12115ASPATH AttributeAS7018128.112.0.0/16AS Path = 88AS 1239SprintAS 1755EboneAT&TAS 3549Global Crossing 128.112.0.0/16AS Path = 7018 88128.112.0.0/16AS Path = 3549 7018 88AS 88128.112.0.0/16PrincetonPrefix OriginatedAS 12654RIPE NCCRIS project AS 1129Global Access128.112.0.0/16AS Path = 7018 88128.112.0.0/16AS Path = 1239 7018 88128.112.0.0/16AS Path = 1129 1755 1239 7018 88128.112.0.0/16AS Path = 1755 1239 7018 8816BGP Path Selection•Simplest case–Shortest AS path–Arbitrary tie break•Example–Four-hop AS path preferred over a three-hop AS path–AS 12654 prefers path through Global Crossing•But, BGP is not limited to shortest-path routing–Policy-based routingAS 3549Global Crossing 128.112.0.0/16AS Path = 3549 7018 88AS 12654RIPE NCCRIS project AS 1129Global Access128.112.0.0/16AS Path = 1129 1755 1239
View Full Document