4.

1 Introduction to Dynamic Routing

Protocols
 4. Dynamic Routing
______________________________________________________________

Introduction to Dynamic Routing Protocols

Dynamic routing protocols allow routers to automatically discover remote
networks, maintain up-to-date routing information, and determine the best path to
those networks.

Purpose of Dynamic Routing Protocols:

●​ Discovery of remote networks.
●​ Maintaining up-to-date routing information.
●​ Choosing the best path to destination networks.
●​ Ability to find a new best path if the current path is no longer available.

Operation of a Dynamic Routing Protocol:

●​ The router sends and receives routing messages on its interfaces.
●​ The router shares routing messages and routing information with other routers
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.
●​ There are different routing protocols as follows:
Cold Start

●​ After a router boots successfully, it applies the saved configuration.

●​ The router initially discovers its own directly connected networks.
●​ It adds those connected interface IP addresses to its routing table.​

Network Discovery​
If a dynamic routing protocol is configured, the router begins to learn remote routes:

●​ It sends update packets containing its routing table information out all interfaces.
●​ It receives updates from directly connected routers.
●​ It adds new information learned from updates to its routing table.

Classification of Routing Protocols:

Category Description Examples

IGP (Interior Gateway Used within an Autonomous RIP, EIGRP, OSPF,

Protocols) System IS-IS

EGP (Exterior Gateway Used between Autonomous BGP

Protocols) Systems
Features / Characteristics of Routing Protocols

Routing protocols can be compared and evaluated based on their characteristics.​

These characteristics determine how efficiently and quickly a routing protocol can
operate in a network.

1. Convergence

●​ Convergence time is the time it takes routers to share information, calculate best
paths, and update routing tables.
●​ Convergence time is the time taken by routers to:
○​ Share routing information
○​ Calculate best paths
○​ Update routing tables
●​ Faster convergence means that the routing protocol quickly adapts to network
topology changes.

2. Scalability

●​ Scalability refers to how well a routing protocol can support a growing network.
●​ A scalable routing protocol should be able to handle many routers and routes
without performance issues.​

3. Classful vs Classless Operation

●​ Classless routing protocols include subnet mask information in routing updates

and support Variable Length Subnet Masking (VLSM) and Classless Inter-Domain
Routing (CIDR).​

○​ Examples: RIPv2, EIGRP, OSPF, IS-IS​

●​ Classful routing protocols do not send subnet mask information and cannot
support VLSM.​

○​ Example: RIPv1
 4. Use of Metrics

A metric is a measurable value assigned by a routing protocol to determine the

overall cost of a path. The best path is the route with the lowest cost.

Protocol Metric Used

RIP Hop count

OSPF Cost based on cumulative bandwidth

EIGRP Bandwidth, delay, load, reliability

5. Administrative Distance (AD)

●​ Administrative Distance is the trustworthiness of a routing source.

●​ Lower AD = more preferred source of routing information.​
(Note: AD values are standard across Cisco systems)

6. Updates Method

Routing protocols differ in how they share routing information:

Protocol Type Update Behavior

Distance Vector Periodic updates shared with neighbors. Routers are not
aware of full topology.
 Link-State No periodic updates; only sends updates when topology
changes. Builds a complete topology map.

7. Loop Prevention Mechanisms

Distance Vector protocols use techniques to prevent routing loops, such as:

●​ Split Horizon​

●​ Hold-down Timers​

●​ Route Poisoning

8. Resource Requirements

Link-state protocols require more system resources.​

Resource Requirement in Link-State Protocols

Memory Stores topology database

CPU Calculates SPF algorithm (Dijkstra)

Bandwidth Flooding LSPs can affect bandwidth

​
4.1 Classification of Protocols
4.2 Classification of Dynamic Routing Protocols

Dynamic routing protocols are classified on the basis of how routing information is
shared and how the best path is selected.

There are three major categories:

1.​ Distance Vector Routing (DVR)

2.​ Advanced Distance Vector Routing (ADVR / Hybrid)
3.​ Link-State Routing (LSR)

Distance Vector Routing (DVR)

Distance Vector Routing (DVR) is a class of dynamic routing techniques in which each
router makes routing decisions based on information received only from its directly
connected neighboring routers, rather than knowing the full network topology.

The term “Distance Vector” denotes:

●​ Distance: The cost associated with reaching a destination network (e.g., hop
count, delay, bandwidth).
●​ Vector: The direction, i.e., the next-hop router that packets must take to
reach that destination.

Thus, DVR protocols operate on the principle of routing by rumor, meaning routers
learn about remote networks indirectly through neighbors.

1) Working Principle

1.​ Each router maintains a Routing Table that lists:

○​ Destination network
○​ Next-hop router
○​ Associated metric (distance)​
 2.​ Routers periodically exchange their entire routing tables with
neighboring routers.​

3.​ Upon receiving an update, the router:

○​ Increments the metric (e.g., adds 1 hop in RIP)
○​ Compares it with existing routes
○​ Chooses the route with the lowest metric​

