1 15-744: Computer Networking L-3 BGP 2 Next Lecture: Interdomain Routing • BGP • Assigned Reading • MIT BGP Class Notes • [Gao00] On Inferring Autonomous System Relationships in the Internet • Ooops… 3 Outline • Need for hierarchical routing • BGP • ASes, Policies • BGP Attributes • BGP Path Selection • iBGP • Inferring AS relationships • Problems with BGP • Convergence • Sub optimal routing 4 Routing Hierarchies • Flat routing doesn’t scale • Each node cannot be expected to have routes to every destination (or destination network) • Key observation • Need less information with increasing distance to destination • Two radically different approaches for routing • The area hierarchy • The landmark hierarchy2 5 Areas • Divide network into areas • Areas can have nested sub-areas • Constraint: no path between two sub-areas of an area can exit that area • Hierarchically address nodes in a network • Sequentially number top-level areas • Sub-areas of area are labeled relative to that area • Nodes are numbered relative to the smallest containing area 6 Routing • Within area • Each node has routes to every other node • Outside area • Each node has routes for other top-level areas only • Inter-area packets are routed to nearest appropriate border router • Can result in sub-optimal paths 7 Path Sub-optimality 1 2 3 1.1 1.2 2.1 2.2 3.1 3.2 2.2.1 3 hop red path vs. 2 hop green path start end 3.2.1 1.2.1 A Logical View of the Internet 8 Tier 1 Tier 1 Tier 2 Tier 2 Tier 2 Tier 3 • National (Tier 1 ISP) – “Default-free” with global reachability info Eg: AT & T, UUNET, Sprint • Regional (Tier 2 ISP) – Regional or country-wide Eg: Pacific Bell • Local (Tier 3 ISP) Eg: Telerama DSL Customer Provider3 9 •Source wants to reach LM0[a], whose address is c.b.a: •Source can see LM2[c], so sends packet towards c •Entering LM1[b] area, first router diverts packet to b •Entering LM0[a] area, packet delivered to a •Not shortest path •Packet may not reach landmarks Landmark Routing: Basic Idea LM2[c] LM1[b] r0[a] LM0[a] r2[c] r1[b] Network Node Path Landmark Radius 10 Landmark Routing: Example d.d.a d.d.b d.d.c d.d.e d.d.d d.d.f d.i.k d.i.g d.d.j d.i.i d.i.w d.i.u d.d.k d.d.l d.n.h d.n.x d.n.n d.n.o d.n.p d.n.q d.n.t d.n.s d.n.r d.i.v 11 Routing Table for Router g Landmark Level Next hop LM2[d] LM0[e] LM1[i] LM0[k] LM0[f] 2 1 0 0 0 f k f k f Router g Router t r0 = 2, r1 = 4, r2 = 8 hops •How to go from d.i.g to d.n.t? g-f-e-d-u-t •How does path length compare to shortest path? g-k-I-u-t d.d.a d.d.b d.d.c d.d.e d.d.d d.d.f d.i.k d.i.g d.d.j d.i.i d.i.w d.i.u d.d.k d.d.l d.n.h d.n.x d.n.n d.n.o d.n.p d.n.q d.n.t d.n.s d.n.r 12 Outline • Need for hierarchical routing • BGP • ASes, Policies • BGP Attributes • BGP Path Selection • iBGP • Inferring AS relationships4 13 Autonomous Systems (ASes) • Autonomous Routing Domain • Glued together by a common administration, policies etc • Autonomous system – is a specific case of an ARD • ARD is a concept vs AS is an actual entity that participates in routing • Has an unique 16 bit ASN assigned to it and typically participates in inter-domain routing • Examples: • MIT: 3, CMU: 9 • AT&T: 7018, 6341, 5074, … • UUNET: 701, 702, 284, 12199, … • Sprint: 1239, 1240, 6211, 6242, … • How do ASes interconnect to provide global connectivity • How does routing information get exchanged Nontransit vs. Transit ASes 14 ISP 1 ISP 2 Nontransit AS might be a corporate or campus network. Could be a “content provider” NET A Traffic NEVER flows from ISP 1 through NET A to ISP 2 (At least not intentionally!) IP traffic Customers and Providers 15 Customer pays provider for access to the Internet provider customer IP traffic provider customer The Peering Relationship 16 peer peer customer provider Peers provide transit between their respective customers Peers do not provide transit between peers Peers (often) do not exchange $$$ traffic allowed traffic NOT allowed A B C5 17 Peering Wars • Reduces upstream transit costs • Can increase end-to-end performance • May be the only way to connect your customers to some part of the Internet (“Tier 1”) • You would rather have customers • Peers are usually your competition • Peering relationships may require periodic renegotiation Peering struggles are by far the most contentious issues in the ISP world! Peering agreements are often confidential. Peer Don’t Peer 18 Routing in the Internet • Link state or distance vector? • No universal metric – policy decisions • Problems with distance-vector: • Bellman-Ford algorithm may not converge • Problems with link state: • Metric used by routers not the same – loops • LS database too large – entire Internet • May expose policies to other AS’s 19 Solution: Distance Vector with Path • Each routing update carries the entire path • Loops are detected as follows: • When AS gets route check if AS already in path • If yes, reject route • If no, add self and (possibly) advertise route further • Advantage: • Metrics are local - AS chooses path, protocol ensures no loops BGP-4 • BGP = Border Gateway Protocol • Is a Policy-Based routing protocol • Is the EGP of today’s global Internet • Relatively simple protocol, but configuration is complex and the entire world can see, and be impacted by, your mistakes. 20 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)6 BGP Operations (Simplified) 21 Establish session on TCP port 179 Exchange all active routes Exchange incremental updates AS1 AS2 While connection is ALIVE exchange route UPDATE messages BGP session 22 Interconnecting BGP Peers • BGP uses TCP to connect peers • Advantages: • Simplifies BGP • No need for periodic refresh - routes are valid until withdrawn, or the connection is lost • Incremental updates • Disadvantages • Congestion control on a routing
View Full Document
Unlocking...