Routing. Classification Of Routing Protocols. Distance .

Routing.Classification of Routing Protocols.Distance-Vector Routing Protocols.Petr Grygárek 2005 Petr Grygarek, VSB-TU Ostrava, Routed and Switched Networks1

IP routing Hop-by-hop According to routing table Longest match Routing table needs to be (constantly) updated toreflect current topology Routing protocol(s) runs between routers 2005 Petr Grygarek, VSB-TU Ostrava, Routed and Switched Networks2

Classificationof Routing Protocols 2005 Petr Grygarek, VSB-TU Ostrava, Routed and Switched Networks3

Classification Criteria Internal (IGP) / External (EGP) number of handled routes possibilities of routing politics specificationConvergence TimeDistance-vector / Link-stateClassfull/ClasslessMetric usedSupport for load balancing (equal or nonequal cost)Summarization possibilitiesScalability – resource comsumption (CPU, bandwidth, )Behaviour on various topologies Split horizon, multiaccess networks (broadcast, NBMA, .) 2005 Petr Grygarek, VSB-TU Ostrava, Routed and Switched Networks4

Classfull/Classless RoutingProtocolsrouting protocol does not send subnet masks Classfulin updates, but presumes that all networks are of in updates, but presumes that all networks are ofA/B/C class often perform automatic summarization on majornetwork boundary by defaultClassless routing protocol carry subnet masks in routeadvertisements VLSM (RFC 1009) may be applied Various prefix lengths (subnet masks) for individual subnets of thesame network no overlap Subnets can be further subnetted for more efficient IP addressallocation Often provides option of route summarization Smaller routing tables 2005 Petr Grygarek, VSB-TU Ostrava, Routed and Switched Networks5

Distance-vector RoutingAlgorithms and Protocols 2005 Petr Grygarek, VSB-TU Ostrava, Routed and Switched Networks6

Distance Vector AlgorithmsWhy “distance vector” ?1. Routes are advertised as vectors vector has it’s length ( metric) and direction ( next-hop))2. Neighboring routers exchange their „vectors ofdistances“ to known networks (i.e. routing tables) vector array 2005 Petr Grygarek, VSB-TU Ostrava, Routed and Switched Networks7

Common Characteristics of DVAlgorithms Principle based on Distributed Bellman-Ford (Ford-Fulkerson)algorithmRouting tables construction is based only on information fromneighboring routers – „routing by rumor“Hop-by-hop updatesPeriodic updates typically every 10-90 secstradeoff between convergence time vs. LoadFull routing table updates (periodic route refresh needed) except of routes suppressed due to Split horizon ruleBroadcast (sometime multicast) updates identity of neighbors is not knownmanual neighbor configuration (unicast) is often supported 2005 Petr Grygarek, VSB-TU Ostrava, Routed and Switched Networks8

DV Algorithms - Timers Update timer periodic routing table broadcastingInvalid (expiration) timer Flush (garbage collection) timer Holddown timer (will be discussed next) maintained separately for every routetypically 3-7 update timer periods.reset every time a route is heard about.if expired, route is marked and propagated as inaccessible (but still usedby router itself)after its expiration, route marked as invalid (by invalid timer) is removedfrom routing tableTimers have to be set consistently across routing domain 2005 Petr Grygarek, VSB-TU Ostrava, Routed and Switched Networks9

Convergence Time(without triggered updates)aR1bR2cR3R4dNetwork a just goes up, assume routing update period 30s R2 learns about network a after 30s (max) R3 learns about network a after 60s (max) R4 learns about network a after 90s 1.5 min (max) 2005 Petr Grygarek, VSB-TU Ostrava, Routed and Switched Networks10

Holddown Timera previously failed route is received with worse Whenmetric from other router than former nexthop, newmetric from other router than former nexthop, newinformation is ignored for time period equal to theholddown timerinformation from failed route's next-hop router is Exception:accepted even with worse metricaccepted even with worse metric Stated another way: if the route’s metrics gets worse or the route disappears completely, router does not acceptother routes for a whilePrevents routes to failed networks from being reintroduced by routers that have not noticed the failureyetHelps to avoid count-to-infinity problem 2005 Petr Grygarek, VSB-TU Ostrava, Routed and Switched Networks11

R1Holddown timerusage exampleR2aR4R3Holddown timer applied on R4: R3 reports network a as unreachable (using triggeredupdate) Holddown timer started for route a on R4 R1 offers route to a via 3 hops as R1 is still not informed about unreachability ofnetwork a- R4 does not believe R1 during holddown time 2005 Petr Grygarek, VSB-TU Ostrava, Routed and Switched Networks12

Triggered updates (Flash updates) If a metric of a route changes (either increases or decreases),information is sent immediately without waiting for the nextupdate period Including detection of new or failed routeGreatly reduces Count-to-Infinity problem (but does noteliminate it completely)The sole changed information may be transmitted instead ofwhole routing tableArtificial (random) pause 1-5s between triggered updates isapplied reduces broadcast storms and flappingImplemented in both RIP versions (RFC 2091), IGRP, 2005 Petr Grygarek, VSB-TU Ostrava, Routed and Switched Networks13

Split Horizon Solves problem of routing loops occurring due toupdates passing each other over a single link Count to infinity problem Poisson reverse – routing information is not onlyfiltered by Split horizon, but intentionally sent withinfinite metric larger updates additional level of safety against propagation ofcorrupted information 2005 Petr Grygarek, VSB-TU Ostrava, Routed and Switched Networks14

