Routing Algorithms in Computer Networks – Dijkstra, Bellman-Ford, Distance Vector and Link State
What You Will Learn
- What routing is and how routers make forwarding decisions
- Dijkstra’s algorithm — step-by-step with worked example
- Bellman-Ford algorithm — how distance vector routing works
- Count-to-infinity problem and its solutions
- Distance vector vs link state routing comparison
- Real routing protocols: RIP, OSPF, BGP
- Routing table structure and longest prefix matching
1. Routing Basics
Routing is the process of selecting the best path for a packet to travel from its source to its destination across an interconnected network of routers. Every time your data crosses a network boundary, a router makes a routing decision.
Think of routing like a GPS navigation system for the internet. Just as GPS calculates the best route based on road conditions, routers calculate the best path based on network topology and link costs (bandwidth, delay, hop count).
Two Key Router Functions
- Routing (control plane): Building and maintaining the routing table — deciding the best next-hop for each destination network. This involves running routing algorithms and exchanging information with other routers.
- Forwarding (data plane): When a packet arrives, looking up the destination IP in the routing table and sending the packet out the correct interface. This happens in hardware at line speed.
Static vs Dynamic Routing
| Type | How Routes Are Set | Pros | Cons |
|---|---|---|---|
| Static routing | Manually configured by network admin | Predictable, secure, low overhead | Does not adapt to failures; impractical at scale |
| Dynamic routing | Automatically learned via routing protocols | Adapts to topology changes automatically | Protocol overhead; potential routing loops during convergence |
2. Routing Tables
Every router maintains a routing table — a list of destination networks, the next-hop router, and the interface to use. When a packet arrives, the router does a lookup and forwards accordingly.
Destination Mask Next Hop Interface
192.168.1.0 /24 10.0.0.1 eth0
10.0.0.0 /8 172.16.0.1 eth1
0.0.0.0 /0 203.0.113.1 eth2 (default)
Longest Prefix Matching
When multiple routing table entries match a destination IP, the router uses the entry with the longest prefix (most specific match) — the one with the most bits in the subnet mask.
Routing table has: 192.168.0.0/16 and 192.168.1.0/24 and 0.0.0.0/0
All three match 192.168.1.50, but /24 is the longest prefix → router uses 192.168.1.0/24 entry.
The default route (0.0.0.0/0) matches everything but is only used when no more specific route exists.
3. Dijkstra’s Algorithm
Dijkstra’s algorithm computes the shortest path from a single source to all other nodes in a graph with non-negative edge weights. It is the foundation of link state routing (used in OSPF).
Algorithm Steps
- Initialise: distance[source] = 0; distance[all others] = ∞; all nodes unvisited
- Pick the unvisited node u with the minimum distance
- For each unvisited neighbour v of u: if distance[u] + weight(u,v) < distance[v], update distance[v] and set previous[v] = u
- Mark u as visited
- Repeat steps 2–4 until all nodes are visited
Graph: A–B(4), A–C(2), B–D(3), B–C(1), C–D(5), C–E(8), D–E(2)
Find shortest paths from A.
Initial: A=0, B=∞, C=∞, D=∞, E=∞
Visit A (dist=0): Update B=4, C=2
Table: A=0✓, B=4, C=2, D=∞, E=∞
Visit C (dist=2, min unvisited): Update B=min(4, 2+1)=3, D=min(∞,2+5)=7, E=min(∞,2+8)=10
Table: A=0✓, B=3, C=2✓, D=7, E=10
Visit B (dist=3): Update D=min(7, 3+3)=6
Table: A=0✓, B=3✓, C=2✓, D=6, E=10
Visit D (dist=6): Update E=min(10, 6+2)=8
Table: A=0✓, B=3✓, C=2✓, D=6✓, E=8
Visit E (dist=8): No updates.
Shortest paths from A: A→B=3 (via C), A→C=2, A→D=6 (via C→B), A→E=8 (via C→B→D)
With adjacency matrix + linear search: O(V²)
With binary heap (priority queue): O((V + E) log V)
With Fibonacci heap: O(E + V log V)
Limitation: Does NOT work correctly with negative edge weights. Use Bellman-Ford for graphs with negative weights.
4. Bellman-Ford Algorithm
Bellman-Ford finds shortest paths from a source to all vertices, and also detects negative weight cycles. It is the basis of distance vector routing.
Algorithm Steps
- Initialise: distance[source] = 0; distance[all others] = ∞
- Repeat (V–1) times: for every edge (u, v, w), if distance[u] + w < distance[v], update distance[v] = distance[u] + w
- Check for negative cycles: run one more iteration; if any distance still decreases, a negative cycle exists
Source = A
Initial: A=0, B=∞, C=∞, D=∞
Round 1 (relax all edges):
A→B: B = min(∞, 0+1) = 1
B→C: C = min(∞, 1+2) = 3
A→C: C = min(3, 0+6) = 3 (no change)
C→D: D = min(∞, 3+3) = 6
B→D: D = min(6, 1+8) = 6 (no change)
Round 2: No changes → converged
Result: A=0, B=1, C=3, D=6
Slower than Dijkstra but works with negative weights and detects negative cycles.
5. Distance Vector Routing
In distance vector routing, each router maintains a table (vector) of known destinations and the distance/cost to reach them. Routers share this table only with their direct neighbours, periodically or on change.
How It Works
- Each router starts knowing only its directly connected links
- Periodically, each router sends its full routing table to all neighbours
- Upon receiving a neighbour’s table, router updates its own using: cost(me→dest) = cost(me→neighbour) + cost(neighbour→dest)
- Continues until no more updates occur (convergence)
Count-to-Infinity Problem
When a link fails, bad news propagates slowly — routers keep believing they can still reach the destination through routes that no longer exist, incrementing costs until they reach the maximum (infinity).
If A–N link fails:
B thinks: “I can reach N via A at cost 2” (stale info)
A hears from B and updates: “I can reach N via B at cost 3”
B hears from A: “Now cost 4” → A updates to 5 → B to 6 → …
This continues until cost = 16 (RIP’s infinity) → route removed (very slow!)
Solutions to Count-to-Infinity
- Split Horizon: Don’t advertise a route back to the router you learned it from. B won’t tell A about routes learned from A.
- Route Poisoning: When a route fails, advertise it with infinite cost immediately. Fast propagation of bad news.
- Hold-down timers: Once a route is marked as failed, ignore any updates about it for a period. Prevents premature “revival.”
- Triggered updates: Send updates immediately when a route changes, instead of waiting for the next periodic timer.
Uses hop count as metric (max 15 hops; 16 = infinity). Periodic updates every 30 seconds. Slow convergence — only suitable for small networks.
6. Link State Routing
In link state routing, each router builds a complete, identical map of the entire network topology, then independently runs Dijkstra’s algorithm to find optimal paths to all destinations.
How It Works
- Neighbour discovery: Each router discovers its directly connected neighbours using HELLO packets
- LSA generation: Each router creates a Link State Advertisement (LSA) describing its neighbours and link costs
- Flooding: Each router floods its LSA to ALL routers in the network (not just neighbours)
- Database building: Each router collects all LSAs, building an identical link-state database (network map)
- SPF calculation: Each router runs Dijkstra’s algorithm on its database to compute the shortest path tree
- Forwarding table: Derived from the shortest path tree
Uses link cost (based on bandwidth) as metric. Supports hierarchical routing (areas). Faster convergence than RIP. Widely used within enterprise and ISP networks.
7. Distance Vector vs Link State
| Feature | Distance Vector | Link State |
|---|---|---|
| Topology knowledge | Only distances + next hops (partial view) | Complete network map |
| Information shared | Routing table with neighbours | LSAs flooded to entire network |
| Algorithm | Bellman-Ford (distributed) | Dijkstra (each router runs independently) |
| Convergence speed | Slow | Fast |
| Count-to-infinity | Yes — a significant problem | No — complete topology prevents this |
| Memory usage | Low (only own routing table) | High (full topology database) |
| CPU usage | Low | High (runs Dijkstra) |
| Scalability | Poor (slow convergence, loops) | Good (with hierarchical areas in OSPF) |
| Real protocols | RIP, IGRP | OSPF, IS-IS |
8. Real Routing Protocols
RIP (Routing Information Protocol)
- Type: Distance Vector
- Metric: Hop count (max 15; 16 = infinity)
- Updates: Every 30 seconds (full table broadcast)
- Convergence: Very slow
- Use: Small, simple networks only
- Versions: RIPv1 (classful), RIPv2 (classless with CIDR), RIPng (IPv6)
OSPF (Open Shortest Path First)
- Type: Link State
- Metric: Cost (typically based on bandwidth: cost = 10⁸ / bandwidth)
- Updates: Only when topology changes (triggered LSAs); partial updates
- Convergence: Fast
- Hierarchy: Divides network into areas; Area 0 (backbone) connects all areas
- Use: Standard enterprise and ISP intra-domain routing protocol
BGP (Border Gateway Protocol)
- Type: Path Vector (evolved from distance vector)
- Metric: Policy-based (AS path length, local preference, MED, etc.)
- Scope: Between Autonomous Systems (inter-domain) — connects ISPs and major networks
- Updates: Triggered (only changes); incremental
- Transport: Runs over TCP (port 179) — reliable delivery guaranteed
- Loop prevention: AS path attribute — if a router sees its own AS in the path, it rejects the route
IGP (Interior Gateway Protocol): operates within a single autonomous system (OSPF, RIP, EIGRP)
EGP (Exterior Gateway Protocol): operates between autonomous systems (BGP)
An autonomous system (AS) is a collection of IP networks under a single administrative domain (e.g., an ISP’s network). Each AS has a unique AS Number (ASN).
9. Common Misconceptions
- “Routing and forwarding are the same thing”: Routing (control plane) is the process of building and updating the routing table. Forwarding (data plane) is the fast lookup and packet transmission when a packet arrives. Routing happens slowly (protocol timers, convergence); forwarding happens at line speed in hardware.
- “Dijkstra works with negative weights”: Dijkstra’s algorithm assumes all edge weights are non-negative. With negative weights, it can produce incorrect results. Use Bellman-Ford for graphs with negative weights. In practice, network link costs are always positive (bandwidth, delay).
- “Longer AS path always means longer physical path”: BGP uses AS path length as a tiebreaker, but other policy attributes (local preference, MEDs) take priority. A shorter AS path in BGP does not necessarily mean fewer physical routers or lower latency — it just means fewer autonomous systems.
- “OSPF always finds the fastest path”: OSPF finds the shortest-cost path based on the configured metric. If administrators configure costs incorrectly (e.g., all links have cost 1 = hop count), OSPF behaves like RIP. Proper cost configuration (based on actual bandwidth) is required for OSPF to make intelligent routing decisions.
- “Count-to-infinity only happens in theory”: Count-to-infinity is a real problem in RIP networks without proper mitigation (split horizon, route poisoning). In large networks running RIP without these features, link failures can cause minutes of routing loops and outages.
10. Frequently Asked Questions
What is the difference between distance vector and link state routing?
Distance vector: each router shares only its routing table (distances) with direct neighbours; uses Bellman-Ford; has slow convergence and count-to-infinity problem; low memory/CPU usage. Example: RIP. Link state: each router floods a complete network map (LSAs) to all routers; each independently runs Dijkstra; fast convergence, no count-to-infinity, but high memory/CPU usage. Example: OSPF. Link state scales better and converges faster, making it the standard for modern enterprise networks.
How does Dijkstra’s algorithm work for routing?
Start with source distance = 0, all others = infinity. Repeatedly pick the unvisited node with the smallest known distance, then update distances to its unvisited neighbours if a shorter path exists through the current node. Mark visited nodes as done. Continue until all nodes are visited. The result is the shortest path from source to every other node. In OSPF, each router runs this on its complete topology database to build its forwarding table.
What is the count-to-infinity problem in distance vector routing?
When a link fails, routers using distance vector routing can enter a slow feedback loop where they keep advertising the failed route with increasing costs until it reaches “infinity” (max hop count). Solutions include split horizon (don’t advertise routes back toward their source), route poisoning (immediately advertise failed routes as infinite cost), and hold-down timers (ignore “better” routes for a period after a failure). These techniques are implemented in RIPv2 to limit — but not fully solve — the problem.
What is BGP and why is it called the protocol of the internet?
BGP (Border Gateway Protocol) routes traffic between autonomous systems (ASes) — the thousands of independent networks (ISPs, universities, companies) that form the internet. Unlike OSPF which optimises for shortest path within one organisation, BGP makes policy-based decisions between organisations. Every ISP uses BGP to advertise which IP address blocks they own and to learn how to reach the rest of the internet. Without BGP, the internet as a global interconnected network could not function.