Dynamic Routing Protocols: RIP & Link-State

• Chapter 2 discusses dynamic routing protocols, distance vector dynamic routing, RIP and RIPng routing, link-state dynamic routing, and the routing table.

Chapter 2 Objectives

• The objectives of this chapter are to explain the basic operation of dynamic routing protocols, compare and contrast dynamic and static routing, and determine which networks are available during an initial network discovery phase.
• Further objectives include defining the different categories of routing protocols and describing how distance vector routing protocols learn about other networks.
• The chapter also aims to identify the types of distance-vector routing protocols, configure the RIP and RIPng routing protocols, and explain how link-state routing protocols learn about other networks.
• Additional learning goals are to describe the information sent in a link-state update and to detail the advantages and disadvantages of using link-state routing protocols.
• The chapter further aims to identify protocols that use the link-state routing process (OSPF, IS-IS), determine the route source, administrative distance, and metric for a given route, and explain the concept of a parent/child relationship in a dynamically built routing table.
• A final objective is to compare the IPv4 and IPv6 classless route lookup processes and to analyze a routing table to determine which route will be used to forward a packet.

Evolution & Operation of Dynamic Routing Protocols

• Dynamic routing protocols have been used in networks since the late 1980s.
• Newer versions of routing protocols support communication based on IPv6.
• Interior Gateway Protocols include Distance Vector (RIPv2, EIGRP) and Link-State (OSPFv2, OSPFv3, IS-IS, IS-IS for IPv6).
• Exterior Gateway Protocols are Path Vector protocols BGP-4 and BGP-MP.
• Routing protocols facilitate the exchange of routing information between routers.
• Dynamic routing protocols discover remote networks, maintain up-to-date routing information, choose the best path to destination networks, and find a new best path if the current path is no longer available.
• The main components of dynamic routing protocols include data structures like tables or databases kept in RAM, routing protocol messages for discovering neighboring routers and exchanging routing information, and algorithms for facilitating routing information for best path determination.
• Data structures include neighbor and topology tables.
• Dynamic routing advantages include automatic sharing of information about remote networks, determining the best path and adding it to routing tables, less administrative overhead compared to static routing, and help for network administrators in managing static routes.
• Disadvantages include the dedication of router resources to protocol operation (CPU time and network link bandwidth), and situations where static routing may be more appropriate.

Static vs Dynamic Routing

• Networks typically use a combination of static and dynamic routing.
• Static routing eases routing table maintenance in small networks not expected to grow significantly.
• Static routing is used for routing to and from a stub network, which has only one default route out and no knowledge of remote networks.
• It is used for accessing a single default router serving as a path to any network not matched in the routing table.
• Advantages of static routing include ease of implementation in small networks, high security due to lack of advertisements, consistent routes to destinations, and no need for routing algorithms or update mechanisms, conserving CPU or RAM resources.
• Disadvantages of static routing include suitability only for simple topologies or default static routes, dramatically increasing configuration complexity as the network grows, and the need for manual intervention to re-route traffic.
• Dynamic routing is suitable in all topologies where multiple routers are required.
• Dynamic routing is generally independent of the network size and can automatically adapt the topology to reroute traffic if possible.
• Dynamic routing can be more complex to implement, less secure (requiring additional configuration settings), dependent on the current topology, and requires more CPU, RAM, and link bandwidth.

Dynamic Routing Protocol Operation