Count to Infinity Problem (1)Router which receives new route from it’s neighbor does notknow that the advertised route leads back to itaR1bR2cR3R4dNumber of hops and next-hop routers from individualrouters to network a:R2: 1,R1R3: 2,R2R4: 3, R3 2005 Petr Grygárek, FEI VŠB-TU Ostrava, Počítačové sítě (Bc.)15

Count to Infinity Problem (2)aR1-R2 link fails:R1bR2cR3R4dR2: ,R3: 2,R2R3 announces to R2 that it can reach a behind 2 hops(but does not inform that it’s route leads through R2 ;-) )R2: 3,R3R3: 2,R2R2 announces to R3 that it can reach a behind 3 hops(R3 had route to a via R2 (2 hops), but R2 now advertises 3 hops, so R3 updatesmetric)R2: 3,R3R3: 3, R2R3 announces to R2 that it can reach a behind 4 hops(R2 had route to a via R3 (3 hops), but R3 now advertises 5 hops, so R2 updatesmetric)R2: 4,R3R3: 3, R2 Metric to network a increases forever in routers R2 and R3, routing loop iscreated 2005 Petr Grygárek, FEI VŠB-TU Ostrava, Počítačové sítě (Bc.)16

More Complex Count to InfinityScenario(even with Split Horizon applied) Example topology: rectangle/triangle of 4/3 routersand one additional router in the corner which fails. ntinf/countinf.htm for detailed explanation Introducing of maximum metric to handle count-to-infinity problem also resolves routing loops occurringdue to updates passing each other over alternatepaths 2005 Petr Grygarek, VSB-TU Ostrava, Routed and Switched Networks17

Route Poissoning Little mess in terminologydefinition: “When a distance vector routing Ciscoprotocol notices that a particular route is no longervalid, it has two choices. One is simply to quitadvertising about that subnet; the other is to advertisethat route, but with an infinite metric, signifying thatthe route is bad. Route poisoning calls for the secondof these options, which removes any ambiguity aboutwhether the route is still valid” 2005 Petr Grygarek, VSB-TU Ostrava, Routed and Switched Networks18

DVA – Advanced issues Passive InterfacesActive and Passive participantsProblem of update synchronization Unicast updates - neighbors’ IP addresses may be configuredexplicitly Limits broadcasts, but requires to maintain list of valid neighborsfor L2 technologies that do not support Usefulbroadacast/multicastRouter may “consume” more than 1 hoplists define consumed hops on interfaces for offsetincoming/outgoing RIP updatesUnnumbered interfacesSpecial operation mode on dial-on-demand circuits Does not require periodic keepalives, only changes are sent periodic network congestionartificial jitter of update periods is often introduced 2005 Petr Grygarek, VSB-TU Ostrava, Routed and Switched Networks19

Advantages of DV routingalgorithms Simple implementation good interoperability Simple configuration no complicated planning but even with DVA hierarchy of network “areas”with summarization may be established Ease of route filtering Both received and propagated routes Filtering at any place (interface) Summarization at any interface 2005 Petr Grygarek, VSB-TU Ostrava, Routed and Switched Networks20

DVA Disadvantages Routing loop can occur in special situations moreeasilly than with LSA Which is why we need additional loop avoidanceprotections like Holddown timer but they increase reconvergence time Reconvergence depends on timer expiration Invalid timer detects failed route No efficient mechanism of neighbor failure detection No Hellos like in LSAs Except advanced DVAs like EIGRP 2005 Petr Grygarek, VSB-TU Ostrava, Routed and Switched Networks21

Routing Information Protocol(RIP) 2005 Petr Grygarek, VSB-TU Ostrava, Routed and Switched Networks22

RIP Overview Long history - since ARPANET (1969) Simple metric (hop count) Simple implementation and configuration, widespread usage,interoperable implementationsRIPv1: RFC 1058 (Hedrick, 1988 (!) )RIPv2: RFC 2453 ( RFC 1723) Uses UDP/520 (both as source and destination port)Support for equal-cost load balancing (some implementations) implemented in various network architectures (IP, IPX, AppleTalk, ) suitable for equal-bandwidth lines and small networkslimited neighbor diameter (hop count 16 infinity) RIP versions can be different on different interfaces 2005 Petr Grygarek, VSB-TU Ostrava, Routed and Switched Networks23

RIP version 1 Classful routing protocol Does not include subnet mask information. Automatic summarization at major network boundaries Updates are sent as broadcasts by default Update sender’s IP address is used as implicit next hop Max 25 entries in update max update length 512B one entry takes 5x4B:Address Family Identifier, IP address, metric, unused fields (waste ofspace) 2005 Petr Grygarek, VSB-TU Ostrava, Routed and Switched Networks24

RIPv1 Packet Format0123 30 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) --------------- --------------- ------------------------------- address family identifier (2) must be zero (2) ------------------------------- ------------------------------- IP address (4) ------------- must be zero (4) ------------- must be zero (4) ------------- metric (4) ------------- 2005 Petr Grygarek, VSB-TU Ostrava, Routed and Switched Networks25

RIP v1 and Subnet Masks RIP is classfull – no masks in routing updates Assumes consistent (constant) subnet mask for all subnets of single major (i.e. class-level) networkIf some router’s interface is connected to the subnetof a major network and it receives a routing update,router will use receiving interface’s mask for theadvertised subnet. Otherwise the class’ default maskis applied 2005 Petr Grygarek, VSB-TU Ostrava, Routed and Switched Networks26

Handling of Constant Subnet Mask inClassful Routing Protocols172.16.2.0, but with what mask ?As I assume the same mask for allsubnets is used, I will apply subnetmask configured at the receivinginterface 1.0/24 2005 Petr Grygarek, VSB-TU Ostrava, Routed and Switched Networks172.16.2.0/2427