4.​ If a route becomes unreachable, the router:

○​ Sets the route metric to infinity (e.g., 16 hops in RIP means
unreachable)
○​ Propagates this information to neighbors

This process continues until all routers hold consistent routing information, i.e., the
network converges.

2) Routing Algorithm

Protocol Algorithm Used Behavior

RIP Bellman–Ford Selects paths based on hop count;

simple but slow to converge

IGRP DUAL precursor (Cisco Multi-metric support (bandwidth,

proprietary) load, delay)

The Bellman–Ford algorithm is iterative and computes shortest paths incrementally

using neighbor information. It requires multiple update cycles to reach
convergence.
3) Characteristics

●​ Periodic Updates: Routing tables are broadcast or multicast at fixed

intervals (e.g., every 30 seconds in RIP).
●​ Neighbor-Based Knowledge: Routers do not form a global network map.
●​ Metric Simplicity: DVR protocols often use simple metrics (like hop
count), making processing overhead low.
●​ Slower Convergence: Because updates propagate step-by-step between
neighbors, convergence time increases in large networks.​

4) Loop Prevention Techniques

DVR protocols are prone to routing loops because routers may propagate
outdated or incorrect routing info. To minimize loops:

Technique Purpose

Split Horizon Prevents sending a route back in the direction from which
it was learned

Route Poisoning Explicitly marks a route as unreachable by setting its

metric to infinity

Hold-Down Temporarily suppresses route updates to stabilize

Timers convergence

Triggered Sends immediate updates when a route changes instead of

Updates waiting for periodic updates

These mechanisms enhance stability and reduce routing oscillations.

5) Strengths and Limitations

Advantages Limitations

Very simple to configure and Convergence is slow in large networks

understand

Low memory and CPU Limited scalability

consumption

Works reliably in small and Susceptible to routing loops

static topologies

Predictable behavior Typically uses less intelligent metrics (e.g.,

hop count in RIP)

6) Examples of DVR Protocols

Protocol Addressing Metric Notes

Support

RIPv1 IPv4 Hop count Classful (no subnet mask info)

RIPv2 IPv4 Hop count Classless, uses multicast ([Link]) and

supports VLSM
RIPng IPv6 Hop count IPv6 version of RIP

IGRP IPv4 Composite Cisco proprietary; obsolete, replaced by

metric EIGRP

/Distance Vector Routing protocols determine routes based on distance (metric)

and vector (next-hop) information learned from neighboring routers. Routing tables
are exchanged periodically, and routers update routes using the Bellman-Ford
algorithm. DVR is simple and resource-efficient but suffers from slow convergence
and is more prone to routing loops, requiring mechanisms such as split horizon,
route poisoning, and hold-down timers. Examples include RIP and IGRP.

Link State Routing (LSR)

Link State Routing protocols are a class of dynamic routing protocols in which
each router constructs a complete and synchronized topological map of the
network.

Instead of relying solely on neighbor routing tables (as in Distance Vector), LSR
protocols exchange link-state information that describes the state of each link in the
network.

This enables every router to run an algorithm that computes the shortest and
loop-free path to every destination.

The primary LSR protocols are:

●​ OSPF (Open Shortest Path First)

●​ IS-IS (Intermediate System to Intermediate System)​

Both utilize Dijkstra’s Shortest Path First (SPF) algorithm.

Core Operational Principles
1) Link-State Advertisements (LSAs / LSPs)

Each router originates link-state advertisements that describe:

●​ Its directly connected networks

●​ Each interface cost (or metric)
●​ Neighbor relationships

These LSAs are flooded throughout the area, ensuring every router has identical
topology information.

2) Link-State Database (LSDB)

All LSAs are stored in a Link-State Database, which serves as a network-wide

topology map.

3) SPF Computation

Each router independently runs Dijkstra’s SPF on its LSDB to compute:

●​ The shortest path tree (SPF tree)

●​ Next-hop routes to all networks​
The best results are inserted into the Routing Table (RIB).​
LSR Operation Sequence

Step Description

1. Neighbor Routers exchange Hello messages to discover

Discovery adjacent routers.

2. LSA Generation Each router builds LSAs describing its links and
state.

3. LSA Flooding LSAs are propagated reliably to all routers in the

same area.

4. LSDB Every router forms an identical LSDB.

Synchronization

5. SPF Calculation Dijkstra’s algorithm is executed to compute the best

paths.

6. Routing Table The best paths are installed in the routing table.
Update
Metric Used

LSR protocols use link cost, generally derived from bandwidth:

Higher bandwidth → Lower cost → Preferred path.

Characteristics of LSR

Characteristic Explanation

Complete Topology Each router has a full network map.

Knowledge

Fast Convergence Only changes trigger recomputation; backup routes

are recalculated rapidly.

Reliable Updates LSAs are acknowledged and sequenced, preventing

loops and stale data.