• Dynamic routing involves sending and receiving routing messages on interfaces.
• It also includes routers sharing routing messages and routing information with others using the same routing protocol.
• Routers exchange routing information to learn about remote networks.
• When a router detects a topology change, the routing protocol can advertise this change to other routers.
• In a cold start, R1 adds the 10.1.0.0 network available through interface FastEthernet 0/0, and 10.2.0.0 is available through interface Serial 0/0/0.
• R2 adds the 10.2.0.0 network available through interface Serial 0/0/0, and 10.3.0.0 is available through interface Serial 0/0/1.
• R3 adds the 10.3.0.0 network available through interface Serial 0/0/1, and 10.4.0.0 is available through interface FastEthernet 0/0.
• For network discovery, R1: sends an update about network 10.1.0.0 out the Serial0/0/0 interface, sends an update about network 10.2.0.0 out the FastEthernet0/0 interface, receives update from R2 about network 10.3.0.0 with a metric of 1, and stores network 10.3.0.0 in the routing table with a metric of 1.
• For network discovery, R2 sends an update about network 10.3.0.0 out the Serial 0/0/0 interface, sends an update about network 10.2.0.0 out the Serial 0/0/1 interface, receives an update from R1 about network 10.1.0.0 with a metric of 1, stores network 10.1.0.0 in the routing table with a metric of 1, receives an update from R3 about network 10.4.0.0 with a metric of 1, and stores network 10.4.0.0 in the routing table with a metric of 1.
• For network discovery, R3 sends an update about network 10.4.0.0 out the Serial 0/0/1 interface, sends an update about network 10.3.0.0 out the FastEthernet0/0, receives an update from R2 about network 10.2.0.0 with a metric of 1, and stores network 10.2.0.0 in the routing table with a metric of 1.
• With exchanging the routing information, R1 sends an update about network 10. 1.0.0 out the Serial 0/0/0 interface and sends an update about networks 10.2.0.0 and 10. 3. 0. 0 out the FastEthernet0/0 interface.
• R1 receives an update from R2 about network 10.4.0.0 with a metric of 2; R1 stores network 10.4.0.0 in the routing table with a metric of 2; the same update from R2 contains information about network 10.3.0.0 with a metric of 1; there is no change, therefore the routing information remains the same.
• R2 sends an update about networks 10.3.0.0 and 10. 4.0.0 out of Serial 0/0/0 interface and sends an update about networks 10. 1. 0. 0 and 10. 2. 0. 0 out of Serial 0/0/1 interface.
• R2 receives an update from R1 about network 10.1.0.0, but there is no change so the routing information remains the same.
• R2 receives an update from R3 about network 10.4.0.0; similarly, there is no change, so the routing information remains the same.
• R3 sends an update about network 10.4.0.0 out the Serial 0/0/1 interface an update about networks 10. 2. 0. 0 and 10. 3. 0. 0 out the FastEthernet0/0 interface.
• R3 receives an update from R2 about network 10. 1. 0. 0 with a metric of 2 and stores network 10. 1. 0. 0 in the routing table with a metric of 2 where the same update from R2 contains information about network 10. 2. 0. 0 with a metric of 1.
• Because there is no change, the routing information remains the same.

Achieving Convergence

• A network is converged when all routers have complete and accurate information about the entire network.
• Convergence time is the time it takes routers to share information, calculate best paths, and update their routing tables.
• A network is not completely operable until converged.
• Convergence properties include the speed of propagation of routing information and the calculation of optimal paths.
• The speed of propagation is the time it takes for routers within the network to forward routing information.
• Older protocols, like RIP, converge slowly, while modern protocols, like EIGRP and OSPF, converge more quickly.

Classifying Routing Protocols

• Routing protocols can be classified as Dynamic.
• There are Interior Gateway Protocols (IGPs) and Exterior Gateway Protocols (EGPs).
• Distance Vector Protocols include RIPv1, IGRP and RIPv2, EIGRP.
• Link-State Routing Protocols are OSPF, IS-IS.
• A Path-Vector Routing Protocol is BGP.
• Interior Gateway Protocols (IGP) are used for routing within an Autonomous System (AS) and include RIP, EIGRP, OSPF, and IS-IS.
• Exterior Gateway Protocols (EGP) are used for routing between Autonomous Systems and the official Internet routing protocol.

Distance Vector Routing Protocols

• Distance vector IPv4 IGPs calculate routes based on distance.
• RIPv1 is the first generation legacy protocol.
• RIPv2 is a simple distance vector routing protocol.
• IGRP was the first generation Cisco proprietary protocol (obsolete).
• EIGRP is an advanced version of distance vector routing.
• Distance vector protocols use routers as sign posts along the path to the final destination.
• Link-state protocols are like having a map of the network topology; a link-state router uses link-state information to create a topology map and select the best path to destination networks.
• Link-state IPv4 IGPs include OSPF (popular standards-based routing protocol) and IS-IS (popular in provider networks).
• Link-state protocols forward updates when the state of a link changes.
• Classful routing protocols lack sending subnet mask information in their routing updates.
• Only RIPv1 and IGRP are classful.
• They can't provide variable length subnet masks (VLSMs) and classless interdomain routing (CIDR) and create problems in discontiguous networks.
• Classless routing protocols include subnet mask information in the routing updates.
• RIPv2, EIGRP, OSPF, and IS IS support VLSM and CIDR and include IPv6 routing protocols.

