Routing - DePaul University DePaul University, Chicago

1y ago
31 Views
1 Downloads
446.44 KB
38 Pages
Last View : 3d ago
Last Download : 5m ago
Upload by : Ronan Garica
Transcription

Network ProtocolsRoutingTDC375 Autumn 03/04John Kristoff - DePaul University1

IPv4 unicast routingAll Internet hosts perform basic routingfor local net destinations, forward to local hostfor non-local nets, forward to default routerDedicated routers often used between networksRouting tables maintain next hop informationForwarding decision based on destination addressrouters can use other info to influence decisionRouters forward to next-hop if not locally attachedTDC375 Autumn 03/04John Kristoff - DePaul University2

Basic IPv4 forwarding processFor an IP datagram received on an interface.remove layer 2 information,extract destination IP address (D),find best match for (D) in routing table,extract forwarding address (F) for next hop,create layer 2 info on outgoing interface,send datagram to (F).TDC375 Autumn 03/04John Kristoff - DePaul University3

IP routing tablesSince each row in a routing table represents anentry associated with one IP network, the size ofthe routing table is directly proportional to thenumber of IP networks known throughout theentire internetwork.TDC375 Autumn 03/04John Kristoff - DePaul University4

IP routing table illustratedTDC375 Autumn 03/04John Kristoff - DePaul University5

Populating the routing tableStatically (through manual configuration)Simple for small sites with few links/routersLacks scalability and flexibilityUseful for permanent route entriesAutomatically (with distributed routing protocols)Allows quick re-route around failures/changesUseful for large networks with redundant pathsFailures in protocol can be catastrophicTDC375 Autumn 03/04John Kristoff - DePaul University6

IP routing illustratedTDC375 Autumn 03/04John Kristoff - DePaul University7

IP routing illustrated (continued)TDC375 Autumn 03/04John Kristoff - DePaul University8

Routing metricsShortest/longest hop pathLowest/highest cost pathLowest/highest reliable pathBest/worst latency/delaySite specific path policy decisionTDC375 Autumn 03/04John Kristoff - DePaul University9

Some routing terminologyAutonomous system (AS)Network(s) set administered by a single entityInterior gateway protocol (IGP)distributed routing protocol used within an ASExterior gateway protocol (EGP)distributed routing protocol used between ASesTDC375 Autumn 03/04John Kristoff - DePaul University10

Distance vector routingEach node maintains a distance to destinatione.g. 4 hops to network XYZ, 2 hops to ABCPeriodically advertise attached nets out each linkLearn other nets from other router advertisementsAdvertise learned routes (add 1 to hop count)Also known as Bellman-Ford after the inventorsTDC375 Autumn 03/04John Kristoff - DePaul University11

Distance vector illustratedTDC375 Autumn 03/04John Kristoff - DePaul University12

Distance vector illustrated [cont]TDC375 Autumn 03/04John Kristoff - DePaul University13

Distance vector illustrated [cont]covergedTDC375 Autumn 03/04John Kristoff - DePaul University14

Problems with distance vectorConvergence time can be slowAlso known as the count to infinity problemWhat happens when link to A fails?TDC375 Autumn 03/04John Kristoff - DePaul University15

Solving count to infinityHold downadvertise infinity for a route and wait beforeswitching paths. hope that news of the changepropagates before timer expires. Kludge.Report the entire pathguarantees no loops, but resource expensiveSplit horizonDo not advertise route to neighbor if it wasreceived from that neighbor. Not foolpoof.TDC375 Autumn 03/04John Kristoff - DePaul University16

Other distance vector tricksTriggered updatesadvertise changes immediately, may causeroute flapping, but generally a good thing to doPoison reversethis is used with split horizon, advertise infinityrather than nothing at allDUALlike hold down, but can switch paths if a newdistance is lower, sufficiently complexTDC375 Autumn 03/04John Kristoff - DePaul University17

Routing information protocol(RIP)RFC 1058 (RIPv1) and RFC 2453 (RIPv2)Very simple distance vector protocolSlow convergence timeUDP broadcast every 30 seconds (by default)Route times out after 180 seconds (by default)Widely used as an IGP (RIPv2 in particular)15 hop limit (anything greater equals infinity)TDC375 Autumn 03/04John Kristoff - DePaul University18

RIPv2Mainly updated to support subnet masksSupports simple authenticationUses IP multicast group for destination addressRoute tag option for interaction with EGPsNext-hop option to associated with advertisementTDC375 Autumn 03/04John Kristoff - DePaul University19

RIPv1 packet formatPacket format:01230 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - command (1) version (1) must be zero (2) --------------- --------------- ------------------------------- RIP Entry (20) --------------- --------------- --------------- --------------- A RIPv1 entry has the following format:01230 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - address family identifier (2) must be zero (2) ------------------------------- ------------------------------- IPv4 address (4) ------------- must be zero (4) ------------- must be zero (4) ------------- metric (4) ------------- TDC375 Autumn 03/04John Kristoff - DePaul University20