Hierarchical Design Supports multi-area routing for scalability (Area 0

backbone in OSPF).
Advantages

●​ Very fast convergence

●​ Loop-free routing, due to full topology visibility
●​ Highly scalable for large enterprise or ISP-grade networks
●​ Efficient incremental updates only during topology change​

Disadvantages
●​ Higher memory requirements (LSDB storage)
●​ More CPU processing (SPF execution)
●​ Initial flooding consumes bandwidth
●​ Design complexity increases with multi-area topologies​

Link State Routing protocols maintain a synchronized network topology

database and compute shortest paths using Dijkstra’s SPF algorithm. They
provide highly accurate, loop-free, and rapidly converging routing,
making them suitable for large, hierarchical networks. Examples include
OSPF and IS-IS.

Advanced Distance Vector Routing (ADVR / Hybrid)

Advanced Distance Vector Routing, also referred to as Hybrid Routing, represents
a class of routing protocols that integrate the operational characteristics of Distance
Vector and Link-State algorithms to achieve high routing efficiency, rapid
convergence, and loop-free path computation.

The canonical implementation of ADVR is EIGRP (Enhanced Interior Gateway

Routing Protocol).
Architectural Characteristics

1.​ Neighbor-Based Operation (Distance Vector Component):

○​ Routing information is exchanged only between adjacent routers
(neighbors).
○​ Neighbor adjacencies are maintained using periodic Hello packets.
○​ ​

○​
2.​ Topology Awareness (Link-State Component):
○​ All feasible routes learned from neighbors are stored in a Topology
Table, not just the best path.
○​ This provides partial topology knowledge, improving convergence
and failover behavior.​

3.​ DUAL (Diffusing Update Algorithm):

○​ Core algorithm responsible for loop-prevention and optimal path
computation.
○​ Ensures loop-free feasible routes through the Feasibility Condition
(FC):

A route is considered feasible if the neighbor’s Advertised Distance (Reported

Distance) is less than the local router’s Feasible Distance.​

4.​ Successor and Feasible Successor Paths:

○​ Successor: Primary next-hop route with minimum computed metric.
○​ Feasible Successor: Standby backup route that satisfies the
Feasibility Condition.
○​ Enables instant (sub-second) convergence, without route
recomputation.
Metric Computation (Composite Metric)

EIGRP uses a vector metric model based on multiple measured parameters:

Default K-values (weights):

Parameter Symbol Default Use

Bandwidth K1 Enabled

Delay K3 Enabled

Reliability K4 Disabled

Load K2/K5 Disabled

Thus, by default, EIGRP metric primarily depends on:

This makes ADVR path-quality aware, unlike RIP which uses only hop count.
Update Propagation Model:

●​ Not periodic.
●​ Uses Triggered Updates → Updates are sent only when a topology change is
detected.
●​ Partial updates only → Only affected routing entries are transmitted.
●​ RTP (Reliable Transport Protocol) ensures reliable and ordered delivery of
routing updates via selective acknowledgment.

This achieves bandwidth efficiency and minimizes unnecessary control plane

traffic.

Routing Tables Maintained

Table Contents Purpose

Neighbor Active adjacencies Determines reachability of

Table neighbors

Topology All learned routes + Used by DUAL for path

Table metrics computation

Routing Best successor routes Installed into the data plane

Table only (FIB)
Operational Behavior Summary

Property Behavior

Convergence Fast (owing to feasible successors + DUAL)

Loop Prevention Mathematically guaranteed via Feasibility Condition

Resource Usage Moderate CPU + higher memory than RIP

Scalability High (suitable for enterprise and large internetworks)

Update Model Triggered, bounded, and reliable

Technical Advantages

●​ Deterministic, loop-free path computation

●​ Sub-second convergence due to backup paths
●​ Bandwidth-efficient update exchange mechanism
●​ Multi-criteria routing metric allows intelligent path selection
●​ Scales efficiently in multi-area and multi-topology environments

Technical Limitations

●​ Requires more memory (stores multiple topology entries)

●​ Higher CPU overhead for DUAL computations
●​ Historically Cisco-proprietary (standardized later under RFC 7868)
●​
Advanced Distance Vector Routing (ADVR) protocols integrate
neighbor-based routing with topology-aware path management. EIGRP, the
primary ADVR protocol, uses the DUAL algorithm to compute loop-free
successors and feasible successors, enabling rapid convergence. Routing
updates are triggered and partial, transported reliably via RTP. Routes are
selected based on a composite metric derived from bandwidth and cumulative
delay. ADVR offers high scalability, deterministic loop prevention, and
sub-second failover performance.

Comparison (DVR vs ADVR vs LSR)

Property DVR LSR ADVR (Hybrid)

Network No topology Full topology Partial topology

Knowledge awareness awareness awareness

Convergence Slow Very fast Fast

Updates Periodic full table Triggered + LSAs Triggered/Partial

Algorithm Bellman-Ford Dijkstra SPF DUAL

Scalability Low High Medium-High