Routing Protocols: Dynamic, IGP, EGP, Distance Vector

• Dynamic routing protocols help discover remote networks
• They maintain up-to-date routing information
• Choose the best paths to destination networks
• Find a new best path if the current one fails

Routing Protocols

• Link-State, Distance Vector, and Path-Vector are all types of routing protocols

IGP and EGP Routing Protocols

• Interior Gateway Protocols (IGP) are for routing within an Autonomous System (AS)
• RIP, EIGRP, OSPF, and IS-IS are examples of IGPs
• Exterior Gateway Protocols (EGP) provide routing between Autonomous Systems
• BGP is an example of an EGP

Distance Vector Protocol

• Routers send and receive information through their interfaces
• Routers share routing details with others using the same protocol
• Exchange helps learn network topologies
• A topology change triggers advertisement of the change to other routers

Link State Protocol

• Link-State routers use information received from other routers
• Create topology maps
• Select the best path to all destination networks in the topology
• Link-state routing protocols don't typically use periodic updates; updates occur when a change exists in the topology
• OSPF and IS-IS protocols are types of Link State

Classful vs Classless

• Classless protocols include subnet mask info in routing updates
• Classful ones do not send subnet mask information
• Classful protocols can't support VLSMs and CIDR
• They also cause issues in discontiguous networks
• Classless IPv4 protocols like RIPv2, EIGRP, OSPF, and IS-IS include the subnet mask in routing updates
• Classless protocols support VLSM and CIDR
• IPv6 routing protocols are classless

Comparing Routing Protocols

• Routing protocols characteristics can be compared, such as: convergence speed, scalability, VLSM use, resource usage, and implementation
• RIPv1 and IGRP are no longer used

Routing Metric

• A measurable value assigned by the routing protocol
• Routes are assigned this value to measure usefulness
• Routing metrics determine the "cost" of a path from source to destination
• Best path is the one with the lowest cost
• Metrics used by dynamic protocols:
• HOP counts for RIP
• Cost based on cumulative bandwidth for OSPF
• Bandwidth, delay, load, and reliability for EIGRP

Distance Vector Operation

• Dynamic routing sends and receives messages on its interfaces
• Shares with other routers with routing is the same
• Information is exchanged to learn remote network info
• Topology changes are advertised to other routers

Cold Start

• A router applies saved config on boot and discovers directly connected networks
• Interface IP addresses added to routing table

Network Discovery

• When a routing protocol is configured, the router exchanges routing updates to discover remote routes
• The router sends an update packet to all interfaces regarding its routing table information
• Receives updates from connected routers and adds the information to its routing tables
• Example of RIP metric is Hop count

Exchanging Routing Information

• Routers exchange the next round of periodic updates to move toward convergence
• Distance vector protocols use split horizon to avoid loops
• Split horizon blocks information that came from an interface to be sent out of that same interface

Achieving Convergence

• A network has converged when all routers have complete and accurate information
• Convergence time is the time to share information, calculate paths, and update tables
• Routing protocols can be rated based on how quickly they converge; the faster, the better

Distance Vector Technologies

• Neighbors are routers sharing a link, configured for the same routing protocol
• Distance vector routing protocols update between neighbors
• Distance vector routing routers use their own interface addresses, and remote network addresses reachable through neighbors
• A distance vector routing protocol such as RIPv1 and RIPv2 sends periodic updates
• RIPv1 sends updates as broadcasts to IP address 255.255.255.255
• RIPv2 and EIGRP use multicast addresses to reach specific neighbors
• EIGRP uses unicast to reach a neighbor, only sending updates when needed

Distance Vector Algorithm

• Defines processes such as sending and receiving routing information
• Mechanisms for calculating best paths and installing routing tables
• Mechanisms for detecting and reacting to topology changes
• The Bellowman-Ford Algorithm is used by RIP
• Diffusing Update Algorithm (DUAL) is used by the EIGRP routing algorithm

Routing Information Protocol (RIP)

• It is easy to congfigure
• Routing updates broadcasted (255.255.255.255) every 30 seconds
• Metric uses hop count
• Is restricted to a 15 hop limit
• RIPv2 offers classless routing and supports VLSM and CIDR
• Sends updates via multicast address 224.0.0.9
• Has reduced routing entries (supports manual route summarization)
• Secure because it supports authentication
• RIPng uses IPv6 for IP addresses, and has a 15 hop limit with an administrative distance of 120

Enhanced Interior Gateway Routing Protocol (EIGRP)

• Has replaced IGRP in 1992, and includes features such as:
• Bounded triggered updates (updates are only sent to routers that require it)
• Hello keepalive mechanism, which exchanges Hello messages to maintain adjacencies
• Maintains a topology table that maintains all routes it receives from neighbours (not only the best ones) in a topology table
• Rapid convergence as it maintains alternate routes
• Multiple network layer protocol support is in place for layer 3 protocols by using Protocol Dependent Modules (PDM)
• Shortest Path First (SPF) calculates

Link State Routing

• Also known as shortest path protocols built around Edsger Dijkstra's algorithm
• IPv4 link-state routing includes, Open Shortest Path First (OSPF) and Intermediate System-to-Intermediate System (IS-IS)

Dijkstra's Algorithm

• Dijkstra’s algorithm is used to calculate the best path route
• It uses accumulated costs along each path, from source to destination
• Each router determine its own cost to each destination within the topology

SPF Example

• A table displays shortest path and cost to reach destination networks from R4 perspective

Link-State Routing Process

• Each router learns directly connected networks.
• Each router says "hello" to neighbors in directly connected networks
• Each router builds a Link-State Packet (LSP) storing state of each directly connected link
• Each router floods LSP to all neighbors which stores all LSP's in a database
• Each router uses the database to construct a map of the topology and computes the best path to each destination network
• This process is the same, whether OSPF uses, IPv4 or IPv6

Link and Link-State

• The first step for the link-state routing process is to learn about own connected network

Say Hello

• Each router uses a Hello protocol to discover any neighbors on its links
• Two link-state routers form an adjacency once they know they share a link
• If a router stops recieving Hello packets from a neightbor, that neighbor is unreachable

Building the Link-State Packet

• Each router builds a link-state packet (LSP) with link-state info of its links

Flooding the LSP

• Each router floods the LSP to all neighbors
• LSP is sent either on router startup, or when topology changes
• LSPs include sequence numbers and information on how old they are

Building the Link-State Database

• The last step is that each router constructs a complete map of the topology and computes the best path

Building the SPF tree

• Each router uses the link-state database and SPF algorithm to construct the SPF tree
• R1 identifies its directly connected networks and costs, then adds any unknown networks and costs
• SPF algorithm then calculates the shortest paths, with each router constructing its own SPF tree independently

Adding OSPF Routes

• The shortest path information is added to the routing table
• Directly connected and static routes are also added

Benefits of Link-State

• Advantages include each router building its own topological map to find the shortest path
• Immediate flooding of LSPS achieves faster convergence
• LSPs only send when there is a topology change
• Hierarchical design occurs when working with multiple areras

Disadvantages of Link-State

• These protocols require additional memory and CPU processing
• Flooding can affect bandwidth
• Multiple areas can reduce the size of the Link-State databases and limit the amount of flooding
• OSPFv2 works with IPv4 networks
• OSPFv3 helps IPv6 networks
• Integrated IS-IS supports IP networks and is primarily used by ISPs and carriers