1、Beyond BGPDan MasseyColorado State University24 October 04 1masseycs.colostate.eduInternet Routingl Challenges Facing Internet Routingn Internet Has Grown Dramatically Large number of routing entries High volumes of updates Frequent topological changesn Fault-Model Has Changed Dramatically More malf
2、unctioning components Intentional attacksl Do we need a fundamentally new routing architecture?24 October 04 2masseycs.colostate.eduToward a New Architecturel One claim: BGP is nearing the end of its useful lifetimen The Internet will soon collapse unless we act!l Other claim: BGP is the best engine
3、ering solution we are likely to producen We need incremental patches to new problemsl Who is right?n Beyond BGP uses Measurements to assess where we are Identification of (new?) routing requirements Development of changes (incremental or new system) to address the above24 October 04 3masseycs.colost
4、ate.eduHow Did We Get To BGPl Simple Distance Vector Routing Algorithmsn Used in early Internet routing designsn Convey only limited informationn Prone to long lasting loopsl Expensive Link State Routing Algorithmsn Learn the Full Network Topologyn Signal every change in every linkl Path Vector Rout
5、ing (BGP)n Middle ground that signals some path datan But does not signal the full topology24 October 04 4masseycs.colostate.eduRIP and DBFRIP Keep shortest path only Distributed Bellman-Ford(DBF) Keep distance info from all neighborsABCE FDD:1D:3D:2D:2D:3Bs route to D: Nexthop=A, Dist=4Bs route to
6、D: Nexthop=A, dist=4Alternate Nexthop=C, Dist=4D: infinity 30sec refreshing interval Damping timer to space out two triggered updates: 15 secondsPoison reverse: B sends infinity distance to A RIP and DBF:Exchange distance info. 24 October 04 5masseycs.colostate.edunInternet: composed of thousands of
7、 Autonomous Systems(ASes).BGP BackgroundnBGP (Border Gateway Protocol): the de facto inter-AS routing protocolAS A R1R2R3AS BAS CR4R5AS ER6BGP Routers BGP Routers24 October 04 6masseycs.colostate.eduHow BGP worksl Uses path vector protocol similar to distance vector protocol.n what if no path availa
8、ble?nConsider an AS as a nodeRoute via A = Route via C = Bs route to D:n route includes entire path(sequence of nodes) DABCED:D:D:D:24 October 04 7masseycs.colostate.eduPath Vector Routing Changesl Worms triggered edge instabiltyn Routers crashed due to ARP cache overflow.n Links were congested by w
9、orm traffic.l BGP Path Exploration Exacerbates Dynamics Bs route to DRoute via A=Route via C=DABCEn Obsolete backup path is used and convergence is delayedwithdraw withdrawwithdraw24 October 04 8masseycs.colostate.eduPolicies and Policy WithdrawalnBut A could stop advertising to B due to a policy ch
10、ange, path is still valid!ABCEpolicy withdrawDn Attach a Failure Withdrawal Community Attributen Only apply the approach to failure withdrawalBs route to DRoute via A= Route via C=Route via C=Route via A= 24 October 04 9masseycs.colostate.eduBGP Traffic EngineeringnBGP Traffic Engineering:nR4 choose
11、s path nR5 chooses path n We assumed an AS could be modeled as a noden with a single best path to the destinationnBut a single AS may advertise more than one path.nDivide one AS into Logical ASes such thatnAll routers within a logical AS have the same best patheach logical AS can be modeled as a nod
12、e.24 October 04 10masseycs.colostate.eduNumber of UpdatesNumber of ASes in NetworkNumber of UpdatesOriginal BGPEnhanced BGPn Substantial reduction is achieved. nE.g. 3766 to 1419 in the 60-AS topologyn MinRouteAdver timer: within 30 seconds, only one advertisement is allowed.n It “packs” consecutive
13、 changes into one update.24 October 04 11masseycs.colostate.eduConvergence timeNumber of ASes in NetworkConvergence Time(seconds)Original BGPEnhanced BGPn Enhanced BGP reduces the convergence time substantially. n E.g. 337.0 seconds to 19.5 seconds in the 60-AS topologyn Elimination of one advertise
14、ment can cut convergence time by 30 seconds24 October 04 12masseycs.colostate.eduImproving Path Vector Convergencel Infocom 02 4 uses consistency to detect invalid paths.n Reject path if r1 is adirect neighbor r1s path is not n Adjusted to account for policy and implement in BGPl Infocom 03 Afek, et
15、 al quickly flushes invalid paths.n BGP requires updates be separated by a min intervaln Send withdraw (to flush route) if blocked by the interval l Our recent work 5 attaches a new attribute:Root Cause Notification (RCN)n Identifies the failed link and includes a sequence number.n Allows any route
16、relying on the failed link to be rejected. 24 October 04 13masseycs.colostate.eduAnalyzing Path Vector Convergencel Route fail-over has two stages.l First, nodes inside the blue triangle lose routes and explore backup paths.n All short invalid paths are exploredl Second, an edge (a0) eventually sele
17、cts the valid backup path via Sk.n Valid routes begin to propagate through the blue triangle.24 October 04 14masseycs.colostate.eduGeneric Convergence ResultsAlgorithm Fail-Over Convergence BoundsSPVP (BGP) (N-1) (M + ld) + 3 Pmax(|E|-degree(G,0)SPVP-AS (N- degree(G,0) ) (M+ld) + 3Pmax(|E| - |E| + D
18、egree(G)SPVP-GF (N-1) ld + 3Pmax(|E| - degree(G,0)SPVP-RCN Distance(G,0) (ld) + (Pmax) Distance(G,0) Pmax = Node Processing Delay, ld = Link DelayM = Minimum Advertisement Interval 24 October 04 15masseycs.colostate.eduSimulation Results24 October 04 16masseycs.colostate.eduWhat About Security?l Con
19、vergence Discussion Neglects Securityn What if routers send intentionally bad information?l What is the Simplest Possible Attack?n Announce someone elses routesl Example: Suppose Univ. of Colorado announces it is the origin for 129.82.0.0/16 n In other words, CU announces CSU IP Address Spacel Can t
20、his Happen and/or What Would Prevent It?24 October 04 17masseycs.colostate.eduMultiple Origin AS (MOAS) Casesl Prefixes originate from Multiple Origin AS (MOAS) n Lower curve likely due to valid operational needsl Spikes are errors that disrupt routing to prefix n Includes loss of routes to top leve
21、l DNS servers24 October 04 18masseycs.colostate.eduInfrastructure Faults and AttacksInternet c.gtld-BGP monitor192.26.92.30originates route to 192.26.92/24l BGP and DNS Provide No Authenticationn Faults and attacks can mis-direct traffic.n One (of many) examples observed from BGP logs.n Server could
22、 have replied with false DNS data.ISPs announced new pathfor 20 minutes to 3 hours24 October 04 19masseycs.colostate.eduBGP-based Solution Examplerouter bgp 59neighbor 1.2.3.4 remote-as 52neighbor 1.2.3.4 send-communityneighbor 1.2.3.4 route-map setcommunity outroute-map setcommunitymatch ip address
23、 18.0.0.0/8set community 59:MOAS 58:MOAS additiveExample configuration:AS5818/8, PATH, MOAS4,58,59AS5918.0.0.0/818/8, PATH, MOAS58,5918/8, PATH, MOAS58,5918/8, PATH, MOAS52, 58AS5224 October 04 20masseycs.colostate.edu(b) Two Origin ASs(a) One Origin ASBGP false origin detectionSimulation Results24
24、October 04 21masseycs.colostate.eduA Simple Filterl Current BGP provides dynamic routesn Explore the opposite extreme.l Select a single static route to each server.n Apply AS path filters to block all other announcements. Also filter against more specifics. l Route changes on a frequency of months,
25、if at all.n Change in IP address, origin AS, or transit policy.n Adjust route only after off-line verification24 October 04 22masseycs.colostate.eduWhy This Works: Theoryl Scale is limited to a small number of routes.n No exponential growth in top level DNS servers. l Loss of a server is tolerable,
26、invalid server is not.n Resolvers detect and time-out unreachable servers. Provided surviving servers handle load, cost is some delay.l Expect predictable properties and stable routes.n Servers dont change without non-trivial effort.n Servers located in highly available locations.24 October 04 23mas
27、seycs.colostate.eduWhy This Works: Datal Analysis based on BGP updates from RIPE.n Archive of BGP updates sent by each peer.n 9 ISPs from US, Europe, and Japan.n February 2001 - April 2002l Some data collection notesn Used only peers that exchange full routing tables Otherwise some route changes are
28、 hidden by policiesn Adjusted data to discount multi-hop effect. Multi-hop peering session resets dont reflect ISP ops.24 October 04 24masseycs.colostate.eduImpact on ReachabilityISP1 (US/Tier 1)24 October 04 25masseycs.colostate.eduHow Static Are The Routes?l 3 changes in route to “A” over 14 month
29、s.l 2 (valid) changes in the origin ASn 5/19/01 origin AS changed from 6245 to 11840 n 6/4/01 origin AS changed from 11840 to 19836l 1 change in transit AS routing policyn 11/8/01 (*,10913, 10913, 10913,*) - (*,10913, *)n Could have built filter to allow this.24 October 04 26masseycs.colostate.eduWh
30、at Routes Are Lost?l Results from 3/1/01 until 5/19/01 AS change.n Reduced reachability to “A” from 99.997% to 99.904% l 18 events when trusted route was withdrawnn 2 resulted in no route available (28 secs, 103 secs)n 8 instances of a back-up route lasting over 3 minutesn Longest lasting back-up ad
31、vertised for 15 minutesl Similar results for other time periods and servers.24 October 04 27masseycs.colostate.eduExample of Filtered Routesl With filter no route at 16:06:3219836109131239701* serverNo route at 16:08:3024 October 04 28masseycs.colostate.eduWorst Case In StudyISP 3 (Europe)ISP 3 used
32、 one main route and a smallnumber of consistent back-up routes. 24 October 04 29masseycs.colostate.eduToward a More Balanced Approachl Required infrequent updates to the filter.n Especially useful to automate infrequent tasks. Natural tendency to forget task or forget how to do task l More paths improves robustnessn Simple filtered allowed only 1 path.n ISP3s reachability can be improved if filterallows two routesl Strike a balance between allowing dynamic changes and restricting to trusted paths.24 October 04 30masseycs.colostate.edu
