Adv Comp Net
Adv Comp Net EECS 589
Popular in Course
Popular in Engineering Computer Science
This 174 page Class Notes was uploaded by Ophelia Ritchie on Thursday October 29, 2015. The Class Notes belongs to EECS 589 at University of Michigan taught by Zhuoqing Mao in Fall. Since its upload, it has received 16 views. For similar materials see /class/231520/eecs-589-university-of-michigan in Engineering Computer Science at University of Michigan.
Reviews for Adv Comp Net
Report this Material
What is Karma?
Karma is the currency of StudySoup.
Date Created: 10/29/15
Internet Routing Dynamics C3589 Lecture 2 Z Morley Mao Jan 11 2004 2 now In gimme sees Two types of Internet Routing Protocols intemet consists ofrougniy 19 000 Autonomous Systems vvnat is an Autonomous system AS tvvcir peionging to singie administrative entity 7 Nth unified ruutiri Iicies intradomain routing protocoi within an Autonomous System 7 Distance Ventur e g i RiP 7 Link State e g OSF F i 545 interdomain routing protocoi between Autonomous Systems A Burder Gatevvay F39rutucui 36M 7 Patn vector protocoi z my In gimme ass Intradomain routing vs Interdomain routin interior ioutei 2 now In gimme sees Intra domain Routing Protocols Link state vs distance vector Uses unreiiabie datagram deiivery r riooding atiayerz Distance vector 7 Routing information Prutucui Rim Eeiimaanurd based 7 Eacn router periodicaiiy excnange reacnapiiity information vntnits neignpors r Minimai communication overnead r Taketsiong to cunverge i e i in proportion to tne maximum patn eng 7 Has count to infinity propiems Link s a e 7 Open snortest Patn First Prutucui osrvri based on Diikstra r Eacn routerperiodicaiiy fioodsimmediate reacnapiiity information to Either ruuters 7 Fast convergence 7 Hign communication and computation overnead z my In gimme ass nte rdomain Routing BGP Use TCP for reIiabIe transport Patn vector p t i Routing messages indicate cnanges no refresnes BGP routing information 7 ii h a Sequence Dr AS indicatingthe path traversed by 7 next nop 7 her attributes Generai operations ofa BGP router r muitipie patns 7 Picks pest patn according to its As poiicies based on EIGF39 decision process 7 instaii pest pick in IP forwarding tapies 2 now In gimme sees Internet Routing Instability Labovilz et al 2000 Metnodoiogy r Coiiect routing messagesfromfive puoiic excnange points Probiems caused by routing instabiiity 7 increased deiays packet ioss and reordering time for routes to converge smaiiscaie route cnanges Reievant BGP information 7 ASVF39ath 7 Next nop to reacn a netWork Tvvo routes are tne same iftney nave tne same ASrPath and Next nop 7 Otner attributes e g i MED communities ignored for now 2 my In gimme ass Measurement melhndnlngy ASerlh samume mm uxaamwaumnmhuvvmw BGP Inlnrmmmn Exchange unawlwmx umnpmw Mman mumrcandudesmm mm 75 mm m Hum uv hm unmamnwmmnlw Example nldelzyed mnvugence MWM L Wm Hw Typvs nl Imerrdnmzin Rnu ng Updates rwmv mm mw Mmmmu PahmIummmns Rammv mmm mwunncmyx u mulgwlwlhrmaw an nsummv 7mm g nxumwamwlwnmnm 9 mm m wan in Events 3930 Rnuling Sucms lmlzh Wm ramIdwaInnmlznhemuuucln m mpmm ma mm mm mm 39 m 39u1quot i 1 f 3139 351quot Mamqu mummmhw nuguxml w mm 7w WWW 3mm wmug mwmmwm Routing Successive Events Pathological Instability AADup e A route is impiicitiywitndi awn and repiaced With a dupiicate oftne originai route patnoiogicai benaVioi or policy iiuctua ion WWDup a Tne repeated transmission of BGP Witndrawais for a pre x tnat is currently unreacnaoie patnoiogicai benavioi Findings BGP updates more than one order of magnitude d larger than expecte Routing information dominated by pathological pdates e impiemertation prooiems Routers do not maintain tne nistory oftne announcements sent to neignoors a routergets topoiogicai cnanges tneyiust sent tnese announoements to aii neighbors irrespective ofwnetner tne routersent previous announcements about tnat route to a neignoor or not 7 Seirsyncnromzation eBeP routers exchange information simultaneously gt mayiead to penodic linkrouter failures 7 Unconstrained routing poiicies may iead to persistent route osciiiations z mum mum use i3 2 Mn mum ass i4 Findings Conclusions Instability and redundant updates exhibits strong Routing in the Internet exhibits many undesirable correlation with load 30 seconds 24 hours and behaviors savequot aY5 Pe 5 e instability overa Wide range oftirne scaies e Overioaded routers faiito respond an tneir neignoors Agymmemcm Witndi39aWn tnern 7 Network outages Instability usually exhibits high frequency a Problem seemsto worsen Pathological updates exhibits both high and low frequencies IiIany problems are due to so ware bugs or No single AS dominates instability statistics memc39em renter arcmtecmres No correlation between size ofAS and its impact on instability statistics There is no small set of paths that dominate instability statistics 2 mum mum use i5 2 Mn mum ass iE Beacons 2003 Motivation Lessons Better understanding of BGP dynamics Even alter decades of experience routing in the Border Gateway Protocol BGP Internet Is not 3 SOME Problem 7 intemet interdomain routing protocoi This attests the difficulty and complexity of Diffcult to understand BGP s dynamic behavior building distributed algorithm in the Internet ie Muiupie adminrgtranve domam In a heterogeneous environment With products 7 Unknown Womamnpohc eg topo og eg from various vendors 7 Unknown operationai prac ices Simple protocols may increase the chance to be Ambiguoug protocoi Specg a Understood e impiementedngnt Proposal a controlled active measurement infrastructure for W continuous BGP monitoring BGP Beacons m z mum mum ass 2 we Ila minim use Wha s z BGP amenquot m Wm v aba vusmevruxwm knmm NnaunueAImhdmw mm WWW mu WWW mm mm mums 4mmmwum pan mmw Wm a Vlvaamvugxng Related wnrk D emncesmm ubmm mmm pmwmma vamlgnamamunuamh a madman I swam Wm rammmmn u mamm was Seamus 9 mummy w send we pm 55 km mm WNW uumm m 1 Hanan 5 schedule 4 1 Hanan Ielm nlngy 39 4mm 5W 32m 5 3 E X 3 W W km I Mum xsanxmuw any L K v n z quotquotWLiEiw 6 an duv m J 39 Jmmaw Mm m m Mquot L h t Study fadravev mum quotWWW Sum 35W hm 2 551m WERE 533M m beam rm rm mm m we mm data ana ysxs 1mm m b Hnwln prncvss Emcnn am meam a M m namemm mm W quot quot Nuance m museuml quotmy u m lv lu mu WWW Beamquot am dmning runch mm hawquot evml m uem by Ciscnvs Jun er Bezcnn example znzlyss a mmquot mm j in W mu 1 mm m mm mm 4 Emma mm mm mm w e laslrhnp rnulels lasthnr mums man Wm m mm mm Human mm m am we mm mule flap dam g Ammmm pm mm mm by mum m wrczuv Mme m max mmmmmwm m ulnavau m M 7 WWW um mmwm mu quotwere scamenum sm e mmmmn can mule SAPstsmn at is mule flap damping n v om e m mum 51m pg ane zp dam 39ng znzly k D39s39 guish between znnnuncemml and withdrawal Cnnvergence znzrys39s Bezmn139s u Interarrivzllimeznz Is C39scnrkelaslrhn rnulels 21 M m A5123 2m Interanivzllime mndeling Bezcnn cnnclminn sums w m wrainmure w new I v u 7 mm H H mm mmm u m anawss mm ymmm 4 Mn mquot mm m Beacan 5m kmr mm mm mmwm 4 mm mm m 51quot IUJLL39TL 1LN mm 7 W m MWquot ummmmmnm romanunqu m WWWawn Rnuling slzh ily cnngvsled nelwnrls Shaikh Znnnj mum wens mm mm messive m an mm iab mv wwwmmwum WW5 games mm wweman hem n aw WWW mm usive Gm maybmwm evahme mbuinessav new and usmm mmmv mm am am a Mammava up mum ammmmmmamlg Nelwnrk cnn gurmmn mmr 7 2 2 RE 139quot i W WWW canswummaea by m we Mum Nahum w w m H mm hnkavmaadnnar m m Internet Routing Dynamics CS589 Lecture 2 Z Morley Mao Jan 11 2004 Z Morley Mao Winter 2005 08589 Two types of Internet Routing Protocols Internet consists of roughly 19000 Autonomous Systems What is an Autonomous system AS A network belonging to single administrative entity With unified routing policies Intradomain routing protocol within an Autonomous System Distance Vector eg RIP Link State eg OSPF lSIS Interdomain routing protocol between Autonomous Systems Border Gateway Protocol BGP4 Path vector protocol Z Morley Mao Winter 2005 C8589 Intradomain routing vs Interdomain routing En L Interior router BGP router Z Morley Mao Winter 2005 08589 lntradomain Routing Protocols Link state vs distance vector Uses unreliable datagram delivery Flooding at layer 2 Distance vector Routing Information Protocol RIP BellmanFord based Each router periodically exchange reachability information with its neighbors Minimal communication overhead Takes long to converge ie in proportion to the maximum path length Has count to infinity problems Link state Open Shortest Path First Protocol OSPF based on Dijkstra Each router periodically floods immediate reachability information to other routers Fast convergence High communication and computation overhead Z Morley Mao Winter 2005 08589 Interdomain Routing BGP Use TCP for reliable transport Path vector protocol Routing messages indicate changes no refreshes BGP routing information AS path a sequence of AS s indicating the path traversed by a route next hop other attributes General operations of a BGP router Learns multiple paths Picks best path according to its AS policies based on BGP decision process Install best pick in IP forwarding tables Z Morley Mao Winter 2005 08589 Internet Routing Instability Labovitz et al 2000 Methodology Collect routing messages from five public exchange points Problems caused by routing instability Increased delays packet loss and reordering time for routes to converge smallscale route changes Relevant BGP information ASPath Next hop Next hop to reach a network Two routes are the same if they have the same AS Path and Next hop Other attributes eg MED communities ignored for now Z Morley Mao Winter 2005 C8589 Measurement methodology Romew ews Data CoHec on Probe 2 WWW Mau meevZDDS csaaa ASPath Sequence of AS s a route traverses Used for loop detection and to apply policy 120100016 ASZ AS3 AS4 130100016 ASZ AS3 110100016 ASZ AS5 Z Morley Mao Winter 2005 08589 BGP Information Exchange Announcements a router has either Learned of a new route or Made a policy decision that it prefers a new route Withdrawals a router concludes that a network is no longer reachable Explicit associated to the withdrawal message Implicit in effect announcement when a route is replaced as a result of an announcement message ln steady state BGP updates should be only the result of infrequent policy changes BGP is stateful requires no refreshes Update rate indication of network stability Z Morley Mao Winter 2005 08589 Example of delayed convergence stage Example topology 0 1 4 9 g e a 1 2 2 1 41 431 node 3 1 41 241 4 1 31 4 3 Assuming node 1 has a route to a destination and it withdraws the route Stage msg processed Msg queued 0 1gt234w 1 1gt234W 2gt34A241 3gt24A341 4gt23A431 2 2 gt34A241 3gt24A341 4gt23A431 3 3gt24A341 4gt23A431 4gt23w 4 4gt23A431 MinRouteAdver timer expires 4gt23W 3gt24A3241 2 gt34A2431 omitted 9 3gt24w Note In response to a withdrawal from 1 node 3 sends out 3 messages 3gt24A341 3gt24A3241 3gt24W Z Morley Mao Winter 2005 08589 1 O Types of Interdomain Routing Updates Forwarding instability may reflect topology changes Policy fluctuations Routing instability may reflect changes in routing policy information Pathological updates redundant updates that are neither routing nor forwarding instability Instability fonvarding instability and policy fluctuation 9 change forwarding path Z Morley Mao Winter 2005 08589 1 1 Routing Successive Events Instability WADiff a route is explicitly withdrawn as it becomes unreachable and is later replaced with an alternative route forwarding instability AADiff a route is implicitly withdrawn and replaced by an alternative route as the original route becomes unavailable or a new preferred route becomes available fonvarding instability WADup a route is explicitly withdrawn and reannounced later fonvarding instability or pathological behavior Z Morley Mao Winter 2005 08589 1 2 Routing Successive Events Pathological Instability AADup A route is implicitly withdrawn and replaced with a duplicate of the original route pathological behavior or policy fluctuation WWDup The repeated transmission of BGP withdrawals for a prefix that is currently unreachable pathological behavior Z Morley Mao Winter 2005 08589 1 3 Findings BGP updates more than one ordeTof magnitude larger than expected Routing information dominated by pathological updates Implementation problems Routers do not maintain the history of the announcements sent to neighbors When a router gets topological changes they just sent these announcements to all neighbors irrespective of whether the router sent previous announcements about that route to a neighbor or no Selfsynchronization BGP routers exchange information simultaneously 9 may lead to periodic linkrouter failures Unconstrained routing policies may lead to persistent route oscillations Z Morley Mao Winter 2005 08589 1 4 Findings Instability and redundant updates exhibits strong correlation with load 30 seconds 24 hours and seven days periods Overloaded routers fail to respond an their neighbors withdrawn them Instability usually exhibits high frequency Pathological updates exhibits both high and low frequencies No single AS dominates instability statistics No correlation between size of AS and its impact on instability statistics There is no small set of paths that dominate instability statistics Z Morley Mao Winter 2005 08589 1 5 Conclusions Routing in the Internet exhibits many undesirable behaviors Instability over a wide range of time scales Asymmetric routes Network outages Problem seems to worsen Many problems are due to software bugs or inefficient router architectures Z Morley Mao Winter 2005 08589 Lessons Even after decades of experience routing in the Internet is not a solved problem This attests the difficulty and complexity of building distributed algorithm in the Internet ie in a heterogeneous environment with products from various vendors Simple protocols may increase the chance to be Understood Implemented right Z Morley Mao Winter 2005 08589 Beacons 2003 Motivation Better understanding of BGP dynamics Border Gateway Protocol BGP Internet interdomain routing protocol Difficult to understand BGP s dynamic behavior Multiple administrative domains Unknown information policies topologies Unknown operational practices Ambiguous protocol specs Proposal a controlled active measurement infrastructure for continuous BGP monitoring BGP Beacons Z Morley Mao Winter 2005 08589 1 8 l 56 What is a BGP Beacon An unused globally visible prefix with known AnnounceNVithdrawal schedule For longterm public use For research purposes to study BGP dynamics To calibrate and interpret BGP updates To study convergence behavior To analyze routing and data plane interaction Useful to network operators Serve to debug reachability problems Test effects of configuration changes eg flap damping setting Z Morley Mao Winter 2005 08589 1 9 Related work Differences from Labovitz s BGP faultinjector Longterm publicly documented Varying advertisement schedule Beacon sequence number AGG field Enabler for many research in routing dynamics RIPE Ris Beacons Set up at 9 exchange points Z Morley Mao Winter 2005 08589 20 Active measurement infrastructure Many 5b ervation pointsT Internet 1 Oregon RouteViews Send 7 r ute update 0 Verio f i 5 MIT 6Berkeley O BGP Beacon 1 1981 3M506o24 21 Mao Wint 2005 C8589 Deployed PSG Beacons Prefix Src Start date Upstream Beacon Beacon AS Provider AS Host Location 198133206024 3130 81002 2914 1239 Randy Bush WA US 192135183024 5637 9402 3701 2914 Dave Meyer OR US 2031063024 1221 92502 1221 Geoff Huston Australia 198327024 3944 102402 2914 8001 Andrew Partan MD US 19283230024 3130 061203 2914 1239 Randy Bush WA US B1 2 3 5 Announced and withdrawn with a fixed period 2 hours between updates 1st daily ANN 300AM GMT 1st daily WD 100AM GMT B4 varying period BS failover experiments Software available at hffpwwwpsgcomzmao 22 Z Morley Mao Winter 2005 C8589 Beacon 5 schedule T13 nannyL Kng u 1 2 L2 39 12 1 R 22mm 39 a F39 I nnn Pad w 155 muggmmn xh amok JUN 14 1mm Q1 EjJr Study failover Live host 1 ISP A behaVIor for beacon for muItIhomed 1311319 3 ISP E customers data anaIySIs Tune 1n GMT Beacon terminology Beacon prefix 198133206024 Input signal Beaconinjected change 30000 GMT Announce A0 50000 GMT Withdrawal W Z Morley Mao Winter 2005 C8589 Internet OUtput signal 001O A1 0040 W 50110 A2 ISignal length number of updates in output signal 3 updates Signa duration Time between first and last update in the signal 50010 50110 60 seconds Interarrival time Time between consecutive updates 24 How to process Beacon data How to identify output signals ignore external events Data cleaning Anchor prefix as reference Same origin AS as beacon prefix Statically nailed down How to minimize interference btw consecutive input signals Beacon period is set to 2 hours Time stamp and sequence number Attach additional information in the BGP updates Make use of a transitive attribute Aggregator fields Z Morley Mao Winter 2005 08589 25 Beacon data cleaning process Raw BGP fee39 Goal Extract Beacon 39 C39ear39yidemfy up ates andBGPresets updates associated 3330 Pdmes Reference updates injeCted rOUting change Discard beacon Identify output signals eventsin uenced by externalrou ng Clean Beacon win10w51nin Beacon refe 39ence changes 26 Beacon example analysis BGP implementation impact Cisco vs Juniper Route flap damping analysis Convergence analysis Interarrival time analysis Z Morley Mao Winter 2005 08589 27 4n n I Cisco vs Juniper update ratelimiting Announcement Cisco Announcement Juniper 1000 1qnn 123456 9 avg signal len120 1000 avg signal len150 800 800 600 600 400 400 200 200 0 1 Z 3 4 0 1 2 3 4 Withdrawal Cisco Withdrawal Juniper I u 1 Gu 800 avg signal len207 800 avg signal len249 600 400 200 123456789 Known last hop Cisco and Juniper routers from the same AS and location Average signal length Average number of updates observed for a single beacon injected change 28 Signal duration sec Signal duration SEC n Ciscolike lasthop routers signal duration vs signal length Beacon 2 Ciscoilike peers Q 00 50 Q 1 2 3 4 5 6 Signal length 39 g g i Q 1 f l g l 00 T l l i i 50 g l L l L H Withdrawal l 234567 1011121314151617 8 9 Signal length Linear increase in signal duration wrt signal length Slope30 sec Due to Cisco s default rate limiting setting amp II Juniperlike lasthop routers signal duration signal length Beacon 2 n JLiI tiper lilte peerst U1 J C D U1 0 Signal ClLil Eititill i sec AI II39IOLII39ICEII I39IEIPII E mmuw i I J j H H U1 l l wi 4 Eiig nal length 8 9 10 11 1392 13 1394 15 1E 1739 1B 19 ignal lliration Sec IquotI h l III 1 F m a I Iti u M III HHI m E39l Hl ili hFIIl IIH U1 J i 39JiilIlH quot4 I i HI i fDi39lil IH LDiI lil I I I Signal length 10111213141516118192021222324125 Signal duration relatively stable wrt increase in signal length Shorter signal duration compared to Cisco Iikequot lasthops 30 What is route flap amping A mechanism to punish unstable routes by suppressing them RFCZ439 Villamizar et al 1998 Supported by all major router vendors Believed to be widely deployed ATampT Verio Goals Reduce router processing load due to instability Prevent sustained routing oscillations Do not sacrifice convergence times for wellbehaved routes There is conjecture a single announcement can cause route suppressnon Z Morley Mao Winter 2005 08589 What is route flap damping Cisco default setting 39 Scope Inbound external routes Penalty Per neighbor per destination k Exponentially decayed Penalty 3OOQ Flap route change Increases for each flap Suppress threshold Decays exponentially 2000 l Pt39 2 Pa 0 1000 750 Reuse threshold I V 2 4 32 Time min Zorleytaq Winter 2005 C8589 Route flap analysis B1 peer max BZ 3 peer max Strong evidence for withdrawal and announcement triggered Rourer type 33 Distinguish between announcement and withdrawal Percentage of suppressed announce signals B1 peer max 82 BZ peer max BS Percentage of suppressed withdrawal signals 3 ca c c n L 4 J o O Summary oWDtriggered sup more likely than ANN triggered sup oCisco overall more likely trigger sup than Juniper AAAWpattern oJuniper more 39 aggressive for Cisco Juniper AWAW pattern Convergence analysis Beacons 123 at Route Views Cumulative percentage of events gtlt mxx v Summary x in W Withdrawas converge slower than W A announcements ff Most beacon events converge within 3 minutes 5 g f K W g M 1ADU R con1 ANN Beac0n3 WD m H 11x We 4 new xx quot 5 60 1 0 120 Reiative convergence delay in seconds 140 160 o 0 O1 Cumulative percentage of events Output signal duration Beacons 123 at Route VIEWS 30 60 90 120 Beacon1 WD Beacon2 ANN BeaconZ WD Beacon3 ANN duration 36 Beacon 1 s upstream change signal dura on in seconds a 2 Beacon 1 at Route Views x x coo oo p o ANN signal duration N m c o o gt sec 00 4 o WDasignal duration ca 0 20 M I 0 2 quot I AugOZ SepO Oc 2 Jan03 FebOSMarOS Apr3 Mav03 Jun03 single homed Multi homed Multi homed A52914 A51239 2914 2 WWW Mau meevZUUS c 5 A512914 Interarrival time analysis Ciscolike lastmp routers beacon 20310630 10 i empirical data H simulated 10 10Z Inter arrival time Complementary cumulative distribution plot Interarrival time modeling 28 i 1 Geom081i with probability 09524 X 1 with probability 00381 90 Exp970 with probability 000957 Geometric distribution body Update ratelimiting behavior every 30 sec Probmissing update train independent of how many already missed Mass at 1 Discretization of timestamps fortimeslt1 Shifted exponential distribution tail Most likely due to route flap damping z MmievMau Wimizm 03589 39 Beacon conclusion Beacons a public infrastructure for BGP analysis Shown examples of Beacon usage Future work Construction of robust and realistic model for BGP dynamics Correlation with data plane Analysis of RIPE Beacons 40 Z Morley Mao Winter 2005 08589 Routing stability in congested networks Shaikh 2000 Investigate effects of routing control message losses on routing stability Loss due to network congestion Previous studies reported correlation between BGP instability and network usage Goal study behavior and evaluate robustness of BGP and OSPF when routing messages are dropped Methodology experimentation and analytical modeling Z Morley Mao Winter 2005 C8589 1 Network configuration Flats r CBFl Source Link HR1 HR2 consistently overloaded by CBR traffic Packet drop probability at HR1 pr rr HR1 HR2 link overload factor fr rr z Marley m Iumerznns cssxv 42 Methodology MeanTime toFlap U2D MeanTime toRecover D2U Overload factors 25400 Data packet size 64 256 1500 bytes Buffer size at HR 4MB 16MB Z Morley Mao Winter 2005 08589 43 Analytical models Assumptions The overload factor remains constant Every packet has the same probability of being dropped depending on the overload factor Packet dropping probability is independent for each packet Markov chains to find expected values of U2D and D2U for OSPF and BGP Z Morley Mao Winter 2005 08589 Conclusions Developed detailed analytical models OSPF s behavior depends only on traffic overload factor Independent of buffer size packet dropping policy BGP s behavior depends on overload factor and RTT BGP s resilience to congestion decreases as RTT increases There is a need to isolate routing messages from data traffic Through scheduling and buffer management 45 Z Morley Mao Winter 2005 08589 Internet AS relationships Routing policy on Internet paths Z Morley Mao Lecture 5 Jan 20 2005 Z Morley Mao Winter 2005 08589 1 BGP route propagation Connectivity does not imply reachability Not all possible routes propagate Commercial relationships determine policies for Route import Route selection Route export Typical relationships Providercustomer customer pay money for transit Peerpeer typically exchange respective customers traffic for free Z Morley Mao Winter 2005 08589 Transit vs peering ISP definition Internet service provider is an organization the tsells access to the Internet Transit definition Business relationship whereby one ISP provides usually sells access to all destinations in its routing table Peering is nontransitive relationship A peers with B B peers with C does not imply A peers with C Peering definition An interconnection business relationship whereby lSPs provide connectivity to each others transit customers Hybrid exists Regional transit Paid peering Z Morley Mao Winter 2005 08589 Example of commercial relationship Ul ff i Him aiaH HJJEEUUE m Z Morley Mao Winter2005 CS589 Tier1 vs Tier2 peering Tier 1 ISPs Buy no transit from any other providers Have only customers and peers Has full mesh peering with other Tier 1 s Motivation for peering Minimize their interconnection costs while providing sufficient interconnection BW to support customer and its growth Tier 2 ISPs ISP that purchases resells transit within an Internet region Z Morley Mao Winter 2005 08589 Benefit of tier2 peering Decreases the cost and reliance on purchased Internet transit Lowers interAS traffic latency Fewer AS hops AS peering links traversed ls peering always better than transit Concerns of peering Traffic asymmetry No SLAs less liability or incentive to improve performance free rather than getting paid Peers become more powerful Z Morley Mao Winter 2005 08589 Peering Wars Reduces upstream transit You would rather have costs customers Can increase endtoend Peers are usually your performance competition May be the only way to Peering relationships may connect your customers to require periodic some part of the Internet renegotiation Tier 1 Peering struggles are by far the most contentious issues in the ISP world Peering agreements are often confidential Z Morley Mao Winter2005 CS589 Where to peer Public peering at public peering locations Private peering Exchangebased interconnection model A meet point at which lSPs exchange traffic Can be neutral Internet business exchange Direct circuit interconnection model Pointto point circuit between the exchange parties Z Morley Mao Winter 2005 08589 Four Types of BGP Messages Open Establish a peering session Keep Alive Handshake at regular intervals Notification Shuts down a peering session Update Announcing new routes or withdrawing previously announced routes Z Morley Mao Winter 2005 08589 9 Policy with BGP BGP provides capability for enforcing various policies Policies are not part of BGP they are provided to BGP as configuration information BGP enforces policies by choosing paths from multiple alternatives and controlling advertisement to other AS s Import policy What to do with routes learned from neighbors Selecting best path Export policy What routes to announce to neighbors Depends on relationship with neighbor Z Morley Mao Winter 2005 08589 1 O Examples of BGP Policies A multihomed AS refuses to act as transit Limit path advertisement A multihomed AS can become transit for some AS s Only advertise paths to some AS s Eg A Tier2 provider multihomed to Tier1 providers An AS can favor or disfavor certain AS s for traffic transit from itself Z Morley Mao Winter 2005 08589 Export Policy An AS exports only best paths to its neighbors Guarantees that once the route is announced the AS is willing to transit traffic on that route To Customers Announce all routes learned from peers providers and customers and selforigin routes To Providers Announce routes learned from customers and selforigin routes To Peers Announce routes learned from customers and selforigin routes Z Morley Mao Winter 2005 08589 Import Routes Q provider route i peer route chstomer route ISP route 0 9 9999 From From provider provider 39 i From i peer v v v vv vvvvv Z Morley Mao Winter 2005 08589 1 3 Export Routes Q provider route i peer route chstomer route ISP route filters block OI Z Morley Mao Winter 2005 08589 I 4 BGP Route Processing Open ended programming Constrained only by vendor configuration language Receive Apply PO39iCy Based on Best Apply PO39iCy Transmit BGP filter routes amp Attribute Routes filter routes amp BGP 5 Apply Import Best Route Best Route Apply Export Policies Selection Table Policies Install forwarding Entries for best Routes IP Forwarding Table Z Morley Mao Winter 2005 08589 BGP UPDATE Message List of withdrawn routes Network layer reachability information List of reachable prefixes Path attributes Origin Path Metrics All prefixes advertised in message have same path attributes Z Morley Mao Winter 2005 08589 Path Selection Criteria Information based on path attributes Attributes external policy information Examples Hop count Policy considerations Preference for AS Presence or absence of certain AS Path origin Link dynamics Z Morley Mao Winter 2005 08589 Important BGP Attributes Local Preference ASPath MED Next hop Z Morley Mao Winter 2005 08589 Local within an AS mechanism to provide relative priority among BGP routers LOCAL PREF AS 100 l AS 200 AS 300 LocaIPrefsoo3 AS 256 gm Pref 500 IBGP Z Morley Mao Winter 2005 08589 LOCAL PREF Common Uses Handle routes advertised to multihomed transit customers Should use direct connection multihoming typically has a primarybackup arrangement Peering vs transit Prefer to use peering connection why In general customer gt peer gt provider Use LOCAL PREF to ensure this Z Morley Mao Winter 2005 08589 20 ASPATH List oftraversed AS s Useful for loop checking and for pathbased route selection length regexp AS 200 170100016 AS 100 180100016 180100016 300 200100 170100016 300 200 Z Morley Mao Winter 2005 08589 21 MultiExit Discriminator MED Hint to external neighbors about the preferred path into an AS Nontransitive attribute Different AS choose different scales Used when two AS s connect to each other in more than one place Z Morley Mao Winter 2005 08589 22 MED Typically used when two ASes peer at multiple locations Hint to R1 to use R3 over R4 link Cannot compare AS40 s values to AS30 s 1801000 MED 50 l 4 A810 1801000 MED 120 1801goo ll AS 30 Z Morley Mao Winter 2005 08589 23 MED IVIED IS Typically used In prOVI erfs sciii er s c arios It can lead to unfairness if used between ISP because it may force one ISP to carry more traffic i ISP1 I i i ISP2 ISP1 ignores MED from ISP2 ISP2 obeys MED from ISP1 ISP2 ends up carrying traffic most of the way Z Morley Mao Winter 2005 08589 24 Other Attributes ORIGIN Source of route IGP EGP other NEXTHOP Address of next hop router to use Check out httpwwwciscocom for full explanation Question Too many choices attributes how to select routes Z Morley Mao Winter 2005 08589 Route Selection Process Highest Local Preference aplagj iiaaanaLanqi is Shortest ASPATH Lowest MED iBGP lt eBGP Lowest IGP cost to BGP egress Throw up hands and break ties Z Morley Mao Winter 2005 08589 Internal vs External BGP BGP can Be usea By ga n i t l39 39airr dut si How do R1 and R2 learn routes Option 1 Inject routes in IGP Only works for small routing tables Option 2 Use lBGP EBGP Z Morley Mao Winter 2005 08589 27 Internal BGP lBGP Same messages as EBGP Different rules about readvertising prefixes Prefix learned from E BGP can be advertised to lBGP neighbor and viceversa but Prefix learned from one lBGP neighbor cannot be advertised to another lBGP neighbor Reason no AS PATH within the same AS and thus danger of looping Z Morley Mao Winter 2005 08589 28 Internal BGP lBGP R3 can tell R1 and R2 prefixes from R4 R3 can tell R4 prefixes from R1 and R2 R3 cannot tell R2 prefixes from R1 R2 can only find these prefixes through a direct connection to R1 Result lBGP routers must be fully connected via TCP contrast with EBGP sessions that map to physical links Z Morley Mao Winter 2005 08589 29 Mesh does not scale Each RR passes only best routes no longer Nquot2 scaling problem Z Morley Mao Winter 2005 08589 Policy Impact Different relationships Transit Peering Export policies 9 selective export Valleyfree routing Number links as 1 0 1 for customerto provider peer and providertocustomer In any path should only see sequence of 1 followed by at most one 0 followed by sequence of 1 Z Morley Mao Winter 2005 08589 31 Why is it useful to infer AS relationships Identify the ASIevel hierarchy of Internet Not shortest path routing Predict ASIevel paths Traffic engineering Understand the Internet better Correlate with and interpret BGP update Identify BGP misconfigurations Eg errors in BGP export rules Z Morley Mao Winter 2005 08589 AS relationships translate into BGP export rules Export to a provider or a peer Allowed its routes and routes of its customers and siblings Disallowed routes learned from other providers or peers Export to a customer or a sibling Allowed its routes the routes of its customers and siblings and routes learned from its providers and peers Valleyfree After traversing a providercustomer or peerpeer edge cannot traverse a customerprovider or peerpeer edge Invalid path gt 2 peer links downhilluphill downhillpeer peenuphm Z Morley Mao Winter 2005 08589 33 Example 1 2 3 1 2 6 3 are valleyfree 1 4 3 1 4 5 3 are not valley free 2 Mav m Man IImtnvz 55559 4 pmvideyto rcustomer edge 77 e e peelrtorpeel edge siin ngrtor sibling edge Related work in the area of inferring AS relationships On inferring Autonomous Systems Relationships in the Internet Gao Z Morley Mao Winter 2005 08589 Find the highest degree AS node to be the top provider of the AS path Left to the top node customerprovider or siblingsibling links Right to the top node providercustomer or sibling sibling links Siblingsibling if providing mutual transit service for each other Peerpeer with top provider and of comparable degree value 35 What are siblings Mutual transit agreement Provide connectivity to the rest of the Internet for each other Typically between two administrative domains such as small ISPs or universities located close to each other cannot afford additional Internet services for better connectivity Z Morley Mao Winter 2005 08589 36 Assumptions of the Gao algorithm Provider is typically larger than its customers Two peers are typically of comparable size Z Morley Mao Winter 2005 08589 Follow up work by Subramanian et al Use BGP tables from multiple vantage points More complete Exploit uniqueness of each point Build ASlevel hierarchy of Internet Relationship based not degree based 5 level classification of AS s Relationship inference rules Position of AS in AS graph gives rank Combine ranks from multiple tables Compare ranks Peerpeer with similar ranks Providercustomer provider with higher ranks Z Morley Mao Winter 2005 08589 38 Hierarchy inference Internet hierarchy 4 inference Inner Core I Based on relationships Not degree Gao I Transit Core Outer Core Regianal ISPs Customer 2 anim mg mezm cm A more recent work Computinq the Types of the Relationships between Autonomous Systems Giuseppe Di Battista Maurizio Patrignani Maurizio Pizzonia University of Rome lll Infocom 2003 Cast it as an optimization problem to find providercutomer relationships that minimize the number of conflicts Shows the problem is NPhard Do not deal with peerpeer relationships well Z Morley Mao Winter 2005 08589 Quantifying the causes of path inflation SpringO3 Path inflation Endtoend paths are significantly longer than necessary Tracedriven study of 65 ISPs to characterize the root causes of path inflation Topology and routing policy choices within an ISP between pairs of ISPs and across the global Internet Highlevel conclusion Peering policies and interdomain routing lead to significant inflation Interdomain path inflation is due to lack of BGP policy to provide convenient engineering of good paths across ISPs Z Morley Mao Winter 2005 08589 Findings lntradomain traffic engineering is commonplace but has minimal impact on path inflation There is significant coldpotato or nonearly exit routing between adjacent lSPs To avoid poor routes loadbalance across multiple peering links Many earlyexit paths are inflated Topology insensitive load balancing can cause significant path inflation Half of the path inflation is due to interdomain routing using ASpath length as a routing metric 42 Z Morley Mao Winter 2005 08589 Internet Path Inflation Z Morley Mao Winter 2005 08589 43 What path inflation is source destination To go from A81 to A88 instead of taking the shortest path 1gt2gt5gt6gt8 take a longer path like 1 gt2 gt3gt4gt6gt8 Z Morley Mao Winter 2005 08589 44 Outline H Tangmunarunkit R Govindan S Shenker and D Estrin The impact of routing policy on Internet paths In IEEE INFOCOM 2001 H Tangmunarunkit R Govindan S Shenker Internet path inflation due to policy routing In SPIE I TCom 2001 L Gao and F Wang The extent of AS path inflation by routing policies In IEEE Global Internet Symposium 2002 N Spring R Mahajan and T Anderson Quantifying the causes of path inflation In ACM SIGCOMM 2003 Z Morley Mao Winter 2005 C8589 45 The impact of routing p0iCY 0quot Internet paths H Tangmunarunkit R Govindan S Shenker D Estrin Z Morley Mao Winter 2005 08589 Methodology Create MarApr 2000 a router level map of the Internet using Mercator Heuristics for Internet Map Discovery INFOCOMM 2000 Create an AS overlay map by assigning routers to ASs Use RouteViews BGP tables and RADB to find ASs Compare router level path induced by shortest AS path routing with shortest router level path 47 Z Morley Mao Winter 2005 C8589 Shortest AS path inflation Shortest AS path W W y I source Shortest router path Z Morley Mao Winter 2005 08589 a g A88 Q destination 48 Results Cumulative Fr 0 5 10 15 20 25 30 In ation Difference hops 20 of the node pairs have a path 5 hop longer then the shortest path Z Mm ev Man WWEVZUUE CSEEB Results Quantified the contribution of shortest AS path routing to path inflation They also found that longer paths are more inflated Shortcomings Overlooked policies applied between ASs Assumed shortest path intradomain routing Map size 2662 A85 is very small Z Morley Mao Winter 2005 08589 50 Internet Path Inflation due to policy routing H Tangmunarunkit R Govindan S Shenker Z Morley Mao Winter 2005 08589 Methodology Reexamination of the previous work using a larger map also consider interdomain policies Create a router map using Mercator and an AS ove ay lnfer policies between ASs Assume a routing model and compare router level paths induced by the routing model and shortest router level paths Z Morley Mao Winter 2005 08589 52 Policies Three types of peering relationships Providercustomer customer pays its provider for transit services Peerpeer exchange traffic between customers no money exchange Siblingsibling have mutual transit agreement merging ISPs Interconnection Peering and Settlements G Huston Internet Protocol Journal 1999 Z Morley Mao Winter 2005 08589 On Inferrm 7 the Internet L Gao ACM IEEE Transactions on Networking 2001 Network Next hop AS Path 4224021 134241273 1740 1 1 19468130254 5459 5413 1 i 1584313348 1849 704 702 701 1 i 19300242 3333 286 1 i 14422824093 1239 1 1 Paths are hierarchical In a path you can have at most one 1 peerpeer link You go up the hierarchy through customer provider links or siblingsibling and down the hierarchy through provider customer links or siblingsibling Z Morley Mao Winter 2005 C8589 Figure taken from LIXn Geo Routing Model A path transverses up the hierarchy through customerprovider links down the hierarchy through providercustomer links across the hierarchy through peerpeer links If more than one possible paths randomly pick one Z Morley Mao Winter 2005 08589 Results Cumulative Fraction Realistic 0 5 IO 15 20 25 30 35 40 Difference Router Hops mmmmggg by realistic and simplified routing policy model 56 Results Fraction ot Node Pairs U 05 l l 5 2 25 Difference AS Hops AS path in ation caused by realistic routing model 95 of the paths have the same AS length Z Mmiw ManWintEiZUm ESSW Conclusions Shortest AS path routing induces inflation Interdomain policies do not induce inflation Z Morley Mao Winter 2005 08589 58 The extent of AS path inflation by routing policies L Gao F Wang Z Morley Mao Winter 2005 08589 59 Methodology Create an AS map of the Internet from RouteViews data Measure the extent of AS path inflation seen by RouteViews Assume a routing model and measure AS path inflation Z Morley Mao Winter 2005 08589 Results mo MN Percentage ofAS Pairs H001 mum 4 h Number ofAS Hops Inflated Fig 7 Percentage of AS pairs Whose chosen paths are visible from the Route View server are inflated by a xed number A Mo ey Mao Wmer ZUUO C5589 Routing Model Novalley routing policy An AS does not provide transit between any two of its providers or peers Prefer Customer routing policy Prefer the free of charge customer route over the peer or provider route Z Morley Mao Winter 2005 08589 Results mo 10 E 39E L 2 g quot1 1 5 mu 5 9 5 mm Il mm was 1 2 s 4 Number ofAS hops in med Path inflation using a novalley routing model Z MnHeyMan WmterZDDS 05589 63 Results i2 395 L i 1 lt E iii a in El n m r 39u p 0 NH n 0001 1 J m Number of AS Hops In ated Path inflation using a no valley and prefer customer routing model 2 Muiiev Mau Winievm cam 64 Conclusion Prefer customer routing model induces significant inflation 45 of the paths are inflated by at least one AS hop Z Morley Mao Winter 2005 08589 65 Quantifying the Causes of Path Inflation Neil Spring Ratul Mahajan Thomas Anderson SIGCOMM 2003 Z Morley Mao Winter 2005 08589 Approach Quantify Internet Path inflation in 3 layers For each layer find topology and policy triggered inflation lnterdomain Routing Peenng lntradomain Routing il Z Morley Mao Winter 2005 08589 Policies Shortest AS path routing Routing between adjacent networks Hot potato routing and MEDs lntradomain routing protocol 67 Methodology lnfer intradomain topology of 65 lSPs using Rocketfuel use traceroutes measured from 42 vantage points Choose mainly large ISPs to have interesting topologies and some smaller lSPs for diversity Extract a P0P level map from the router level map Z Morley Mao Winter 2005 08589 68 Metric Additive Latency Z Muriey Mau Writer ZEIEIS 05589 Intradomain Topology of an ISP Figure taken from N Spring Metric Additive Latency Hypothetical direct link Intradomain Topology of an ISP Figure taken from N Spring Z MuneyMau WnterZDDE 05589 Metric Additive Latency Hypothetical direct link 1 r choose long Intradomian Topology of an ISP Figure taken from N Spring Z Muriey Mau VthEr ZEIEIS 05589 Intradomain layer Infer intradomain policies using a constraint based approach Intradomain topology does not cause lot of inflation pointing to well connected topologies Intradomain policies do not cause lot of inflation meaning that intradomain traffic engineering is not inconsistent with link latencies Z Morley Mao Winter 2005 08589 Intradomain layer results Cumulative fraction of paths 0 5 ll 15 20 25 Additive in ation ms Intradomain Topology Inflation m z Mmiev Mau Winlevznn 03589 Cumulative fraction of paths in A m g as c 2 on g E 04 E I 02 g lt 10 0 5 IO 5 20 Additive in ation ms Intrado main Policy Inflation s Characterize Peering Policies destination H source B BGP uses MEDs to indicate preferred links Late exit Cold potato routing Use the link indicated MED from your neighbor BgtGgtFgtH Early exit Hot potato routing Use the link Closest to the source B gtCgtDgtEgtFgtH Z Morley Mao Winter 2005 08589 74 Characterize Traces Early exit If one peering link point is seen from each ingress Characterize as late if the path length in the downstream ISP from peering point to destination is less than from the early exit to destination Use this metric to classify traces in three categories Late exit often late exit for most paths Late exit sometimes late exit for the minority of the paths Engineered but not late downstream carries traffic over longer pat 3 Z Morley Mao Winter 2005 08589 75 Characterization results 2 E 10 m E 08 Tier1 ISPs Late exit often 15 3 0396 39 Late exit sometimes 10 E 04 EarIyexit 19 t Single peering point 42 1 02 Engineered but not late 13 IE E 00 39 I 39 I 39 I7 39 I 39 I L 00 02 04 06 08 10 Fraction paths routed quotearlyquot Median is 57 meaning that most ISPs use early exit most of the Sign Z Moriey Mao Winter 2005 C8589 Peering Policies Inflation V 5 10 N Q a 08 g They compare inflation 39g 06 caused by using early exit 5 routing relative to an ideal 3 04 optimal exit policy gt E E 02 S U 00 0 5 1 0 1 5 Additive in ation ms 20 The top 5 of the paths suffers an inflation of more than 12 ms Z Morley Mao VWnter 2005 08589 77 Interdomain layer methodology Infer policies using Lixin Gao Heuristics Assume Novalley and Prefer customer routing model Find inflation caused by shortest AS path routing no valley and no valley prefer customer Z Morley Mao Winter 2005 08589 78 Interdomain layer SP Shortest AS path routing NV valley free paths PC Prefer Customers Shortest AS path can be much longer than shortest latency paths Prefer customer and novalley policies cause little in ation 06 04 SP SP NV SP PC NV 02 Cumulative fraction of paths 00 0 g 10 15 Additive in ation ms ZMorleyMaoWlnler2005 08539 Cumulative Results Median Mean 95 Intra domain Topology 10 ms 24 ms 84 ms Policy 141115 32 ms 115 ms Peering Topology 20 ms 50 ms 177 ms Policy 30 ms 65 ms 245 ms Interdomain Topology 301115 73 ms 341 ms Policy 69 ms 139 ms 603 ms Figure 17 Cumulative path in ation caused by each of the six factors computed With reference to a hypothetical direct link z Marley Man Winter mus 05589 Conclusion Path Inflation is caused by BGP shortest AS path routing and by inefficient peering It is not clear if policies contribute to path inflation Propose an informed BGP that carries location of egress links Shortest AS path routing alternative Z Morley Mao Winter 2005 08589 81 Discussion topics Alternative routing models Game theory Auction based routing Multipath routing What can enduser do given restricted routing policies Overlay routing Security implications How robust is internet routing Z Morley Mao Winter 2005 08589 82 Some research project suggestions Z Morley Mao Winter 2005 08589 Analyze a new attack against routing protocols and devise a defense mechanism Route flap damping attack Design router primitives to defend against DDoS Worm infrastructure attacks Push back for DDoS How to exploit topology information to launch routing attacks Variations of linkcutting attacks Attack detection Exchange of information among lSPs Signature behavior based Routing protocol analyzers Bro lntradomain topology design considerations Route reflector vs AS confederations or hybrid Robustness ease of configuration securitytrust 83 Internet Routing Security Issues Z Morley Mao Lecture 3 Jan 13 2005 Z Morley Mao Winter 2005 08589 Lecture outline Recap of last lecture any questions Existing routing security mechanisms SBGP General threats to routing protocols BGP vulnerability testing Path validation in BGP Z Morley Mao Winter 2005 08589 Previous lecture Effect of MinRouteAdver Timer Updates Convergence time Tmin Umin 0 Mu MRAI 0 Mt MRAI A function of topology observation point and a location that originates the change Mu optimal MRAI beyond which total updates is stable Mt optimal MRAI to minimize convergence time There is no single optimal value Z Morley Mao Winter 2005 08589 3 Recap of previous lecture Internet routing is still not wellunderstood For example difficult to interpret BGP update messages Holy grail root cause analysis of BGP updates need to correlate intradomain and interdomain changes Measurement is useful for understanding routing stability Effect of congestion on routing protocols ls TCP the right transport for BGP How should router treat routing messages differently Future research direction in BGP Protocol characterization data plane correlation Better interpretation of BGP updates BGP monitoring Correlation with IGP Protocol improvement better convergence delay Protocol analysis modeling formal analysis Z Morley Mao Winter 2005 08589 Why do we care about Internet routing security BGP ties the Internet together Critical communication infrastructure BGP is vulnerable to configuration and routing attacks Example routing attacks Fraudulent origination Fraudulent modification Overloading router CPU Configuration errors are common Impact Traffic black holed Destinations unreachable dark address space Traffic intercepted modified Z Morley Mao Winter 2005 08589 Current proposals and solutions SBGP Secure BGP httpwwwnettechbbncomsbgpsbgpindexhtml Routing origination digitally signed BGP updates digitally signed Addressbased PKI to validate signatures SOBGP Secure Origin BGP ftpftpengciscocomsobgpindexhtml Guards against origination fraud No protection against midpath disruptions Current adhoc solutions TCP MD5 RFC 2385 protects a single hop Inbound filters route limits martian checks BTSH ttl hack Neither guarantees that routes are actually usable Provides accountability Z Morley Mao Winter 2005 08589 Details of SBGP Uses PKI Signing party certifies the next hop and propagates it throughout the net Use optional transitive BGP attributes to encode signatures Optimization Predistribute most certificates to each BGP speaker Offload certificate verification Lazy validation of routes Cache signed routes and originations Z Morley Mao Winter 2005 08589 Why is SBGP not here today Expensive to deploy Steady state overhead is 14 Kbps Consumes a lot of CPU need hardware support Need more memory on routers PKI has to be set up Complex Requires router upgrade Do not deal with route withdrawals Perhaps an intermediate solution can be used PKI among tier1 lSPs Z Morley Mao Winter 2005 08589 Generic Threats to Routing Protocols BarbirMurphyYangZOO3 Provides a framework for discussion of Routing attacks Defense and detection mechanisms Classification of vulnerability Design inherent choice in protocol spec Important to discover Implementation bug based on coding error Should eventually get fixed Misconfiguration weak passwords failure to use security features block admin ports More prevalent today and need better tools for configuration Z Morley Mao Winter 2005 08589 Background Scope all routing protocols Routing functions Transport subsystems eg IP or TCP Can be attacked Neighbor state maintenance Configuration of neighbors eg HELLO KeepAIive Database maintenance routing state Threat sources outsider or insider Insider transmit bogus messages Outsider subvert unprotected transport Read insert reply modify Outsider is more difficult Z Morley Mao Winter 2005 08589 1 O Threat consequences Network as a whole Network congestion Routing loops Routing information disclosure Arguable less true for Internet interdomain routing Routing instability churn Routing blackholes Network partition Router overload Individual prefixes Starvation or blackhole Eavesdrop Cut external reachability affected Delay or performance degradation loops Z Morley Mao Winter 2005 08589 1 1 Threat consequence and actions Threat consequence zone The area within which threat actions are affected Threat consequence periods Duration long lived Does the protocol itself have a way to limit duration Eg route refreshes Threat actions Some actions can be prevented eg authorization policies with strong authentication Some actions can be detected auditing and logging Tradeoff between security and performance Complexity if the enemy of security smb My comment after detection what is required to revert to the normal state An important operational issue Z Morley Mao Winter 2005 08589 BGP Vulnerability Testing NanogZ8 ConveryampFranz Is BGP really vulnerable Answer the question based on testing 7 vendor implementations httpwwwnanoqorqmtqO306pdffranzpdf TCP connection establishment tests Varies from silent reject to full 3way handshake BGP RST or NOTIFICATION Timeout varies from none to 13 minutes before next attack attempt No BGP session established TCP spoofing is required to inject data Z Morley Mao Winter 2005 08589 1 3 Effect of TCP resource exhaustion on BGP Goal prevent new BGP sessions from being established or impact existing sessions Methods SYN ESTABLISHED FINWAIT1 flooding Result Up to 56 minutes delay in BGP session establishment Moderate increase in CPU utilization and latency No impact on existing sessions For significant impact attacker needs to break the current session and SYN flood both peers ACL can help reduce impact on CPU Z Morley Mao Winter 2005 08589 1 4 TCP reset and BGP route insertion Blind TCP sequence number guessing operationally impossible Pseudorandom ISN Requires some guessing work Routers can notice Based on large packet volume Assume one can guess TCP seq no Routes can be inserted ACK with overlapping seq no will detect it May impact the FIB and takes some time to flush bad route Z Morley Mao Winter 2005 08589 BGP peer hijack using ARP spoo ng Arpspoof allows an attacker to poison the Arp table of a BGP peer on a LAN Session is terminated and reestablished with the attacker Defense mechanisms Static Arp for ethernet peering Static CAM entries and port security for ethernet switches Detection duplicate Arp replies Z Morley Mao Winter 2005 08589 1 6 BGPTCP implementation recommendations Extensive configurable logging of connection failures Aggressive rejection of TCP connections from nonconfigured peers and aggressive timeouts To minimize TCP resource exhaustion attacks Source port randomization Length BGP session timeouts To minimize message flooding attacks BGP TTL Hack Z Morley Mao Winter 2005 08589 1 7 Best common practice A compromised router is the most valuable asset to an attacker Non BGP specific Router hardening Packet filtering to stop spoofed BGP messages at the edge prevents almost all TCP based attacks Z Morley Mao Winter 2005 08589 1 8 Routing Protocol Framework Information Model OSPF RIPV2 BGP4 I RIB I RIB l RIB V Forwarding FIB Information Destmatlonv NeXtHOP Base i Forwarding Algorithm gt Forwardlng T Decision NPDU Header Network Protocol Data Unit Z Morley Mao Winter 2005 08589 RIB vs FIB RIB Routing Information Base holds all routing information received from routing peers AdjRlBsln the LocRIB and the AdjRlBsOut routes that will be used by the local BGP speaker must be present in the LocRIB routes that are received from other BGP speakers are present in the AdjRlBsln FIB FonIvarding Information Base minimum amount of information necessary to make a fonNardIng deCISlon on a particular packet Typically network pre x and next hop information Contains unique paths no secondary paths Size of the FIB influences the speed of forwarding due to longest prefix lookup Z Morley Mao Winter 2005 08589 Considerations in validating the path in routing protocols draftwhitepathconsidei ions00txt Path vector protocol participant cannot verify whether the path a packet takes to its destination corresponds to the path advertised by the routing protocol whether the chosen path is in accordance with the policies of other ASes This due to path vector routing protocols abstract information about intraAS routing decisions ASes can remove routes form the routing systems this may prevent another AS from enforcing its own policy Z Morley Mao Winter 2005 08589 Validity of a path 1 Does a path from the advertising router to the destination advertised actually exist 2 Does the path advertised fall within the policies of the route39s originator and all intermediate autonomous systems 3 Is the advertising router authorized to advertise a path to the destination 2 and 3 cannot be verified in a distance or path vector protocol Z Morley Mao Winter 2005 08589 Example 1 The advertised path may not fall within the policies of the receiver E local path C through AS 3 D through E B throu n B s routing table AS path nexthop 5 E preferred 3 5 C Z Morley Mao Winter 2005 08589 Some subtleties here BGP forwarding information looks like this Prefix and nexthop Nexthop is the IP address of the nexthop router for forwarding traffic You must have the IGP route to the nexthop forthe route to be usable When B fonNards traffic it goes through C to reach E the nexthop of the path C s fonNarding table is inconsistent with B It prefers AS path 2 3 5 24 Z Morley Mao Winter 2005 08589 Why can this happen lntraAS configuration of an AS can cause packets to follow a path inconsistent with advertised path Internal inconsistency in routing decisions within an AS Path vector routing depends interior routing protocols Other examples route reflection Any lesson here Guarantee the consistency of routes for all routers within an AS 25 Z Morley Mao Winter 2005 08589 Example 2 Advertising router may not be authorized to advertised a path to the destination 1012023 101 2024 1 1012023 10 1202 19 D prefers 39 7 7 19 69 1012024 from C more secure 1012024 3983 1013024 from B 1012023 A does not receive 1012024 from C A s choice of B D overrides D s implicit policy of only accepting this traffic from C This is due to removal of information from the routing system Lack of information does NOT mean lack of authorization to transit a path Z Morley Mao Winter 2005 08589 How can routing information be deleted Filtering based on prefix length Filtering based on the presence of supernets Filtering based on receiver Doesn t want to transit traffic for a peer Very prevalent especially between peers or inside Internet core Z Morley Mao Winter 2005 08589 27 Comparison Type of protocol Advantages Limitations Linkstate Fast convergence Low churnmajor event High visibility Lack of scalability isolation Distancevector Isolation Scalability simplicity Loops count to infinity slow convergence little visibility high churn Pathvector No routing loops No count to infinity Scalability reasonable visibility No isolation Slow convergence High churn Z Morley Mao Winter 2005 08589 28 OSPF Link State routing protocol RFC1583 Routers are organized in domains and areas Hello message for neighbor acquisition Link State information are flooded through the whole area A topology database is maintained by every router 29 Z Morley Mao Winter 2005 08589 Important LSA fields Advertising router ID originator Advertised link or network ID Sequence number 0x80000001 0x7ffffffi Age 0 60 minutes Z Morley Mao Winter 2005 C8589 30 When to Originate a LSA Upon link state changes or Upon timer expiration Z Morley Mao Winter 2005 08589 31 Questions to Ask I How do you know one LSA is fresher than the other I An LSA originated by you will be received by every router will you receive the LSA originated by you I Will the sequence number wraparound cause any problem ie Ox7fffffff I Age gt 1 hour Z Morley Mao Winter 2005 08589 Sequence 01d VS new LSAS Next OX80000002 Only accept LSAs with newerlarger Seq Z Morley Mao Winter 2005 08589 Sequence amp SelfStabilization 1 0x90001112 2 router crashes 3 0x80000001 4 0x90001112 an old copy still exists Z Morley Mao Winter 2005 08589 34 Flushing via Premature Aging Speci ed behavior when Seq wraps around 123 1 0X7FFFFFFF I 3 2 0X7FFFFFF wit MaXAge to purge this entry 3 0x80000001 Z Morley Mao Winter 2005 08589 Attack the Routing Infrastructure Vicious Advertising Routers Flooding 0 EVIL 1 up gt down 2 not exist gt up Impact varies depending on how critical the link is to the world Z Morley Mao Winter 2005 08589 36 Attack the Routing Infrastructure Vicious Intermediate Routers Flooding All the links can be attacked Authentication please come to the rescue Z Morley Mao Winter 2005 08589 Exchanging without LSA Signature If attackers can just change the content of LSAs Without being detected the routers must use all LSAs with care 39 391 Seq 1 Z Morley Mao Winter 2005 08589