RIPv2 packet formatPacket format is the same, RIPv2 entry format is:01230 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - Address Family Identifier (2) Route Tag (2) ------------------------------- ------------------------------- IP Address (4) ------------- Subnet Mask (4) ------------- Next Hop (4) ------------- Metric (4) ------------- Authentication uses one entry of the format:01230 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - Command (1) Version (1) unused --------------- --------------- ------------------------------- 0xFFFF Authentication Type (2) ------------------------------- ------------------------------- Authentication (16) ------------- TDC375 Autumn 03/04John Kristoff - DePaul University21

Link state routingAll routes have complete network topologyinformation (database within their area)link state packets are flooded to all area routersEach router computes its own optimal pathConvergence time is very shortProtocol complexity is higher than distance vectorEnsures a loop free environmentTDC375 Autumn 03/04John Kristoff - DePaul University22

Link state routing illustratedTDC375 Autumn 03/04John Kristoff - DePaul University23

Link state routing databasesLink state databasecontains latest link state packet from each routerPATH (permanent) database(router id / path cost / forwarding direction) tupleTENT (tenative) databasesame format as PATH, candidate PATH entriesForwarding database (aka FIB)contains ID and forwarding directionTDC375 Autumn 03/04John Kristoff - DePaul University24

Dijkstra's algorithmStart with self as root of the tree(my ID / cost 0 / forwarding direction 0) in PATHFor each node in PATH, examine its LSP and placethose neighbors in TENT if not already in PATH orTENT (with lower cost)If TENT is empty, exit, otherwise find ID with lowestcost in TENT and move it to PATHTDC375 Autumn 03/04John Kristoff - DePaul University25

Dijkstra's algorithm illustrated1. Start with A, put A in PATH, examine A's LSP, add B and D to TENT2. B is lowest path cost in TENT, place B in PATH, examine B's LSP, put C,E in TENT3. D is lowest path cost in TENT, place D in PATH, examine D's LSP, found better E path4. C is lowest path cost in TENT, place C in PATH, exame C's LSP, found better E path again5. E is lowest path cost in TENT, place E in PATH, examine E's LSP (no better paths)6. TENT is empty, terminateTDC375 Autumn 03/04John Kristoff - DePaul University26

Open shortest path first (OSPF)Standardized as RFC 2328 (OSPFv2)Relatively complexSupports multiple route metrics (no one does this)Allows 2-tier area hierarchy for scalingRelatively efficientGood convergence propertiesRuns directly over IPRecommended IGP by the IETFTDC375 Autumn 03/04John Kristoff - DePaul University27

OSPF packetsHellolink maintenanceExchangeinitial exchange of routing tablesFloodingincremental routing updatesTDC375 Autumn 03/04John Kristoff - DePaul University28

OSPF database recordsRouter linkssummarizes links from advertising routerNetwork linkstransit networks (broadcast and non-broadcast)Summary linkssummary info advertised by area border routersExternal linksimported routes, typically from EGPTDC375 Autumn 03/04John Kristoff - DePaul University29

Common OSPF header01230 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - Version # Type Packet length - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - Router ID - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - Area ID - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - Checksum AuType - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - Authentication - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - Authentication - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - TDC375 Autumn 03/04John Kristoff - DePaul University30

Interdomain routingRouting domains are independently fundedRouting domains do not trust each otherDifferent routing domains have different policiesStatic routingEGP – first interdomain routing protocolBGP – current path vector routing protocolTDC375 Autumn 03/04John Kristoff - DePaul University31

Border gateway protocol (BGP)Current version 4 standardized in RFC 1771Runs over TCPList of AS numbers comprise a full path to networkAnnouncements can be edited (paths padded)Can selectively filter or preference received routesRoute can be selected on path or a preferenceexternal BGP versus internal BGPTDC375 Autumn 03/04John Kristoff - DePaul University32

BGP attributesDescribes routes in BGP updatesConfusing descriptions of attributese.g. well known must be supportede.g. mandatory must be present in updatesExamplesAS pathcommunityunreachableTDC375 Autumn 03/04John Kristoff - DePaul University33

ConfederationsGroup of ASes that appear as a single ASA form of aggregationMay simplify routing policies“Don't route through confed X” as opposed to“don't go through AS A, AS B, AS C, etc.”Sub-optimal routing may resultmultiple ASes in path vector appear as a loopTDC375 Autumn 03/04John Kristoff - DePaul University34

BGP message typesOpenfirst message when neighbors come upUpdatecontains routing informationNotificationfinal message before session is disconnectedKeepalivereassures reachability in absence of updatesTDC375 Autumn 03/04John Kristoff - DePaul University35

Route dampeningRoutes that oscillate ripple through the Internetconsumes CPU and causes instability (churn)Unstable (flapping) routes are penalizedfor some period of time, the flap is suppressedsuppression time can increase to a maximumsuppression of routes results in lost connectivityDampen big/important netblocks more cautiouslyDampening may introduce stabilities of its ownTDC375 Autumn 03/04John Kristoff - DePaul University36

