ROUTING ALGORITHMS IN COMPUTER
NETWORKS
1. Introduction
Routing is the process of selecting the best path for transmitting data packets from one network to another. Routers
use routing algorithms to determine efficient1 paths between source and destination devices. The two major routing
approaches are Distance Vector Routing and Link-State Routing. Distance Vector Routing relies on routers
X Y
exchanging routing tables with neighboring routers, while Link-State Routing requires routers to build a complete map
of the network topology.
Distance Vector Routing mainly uses the Bellman-Ford algorithm, while Link-State Routing uses the Dijkstra Shortest
Path First (SPF) algorithm. 5These routing methods are implemented
2 in real-world routing protocols such as Routing
Information Protocol (RIP), Enhanced Interior Gateway Routing Protocol (EIGRP), and Open Shortest Path First
(OSPF).
Z
Figure 1: Distance Vector Network Topology and Link Costs
2. Distance Vector Routing
Distance Vector Routing is a routing technique in which routers maintain routing tables containing the shortest known
distance to every destination. Routers exchange routing tables with neighboring routers periodically and update their
routes using the Bellman-Ford algorithm.
Initially, each router only knows the cost to directly connected neighbors. For example, router X initially believes the
shortest path to router Z is the direct cost of 5. After receiving routing information from router Y, router X discovers a
shorter path X → Y → Z with a total cost of 3.
Router Initial Distance Vector
X (0,1,5)
Y (1,0,2)
Z (5,2,0)
3. Link-State Routing
Link-State Routing is a routing methodR2where every router builds a complete map of the network topology. Routers
exchange Link-State Advertisements
LSA (LSAs), synchronize
LSA their Link-State Databases (LSDBs), and independently
calculate shortest paths using the Dijkstra SPF algorithm.
OSPF routersR1begin by sending Hello packets to discover neighboring
R3 routers. Once neighbors are discovered,
routers form adjacencies and exchange LSAs. The LSAs are flooded throughout the OSPF area so that all routers
maintain identical topology information.
R4
Figure 2: OSPF Link-State Advertisement Flooding
4. Bellman-Ford versus Dijkstra Algorithm
The Bellman-Ford algorithm is used in Distance Vector Routing protocols such as RIP. Routers exchange routing
tables periodically and calculate shortest paths using information from neighboring routers only.
The Dijkstra algorithm is used in Link-State Routing protocols such as OSPF. Routers maintain a complete topology
map and independently compute shortest paths using the SPF algorithm. Dijkstra converges faster and is more
suitable for large enterprise networks.
Feature Bellman-Ford Dijkstra SPF
Routing Type Distance Vector Link-State
Network Knowledge Neighbors Only Complete Topology
Convergence Speed Slower Faster
Scalability Small Networks Large Networks
Example Protocol RIP OSPF
5. Convergence Behaviour
Convergence refers to the process by which all routers obtain accurate and consistent routing information. Distance
Vector Routing converges more slowly because routers exchange updates periodically. During network failures,
incorrect routing information may circulate for a long time, causing the count-to-infinity problem.
Link-State Routing protocols such as OSPF converge much faster because topology changes are immediately
flooded throughout the network. Routers independently recompute shortest paths using the Dijkstra algorithm
whenever a topology change occurs.
6. Update Mechanisms
Distance Vector protocols use periodic routing updates. RIP sends updates every 30 seconds to neighboring routers.
Several techniques are used to reduce routing instability, including Split Horizon, Route Poisoning, and Hold-Down
Timers.
Split Horizon prevents routers from advertising routes back through the same interface from which they were learned.
Route Poisoning advertises failed routes with an infinite metric to indicate that the destination is unreachable.
Hold-Down Timers temporarily prevent unstable route changes from spreading through the network.
Link-State Routing protocols use triggered updates instead of periodic table exchanges. Whenever a network
topology changes, routers immediately flood LSAs throughout the OSPF area.
7. Real-World Routing Protocols
Routing Information Protocol (RIP)
RIP is one of the oldest Distance Vector Routing protocols. It uses hop count as the routing metric and supports a
maximum of 15 hops. RIP is easy to configure and suitable for small office networks and educational environments.
Enhanced Interior Gateway Routing Protocol (EIGRP)
EIGRP is an advanced Cisco routing protocol that combines features of both Distance Vector and Link-State Routing.
It uses the Diffusing Update Algorithm (DUAL) for fast convergence and supports metrics such as bandwidth, delay,
reliability, and load.
Open Shortest Path First (OSPF)
OSPF is a Link-State Routing protocol that uses the Dijkstra SPF algorithm. Routers exchange LSAs, build LSDBs,
and independently compute shortest paths. OSPF converges quickly and is widely used in enterprise and large-scale
networks.
8. Suitable Use Cases
Distance Vector Routing protocols such as RIP are best suited for small-scale networks because of their simplicity
and low resource requirements. Examples include small office environments, school laboratories, and simple
enterprise networks.
Large-scale enterprise networks require faster convergence, scalability, and accurate topology awareness. Protocols
such as OSPF are preferred because they efficiently manage complex topologies and large routing domains.
EIGRP is commonly used in medium-sized and large Cisco enterprise networks because of its fast convergence and
efficient route calculations.
9. Conclusion
Routing algorithms are essential for efficient communication in computer networks. Distance Vector Routing uses the
Bellman-Ford algorithm and exchanges routing information between neighboring routers, while Link-State Routing
uses the Dijkstra SPF algorithm and maintains a complete network topology map.
Protocols such as RIP, EIGRP, and OSPF demonstrate how different routing methods are applied in real-world
networks. Although Distance Vector Routing is simpler and suitable for smaller environments, Link-State Routing
provides faster convergence, scalability, and reliability for modern enterprise networks.