DOC PREVIEW
Princeton COS 461 - Policy­Based Path­Vector Routing

This preview shows page 1-2-3-18-19-37-38-39 out of 39 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 39 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 39 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 39 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 39 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 39 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 39 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 39 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 39 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 39 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

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–WithdrawalIf 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

Princeton COS 461 - Policy­Based Path­Vector Routing

Documents in this Course
Links

Links

39 pages

Lecture

Lecture

76 pages

Switches

Switches

35 pages

Lecture

Lecture

42 pages

Links

Links

39 pages

Lecture

Lecture

34 pages

Topology

Topology

42 pages

Lecture

Lecture

42 pages

Overview

Overview

42 pages

Sockets

Sockets

45 pages

Load more
Download Policy­Based Path­Vector Routing
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Policy­Based Path­Vector Routing and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Policy­Based Path­Vector Routing 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?