Introduction
In modern computer networks, routers are responsible for forwarding data
packets from a source device to a destination device. To perform this task
efficiently, routers must determine the best available path through the
network. This process is known as routing, and it is accomplished using
routing algorithms.
One of the earliest and most important routing techniques is the Distance
Vector Routing Algorithm. It forms the foundation of several routing
protocols and has played a significant role in the development of computer
networking.
The Distance Vector Routing Algorithm is simple, distributed, and
efficient for small to medium-sized networks. Protocols such as RIP
(Routing Information Protocol) use this algorithm to exchange routing
information and build routing tables.
In this article, we will explore the Distance Vector Routing Algorithm,
its working principles, characteristics, advantages, limitations, and
real-world applications.
What is a Distance Vector Routing Algorithm?
A Distance Vector Routing Algorithm is a dynamic routing algorithm in
which each router maintains information about the distance and direction
(vector) to every destination network.
The term Distance Vector comes from:
- Distance → The cost required to reach a destination.
- Vector → The direction or next-hop router used to reach that destination.
Using this information, routers exchange routing data with their
neighboring routers and continuously update their routing tables until the
best routes are discovered.
Definition
Distance Vector Routing is a dynamic routing algorithm where routers share
routing information with their immediate neighbors and calculate the
shortest path to each destination based on distance metrics such as hop
count.
Why is Distance Vector Routing Important?
Distance Vector Routing helps routers:
- Discover network paths automatically.
- Adapt to network changes.
- Select the shortest path to a destination.
- Reduce manual configuration.
- Maintain routing information dynamically.
Without routing algorithms, network administrators would need to manually
configure routes for every device, which becomes impossible in large
networks.
Real-World Example
Imagine you are traveling from Chennai to Delhi.
You do not know every road in India. Instead, you ask nearby people for
directions.
Each person provides information about:
- The distance to Delhi.
- The best direction to take.
By continuously gathering information from nearby people, you eventually
discover the best route.
Distance Vector Routing works in a similar manner. Routers learn routes
from neighboring routers and gradually build a complete view of the
network.
Characteristics of Distance Vector Routing
Distance Vector Routing has three important characteristics:
1. Distributed
The algorithm is distributed because each router communicates only with
its directly connected neighbors.
There is no central controller managing routing decisions.
Example
Router A exchanges information only with Routers B and C if they are
directly connected.
2. Iterative
The routing process repeats continuously until all routers have consistent
routing information.
Routers repeatedly exchange updates and recalculate routes.
Example
When a new network is added, routers continue sharing updates until every
router learns about the new destination.
3. Asynchronous
Routers do not need to update simultaneously.
Each router can send and receive updates independently.
Example
Router A may update its routing table before Router B receives the
information.
Key Principles of Distance Vector Routing
To understand how the algorithm works, remember these three fundamental
principles:
1. Knowledge Sharing
Each router shares its knowledge of the network with neighboring routers.
The information includes:
- Destination networks
- Distance to each destination
- Next-hop router
2. Communication with Neighbors Only
Routers exchange routing information only with directly connected
neighbors.
They do not communicate directly with distant routers.
3. Periodic Updates
Routers regularly send routing updates.
For example, RIP sends updates every 30 seconds.
This ensures routing tables remain current and accurate.
Distance Vector Terminology
Before understanding the algorithm, let's define some important terms.
Router
A networking device that forwards packets between networks.
Neighbor Router
A router directly connected to another router.
Hop Count
The number of routers a packet passes through to reach its destination.
Example
A → B → C → D
Hop Count = 3
Routing Table
A database maintained by each router containing route information.
A routing table typically includes:
Destination Network Cost
Next Hop
Network 1
1
Direct
Network 2
2
Router B
Network 3
3
Router C
Bellman-Ford Algorithm
The Distance Vector Routing Algorithm is based on the Bellman-Ford
Algorithm.
The Bellman-Ford Algorithm calculates the shortest path by comparing
available routes and selecting the route with the minimum cost.
The basic formula is:
Dx(y) = min [ c(x,v) + Dv(y) ]
Where:
- Dx(y) = Distance from router x to destination y
- c(x,v) = Cost from router x to neighbor v
- Dv(y) = Distance from neighbor v to destination y
The router selects the route with the lowest total cost.
How Distance Vector Routing Works
The algorithm follows a series of steps.
Step 1: Initialize Routing Tables
Each router initially knows:
- Its own network
- Directly connected neighbors
Unknown destinations are assigned an infinite cost.
Step 2: Exchange Routing Tables
Each router sends its routing table to neighboring routers.
Example:
- A sends to B
- B sends to A and C
- C sends to B and D
Step 3: Calculate New Routes
Each router applies the Bellman-Ford equation.
If a shorter path is found:
- Cost is updated.
- Next-hop information is updated.
Step 4: Update Routing Table
The router stores the new best route.
Example
Router A learns from Router B that:
Network D can be reached in 2 hops.
Since A requires one hop to reach B:
A → B → D
Cost = 1 + 2 = 3
Router A updates its routing table.
Step 5: Repeat Until Stable
Routers continue exchanging updates until no further changes occur.
This state is known as:
Convergence
Convergence occurs when all routers have identical and accurate routing
information.
Routing Table Creation
Initially, every router creates a routing table containing:
Destination Network ID
The network where data must be delivered.
Cost
The number of hops required to reach the destination.
Next Hop
The neighboring router that should receive the packet.
Routing Table Updating
Whenever a router receives an update:
- Compare existing routes.
- Calculate new route costs.
- Select the route with the lowest cost.
- Replace old routes if a better path exists.
- Share updated information with neighbors.
This process continues automatically.
Example of Distance Vector Routing
Consider the following routers:
A ---- B ---- C ---- D
\ /
\ /
E ---- F
Initially:
- A knows only B and E.
- B knows A and C.
- C knows B and D.
As routing tables are exchanged:
- A learns about C through B.
- A learns about D through B and C.
- F learns about B through A.
Eventually, every router learns the best route to every network.
Advantages of Distance Vector Routing
Simple Implementation
Easy to configure and understand.
Low Hardware Requirements
Requires less memory and processing power.
Automatic Route Discovery
Routers automatically learn new routes.
Suitable for Small Networks
Works effectively in small and medium-sized environments.
Dynamic Updates
Adjusts routing information automatically when network changes occur.
Limitations of Distance Vector Routing
Slow Convergence
It may take time for all routers to learn network changes.
Routing Loops
Packets may circulate endlessly due to incorrect routing information.
Example
Router A believes Router B has the route.
Router B believes Router A has the route.
Packets continuously loop.
Count-to-Infinity Problem
Routers may continuously increase route costs when a network becomes
unreachable.
Example
Router A says:
"Destination cost is 2."
Router B says:
"Destination cost is 3."
The cost keeps increasing until it reaches infinity.
Limited Scalability
Not suitable for very large networks.
Solutions to Distance Vector Problems
Modern routing protocols use techniques to overcome limitations.
Split Horizon
Prevents routers from advertising routes back through the same interface.
Route Poisoning
Marks failed routes with an infinite metric.
Hold-Down Timers
Temporarily ignore unstable routing updates.
Triggered Updates
Immediately notify routers about topology changes instead of waiting for
periodic updates.
Protocols That Use Distance Vector Routing
RIP (Routing Information Protocol)
- Uses hop count metric
- Maximum hop count = 15
- Updates every 30 seconds
IGRP (Interior Gateway Routing Protocol)
- Developed by Cisco
- Uses bandwidth and delay metrics
- Supports larger networks than RIP
EIGRP (Enhanced Interior Gateway Routing Protocol)
- Advanced version of IGRP
- Uses DUAL algorithm
- Faster convergence
- Often considered a hybrid routing protocol
Applications of Distance Vector Routing
Distance Vector Routing is used in:
- Small office networks
- Educational laboratories
- Legacy enterprise systems
- Branch office networks
- RIP-based environments
It is particularly useful where network complexity is low.