Routing Protocol Characteristics

• RIPv1 has slow speed convergence, small scalability, does not use VLSM, has low resource usage, and simple implementation and maintenance.
• RIPv2 has slow speed convergence, small scalability, can use VLSM, has low resource usage, and simple implementation and maintenance.
• IGRP has slow speed convergence, small scalability, does not use VLSM, has low resource usage, and simple implementation and maintenance.
• EIGRP has fast speed convergence, large scalability, can use VLSM, has medium resource usage, and complex implementation and maintenance.
• OSPF has fast speed convergence, large scalability, can use VLSM, has high resource usage, and complex implementation and maintenance.
• IS-IS has fast speed convergence, large scalability, can use VLSM, has high resource usage, and complex implementation and maintenance.

Routing Protocol Metrics

• A metric is a measurable value assigned by the routing protocol to different routes based on their usefulness.
• Used to determine the overall "cost" of a path from source to destination with routing protocols determining the best path based on the route with the lowest cost.

Distance Vector Technologies

• Distance vector routing protocols share updates between neighbors.
• They aren't aware of the network topology and some send periodic updates to broadcast IP 255.255.255.255 even if the topology hasn't changed.
• Updates consume bandwidth and network device CPU resources.
• RIPv2 and EIGRP use multicast addresses.
• EIGRP will only send an update when the topology has changed.
• Purposes of routing algorithms include sending and receiving updates, calculating best path and install route, and detect and react to topology changes.
• RIP uses the Bellman-Ford algorithm and IGRP and EIGRP use the Diffusing Update Algorithm (DUAL) routing algorithm developed by Cisco.

RIPv1 vs RIPv2

• Regarding RIP vs RIPv2, both use hop count as a metric with a maximum of 15 hops.
• RIPv1 uses the 255.255.255.255 update address and the 224.0.0.9 address by RIPv2.
• RIPv1 does not support VLSM, CIDR, summarization or authentication whereas RIPv2 supports VLSM, CIDR, summarization and authentication.
• RIPng is based on RIPv2 with a 15 hop limitation and the administrative distance of 120.
• EIGRP uses a composite metric consisting of bandwidth and delay with reliability and load also factored in.
• EIGRP sends updates to address 224.0.0.10, supports VLSM, CIDR, summarization, and authentication, features lacking in IGRP.
• EIGRP also uses bounded triggered updates, a Hello keepalives mechanism, maintains a topology table, supports rapid convergence, and is a multiple network layer protocol support

Configuring RIP

• To configure advertising networks, enter global configuration mode, then router configuration mode for RIP.
• Use network commands to advertise networks.
• Default RIP settings included the following: outgoing update filter list for all interfaces is not set; incoming update filter list for all interfaces is not set.
• Updates are sent every 30 seconds, invalid after 180 seconds, held down for 180 seconds, and flushed after 240.
• Sending automatic summarization and version 1 are enabled.
• To enable RIPv2, enter router configuration mode and use the "version 2" command.
• Disable automatic summarization with the command "no auto-summary".
• To configure a passive interface, enter router configuration mode and use the "passive-interface [interface]" command.
• Sending out unneeded updates on a LAN impacts the network in three ways: wasted bandwidth, wasted resources, and security risk.
• To propagate a default route, use the command "ip route 0.0.0.0 0.0.0.0 [next hop or exit interface]" then use the command "default-information originate" in the router RIP configuration.

Link-State Operation: SPF

