115-744: Computer NetworkingL-3 BGPNext Lecture: Interdomain Routing•BGP• Assigned Reading• MIT BGP Class Notes• [Gao00] On Inferring Autonomous System Relationships in the Internet• Ooops…2Outline• Need for hierarchical routing•BGP•ASesPolicies•ASes, Policies• BGP Attributes• BGP Path Selection•iBGP• Inferring AS relationships• Problems with BGP• Convergence3• Sub optimal routingRouting Hierarchies• Flat routing doesn’t scale• Each node cannot be expected to have routes t d ti ti ( d ti ti t k)to every destination (or destination network)• Key observation• Need less information with increasing distance to destination• Two radically different approaches for ti4routing• The area hierarchy• The landmark hierarchy2Areas• Divide network into areas• Areas can have nested bsub-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 areasSbf1231.11.22.12.22.2.12.2.21.2.11.2.25•Sub-areas of area are labeled relative to that area• Nodes are numbered relative to the smallest containing area3.13.2Routing• Within area• Each node has routes to every other nodey• Outside area• Each node has routes for other top-level areas only• Inter-area packets are routed to nearest appropriate border router6appropriate border router• Can result in sub-optimal pathsPath Sub-optimality12211.11.22.12.22.2.1startend3.2.11.2.1733.13.23 hop red pathvs.2 hop green pathA Logical View of the Internet• National (Tier 1 ISP)– “Default-free” with globalreachabilityinfoTier 1 Tier 1Tier 2Tier 2Tier 3global reachabilityinfoEg: AT & T, UUNET, Sprint• Regional (Tier 2 ISP)– Regional or country-wideCustomerProvider8Tier 2Eg: Pacific Bell• Local (Tier 3 ISP)Eg: Telerama DSL3•Source wants to reach LM0[a], whose address is bLandmark Routing: Basic Ideac.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, ktdli dtLM2[c]LM1[b]r0[a]LM0[a]r1[b]9packet delivered to a•Not shortest path•Packet may not reach landmarksr2[c]Network NodePathLandmark RadiusLandmark Routing: Exampled.d.fd.d.ad.d.bd.d.cd.d.ed.d.dd.i.kd.i.gd.d.jd.i.id.i.wd.i.ud.d.kd.d.ld.i.v10d.n.hd.n.xd.n.nd.n.od.n.pd.n.qd.n.td.n.sd.n.rRouting Table for Router gLandmark Level Next hopLM2[d]LM[i]21fLM0[e]LM1[i]LM0[k]LM0[f]1000kfkfRouter gRouter tr0 = 2, r1 = 4, r2 = 8 hops• How to go from d.i.g to d.d.ad.d.bd.d.cd.d.ed.d.dd.d.fd.i.kd.i.gd.d.jd.i.id.i.wd.i.ud.d.kd.d.ld.n.hd.n.xd.n.nd.n.t11d.n.t? g-f-e-d-u-t• How does path length compare to shortest path? g-k-I-u-td.n.nd.n.od.n.pd.n.qd.n.sd.n.rOutline• Need for hierarchical routing• BGP•ASesPolicies•ASes, Policies• BGP Attributes• BGP Path Selection• iBGP• Inferring AS relationships124Autonomous Systems (ASes)• Autonomous Routing Domain• Glued together by a common administration, policies etc • Autonomous system –is a specific case of an ARD yp• 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 1219913UUNET: 701, 702, 284, 12199, …• Sprint: 1239, 1240, 6211, 6242, …• How do ASes interconnect to provide global connectivity • How does routing information get exchangedNontransit vs. Transit ASesISP 2ISP 1ISP 2Nontransit ASNET A14might be a corporateor campus network.Could be a “content provider”NET ATraffic NEVER flows from ISP 1through NET A to ISP 2(At least not intentionally!)IP trafficCustomers and ProvidersproviderIP trafficprovidercustomer15Customer pays provider for access to the InternetcustomerThe Peering RelationshippeerpeerPeers provide transit between ABC16peerpeercustomerproviderptheir respective customersPeers do not provide transit between peersPeers (often) do not exchange $$$trafficallowedtraffic NOTallowed5Peering Wars• Reduces upstream transit t• You would rather have Peer Don’t Peercosts• Can increase end-to-end performance• May be the only way to connect your customers to some part of the Internet (“Tier 1”)customers• Peers are usually your competition• Peering relationships may require periodic renegotiation17Internet (Tier 1) gPeering struggles are by far the most contentious issues in the ISP world!Peering agreements are often confidential.Routing in the Internet• Link state or distance vector?• No universal metric –policy decisionspy• Problems with distance-vector:• Bellman-Ford algorithm may not converge• Problems with link state:• Metric used by routers not the same – loops18• LS database too large – entire Internet• May expose policies to other AS’sSolution: Distance Vector with Path• Each routing update carries the entire path•Loops are detected as follows: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:Mti l lAS h th t l19•Metrics are local -AS chooses path, protocol ensures no loopsBGP-4• BGP = Border Gateway Protocol • Is a Policy-Based routing protocol •Is the EGP of today’s global Internet•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. 1989 : BGP-1 [RFC 1105]– Replacement for EGP (1984, RFC 904)201990 : BGP-2 [RFC 1163]1991 : BGP-3 [RFC 1267]1995 : BGP-4 [RFC 1771] – Support for Classless Interdomain Routing (CIDR)6BGP Operations (Simplified) Establish session onTCP port 179AS1Exchange allactive routes AS2BGP session21Exchange incrementalupdatesAS2While connection is ALIVE exchangeroute UPDATE messagesInterconnecting 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 protocol?22ggp• Inherits TCP vulnerabilities!• Poor interaction during high loadFour Types of BGP Messages• Open : Establish a peering session. •Keep Alive : Handshake at regular intervals.Keep Alive : Handshake at regular intervals. • Notification : Shuts down a peering session. • Update : Announcing new routes or
View Full Document
Unlocking...