CS551Inter-domain RoutingBill Chenghttp://merlot.usc.edu/cs551-f121 Computer Communications - CSCI 551 Copyright © William C. ChengInter-domain Routing2 Computer Communications - CSCI 551 Copyright © William C. Chengline cardline cardline cardline cardline cardrouteprocessorinterconnect(backplane, crossbar, etc.)Cisco 7xxx RouterJohn Stewart III: "BGP4 - Inter-domain routing in the Internet"3Sources Computer Communications - CSCI 551 Copyright © William C. ChengRFC1771 [Rekhter95a]: main BGP RFCRFC1772-3-4: application, experiences, and analysis of BGPRFC1965: AS confederations for BGPChristian Huitema: "Routing in the Internet", chapters 8 and 9Cisco tutorial online[Gao00b] sections 2.1 and 3.1excellent terse overview of BGP4BGP History Computer Communications - CSCI 551 Copyright © William C. Chengreachability protocol (no shortest path)Mid-80s: EGPdid not accommodate cycles (tree topology)evolved when all networks connected to ARPANETLimited size network topologyResult: BGP introduced as routing protocolToday: BGP-4 is the standard, IETF working on BGP-NGmysubnet 25BGP Basic Idea Computer Communications - CSCI 551 Copyright © William C. Chengmysubnet 1itsborderrouterotherrouterotherrouterotherrouterotherroutermyborderroutermynetworksmy ISPISP 3ISP 4my routesto theInternetInternetroutesto me... with dynamic changesand lots of controlMy ISP hardcodesmy networks intotheir routers6Simplify: No Dynamic Routing Computer Communications - CSCI 551 Copyright © William C. Chengmysubnet 2mysubnet 1itsborderrouterotherrouterotherrouterotherrouterotherroutermyborderroutermynetworksmy ISPISP 3ISP 4I use staticdefault routeto send all traffic7Complicate: Multihoming Computer Communications - CSCI 551 Copyright © William C. Chengmysubnet 2mysubnet 1itsborderrouterotherrouterotherrouterotherrouterotherroutermyborderroutermynetworksmy ISPISP 3ISP 4static routes do not work welllinks to multiple ISPsmultihomed hostsWhere?8Where And Why BGP? Computer Communications - CSCI 551 Copyright © William C. ChengE-BGP for inter-domain routing (between AS’s)I-BGP for intra-domain routing (within an AS)to deal with dynamics (link failure/recovery)Why?configurable policies on routesAS: autonomous system9BGP Terminology Computer Communications - CSCI 551 Copyright © William C. ChengPeer: an adjacent router (Note: not the same meaning as ISPpeering)Exchange point: place where many ISPs have routers andconnectionsRIB: routing information baseAdj-RIB-In: incoming routing informationLoc-RIB: local routing informationAdj-RIB-Out: outgoing routing informationa set of routers under a single technical administrationWhat is an AS?10Autonomous Systems Computer Communications - CSCI 551 Copyright © William C. Chenguses an interior gateway protocol (IGP) and commonmetrics to route packets within the ASuses an exterior gateway protocol (EGP) to route packetsto other AS’sAS may use multiple IGPs and metrics, but appears assingle AS to other AS’sWhy have both EGP and IGP?know different levels of detaildifferent levels of trustpolicy issues are much more important in EGP11Example Computer Communications - CSCI 551 Copyright © William C. Cheng1.2.11.2.21.21.11232.1 2.22.2.22.2.13.13.21.2.33.2.155.15.244.14.2EGPEGPEGPEGPEGPIGPIGPIGPIGPIGPAS1Stub: an AS that has only a single connection to one otherAS - carries only local trafficMulti-homed: an AS that has connections to more than oneAS, but does not carry transit trafficTransit: an AS that has connections to more than oneAS, and carries both transit and local traffic (under certainpolicy restrictions)12 Computer Communications - CSCI 551 Copyright © William C. Cheng AS Categories Stub Multi-homedMeMeAS1 AS3TransitMeAS1 AS3no universal metric - policy decisionsLink state or distance vector?13EGP Protocol Choices Computer Communications - CSCI 551 Copyright © William C. ChengBellman-Ford algorithm slow to converge (counting toinfinity problem)Problems with distance-vector:metric used by routers in different AS’s is not the same -may create loopsProblems with link state:link state database too large - entire Internetmay expose policies to other AS’swhen AS gets route check if AS already in pathEach routing update carries the entire path (AS’s appearin the path)14Solution: DV with Path Vectors Computer Communications - CSCI 551 Copyright © William C. ChengLoops are detected as follows:if yes, reject routeif no, add itself and (possibly) advertise route furtherAdvantage:metrics are local - AS chooses path, protocol ensures noloopsI-BGP communicate over multiple hopsBGP uses TCP to connect peers (port 179)15Interconnecting BGP Peers Computer Communications - CSCI 551 Copyright © William C. Chengno need for periodic refresh - routes are valid until with-drawn, or the connection is lost (hard state or soft state?)Advantages:incremental updatescongestion control on a routing protocol?Disadvantagessimplicity from reliability and orderingend-to-end argument: TCP connection can be alive butrouting mechanism can be hung, must have BGPkeepaliveTCP has keepalive option, why BGP keepalive also?consistent with the hop-by-hop Internet paradigmBGP advertises to neighbors only those routes that it uses16Hop-by-hop Model Computer Communications - CSCI 551 Copyright © William C. Chenge.g., AS1 cannot tell AS2 to route to other AS’s in amanner different than what AS2 has chosen (need sourcerouting for that)17Protocol Observations Computer Communications - CSCI 551 Copyright © William C. Chengtimeout (hold time)How does BGP know when a link is down/out?see [Shaihk00a]path vector via AS_PATHSHow does BGP avoid looping paths?loop detection on route receipt (or transmission [Labovitz00a])18BGP Messages Computer Communications - CSCI 551 Copyright © William C. ChengOPEN: sets up timeout, AS, id, etc.UPDATE: update (inject, withdraw) routes with attributesNOTIFICATION: error reportingKEEPALIVE: no change, but link is upTCP has keepalive option, why BGP keepalive also?end-to-end argument: TCP connection can be alive butrouting mechanism can be hung, must have BGPkeepaliveORIGIN: where prefix orginates19BGP Attributes Computer Communications - CSCI 551 Copyright © William C. ChengAS_PATH: path for routingNEXT_HOP: where to send dataMULTI_EXIT_DISCRIMINATOR: used to influencemulti-homingWhy BGP Attributes?want to do policy routingwant some way to prevent looping in DV routing(AS_PATH)flexibilities (allows extensibility)BGP provides capability for enforcing various
View Full Document
Unlocking...