INTERDOMAIN*ROUTING*POLICY*READING:*SECTIONS*4.3.3*PLUS*OPTIONAL*READING*COS$461:$Computer$Networks$Spring$2009$(MW$1:30‐2:50$in$COS$105)$Mike$Freedman$Teaching$Assistants:$WyaI$Lloyd$and$Jeff$Terrace$hIp://www.cs.princeton.edu/courses/archive/spring09/cos461/$1!Goals$of$Today’s$Lecture$• BGP$convergence$– Causes$of$BGP$rouVng$changes$– Path$exploraVon$during$convergence$• Business$relaVonships$between$ASes$– Customer‐provider:$customer$pays$provider$– Peer‐peer:$typically$seIlement‐free$• Realizing$rouVng$policies$– Import$and$export$filtering$– Assigning$preferences$to$routes$• MulVple$routers$within$an$AS$– Disseminated$BGP$informaVon$within$the$AS$– Combining$with$intradomain$rouVng$informaVon$2!BGP$Convergence$3!Causes$of$BGP$RouVng$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$congesVon$on$the$physical$path$• Changes$in$rouVng$policy$– Changes$in$preferences$in$the$routes$– Changes$in$whether$the$route$is$exported$• Persistent$protocol$oscillaVon$– Conflicts$between$policies$in$different$ASes$4!RouVng$Change:$Path$ExploraVon$• IniVal$situaVon$– DesVnaVon$0$is$alive$– All$ASes$use$direct$path$• When$desVnaVon$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)$$null$5!1 2 3 0 (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)BGP$Converges$Slowly$• Path$vector$avoids$count‐to‐infinity$– But,$ASes$sVll$must$explore$many$alternate$paths$– …$to$find$the$highest‐ranked$path$that$is$sVll$available$• Fortunately,$in$pracVce$– Most$popular$desVnaVons$have$very$stable$BGP$routes$– And$most$instability$lies$in$a$few$unpopular$desVnaVons$• SVll,$lower$BGP$convergence$delay$is$a$goal$– Can$be$tens$of$seconds$to$tens$of$minutes$– High$for$important$interacVve$applicaVons$– …$or$even$convenVonal$applicaVon,$like$Web$browsing$6!7!BGP$Not$Guaranteed$to$Converge$Example$known$as$a$“dispute$wheel”$1! 2!d!3!31d!3d!…!23d!2d!...!12d!1d!…!1d!31d!2d!12d!Business$RelaVonships$8!Business$RelaVonships$• Neighboring$ASes$have$business$contracts$– How$much$traffic$to$carry$– Which$desVnaVons$to$reach$– How$much$money$to$pay$• Common$business$relaVonships$– Customer‐provider$• E. g.,$Princeton$is$a$customer$of$USLEC$• E. g.,$MIT$is$a$customer$of$Level3$– Peer‐peer$• E. g.,$UUNET$is$a$peer$of$Sprint$• E. g.,$Harvard$is$a$peer$of$Harvard$Business$School$9!Customer‐Provider$RelaVonship$• 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$it$10!d d provider customer customer provider Traffic to the customer Traffic from the customer announcements trafficCustomer$ConnecVng$to$a$Provider$11!Provider Provider 1 access link 2 access links Provider 2 access routers Provider 2 access PoPsMulV‐Homing:$Two$or$More$Providers$• MoVvaVons$for$mulV‐homing$– Extra$reliability,$survive$single$ISP$failure$– Financial$leverage$through$compeVVon$– BeIer$performance$by$selecVng$beIer$path$– Gaming$the$95th‐percenVle$billing$model$12!Provider 1 Provider 2Princeton$Example$• Internet:$customer$of$USLEC$and$Patriot$• Research$universiVes/labs:$customer$of$Internet2$• Local$non‐profits:$provider$for$several$non‐profits$13!Patriot USLEC Internet214!How$many$links$are$enough?$K upstream ISPs!Not much benefit beyond 4 ISPs"Akella et al., “Performance Benefits of Multihoming”, SIGCOMM 2003!Peer‐Peer$RelaVonship$• Peers$exchange$traffic$between$customers$$– AS$exports$only$customer$routes$to$a$peer$– AS$exports$a$peer’s$routes$only$to$its$customers$– Oien$the$relaVonship$is$seIlement‐free$(i.e.,$no$$$$)$15!peer peer Traffic to/from the peer and its customers d announcements trafficAS$Structure:$Tier‐1$Providers$• Tier‐1$provider$– Has$no$upstream$provider$of$its$own$– Typically$has$a$naVonal$or$internaVonal$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$connecVons$between$Ver‐1$providers$16!AS$Structure:$Other$ASes$• Other$providers$– Provide$transit$service$to$downstream$customers$– …$but,$need$at$least$one$provider$of$their$own$– Typically$have$naVonal$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$ASes$17!18!The$Business$Game$and$Depeering$• CooperaVve$compeVVon$(brinksmanship)$• Much$more$desirable$to$have$your$peer’s$customers$– Much$nicer$to$get$paid$for$transit$• Peering$“Vffs”$are$relaVvely$common$31$Jul$2005:$Level$3$NoVfies$Cogent$of$intent$to$disconnect.$16$Aug$2005:$Cogent$begins$massive$sales$effort$and$menVons$a$15$Sept.$$expected$depeering$date.$31$Aug$2005:$Level$3$NoVfies$Cogent$again$of$intent$to$disconnect$$(according$to$Level$3)$5$Oct$2005$9:50$UTC:$Level$3$disconnects$Cogent.$Mass$hysteria$ensues$up$$$to,$and$including$policymakers$in$Washington,$D.C.$7$Oct$2005:$Level$3$reconnects$Cogent$During the “outage”, Level 3 and Cogentʼs singly homed customers could not reach each other. (~ 4% of the Internetʼs prefixes were isolated from each other)!19!Depeering$ConVnued$Resolution…!…but not before an attempt to steal customers!!As of 5:30 am EDT, October 5th, Level(3) terminated peering with Cogent without cause (as permitted under its peering agreement with Cogent) even though both Cogent and Level(3) remained in full compliance with the previously existing interconnection agreement. Cogent has left the peering circuits open in the hope that Level(3) will change its mind and allow traffic to be exchanged between our networks. We are extending a special offering to
View Full Document
Unlocking...