Border Gateway Protocol v4Rob SherwoodStanford CS144October 14, 2009WhatIntra-domain routing protocols (IGP)Last timeOSPF – link stateIS-IS: like OSPF but not on IPRIP – distance vectorInter-domain (EGP)TodayBorder Gateway Protocol v4Path vector routing protocol: list possible pathsNo other EGP’s today... why?Why Inter vs. Intra?Why not just use OSPF everywhere?e.g., hierarchies of OSPF areasWhy Inter vs. Intra?Why not just use OSPF everywhere?e.g., hierarchies of OSPF areasHint: scaling is not the only limitationWhy Inter vs. Intra?Why not just use OSPF everywhere?e.g., hierarchies of OSPF areasHint: scaling is not the only limitationBGP is a policy control and information hidingprotocolintra == trusted, inter == untrustedWhy Study BGP?Critical protocol: makes the Internet runOnly widely deployed EGPActive area of problems!EfficiencyCogent vs. Level3: Internet partitionPakistan accidentally took down YouTubeSpammers use prefix hijackingOutlineHistory (ver y briefl y!)FunctionPropertiesPolici esExampleProblems and propos ed soluti onsHistoryWhy border gateway protocol?Histori cal distinction:1rfc1105 : BGPv1 1989 : ”dir ecti onal” routing2rfc1163 : BGPv2 1990 :3rfc1267 : BGPv3 19914rfc1654 : BGPv4 (proposed) 19945rfc1771 : BGPv4 (actual) 1995: CIDR supportrfc1772-1774 additional infoHigh LevelAbstract each AS down to a single nodeExchange prefix-reachabi lity wi th all neighbors“I can reach prefix 171.67.0.0/14 throughAS’es 15444 3549 174 46749 32”Select a single path by routing policyCritical: learn many paths, propagate only one!Add your ASN to advertised pathsBGP ExampleAS 1AS 2AS 4AS 51.2.0.0/16AS 3Only 1 RouterPer AS (for now)BGP ExampleAS 1AS 2AS 4AS 51.2.0.0/161.2.0.0/16: AS 1AS 31.2.0.0/16: AS 1Only 1 RouterPer AS (for now)BGP ExampleAS 1AS 2AS 4AS 51.2.0.0/161.2.0.0/16: AS 2 1AS 31.2.0.0/16: AS 5 1Only 1 RouterPer AS (for now)BGP ExampleAS 1AS 2AS 4AS 51.2.0.0/16AS: 3 2 1AS 3AS: 4 5 1Only 1 RouterPer AS (for now)BGP ExampleAS 1AS 2AS 4AS 51.2.0.0/16AS 3Only 1 RouterPer AS (for now)BGP ImplicationsExplicit AS path == loop free!Except under churn, IGP/EGP mismatch, etc.Not all ASes know all pathsAS abstraction – loss of efficiencyShortest AS path not guaranteedScaling32K ASes300K+ prefixesTransport Details1Border routers must directly connect2Connect tcp port 17 93Negotiate features4Full information exchange – expensiv e!5Exchange periodic updates indefinitelySession resets are expensi ve (both in CPU and tothe entire network!) and should be avoided.AdvertisementsDestination prefix: 171.67.0.0/ 14AS Path: ASN 15444 3549 174 46749 32Next Hop IP: just like in RIPv2Knobs for traffic engineeringMetric, Weight, LocalPath, MED, CommunitiesLots of voodooGetting Your Hands DirtyRouteViews Project:http://www .routeviews. org/1telnet route-views.linx.routeviews.org2show ip bgp 171. 67.0.0/14 longer-prefixesnote that all paths are learned internallynot a production deviceRoute Selection 1/21Next-Hop reachable?2Prefer highest weight3Prefer highest local-pref4Prefer locally originated routes5Prefer routes with shortest AS path lengthRoute Selection 2/26Prefer path with lowest origin type7Prefer route with lowest MED value8Prefer eBGP over iBGP9Prefer routes with lowest cost to egress pointhot-potato routing10Tie-braking rulese.g., lowest router-id, oldest routeRevisit RouteViews DataWhy was that route selected?Why are there two routes to Stanford?External vs. Internal BGPAS 1AS 2AS 4AS 51.2.0.0/16AS 3Only 1 RouterPer AS (for now)External vs. Internal BGPAS 1AS 2AS 4AS 51.2.0.0/16AS 3iBGP keeps AS consistentMultiple Peering Points!BGP Relationships 1/2Customer/Provider:Customers pay for connectivitye.g., Stanford pays Cog entCustomer is a stub, provider is a transitAmount and cost structure can vary wildlyMany customers are multi-homedStanford also connects to Calren/Internet2Typical policy: prefer routes from customersBGP Relationships 2/2Peers:ASes agree to exchange traffic for freePenalties/renegotiate if imbalanceTier 1 ISPs have no default ro ute: all peer witheach otherYou are Tier i + 1 if you have a default routeto a Tier iBGP Relationship DramaCogent vs. Level3http://www .isp-planet.com/business/2005/cogentlevel 3.htmlLevel3 and Cogent were peersIn 2005, Level3 decided to start chargingCogentCogent said NoInternet partition: Cogent’s customers couldn’tget to Level3’s customersother ISPs were affected as wellThey came to a new, undisclosed agreement 3weeks laterBGP Problems and Solutions1Security2Convergence3Scaling (route reflectors)4Traffic engineering - AS preprending5Multiple stable solutio ns - BGP ”Wedgies”BGP SecurityAnyone can source a prefix announcementBGP is not very secure :-(YouTube’s prefix is 208.65 .152.0/22To block YouTube (by government directiv e), aPieNET advertised 208.65.152 .0/23 and208.65.152 .128/23 (lo ngest prefix match)Spammers steal unused IP space to hideSecure BGP is currently being deployedBGP ConvergenceGiven a change, how long until the networkre-stabilizes?... depends on the change: sometimes never.Open research problem: “tweak and pray”Distributed setting is challengingEasier: does thereexist a stable configuration?Distributed: open research problemCentralized: NP-Complete problem![Griffin-Sigcomm99]Scaling iBGP: Route ReflectorsAS 1AS 2AS 4AS 51.2.0.0/16AS 3iBGP keeps AS consistentMultiple Peering Points!Scaling iBGP: Route ReflectorsiBGP Mesh == O(n^2) messAS 1Scaling iBGP: Route ReflectorsSolution: Route ReflectorsO(n*k)AS 1Traffic Engineering“Route-map” programs to set weightsRoute filtering: input and outputMore specifi c routes: longest prefixAS prependi ng: “32 32 32 32”Imprecise sciencerfc4264: BGP WedgiesA Comm on config :Prefer customer routes over non-customerThen prefer shortest AS pathrfc4264: BGP WedgiesAS 1AS 2AS 4AS 51.2.0.0/161.2.0.0/16: AS 1 1 1 1AS 31.2.0.0/16: AS 1Backup Routerfc4264: BGP WedgiesAS 1AS 2AS 4AS 51.2.0.0/161.2.0.0/16: AS 1 1 1 1AS 3AS 5 1Backup Routerfc4264: BGP WedgiesAS 1AS 2AS 4AS 51.2.0.0/161.2.0.0/16: AS 1 1 1 1AS 3AS 4 5 1Backup Routerfc4264: BGP WedgiesAS 1AS 2AS 4AS 51.2.0.0/161.2.0.0/16: AS 1 1 1 1AS 3AS 3 4 5 1Backup Routerfc4264: BGP WedgiesAS 1AS 2AS 4AS 51.2.0.0/161.2.0.0/16: AS 1 1 1 1AS 3AS 2 3 4 5 1Backup Routerfc4264: BGP WedgiesAS 1AS 2AS 4AS 51.2.0.0/161.2.0.0/16: AS 1 1 1 1AS 3Backup RouteLink Failure!rfc4264: BGP WedgiesAS 1AS 2AS 4AS 51.2.0.0/161.2.0.0/16: AS 1 1 1 1AS 3Backup RouteAS 2 1 1 1 1rfc4264: BGP WedgiesAS 1AS 2AS 4AS
View Full Document
Unlocking...