Question? Leave a message!

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

Routing Protocols (RIP, EIGRP, OSPF, PNNI, IS-IS) 35
Routing II: Protocols (RIP, EIGRP, OSPF, PNNI, ISIS) Shivkumar Kalyanaraman 1Overview  RIP, RIPv2, EIGRP  OSPF, PNNI, ISIS: 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 pingpong loops (infinite distance = 16 hops) Shivkumar Kalyanaraman 3RIPv1 Problems (Continued)  Split horizon/poison reverse does not guarantee to solve counttoinfinity problem 16 = infinity = RIP for small networks only Slow convergence  Broadcasts consume nonrouter resources  RIPv1 does not support subnet masks (VLSMs) No authentication Shivkumar Kalyanaraman 4RIPv2  Why Installed base of RIP routers  Provides: VLSM support Authentication Multicasting “Wiresharing” 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 5EIGRP (Interior Gateway Routing Protocol)  CISCO proprietary; successor of RIP (late 80s)  Several metrics (delay, bandwidth, reliability, load etc)  Uses TCP to exchange routing updates  Loopfree 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 unreachability 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 sourcerouting with linkstate  Type Qualityofservice routing (multiple route tables) possible  Caveat: With pathvectortype (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 = nexthops 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, PtMpt subnets: designated router (DR) concept  Areas and Hierarchy Area types: Normal, Stub, NSSA: filtering External Routes (from other ASs), interaction with interdomain 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: wraparound, 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 outof date LSPs) = selective synchronization Shivkumar Kalyanaraman 14LSAtypes, Neighbor flooding Adjacencies in Different Subnets Shivkumar Kalyanaraman 15OSPF RouterLSA: 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 bidirectional 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 19RouterLSA: Shivkumar Kalyanaraman 20Database Synchronization  LS Database (LSDB): collection of the Link State Advertisements (LSAs) accepted at a node.  This is the “map” for Dijkstra algorithm  When the connection between two neighbors comes up, the routers must wait for their LS DBs to be synchronized.  Else routing loops and black holes due to inconsistency  OSPF technique:  Source sends only LSA headers, then  Neighbor requests LSAs that are more recent.  Those LSAs are sent over  After sync, the neighbors are said to be “fully adjacent” Shivkumar Kalyanaraman 21Recap: IP Subnet Model  Each subnet assigned one or more address prefixes.  Each address prefix is called an IP subnet  IP routes to subnets, not to individual hosts  Two hosts on different IP subnets have to go through one or more routers.  Even if they are on the same “physical” network Shivkumar Kalyanaraman 22IP Subnet Model (Contd)  Two hosts or routers on a common subnet can send packets “directly” to one another  Two routers cannot exchange routing information directly unless they have one or more IP subnets in common  All these issues will be strained as we study OSPF adjacency operation over different subnets Shivkumar Kalyanaraman 23Broadcast Media Issues  Multiple (N) OSPF routers attached to a common subnet  Problems: One “physical link” vs N(N1) “adjacencies” How many “links” to be counted for Dijkstra algo Shivkumar Kalyanaraman 24Broadcast net: links for DIjkstra  Each router is assumed to be “linked” to every other router for the purposes of Dijkstra.  Hello protocol optimization:  Each node multicasts Hello to (multicast address “AllSPFRouters”)  The Hello multicast message also indicates acks for other routers’ Hellos by listing their RouterIDs  “Link” relationship for purposes of Dijkstra maintained by each node sending a single Hello packet, instead of N packets.  What about “flooding adjacencies”, I.e.,  Whom to send (flood) LSAs when a router generates or learns a new LSA  Does it need to synchronize DBs with all nodes Shivkumar Kalyanaraman 25Flooding Adjacencies : option 1  Using RouterLSAs … 2  O(N) RouterLSAs, with O(N ) adjacency info 2  Multicast of RouterLSAs does not solve O(N ) DB synchronization issue Shivkumar Kalyanaraman 26Flooding Adjacencies: option 2  New LSAtype: NetworkLSA …  O(N) RouterLSAs + 1 networkLSA+ O(N) adjacencies 2  Converted O(N ) adjacency problem into O(N) problem Shivkumar Kalyanaraman 272 Recap: O(N ) model  O(N) model  Question: Who creates the networkLSA Shivkumar Kalyanaraman 28Designated Router (DR)  One router elected as a designated router (DR)  Each router maintains flooding adjacency with the DR, I.e., sends acks of LSAs to DR  DR informs each router of other routers on LAN  DR generates the networkLSA on subnet’s behalf after synchronizing with all routers Shivkumar Kalyanaraman 29DR, BDR … continued  Backup DR (BDR) also syncs with all routers, and takes over if DR dies (typically 5 s wait)  Total: 2N – 1 adjacencies  Multicastbased optimization: New LSAs, Hellos sent to AllSPFRouters avoids DR readvertising new information LSA acks sent to AllDRRouters avoids separate copies to be sent to DR and BDR  DR election: First router on net = DR, second = BDR RouterPriority: 0, 127 indicated in Hello packet= highest priority router becomes DR If network is partitioned and healed, the two DRs are reduced to one by looking at RouterPriority Shivkumar Kalyanaraman 30NetworkLSA Example: Summary DR Shivkumar Kalyanaraman 31What if subnet does not support broadcast  NonBroadcast Multiple Access (NBMA) media  NBMA segments may support more than 2 routers, and allow any two routers to communicate directly, but do not support datalink broadcast/mcast capability  Eg:X.25, SMDS, FrameRelay, ATM etc  Connectionoriented (VCbased) communication  Each VC is costly = setting up full mesh for Hellos is prohibitively expensive  Two flooding adjacency models in OSPF:  NonBroadcast Multiple Access (NBMA) model  PointtoMultipoint (ptmpt) Model  Different tradeoffs… Shivkumar Kalyanaraman 32NBMA Subnet Model  Neighbor discovery: manually configured  Dijkstra SPF views NBMA as a full mesh  Most routers assigned a RouterPriority = 0  Other routers: eligible to become DRs =  ID of all routers in the NBMA configured  Maintains VCs and Hellos with all routers eligible to become DRs (RouterPriority 0)  Enables election of new DR if current one fails  DR and BDR only maintain VCs and Hellos with all routers on NBMA  DB synchronization works same as broadcast subnet  Flooding in NBMA always goes through DR  Multicast not available to optimize LSA flooding.  DR generates networkLSA just like broadcast subnet Shivkumar Kalyanaraman 33NBMA vs PtMpt Subnet Model  Key assumption in NBMA model:  Each router on the subnet can communicate with every other (same as IP model)  But this requires a “full mesh” of expensive PVCs at the lower layer  Many organizations have a hubandspoke PVC setup, a.k.a. “partial mesh”  Conversion into NBMA model requires multiple IP subnets, and complex configuration (see fig on next slide)  OSPF’s ptmpt subnet model breaks the rule that two routers on the same network must be able to talk directly  Can turn partial PVC mesh into a single IP subnet Shivkumar Kalyanaraman 34Partial Mesh FRelay: NBMA model Shivkumar Kalyanaraman 35Partial Mesh FRelay: ptmpt model Shivkumar Kalyanaraman 36PtMpt Subnet Model  Each router: single OSPF interface, but multiple neighbor relationships  Note that neighbor relationships not formed to nodes to which direct PVC does not exist.  Key differences:  No DRs or BDRs Just hellos over the PVCs. Make sure that the communication is bidirectional.  I.e. Partial mesh is viewed in Dijkstra as a partial mesh. Full mesh view not forced like in NBMA model.  Sometimes autoconfiguration is possible.  Loss in efficiency because the DB synchronization has to be done between every peer.  O(n2) if full mesh. So, in true full PVC mesh situations, it is better to operate subnet as an NBMA Shivkumar Kalyanaraman 37Hierarchical Routing Shivkumar Kalyanaraman 38Why Hierarchy  Information hiding (filtered) = computation, bandwidth, storage saved = efficiency = scalability  Address abstraction vs Topology Abstraction  Multiple paths possible between two areas  Shivkumar Kalyanaraman 39Hierarchical OSPF Shivkumar Kalyanaraman 40Area  Configured area ID  A set of address prefixes Do not have to be contiguous So a prefix can be in only one area  A set of router IDs Router functions may be interior, interarea, or external Shivkumar Kalyanaraman 41Hierarchical OSPF  Twolevel hierarchy: local area, backbone.  Linkstate advertisements only in area  each nodes has detailed area topology; only know direction (shortest path) to nets in other areas.  Twolevel restriction avoids counttoinfinity issues in backbone routing.  Area border routers (ABR): “summarize” distances to nets in own area, advertise to other Area Border routers.  Backbone routers: uses a DVstyle routing between backbone routers  Boundary routers (ASBRs): connect to other ASs (generate “external” records) Shivkumar Kalyanaraman 42Sample Area Configuration Shivkumar Kalyanaraman 43SummaryLSA Example Shivkumar Kalyanaraman 44Externals and Aggregation 1  A full ISP routing table has approximately 100K routes But will you do anything differently if you know all of them and have a single ISP Multiple ISP situations call for complex OSPF and BGP design  Never redistribute IGPs into BGP (later…)  Redistribute BGP into IGPs with extreme care Shivkumar Kalyanaraman 45Externals Aggregation 2  In an enterprise Limit externals from subordinate domains (e.g., RIP) to be within area (areascope)  Flood only in area 0 and in area with ASBR Allow externals from Internet, peer domains to go outside Area 0…  Only when there will be significant path differences  Do things with defaults where possible Shivkumar Kalyanaraman 46Type 1 and Type 2 externals  Type 2: Default type for routes distributed into OSPF EGP costs very different from IGP costs Exit based on external (EGP) cost only  Type 1 Needs to be set explicitly: not default IGP costs can be compared and summed Selects exit based on internal + external costs Shivkumar Kalyanaraman 47Stubbiness: A Means of Controlling Externals Shivkumar Kalyanaraman 48Normal Areas  Flood ASexternalLSAs (type 5) across area boundaries (AS flooding scope)  ASBRsummaryLSAs (type 4) advertises location of ASBR (area flooding scope) Shivkumar Kalyanaraman 49Stub Areas  ASexternalLSAs (type 5) not flooded into stub areas  SummaryLSA flooded only optionally  Default route to ABR for all nonarea prefixes  Paths may be inefficient, cannot place an ASBR in Shivkumar Kalyanaraman stub areas 50NotSoStubbyAreas (NSSA)  A subset of external LSAs may be flooded  Use Type7 LSAs for such external routes  Used to import RIP domain routes and flood it externally, but keep default route for BGP routes Shivkumar Kalyanaraman 51ISIS Overview  The Intermediate Systems to Intermediate System Routing Protocol (ISIS) was originally designed to route the ISO Connectionless Network Protocol (CLNP) . (ISO10589 or RFC 1142)  Adapted for routing IP in addition to CLNP (RFC1195) as Integrated or Dual ISIS (1990)  ISIS is a Link State Protocol similar to the Open Shortest Path First (OSPF). OSPF supports only IP  ISIS competed necktoneck with OSPF.  OSPF deployed in large enterprise networks  ISIS deployed in several large ISPs Shivkumar Kalyanaraman 52ISIS Terminology Intermediate system (IS) Router Designated Intermediate System (DIS) Designated Router Pseudonode Broadcast link emulated as virtual node by DIS End System (ES) Network Host or workstation Network Service Access Point (NSAP) Network Layer Address Subnetwork Point of attachment (SNPA) Datalink interface Packet data Unit (PDU) Analogous to IP Packet Link State PDU (LSP) Routing information packet Level 1 and Level 2 – Area 0 and lower areas Shivkumar Kalyanaraman 53Functional Comparison  Protocols are recognizably similar in function and mechanism (common heritage)  Link state algorithms  Two level hierarchies  Designated Router on LANs  Widely deployed (ISPs vs enterprises)  Multiple interoperable implementations  OSPF more “optimized” by design (and therefore significantly more complex)  ISIS not designed from the start as an IP routing protocol (and is therefore a bit clunky in places) Shivkumar Kalyanaraman 54Sample comparison points  Encapsulation  OSPF runs on top of IP= Relies on IP fragmentation for large LSAs  ISIS runs directly over L2 (next to IP) = fragmentation done by ISIS  Media support  Both protocols support LANs and pointtopoint links in similar ways  ISIS supports NBMA in a manner similar to OSPF pt mpt model: as a set of pointtopoint links  OSPF NBMA mode is configurationheavy and risky (all routers must be able to reach DR; bad news if VC fails) Shivkumar Kalyanaraman 55Packet Encoding  OSPF is “efficiently” encoded  Positional fields, 32bit alignment  Only LSAs are extensible (not Hellos, etc.)  Unrecognized types not flooded. OpaqueLSAs recently introduced.  ISIS is mostly TypeLengthValue (TLV) encoded  No particular alignment  Extensible from the start (unknown types ignored but still flooded)  All packet types are extensible  Nested TLVs provide structure for more granular extension Shivkumar Kalyanaraman 56ISIS LS Database: Generic Packet Format No. of Octets Intradomain Routing Protocol Discriminator 1 Length Indicator 1 Version/Protocol ID Extension 1 1 ID Length R R R 1 PDU Type Version 1 1 Reserved 1 Maximum Area Addresses PacketSpecific Header Fields TLV Fields Shivkumar Kalyanaraman 57More detailed comparison provided as a reference (not covered in class)… Shivkumar Kalyanaraman 58Private Network to Node Interface (PNNI)  Link State Routing Protocol for ATM Networks  “A hierarchy mechanism ensures that this protocol scales well for large worldwide ATM networks. A key feature of the PNNI hierarchy mechanism is its ability to automatically configure itself in networks in which the address structure reflects the topology…” Shivkumar Kalyanaraman 59PNNI Features  Scales to very large networks.  Supports hierarchical routing.  Supports QoS.  Supports multiple routing metrics and attributes.  Uses source routed connection setup.  Operates in the presence of partitioned areas.  Provides dynamic routing, responsive to changes in resource availability.  Separates the routing protocol used within a peer group from that used among peer groups.  Interoperates with external routing domains, not necessarily using PNNI.  Supports both physical links and tunneling over VPCs. Shivkumar Kalyanaraman 60PNNI Terminology (partial)  Peer group: A group of nodes at the same hierarchy  Border node: one link crosses the boundary  Logical group node: Representation of a group as a single point  Child node: Any node at the next lower hierarchy level  Parent node: LGN at the next higher hierarchy level  Logical links: links between logical nodes  Peer group leader (PGL): Represents a group at the next higher level.  Node with the highest "leadership priority" and highest ATM address is elected as a leader.  PGL acts as a logical group node.  Uses same ATM address with a different selector value.  Peer group ID: Address prefixes up to 13 bytes Shivkumar Kalyanaraman 61PNNI Terminology Shivkumar Kalyanaraman 62Hierarchical Routing: PNNI Shivkumar Kalyanaraman 63Source Routing  Source specifies route as a list of all intermediate systems in the route. Abstracts out area hops.  Designated Transit List (DTL) Source route across each level of hierarchy Entry switch of each peer group specifies complete route through that group Set of DTLs and manipulations implemented as a stack  DTL example: next slide Shivkumar Kalyanaraman 64DTL Example Shivkumar Kalyanaraman 65Crank back and Alternate Path Routing  If a call fails along a particular route:  It is cranked back to the originator of the top DTL  The originator finds another route or  Cranks back to the generator of the higher level source route Shivkumar Kalyanaraman 66Summary  DV Protocols: RIP, EIGRP  LS Protocols: OSPF, ISIS, PNNI Shivkumar Kalyanaraman 67