Interdomain Routing Policy Reading: Sections 4.3.3 plus optional readingGoals of Today’s LectureBGP ConvergenceCauses of BGP Routing ChangesBGP Session FailureRouting Change: Before and AfterRouting Change: Path ExplorationSlide 8BGP Converges SlowlyBusiness RelationshipsSlide 11Customer-Provider RelationshipCustomer Connecting to a ProviderMulti-Homing: Two or More ProvidersPrinceton ExamplePeer-Peer RelationshipAS Structure: Tier-1 ProvidersAS Structure: Other ASesRealizing BGP Routing PolicyBGP Policy: Applying Policy to RoutesBGP Policy: Influencing DecisionsImport Policy: Local PreferenceImport Policy: FilteringExport Policy: FilteringSlide 25Export Policy: Attribute ManipulationBGP Policy ConfigurationMultiple Routers in an ASAS is Not a Single NodeAn AS is Not a Single NodeInternal BGP and Local PreferenceSlide 32Early-Exit or Hot-Potato RoutingRealizing Hot-Potato RoutingJoining BGP and IGP InformationJoining BGP with IGP InformationSome Routers Don’t Need BGPSlide 38Conclusions1Interdomain Routing PolicyReading: Sections 4.3.3 plus optional readingCOS 461: Computer NetworksSpring 2008 (MW 1:30-2:50 in COS 105)Jennifer RexfordTeaching Assistants: Sunghwan Ihm and Yaping Zhu http://www.cs.princeton.edu/courses/archive/spring08/cos461/2Goals of Today’s Lecture•BGP convergence–Causes of BGP routing changes–Path exploration during convergence•Business relationships between ASes–Customer-provider: customer pays provider–Peer-peer: typically settlement-free•Realizing routing policies–Import and export filtering–Assigning preferences to routes•Multiple routers within an AS–Disseminated BGP information within the AS–Combining with intradomain routing information3BGP Convergence4Causes of BGP Routing Changes•Topology changes–Equipment going up or down–Deployment of new routers or sessions•BGP session failures–Due to equipment failures, maintenance, etc.–Or, due to congestion on the physical path•Changes in routing policy–Changes in preferences in the routes–Changes in whether the route is exported•Persistent protocol oscillation–Conflicts between policies in different ASes5BGP Session Failure •BGP runs over TCP–BGP only sends updates when changes occur–TCP doesn’t detect lost connectivity on its own•Detecting a failure–Keep-alive: 60 seconds–Hold timer: 180 seconds•Reacting to a failure–Discard all routes learned from the neighbor–Send new updates for any routes that changeAS1AS26Routing Change: Before and After01230123(1,0)(2,0)(3,1,0)(2,0)(1,2,0)(3,2,0)7Routing Change: Path Exploration•AS 1–Delete the route (1,0)–Switch to next route (1,2,0)–Send route (1,2,0) to AS 3•AS 3–Sees (1,2,0) replace (1,0)–Compares to route (2,0)–Switches to using AS 20123(2,0)(1,2,0)(3,2,0)8Routing Change: Path Exploration•Initial situation–Destination 0 is alive–All ASes use direct path•When destination dies–All ASes lose direct path–All switch to longer paths–Eventually withdrawn•E.g., AS 2–(2,0) (2,1,0) –(2,1,0) (2,3,0) –(2,3,0) (2,1,3,0)–(2,1,3,0) null1230(1,0)(1,2,0)(1,3,0)(2,0)(2,1,0)(2,3,0)(2,1,3,0)(3,0)(3,1,0)(3,2,0)9BGP Converges Slowly•Path vector avoids count-to-infinity–But, ASes still must explore many alternate paths–… to find the highest-ranked path that is still available•Fortunately, in practice–Most popular destinations have very stable BGP routes–And most instability lies in a few unpopular destinations•Still, lower BGP convergence delay is a goal–Can be tens of seconds to tens of minutes–High for important interactive applications–… or even conventional application, like Web browsing10Business Relationships11Business Relationships•Neighboring ASes have business contracts–How much traffic to carry–Which destinations to reach–How much money to pay•Common business relationships–Customer-providerE.g., Princeton is a customer of USLECE.g., MIT is a customer of Level3–Peer-peerE.g., UUNET is a peer of SprintE.g., Harvard is a peer of Harvard Business School12Customer-Provider Relationship•Customer needs to be reachable from everyone–Provider tells all neighbors how to reach the customer•Customer does not want to provide transit service–Customer does not let its providers route through itddprovidercustomercustomerproviderTraffic to the customer Traffic from the customerannouncementstraffic13Customer Connecting to a ProviderProviderProvider1 access link2 access linksProvider2 access routersProvider2 access PoPs14Multi-Homing: Two or More Providers•Motivations for multi-homing–Extra reliability, survive single ISP failure–Financial leverage through competition–Better performance by selecting better path–Gaming the 95th-percentile billing modelProvider 1Provider 215Princeton Example•Internet: customer of USLEC and Patriot•Research universities/labs: customer of Internet2•Local non-profits: provider for several non-profitsPatriotUSLECInternet216Peer-Peer Relationship•Peers exchange traffic between customers –AS exports only customer routes to a peer–AS exports a peer’s routes o nly to its customers–Often the relationship is settlement-free (i.e., no $$$)peerpeerTraffic to/from the peer and its customersdannouncementstraffic17AS Structure: Tier-1 Providers•Tier-1 provider–Has no upstream provider of its own–Typically has a national or international backbone•Top of the Internet hierarchy of ~10 ASes–AOL, AT&T, Global Crossing, Level3, UUNET, NTT, Qwest, SAVVIS (formerly Cable & Wireless), and Sprint–Full peer-peer connections between tier-1 providers18AS Structure: Other ASes•Other providers–Provide transit service to downstream customers–… but, need at least one provider of their own–Typically have national or regional scope–Includes several thousand ASes•Stub ASes–Do not provide transit service to others–Connect to one or more upstream providers–Includes the vast majority (e.g., 85-90%) of the ASes19Realizing BGP Routing Policy20BGP Policy: Applying Policy to Routes•Import policy–Filter unwanted routes from neighborE.g. prefix that your customer doesn’t own–Manipulate attributes to influence path selectionE.g., assign local preference to favored routes•Export policy–Filter routes you don’t want to tell your neighborE.g., don’t tell a peer a route learned from other peer–Manipulate attributes to control what they seeE.g.,
View Full Document