Sample Cisco configRouter bgp 12345bgp log-neighbor-changesnetwork 128.160.0.0 mask 255.255.0.0neighbor 36.5.1.1 remote-as 54321neighbor 36.5.1.1 description E-BGP peer with XYZ corp.neighbor 36.5.1.1 password as54321passwordneighbor 36.5.1.1 version 4neighbor 36.5.1.1 prefix-list invalid inneighbor 36.5.1.1 prefix-list announce outip prefix-list invalid seq 10 deny 0.0.0.0/8 le 32ip prefix-list invalid seq 20 deny 10.0.0.0/8 le 32ip prefix-list invalid seq 30 deny 127.0.0.0/8 le 32.ip prefix-list announce seq 10 permit 128.160.0.0/16ip prefix-list announce seq 20 deny 0.0.0.0/0 le 32TDC375 Autumn 03/04John Kristoff - DePaul University37

Final thoughtsRouting protocols tend to work 99.99% of the timeBut when failures occur, they tend to be catastrphicThis is probably the most network intelligenceneeded for basic Internet operationInternet peeringRoute filtering, protection and policy issuesTDC375 Autumn 03/04John Kristoff - DePaul University38

e.g. 4 hops to network XYZ, 2 hops to ABC Periodically advertise attached nets out each link Learn other nets from other router advertisements Advertise learned routes (add 1 to hop count) Also known as Bellman-Ford after the inventors. TDC375 Autumn 03/04 John Kristoff - DePaul University 12 Distance vector illustrated. TDC375 Autumn 03/04 John Kristoff - DePaul University 13 Distance vector .

Related Documents:

systems (AS) (a.k.a. "domains") inter-AS routing § routing among AS'es § gateways perform inter-domain routing (as well as intra-domain routing) Internet approach to scalable routing intra-AS routing § routing among hosts, routers in same AS ("network") § all routers in AS must run sameintra-domain protocol § routers in .

iv Routing TCP/IP, Volume II About the Author Jeff Doyle, CCIE No. 1919, is vice president of research at Fishtech Labs. Specializing in IP routing protocols, SDN/NFV, data center fabrics, MPLS, and IPv6, Jeff has designed or assisted in the design of large-scale IP service provider and enterprise net-works in 26 countries over 6 continents.File Size: 7MBPage Count: 158Explore furtherRouting TCP/IP Volume 1 PDF Download Free 1578700418ebooks-it.orgDownload [PDF] Routing Tcp Ip Volume 1 2nd . - Usakochanwww.usakochan.netCcie Routing Tcp/ip Vol 1(2nd) And 2 Free . - Ebookeewww.ebookee.netJeff Doyle eBooks Download Free eBooks-IT.orgebooks-it.orgCCIE Professional Development Routing TCP . - Academia.eduwww.academia.eduTcp ip volume 1 jeff doyle pdf - AKZAMKOWY.ORGakzamkowy.orgRecommended to you b

Tutorial 13: Routing 3 Routing Routing is het gedeelte van SolidWorks waarmee je leidingen, bedradingen en componenten aan je pro-duct kunt toevoegen. Routing is geen onderdeel van de basisversie van SolidWorks. Gebruik je de Stu-dent Design Kit van SolidWorks, dan kun je deze tutorial dus niet doen. In de Student Edition is Routing

Department of Modern Languages MA Programs Handbook 1 HANDBOOK Master of Arts Programs Department of Modern Languages DePaul University Revised 31 August 2015 Department of Modern Languages SAC 310 2320 North Kenmore Avenue DePaul University Chicago, Illinois 60634 USA email: languages@depaul.edu telephone: 773.325.7320

DePaul Symphony Orchestra, concertmaster, 2014-2015 Civic Orchestra of Chicago, 2013-2015 DePaul Concert Orchestra 2011-2013 DePaul Opera Theater Orchestra, 2012-2015 Interlochen Arts Academy Orchestra, assistant c

Enhanced Interior Gateway Routing Protocol (EIGRP) is an example of a balanced hybrid routing protocol. EIGRP has several advantages over Routing Information Protocol (RIP) and Interior Gateway Routing Protocol (IGRP), and even some advantages over Open Shortest Path First (OSPF) and Intermediate System-to-Intermediate System (IS-IS).

Here is a look at the Festool MFS 400 and MFS 700, multi-routing template system. While these tools excel as routing templates they are capable of far more. Routing operations like open-field inlays, borders, cutouts, mortises, routing circles, curves and arcs are just part of what the MFS system can

Rough paths Guide for this section Hölder p-rough paths, which control the rough differential equations dxt F(xt)X(dt),d ϕt F X(dt), and play the role of the controlhin the model classical ordinary differential equation dxt Vi(xt)dh i t F(xt)dht are defined in section 3.1.2. As R -valued paths, they are not regular enough for the formula µts(x) x Xi ts Vi(x) to define an .