Slide 1Next Lecture: Interdomain RoutingOutlineRouting HierarchiesAreasRoutingPath Sub-optimalityA Logical View of the InternetLandmark Routing: Basic IdeaLandmark Routing: ExampleRouting Table for Router gOutlineAutonomous Systems (ASes)Nontransit vs. Transit ASesCustomers and ProvidersThe Peering RelationshipPeering WarsRouting in the InternetSolution: Distance Vector with PathBGP-4BGP Operations (Simplified)Interconnecting BGP PeersFour Types of BGP MessagesPolicy with BGPExamples of BGP PoliciesExport PolicyImport RoutesExport RoutesBGP UPDATE MessagePath Selection CriteriaImportant BGP AttributesLOCAL PREFLOCAL PREF – Common UsesAS_PATHMulti-Exit Discriminator (MED)MEDMEDRoute Selection ProcessInternal vs. External BGPInternal BGP (I-BGP)Internal BGP (I-BGP)Route ReflectorPolicy ImpactHow to infer AS relationships?[Gao00] Basic AlgorithmHow does Phase 2 work?Next Lecture: Congestion ControlSafety: No Persistent OscillationMain Idea of Optional PaperOutlineMulti-homingMulti-homing to Multiple ProvidersAddress Space from one ISPPitfallsAddress Space from Both ISPsAddress Space Obtained IndependentlyOutlineSigns of Routing InstabilityRoute Flap StormRoute Flap DampeningBGP Limitations: OscillationsBGP Limitations: OscillationsBGP Limitations: OscillationsBGP Limitations: OscillationsBGP Limitations: OscillationsBGP Limitations: OscillationsBGP Limitations: OscillationsBGP Oscillations15-744: Computer NetworkingL-3 BGP2Next Lecture: Interdomain Routing•BGP•Assigned Reading•MIT BGP Class Notes•[Gao00] On Inferring Autonomous System Relationships in the Internet3Outline•Need for hierarchical routing•BGP•ASes, Policies•BGP Attributes•BGP Path Selection•iBGP •Inferring AS relationships•Problems with BGP•Convergence•Sub optimal routing4Routing 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 hierarchy5Areas•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 area6Routing•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 paths7Path Sub-optimality1 231.11.22.12.23.13.22.2.13 hop red pathvs.2 hop green pathstartend3.2.11.2.1A Logical View of the Internet8Tier 1 Tier 1Tier 2Tier 2Tier 2Tier 3•National (Tier 1 ISP)–“Default-free” with global reachability infoEg: AT & T, UUNET, Sprint•Regional (Tier 2 ISP)–Regional or country-wideEg: Pacific Bell•Local (Tier 3 ISP)Eg: Telerama DSLCustomerProvider9•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 landmarksLandmark Routing: Basic IdeaLM2[c]LM1[b]r0[a]LM0[a]r2[c]r1[b]Network NodePathLandmark Radius10Landmark Routing: Exampled.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.od.n.pd.n.qd.n.td.n.sd.n.rd.i.v11Routing Table for Router gLandmark Level Next hopLM2[d]LM0[e]LM1[i]LM0[k]LM0[f]21000fkfkfRouter gRouter tr0 = 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-td.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.od.n.pd.n.qd.n.td.n.sd.n.r12Outline•Need for hierarchical routing•BGP•ASes, Policies•BGP Attributes•BGP Path Selection•iBGP •Inferring AS relationships13Autonomous 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 exchangedNontransit vs. Transit ASes14ISP 1ISP 2Nontransit ASmight 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 Providers15Customer pays provider for access to the InternetprovidercustomerIP trafficprovidercustomerThe Peering Relationship16peer peercustomerproviderPeers provide transit between their respective customersPeers do not provide transit between peersPeers (often) do not exchange $$$trafficallowedtraffic NOTallowedABC17Peering 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 renegotiationPeering struggles are by far the most contentious issues in the ISP world!Peering agreements are often confidential.Peer Don’t Peer18Routing 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’s19Solution: 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 loopsBGP-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,
View Full Document
Unlocking...