• Link-state routing protocols use the shortest path for best routes.
• Link-state Routing Protocols are OSPF and IS-IS.
• R4 needs to be able to flood through R1, R2 and R3 routers.
• Dijkstra's Algorithm is used to determine shortest path, calculating the best path for host on R2 LAN to reach host on R3 LAN: R2 to R1 (20) + R1 to R3 (5) + R3 to LAN (2) = 27
• Each router learns about its own directly connected networks and is responsible for "saying hello" to neighbors on directly connected networks building a Link State Packet (LSP) containing the state of each directly connected link.
• Routers flood the LSP to all neighbors who then store all LSP's received in a database.
• Each router then uses the database to construct a complete map of the topology to compute the best path to each destination network.
• During discovery, each router learns its own links and directly connected networks.
• Link 1 involves network 10.1.0.0/16 and link 2 consists of Network: 10.2.0.0/16.
• Each router is also responsible for meeting it neighbors with the second step in linking state updates.
• Each router builds a link-state packet (LSP) containing the state of each directly connected link.
• An LSP would include R1 with Ethernet network 10.1.0.0/16, Cost 2, R1 -> R2 with Serial point-to-point network 10.2.0.0/16 and Cost 20; R1 -> R3 Serial point-to-point network 10.7.0.0/16 and Cost 5 and, R1 -> R4: Serial point to point network 10.4.0.0/16 and Cost 20.
• Each router floods the LSP to all neighbors who then store all LSPs received in a database, using 10.5.0.0/16, 10.2.0.0/16, and 109.0.0/16 to map the network.
• Each router uses the database to construct a complete map of the topology to compute the best path to each destination network.

Resulting SPF Tree for R1

• 10.5.0.0/16 with Shortest Path of R1 -> R2 and 22 for cost
• 10.6.0.0/16 with Shortest Path of R1 -> R3 and 7 for cost
• 10.7.0.0/16 with Shortest Path of R1 -> R3 and 15 for cost
• 10.8.0.0/16 with Shortest Path of R1 -> R3 -> R4 and 17 for cost
• 10.9.0.0/16 with Shortest Path of R1 -> R2 and 30 for cost
• 10.10.0.0/16 with Shortest Path of R1 -> R3 -> R4 and 25 for cost
• 10.11.0.0/16 with Shortest Path of R1 -> R3 -> R4 -> R5 and 27 for cost
• OSPF routes are then mapped to the routing table as with other directly connected networks and routing settings to create an organized approach to network traffic.

Advantages & Disadvantages of Link-State Routing Protocols

• Each router builds its own topological map of the network to determine the shortest path.
• Immediate flooding of LSPs achieves faster convergence.
• LSPs are sent only when there is a change in the topology and contain only the information regarding that change.
• The hierarchical design is used when implementing multiple areas.
• Maintaining a link-state database and SPF tree requires additional memory.
• Calculating the SPF algorithm also requires additional CPU processing.
• Bandwidth can be adversely affected by link-state packet flooding.
• Areas are created to minimize router resource usage.
• Protocols that Use Link-State include two open shortest path and IS-IS.
• Open Shortest Path was first created in 1987.
• Open Shortest Path as now two current versions; OSPFv2 for IPv4 and OSPFv3 for IPv6 networks.
• IS-IS was first designed by International Organization for Standardization (ISO).

IPv4 Routing Table Entries

• Routes are discussed in terms of ultimate routes with level 1, level 1 parent and level 2 child routes.
• An ultimate route is a routing table entry that contains either a next-hop IP address or an exit interface where directly connected routes and linked learned routes are ultimate routes.
• Sources of Level 1 Routes include Networks, Supernets,Default.
• The router continues searching level 1 supernet routes in the routing table for a match, including the default route, if there is one, with Level 1 routes.
• Level 1 parent routes contains subnet masks and Gigabit Ethernet connections.
• After examining child routes if there is a match of layer two subnet the layer will be used to forward data packets.
• The best route is described by what the longest match, determined using IP packet destination.

Chapter 2 Key Points

• Dynamic routing protocols enable routers to automatically learn about remote networks from other routers.
• Protocols purpose includes discovery of remote networks; maintaining up-to-date routing information; choosing the best path to destination networks and finding a new best path if the current path is no longer available.
• Dynamic protocols are the best choice for large networks, in which static routing would be better for stub networks.
• A function to inform other routers about changes Can be classified as either classful or classless, distance-vector or link-state, and an interior or an exterior gateway protocol A link-state routing protocol can create a complete view or topology of the network.
• Metrics are used to determine the best route or shortest path.
• Different Routing protocols may include (hops, bandwidth, delay, reliability and load).
• Each route is determined by the administrative distance value where lower is preferred.
• Routers are determined by directly connected networks over static routes.
• OSPF is a OSPF link on interface where link-states is available and will apply Dijkstra's total cost to determine routes and algorithms from source to destination.
• *show ip protocols command displays the IPv4 and IPv6 routing protocol settings.