Computer Networks CS 242
Popular in Course
Popular in ComputerScienence
This 49 page Class Notes was uploaded by Jordon Hermiston on Thursday October 29, 2015. The Class Notes belongs to CS 242 at Wellesley College taught by Staff in Fall. Since its upload, it has received 27 views. For similar materials see /class/230942/cs-242-wellesley-college in ComputerScienence at Wellesley College.
Reviews for Computer Networks
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 10/29/15
J I J etw0rk Layer Real i fe Routing with BGP CS 242 Computer Networks Week 10 Thursday 111507 Daniel Bilar Wellesley College Fall 2007 l 1 Goals today I Review Shortest Path routing with Link State and Distance Vector protocols l Understanding routing and components in real world Interplay between policy constraints and algorithms Router aggregation through Autonomous Systems Inter and intradomain routing Some slides adapted and pictures gratefully acknowledged from Kurose Liebeherr Rexford Schul 39 Routing Algorithm classification Global or decentralized information Global link state algorithms I all routers have complete topology link cost info Decentralized distance vector algorithms I router knows physically connected neighbors link costs to neighbors I iterative process of computation exchange of info with neighbors 1 Routing algorithm Link State I Tells world about the neighbours Each node assumed to know state of links to its neighbors Step 1 Flooding Each node broadcasts its state to all other nodes a so called Link State Packet LSP Node ID List of neighbors and link cost Time to live TTL and more Node outputs LSP on all its links Step 2 Shortest path tree ii Each node computes shortest paths to all other nodes from global state i Can use Dijkstra s shortest path tree SPT algorithm for example Requires global information Widespread Internet routing protocol that uses this algor1thm 1s OSPF quot1 Routing algorithm Distance Vector I Tells neighbours about the world I Each router maintains a distance table A row for each possible destination A column for each neighbor DXYZ distance from X to Y Via Z I Router periodically tells immediate neighbors its distance to every other router in the network I Requires only local information Has some subtle problems bc of that I Wide spread Internet routing protocol that uses this type of algorithm is BGP RIP Example DV table for E DE A 13Via 5915 C o o w u DXYZ distance from X to Y Via Z DV table for E 6 Distance Vector Link Cost Changes Link cost changes I Good news travels fast I Bad news travels slow count to infinity problem Y via Y D l x z D X z D x z D x z D x z X 6 X I X X X Cquot I I 39 1 1 I I I I 92 XViaY DZI x YDZ x YDZ x YDZ x Y x50 x50 x50 x50 x50 I CXY time Change t0 t1 t2 t3 t 4 Count to Infinity Problem The routing table doesn t converge or stabilize Inherent subtle problem of limited local information uncertainties Link AE goes down A periodic update kicks in and A advertises that its distance to E is infinity At about the same time B and C tell each other that they can reach E in 2 hops B knows now that it can t communicate with E via A but concludes that it can send traffic to C which says it can reach A in 2 hops Now B is thinking that its distance to E is 3 hops and it lets A know about that Argh now A is going to think it can reach E in 4 hops and it will tell C of this fact Where does this end l Recap LS and DV algorithms Message complexity Speed of convergence Robustness Link state OnE messages exchanged On2 running time may oscillate Node can advertise incorrect link cost nodes compute own table Distance vector Messages exchanged between neighbors only Convergence times vary may contain routing loops Node can advertise incorrect path costs to all dest errors propagate But does LS DV scale hus ar has been an ms 1deallzat10n Muhvhnmedns cm L all routers identical M was I Our rfouting study t network at gt not true in practice I For the entire Internet A Link broadcast among all routers on the Internet would leave no room for data packets I Solution is introducing hierarchy of routers r A DV algorithm Aggregate routers into regions autonomous systemsquot iterated among t e AS entire Internet would I Routers in same AS run same routing protocol intrae never converge AS routing Protocol Routers in different AS can run different intraeAS routing protocol 1 o R o A lunnmuus mom t A mnumc ystm An autonomous system AS is a region of the Internet that is administered by a single entity and that has a uni ed routing policy t1 Needed because no routing protocol can scale to entire Internet Each is a igned an Number gASN Wellesley campus network A833022 Rogers Cable Inc A8812 print A81239 A81240 AS 6211 m Interdomain routing is concerned vyith determining paths between autonomous systems Inter omam routm uting rotocols for interdomain routing are called exterior gateway protoco s EGP 11 1 Border Gateway Protocol BGP I Provides routing among autonomous systems EGP I Policies to control routes advertised I Uses reliable transport TCP I Gives path of autonomous systems for each destination I Currently the EGP of choice in the Internet IGPs RIP and OSPF Routing within an autonomous system 1GP Hop count metric Carried over UDP Broadcast or multicast delivery Uses Distance vector algorithm M Routing within an autonomous system 1GP I CIDR subnet support I Carried in OSPF messages directly over IP Authenticated message exchange Allows routes to be imported from outside the AS Uses Link State algorithm 13 h From T Grif n BGP Tutorial ICNP 2002 Inter and Intradomain Routing I Routing protocols for intradomain routing are called interior gateway RIP BGP ospF ltgt Process Process Process ltgt protocc s 1GP r2333 I Lizard Objective shortest path I Routing protocols for routtilng ta e 1nterdoma1n rout1ng are I routing table called exterlor gateway WWI IP protocols EGP incominglp gtForwarding outgoing l Objective satisfy policy of datagrams datagrams the AS Multiple routing protocols can run on the same router Each routing protocol updates the routing table 15 Interdomain vs Intradomain I Intradomain routing w Routing is done based on metrics Routing domain is one autonomous system I Interdomain routing w Routing is done based on policies Routing domain is the entire Internet 16 39 1 Too simple ShortestPath Routing l Shortest path is a theoretical delightful goal In practice there are multiple objectives that must be balanced and reconciled 39 SP often incompatible with commercial relationships J 4 Natlonal I National YES SP1 p SP2 NO Regional Regional Regional Wq r2f ISP1 rsJ Leeustz J 35th w 1 Too much Link State Routing I Topology information is ooded High bandwidth and storage overhead Forces nodes to divulge sensitive information I Entire path computed locally per node High processing overhead in a large network I Minimizes some notion of total distance Works only if policy is shared and uniform I Typically used only inside an AS Eg OSPF 18 Will it stop Distance Vector I Advantages Hides details of the network topology Nodes determine only next hop toward the dest I Disadvantages Minimizes some notion of total distance which is difficult in an interdomain setting Slow convergence due to the counting to infinity problem bad news travels slowly Idea extend the notion of a distance vector to make it easier to detect loops 19 Path Vector Routing I Extension of Distance Vector routing Support exible routing policies if Avoid counttoin nity problem I Key idea advertise the entire path 7 Distance vector send distance metric per dest d 9 Path vector send the entire path for each dest d d path 21 d path 1 data traf c data traf c Faster Loop Detection I Node can easily detect a loop 1 Look for its own node identifier in the path 1 Eg node 1 sees itself in the path 3 2 1 I Node can simply discard paths with loops I Eg node 1 simply discards the advertisement d path 21 d path 1 j d path 321 l Flexible Policies I Each node can apply local policies Path selection Which path to use Path export Which paths to advertise I Examples Node 2 may prefer the path 2 3 1 over 2 1 Node 1 may not let node 3 hear the path 1 2 22 39 1 Challenges to Interdomain Routing I Scale Pre xes 150000 200000 and growing ASes 20000 Visible ones and growing AS paths and routers at least in the millions I Concerns besides optimality Policy Need control over where you send traf c and who can send traffic through you I Notion of Privacy ASes don t want to divulge internal topologies or their business relationships with neighbors 23 1 Border Gateway Protocol I Idea Allows subnet to advertise its existence to rest of Internet I am here I Standard Interdomain EGP routing protocol for the Internet I Prefix based path vector protocol El Policy based routing based on AS Paths I BGP Operations Establish sessioh on 390 TCP port 179 Exchange all active routes quot Exchange incremental updates 39 25 1 BGP Destinations l BGP destinations are not hosts but CIDRized prefixes with each prefix representing a subnet or collection of subnets t Ex 14913000 16 is the Wellesley subnet prefix I Route attributes including AS path e 7018 88 Nexthop IP address eg 1227o121T 192021 RS 7018 121270121 7 ATampT 7 AS 33022 1 s 121554 Wellesley 4 j i I RIPE NC J J I J RIS prOJect l i 1491300016 12811200I16 AS path 33022 Next Hop 192021 AS path 7018 33022 Next Hop 121270121 BGP Update overv1ew l Using eBGP session between 3a and 10 A83 sends pre x reachability info to ASL 10 can then use iBGP do distribute new pre x info to all routers 1n ASl 1b can then readvertise newreachability info to AS2 over 1bto2a eBGP sess1on I When router learns of new prefix creates entry for pre x 1n 1ts forwardlng table eBGP session iBGP session 27 l BGP Route I route prefix attributes Advertised prefix includes BGP attributes I Two important attributes AS PATH contains ASs through which pre x advertisement has passed eg AS 67 AS 17 NEXTHOP indicates specific internalAS router to nexthop AS may be multiple links from current AS to nexthopAS I When gateway router receives route advertisement uses import policy to accept decline 28 I I 7 AS PATH KS 1 139 lzssggtz lgs 1239 701 s 7 Globa Access AS 1755 12811200l16 AS Path 1239 7 AS Path 1129 17551239 7018 88 J El30ne VJ AS 12654 AS 1239 V 12811200l16 RIPE Nlt3C Sprint NS Path 7018 88 RIS project J J 4 J 12811200l16 AS7018 12811200l16 AS Path 88 4 AT J gt 39 AS 88 I 12811200l16 7 AS Princeton AS path 7018 88 Global Crossmg a J 17 17115 7 j J Pre x Originated 29 I r u AS PATH Attribute A81 advertises to A83 Destination 138166424 A8 PATH A81 A82 NEXT HOP IP address of 1c s interface to A83 3c lt2 2 3393 1c 2a s ltgt I I I 6 A53 13 II i J x I I I I eBGP sessxon iBGP session I x v D A51 A82 advertises to A81 Destination 138166424 A8 PATH A82 NEXT HOP IP address of 2a s interface to A83 30 l BGP Route selection I Router may learn about more than 1 route to some prefix Policy trumps algorithm good thing I Rules for route selection local preference value attribute policy decision shortest AS PATH closest NEXT HOP router hot potato routing additional criteria 31 39 I J BGP What do we mean by policy legend r39ovider39 Idetwor39k customer network Q I Assume ABC are provider networks and XWY are customer of provider networks I A advertises path AW to B and B then advertises path BAW to X I Should B advertise path BAW to C iH No way B gets no revenue for routing CBAW since neither W nor C are B s customers 12 B wants to force C to route to w via A 12 B wants to route only to from its customers I Here Economic policy decision 32 1 BGP Path Selection simpleL f Rs 1129 I Global Access Shortest AS path 1281120016 Arbitrary tie break I Example Ail g J RtS project preferred over a five hop l sggtigcggig 701888 AS 12654 prefers path AS 3519 leobal Crossig J Short AS PATH length I AS path length can be misleading if An AS may have many routerlevel hops BGP says that path is better J 34 BGP Path selection Policy I Import policy Filter unwanted routes from neighbor l E g prefix that your customer doesn t own Manipulate attributes to in uence path selection I Eg assign local preference to favored routes I Export policy 7 Filter routes you don t want to tell your neighbor I E g don t tell a peer a route learned from other peer Manipulate attributes to control what they see I E g make a path look artificially longer than it is 35 11 BGP In uencing Decisions Receive BGP Updates 7 Based on Best Attribute Routes Values Transmit BGP Updates Policies 7 l j Apply Import LL Best Route LN Best Route 39 Policies Selection Table 7 l L IP Forwarding Table Import Policy Local Preference I Favor one path over another Override the in uence of AS path length Apply local policies to prefer a path I Example Prefer customer over peer Localpref 90 ATampT Sprlnt Localpref 100 p 37 Import Policy Filtering I Discard some route announcements Detect con guration mistakes and attacks I Examples on session to a customer L Discard route if prefix not owned by the customer Discard route that contains other large ISP in AS path ATampT USLEC 12811200l16 38 Export Policy Filtering I Discard some route announcements Limit propagation of routing information I Examples Don t announce routes from one peer to another UUNET ATampT Sprlnt I network 39 v u V x Princeton 1 3 operator tquot quot I 12811200l16 39 39 Export Policy Attribute Manipulation I Modify attributes of the active route To in uence the way other ASes behave I Example AS prepending Artificially in ate the AS path length seen by others 7 To convince some ASes to send traf c another way ATampT j USLEC 88 12811200l16 4o w 1 BGP Policy Configuration I Routing policy languages are vendor specific Not part of the BGP protocol specification different languages for Cisco Juniper etc I All languages have some key features Policy as a list of clauses Each clause matches on route attributes I either discards or modifies the matching routes I Con guration done by human operators I Policies Business relationships traf c englneerlng securlty Multiple sometimes mutually exclusive objectives have to be balanced 41 BGP Hot Potato Routing I Idea Get the packet out of one s own AS as Quickly as possible C O I Router R3 in autonomous system A receives two Route to x Rig advertisements to network X Which route should it pick I Hot Potato Rule i Select the iBGP peer that has the shortest IGP route Add a routing table entry for destination X i I I lt hot potato I Here R1 has the shortest path 7 42 BGP Hot Potato Routing Perils ASl would serve its customer source better by not picking the shortest route to AS 2 In fact customer may have paid for a high bandwidth service This is why policy trumps algorithms Source Destination 43 w 1 Pulling it together BGP and IGP I Border Gateway Protocol BGP Announces subnet reachability to external destinations 39 Maps a destination pre x to an egress exit point 128112oo16 reached via 192021 I Interior Gateway Protocol IGP Used to compute paths within the AS 39 Maps an egress point to an outgoing link 192021 reached via 10111 10111 192021 44 39 Joining BGP with IGP Information 12811200I16 i Next Hop 192021 destination lnext hop 19202030 I10101010 l destination I next hop 1281120016 10101010 destination I next hop 19202030 10101010 1281120016I 192021 39w 1 45 l 1 BGP Routing Changes I Topology changes Equipment going up or down Deployment of new routers or sessions BGP session failures ii Congestion on the physical path Due to equipment failures maintenance Changes in routing policy n Reconfiguration of preferences Reconfiguration of route filters Persistent protocol oscillation Con icts between policies in different ASes BGP routing table change rates tells you something about Internet health ii See Passive Internet Health Monitoring With BGP httpwwwnanogorgmtg 0310pdfmcgrathpdf 46 l 1 BGP Convergence I Theory Path vector avoids counttoinfinity Still AS s still must explore many alternate aths to nd the highestranke path that is still ava1 able I Practice Most popular destinations have very stable BGP routes Most instability lies in a few unpopular destinations I Lower BGP convergence delay is a goal Can be tens of seconds to tens of minutes High for important interactive ap lications and even conventlonal appllcatlon11ke We brows1ng 47 w 1 Summary I Autonomous systems aggregates routers into regions I Interior Gateway Protocols IGPs provide routin within an AS exterior Gateway Protocols EGPs prov1de rout1ng between AS I BGP a policy based path vector routing protocol is used as the standard EGP Path Vector improved Distance Vector routing tell neighbours more about the world I Routing protocol operate at a global scale with tens of thousands of independent networks that each have their own olicy goals and all want fast convergence gt oly cow that it works as well as it does 48 For Monday I Read ch 5153 5556 I Work on your projects 49
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'