Interdomain RoutingToday’s Lecture: Interdomain RoutingInternet RoutingInternet Routing Protocol: BGPTwo Flavors of BGPInternal BGP (iBGP)Example BGP Routing TableRouting Attributes and Route SelectionOther BGP AttributesLocal PreferenceCommunities and Local PreferenceAS Path LengthAS Path Length Hack: PrependingMultiple Exit Discriminator (MED)Problems with MEDHot-Potato RoutingProblems with Hot-Potato RoutingWhat policy looks like in Cisco IOSGeneral Problems with BGPInternet Business Model (Simplified)Filtering and RankingsThe Business Game and DepeeringDepeering ContinuedSlide 24Policy InteractionsStrawman: Global Policy CheckThink Globally, Act LocallyMain Idea of Today’s PaperRelationship #1: Customer-ProviderRelationship #2: PeeringRankingsAdditional Assumption: HierarchySafety: Proof SketchActivation Sequence: IntuitionSlide 35Proof, Step 1: Customer RoutesProof, Step 2: Peer & Provider RoutesRanking and Filtering InteractionsSome problemsOther Possible Local RankingsWhat Rankings Violate Safety?Interdomain Routing(Nick Feamster)February 4, 20082Today’s Lecture: Interdomain Routing•Today’s interdomain routing protocol: BGP–BGP route attributes•Usage•Problems–Business relationships•Today’s Paper: Stable Internet Routing without Global Coordination–Main ideas–ExtensionsSee http://nms.lcs.mit.edu/~feamster/papers/dissertation.pdf (Chapter 2.1-2.3) for good coverage of today’s topics.3Internet Routing•Large-scale: Thousands of autonomous networks•Self-interest: Independent economic and performance objectives•But, must cooperate for global connectivityComcastAbileneAT&TCogentGeorgiaTechThe Internet4Internet Routing Protocol: BGPRoute AdvertisementAutonomous Systems (ASes)SessionTraffic Destination Next-hop AS Path130.207.0.0/16130.207.0.0/16192.5.89.8966.250.252.4410578..2637174… 26375Two Flavors of BGP•External BGP (eBGP): exchanging routes between ASes•Internal BGP (iBGP): disseminating routes to external destinations among the routers within an ASeBGPiBGPQuestion: What’s the difference between IGP and iBGP?6Internal BGP (iBGP)“iBGP”Default: “Full mesh” iBGP. Doesn’t scale.Large ASes use “Route reflection” Route reflector: non-client routes over client sessions; client routes over all sessions Client: don’t re-advertise iBGP routes.7Example BGP Routing Table> show ip bgp Network Next Hop Metric LocPrf Weight Path*>i3.0.0.0 4.79.2.1 0 110 0 3356 701 703 80 i*>i4.0.0.0 4.79.2.1 0 110 0 3356 i*>i4.21.254.0/23 208.30.223.5 49 110 0 1239 1299 10355 10355 i* i4.23.84.0/22 208.30.223.5 112 110 0 1239 6461 20171 iThe full routing table> show ip bgp 130.207.7.237BGP routing table entry for 130.207.0.0/16Paths: (1 available, best #1, table Default-IP-Routing-Table) Not advertised to any peer 10578 11537 10490 2637 192.5.89.89 from 18.168.0.27 (66.250.252.45) Origin IGP, metric 0, localpref 150, valid, internal, best Community: 10578:700 11537:950 Last update: Sat Jan 14 04:45:09 2006Specific entry. Can do longest prefix lookup:PrefixAS pathNext-hop8Routing Attributes and Route Selection•Local preference: numerical value assigned by routing policy. Higher values are more preferred.•AS path length: number of AS-level hops in the path•Multiple exit discriminator (“MED”): allows one AS to specify that one exit point is more preferred than another. Lower values are more preferred.•Shortest IGP path cost to next hop: implements “hot potato” routing•Router ID tiebreak: arbitrary tiebreak, since only a single “best” route can be selectedBGP routes have the following attributes, on which the route selection process is based:9Other BGP Attributes•Next-hop: IP address to send packets en route to destination. (Question: How to ensure that the next-hop IP address is reachable?)•Community value: Semantically meaningless. Used for passing around “signals” and labelling routes. More in a bit.Next-hop: 4.79.2.1iBGP4.79.2.14.79.2.2Next-hop: 192.5.89.8910Local Preference•Control over outbound traffic•Not transitive across ASes•Coarse hammer to implement route preference•Useful for preferring routes from one AS over another (e.g., primary-backup semantics)PrimaryBackupHigher local prefLower local prefDestination11Communities and Local Preference•Customer expresses provider that a link is a backup•Affords some control over inbound traffic•More on multihoming, traffic engineering in Lecture 7PrimaryBackup“Backup” CommunityDestination12AS Path Length•Among routes with highest local preference, select route with shortest AS path length•Shortest AS path != shortest path, for any interpretation of “shortest path”DestinationTraffic13AS Path Length Hack: Prepending•Attempt to control inbound traffic•Make AS path length look artificially longer•How well does this work in practice vs. e.g., hacks on longest-prefix match?DAS 1AS 2AS 3AS 4AS Path: “1”AS Path: “1 1”AS Path: “3 1 1”AS Path: “2 1”Traffic14Multiple Exit Discriminator (MED)•Mechanism for AS to control how traffic enters, given multiple possible entry points.ISan FranciscoNew YorkLos AngelesDest.TrafficMED: 10MED: 2015Problems with MED•Safety: No persistent oscillations–Routing system should “settle down”, assuming the system’s inputs are not changing•R3 selects A•R1 advertises A to R2•R2 selects C•R1 selects C–(R1 withdraws A from R2)•R2 selects B–(R2 withdraws C from R1)•R1 selects A, advertises to R2R1R3 R2ABC2 1MED: 10MED: 20Preference between B and C at R2 depends on presence or absence of A.16Hot-Potato Routing•Prefer route with shorter IGP path cost to next-hop•Idea: traffic leaves AS as quickly as possibleINew York AtlantaWashington, DC510Dest.Common practice: Set IGP weights in accordance with propagation delay (e.g., miles, etc.)Traffic17Problems with Hot-Potato Routing•Small changes in IGP weights can cause large traffic shiftsINew YorkAtlantaWashington, DC510Dest.Question: Cost of sub-optimal exit vs. cost of large traffic shiftsTraffic1118What policy looks like in Cisco IOSInbound “Route Map”(import policy)eBGP Session19General Problems with BGP•Convergence•Security –Too easy to “steal” IP address space•http://www.renesys.com/blog/2006/01/coned_steals_the_net.shtml•Regular examples of suspicious activity (see Internet Alert