CS 6390 Advanced Computer NetworksInter-AS routing in the Internet: (BGP)Inter-domain routingReachability vs OptimalityPath selectionRouting LoopsCustomers and ProvidersNontransit vs. Transit ASesSelective TransitCustomers Don’t Always Need BGPCustomer-Provider HierarchyThe Peering RelationshipPeering Provides ShortcutsBGP-4BGP Operations (Simplified)A Sample BGP tableSlide 17BGP: controlling who routes to youSlide 19So, which routes to advertise and whom to advertise?Two Types of BGP Neighbor RelationshipsWhy do we need iBGP?Slide 23BGP Route ProcessingRoute Selection SummarySo many choices …ASPATH AttributeChoosing between multiple exit pointsMultihomed Backups (Outbound Traffic)Multihomed Backups (Inbound Traffic)Interdomain Loop PreventionShorter Doesn’t Always Mean ShorterHow to integrate intra-domain and inter-domain routingCS 6390Advanced Computer NetworksInter-domain Routing(BGP)Inter-AS routing in the Internet: (BGP) Figure 4.5.2-new2: BGP use for inter-domain routing AS2 (OSPF intra-AS routing) AS1 (RI P intra-AS routing) BGP AS3 (OSPF intra-AS routing) BGP R1 R2 R3 R4 R5Inter-domain routing BGP providesInter-domain reachability in a scalable wayEnables ISPs to implement various policiesHelps ISPs to cooperate under competitive circumstancesInter-domain routing is hardDue to its large scale More than 150,000 prefixes and ~20,000 ASesDue to autonomous nature of ASesCost metrics may be different in different ASesDue to trust issuesDue to the need to support various types of policiesReachability vs OptimalityEach AS can choose its own intra-AS routing protocolCan use any cost metrics to its interior pathsNo consistency between ASesA cost of 1000 may be good for one, may be unacceptable for otherImpossible to find least cost path to a destination ASAny path is okay!Each AS originates “reachability advertisements”I’m AS1 and I own networks 129.110/16, 129.111/16ASes advertise/exchange reachability to other ASesI’m AS2 and can reach AS1 that includes 129.110/16 and 129.111/16 (no cost is mentioned!)So the advertised path is (AS2 AS1)Path selectionSuppose AS3 sends its-path-to-AS1 (AS3 AS2 AS1) to its peer AS4AS4 may or may not select the path offered by AS3Cost, policy (don’t route via competitors AS), loop prevention reasonsIf AS4 select the path, thenPath (AS4,AS1) = AS4, Path(AS3,AS1)AS3 can control incoming traffic by controlling its route advertisementsE.g., don’t want to route traffic to AS1 -> don’t advertise any routes to AS1 to neighbor AS4AS1AS2AS3AS4Routing LoopsExample:AS2 announces to AS3 it can reach AS1AS3 announces to AS4 it can reach AS1AS4 announces to AS2 it can reach AS1AS2 chooses AS4 as its next hop to AS1AS1AS2AS3AS4Loops are bad!Traffic interruptionCongestion in the networkCustomers and ProvidersCustomer pays provider for access to the InternetprovidercustomerIP trafficprovidercustomer8Nontransit vs. Transit ASesISP 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 trafficInternet Serviceproviders (often)have transit networks9Selective TransitNET BNET CNET A provides transitbetween NET B and NET Cand between NET D and NET CNET ANET DNET A DOES NOTprovide transitBetween NET D and NET BMost transit networks transit in a selective manner…IP trafficCustomers Don’t Always Need BGPprovidercustomerNail up default routes 0.0.0.0/0pointing to provider.Nail up routes 192.0.2.0/24pointing to customer192.0.2.0/24Static routing is the most common way of connecting anautonomous routing domain to the Internet.Customer-Provider HierarchyIP trafficprovidercustomerThe Peering Relationshippeer peercustomerproviderPeers provide transit between their respective customersPeers do not provide transit between peersPeers (often) do not exchange $$$trafficallowedtraffic NOTallowedPeering Provides ShortcutsPeering also allows connectivity betweenthe customers of “Tier 1” providers.peer peercustomerproviderBGP-4BGP (Border Gateway Protocol)Current standard protocol for interdomain routingEach AS has One or more border routersConnects an AS to the InternetUsed for external routesOne or more BGP routers (BGP speakers)Routers that participate in the interdomain routingBGP routersReceive, filter route advertisements from neighbor BGP routersPerform route selectionTo route to destination X, which path (of several advertised) will be takenSend route advertisements to neighborsBGP is a Path Vector protocolSimilar to distance vector protocolBGP routes to networks, not individual hostsBGP advertisements include complete pathComplete path: list of ASes to reach a particular networkWhy? What is the utility of including the complete path?15BGP Operations (Simplified) Establish session on TCP port 179Exchange allactive routes Exchange incremental updatesAS1AS2While connection is ALIVE exchangeroute UPDATE messagesBGP sessionruns on TCProuter> show ip bgpnext hop AS path* 12.104.140.0/22 213.200.87.254 0 3257 1239 701 6985 i* 209.123.12.51 0 8001 7911 701 6985 i* 203.62.252.26 0 1221 4637 701 6985 i64.50.230.1 0 4181 3356 701 6985 i* 12.104.147.0/24 213.200.87.254 0 3257 7132 21744 i* 209.123.12.51 0 8001 1784 7132 21744 i* 64.50.230.1 0 4181 7132 21744 i* 216.191.65.118 0 15290 7132 21744 i* 213.140.32.146 0 12956 7132 21744 i* 12.104.244.0/24 213.200.87.254 0 3257 1239 701 15343 i* 64.50.230.1 0 4181 3356 701 15343 i* 209.123.12.51 0 8001 7911 701 15343 i* 157.130.182.254 0 19092 701 15343 i* 203.62.252.26 0 1221 4637 701 15343 iA Sample BGP tableBGP messagesBGP messages:OPEN: opens TCP connection to peer and authenticates senderUPDATE: advertises new path (or withdraws old)IP Prefix: AttributesKEEPALIVE: keeps connection alive in absence of UPDATES; also ACKs OPEN requestNOTIFICATION: reports errors in previous msg; also used to close connectionBGP: controlling who routes to you Figure 4.5-BGPnew: a simple BGP scenario A B C W X Y legend: customer
View Full Document