Question? Leave a message!

Routing Protocols (RIP, EIGRP, OSPF, PNNI, IS-IS)

Routing Protocols (RIP, EIGRP, OSPF, PNNI, IS-IS) 35
Dr.ShivJindal Profile Pic
Published Date:19-07-2017
Website URL
Routing II: Protocols (RIP, EIGRP, OSPF, PNNI, IS-IS) Shivkumar Kalyanaraman 1Overview  RIP, RIPv2, EIGRP  OSPF, PNNI, IS-IS: LS efficiency & robustness  Link state distribution, DB synchronization, NBMAs etc  Refs: Chap 16,14  Books: “Interconnections” by Perlman, “OSPF” by John Moy, “Routing in Internet” by Huitema.  Reference: RFC 2328: OSPF Version 2: In HTML  Reading: Notes for Protocol Design, E2e Principle, IP and Routing: In PDF  Reading: Routing 101: Notes on Routing: In PDF In MS Word  Reference: Tsuchiya, "The Landmark Hierarchy: A New Hierarchy for Routing in Very Large Networks" Shivkumar Kalyanaraman 2RIP: Routing Information Protocol  Uses hop count as metric (max: 16 is infinity)  Tables (vectors) “advertised” to neighbors every 30 s.  Each advertisement: upto 25 entries  No advertisement for 180 sec: neighbor/link declared dead  routes via neighbor invalidated  new advertisements sent to neighbors (Triggered updates)  neighbors in turn send out new advertisements (if tables changed)  link failure info quickly propagates to entire net  poison reverse used to prevent ping-pong loops (infinite distance = 16 hops) Shivkumar Kalyanaraman 3RIPv1 Problems (Continued)  Split horizon/poison reverse does not guarantee to solve count-to-infinity problem 16 = infinity = RIP for small networks only Slow convergence  Broadcasts consume non-router resources  RIPv1 does not support subnet masks (VLSMs) No authentication Shivkumar Kalyanaraman 4RIPv2  Why ? Installed base of RIP routers  Provides: VLSM support Authentication Multicasting “Wire-sharing” by multiple routing domains, Tags to support EGP/BGP routes.  Uses reserved fields in RIPv1 header.  First route entry replaced by authentication info. Shivkumar Kalyanaraman 5E-IGRP (Interior Gateway Routing Protocol)  CISCO proprietary; successor of RIP (late 80s)  Several metrics (delay, bandwidth, reliability, load etc)  Uses TCP to exchange routing updates  Loop-free routing via Distributed Updating Alg. (DUAL) based on diffused computation  Freeze entry to particular destination  Diffuse a request for updates  Other nodes may freeze/propagate the diffusing computation (tree formation)  Unfreeze when updates received.  Tradeoff: temporary un-reachability for some destinations Shivkumar Kalyanaraman 6Link State vs. Distance Vector  Link State (LS) advantages:  More stable (aka fewer routing loops)  Faster convergence than distance vector  Easier to discover network topology, troubleshoot network.  Can do better source-routing with link-state  Type & Quality-of-service routing (multiple route tables) possible  Caveat: With path-vector-type (paths instead of distances) DV routing, these differences blur… Shivkumar Kalyanaraman 7Link State Protocols  Key: Create a network “map” at each node.  1. Node collects the state of its connected links and forms a “Link State Packet” (LSP)  2. Flood LSP = reaches every other node in the network and everyone now has a network map.  3. Given map, run Dijkstra’s shortest path algorithm (SPF) = get paths to all destinations  4. Routing table = next-hops of these paths.  5. Hierarchical routing: organization of areas, and filtered control plane information flooded. Shivkumar Kalyanaraman 8Link State Issues  Reliable Flooding: sequence s, age  LSA types, Neighbor discovery and maintainence (hello) Efficiency in Broadcast LANs, NBMA, Pt-Mpt subnets: designated router (DR) concept  Areas and Hierarchy Area types: Normal, Stub, NSSA: filtering External Routes (from other ASs), interaction with inter-domain routing.  Advanced topics: incremental SPF algorithms Shivkumar Kalyanaraman 9Reliable Flooding… Shivkumar Kalyanaraman 10Topology Dissemination  A.k.a LSP distribution  1. Flood LSPs on links except incoming link Require at most 2E transfers for n/w with E edges  2. Sequence numbers to detect duplicates Why? Routers/links may go down/up Issue: wrap-around, larger sequence number is not the most recent Shivkumar Kalyanaraman 11Sequence Number Space Organization  Circular space: S1 S2 S3 S1  Accidental bit errors in switch memory caused this problem in ARPANET  Lollipop sequence: Start with S0, increment till you reach circle and then view it as a circular space  No ambiguity in lollipop handle  Linear space: OSPFv2.  If Smax reached, expicitly delete Smax LSA before wrapping around Shivkumar Kalyanaraman 12Topology Dissemination (Continued)  Checksum field: Drop packet if in error, get retransmission from neighbor  Age field (similar to TTL) Number of seconds since LSA originated Periodically incremented after acceptance Originating router refreshes LSA after 30 min Delete if Age = MaxAge Low age field + large seq = that LSA is flapping or frequently changing … Shivkumar Kalyanaraman 13Recovering from a partition  On partition, LSP databases can get out of synch  Databases described by database descriptor records  Routers on each side of a newly restored link talk to each other to update databases (determine missing and out-of- date LSPs) = selective synchronization Shivkumar Kalyanaraman 14LSA-types, Neighbor & flooding Adjacencies in Different Subnets Shivkumar Kalyanaraman 15OSPF Router-LSA: Scenario Shivkumar Kalyanaraman 16Neighbor Discovery & Relationship  Every OSPF router sends out 'hello' packets  Hello packets used to determine if neighbor is up  Hello packets sent periodically (short intervals)  HelloInterval = 10s (in example)  Assumes neighbor dead if no response within  RouterDeadInterval = 40s (in example)  This is also called an “adjacency”  Note that adjacency is a logical routing relationship and is more than physical connection.  It consumes bandwidth and computation resources  Becomes an issue if large number of adj need to be maintained Shivkumar Kalyanaraman 17Neighbor …  Once an adjacency is established, trade information  Neighbor relationship is bi-directional as a result of OSPF hello packets  Local topology information is packaged in a "link state announcement“ (LSA)  Multiple types of LSAs: (detail later)  Initial DB synchronization  New announcements are sent ONCE, and only updated if there's a change  Or every 45mins... Shivkumar Kalyanaraman 18Hello: Packet Format Shivkumar Kalyanaraman 19Router-LSA: Shivkumar Kalyanaraman 20