Routing Algorithms

Routing is the process of selecting the best path for data packets to travel from source to destination across a network.

A Routing Algorithm determines how a router builds its routing table and decides the optimal path based on specific metrics such as hop count, cost, bandwidth, or delay.

Routing algorithms are broadly classified into two categories:

Distance Vector Routing
Link State Routing

1. Routing Metrics

Before examining algorithms, it is important to understand the criteria used to determine the "best" path:

Metric	Description
Hop Count	Number of routers a packet passes through
Cost	Administrative weight assigned to a link
Bandwidth	Capacity of the link
Delay	Time taken for a packet to traverse a link
Reliability	Probability of successful transmission
Load	Current traffic on a link

2. Distance Vector Routing

Concept

In Distance Vector Routing, each router maintains a routing table (distance vector) that contains:

The destination network
The distance (cost/hop count) to that destination
The next hop router to reach it

Routers share their entire routing table with their directly connected neighbors at periodic intervals.

How It Works

Each router initializes its table with directly connected neighbors (distance = 1) and sets all other destinations to infinity.
Routers periodically broadcast their distance vectors to neighbors.
Upon receiving a neighbor's table, a router updates its own table using the Bellman-Ford equation.
This process repeats until all routing tables converge (no more changes occur).

Bellman-Ford Equation

D(x, y) = min{ c(x, v) + D(v, y) }
           for all neighbors v of x

Where:

D(x, y) = estimated cost from router x to destination y
c(x, v) = cost of direct link from x to neighbor v
D(v, y) = neighbor v's estimated cost to reach y

Example

Network topology:

A ---4--- B ---3--- C
|                   |
2                   1
|                   |
D --------5-------- E

Router A's initial table:

Destination	Cost	Next Hop
A	0	-
B	4	B
D	2	D
C	∞	-
E	∞	-

After exchanging with neighbors B and D, Router A learns better paths through them and updates accordingly.

Count-to-Infinity Problem

A critical issue in distance vector routing:

When a link fails, incorrect routing information can propagate through the network, causing routers to endlessly increment hop counts, believing the destination is reachable through each other.

Example:

A and B are connected. A reaches C through B (cost 2).
If the A-B link fails:
- B hears from A that A can reach C at cost 2 (via old info)
- B updates: cost to C = 3 (A's 2 + 1)
- A then updates: cost to C = 4 (B's 3 + 1)
- Counts keep incrementing until infinity threshold (typically 16 for RIP)

Solutions:

Split Horizon: Do not advertise a route back to the neighbor from which it was learned.
Poison Reverse: Advertise a failed route with an infinite metric back to the source.
Hold-down timers: Ignore updates about a failed route for a set duration.

Characteristics of Distance Vector

Feature	Description
Information shared	Full routing table with neighbors
Knowledge	Local (only knows neighbor info)
Convergence	Slow
Complexity	Low
Scalability	Poor for large networks
Examples	RIP, IGRP, EIGRP

3. Bellman-Ford Algorithm

Definition

The Bellman-Ford Algorithm is a shortest path algorithm used in distance vector routing. It can handle negative edge weights and can detect negative cycles.

Unlike Dijkstra's algorithm, Bellman-Ford works even when some link costs are negative (which can occur in certain routing metrics).

Algorithm Steps

Given: A graph with V vertices and E edges, and a source node S.

Initialize distance to source = 0, all others = ∞
Repeat (V - 1) times:
- For each edge (u, v) with weight w:
  - If dist[u] + w < dist[v], update dist[v] = dist[u] + w
Check for negative cycles:
- For each edge (u, v) with weight w:
  - If dist[u] + w < dist[v], a negative cycle exists

Worked Example

Network:

Nodes: A, B, C, D, E
Edges: A→B(6), A→D(7), B→C(5), B→D(8), B→E(-4),
       C→B(-2), D→E(9), D→C(-3), E→C(7), E→A(2)
Source: A

Initialization: dist = {A:0, B:∞, C:∞, D:∞, E:∞}

After (V-1) = 4 iterations, the algorithm relaxes all edges and finds shortest paths.

Time Complexity

Case	Complexity
Time	O(V × E)
Space	O(V)

Bellman-Ford vs Dijkstra

Feature	Bellman-Ford	Dijkstra
Negative weights	Handled	Not supported
Negative cycles	Detects them	Cannot detect
Time Complexity	O(V × E)	O(V^2) or O(E log V)
Approach	Dynamic programming	Greedy
Use in routing	Distance Vector	Link State (OSPF)

4. Link State Routing

Concept

In Link State Routing, each router has complete knowledge of the entire network topology.

Every router:

Discovers its direct neighbors and the cost of each link
Broadcasts this information (called a Link State Advertisement / LSA) to ALL routers in the network using flooding
Each router independently runs Dijkstra's algorithm on the complete topology map to compute shortest paths to all destinations
Builds its routing table from the computed shortest path tree

How It Works

Step 1 — Hello Protocol: Each router sends "Hello" packets to discover neighbors and measure link costs.

Step 2 — LSA Flooding: Each router creates an LSA containing:

Router ID
List of neighbors
Cost to each neighbor

This LSA is flooded to all routers in the network.

Step 3 — Build Link State Database (LSDB): Each router assembles a complete map of the network from received LSAs.

Step 4 — Run Dijkstra's Algorithm: Each router independently computes the shortest path tree from itself to all destinations.

Step 5 — Populate Routing Table: The shortest path tree is used to populate the router's forwarding table.

Characteristics of Link State

Feature	Description
Information shared	Only local link state (to all routers)
Knowledge	Global (complete network topology)
Convergence	Fast
Complexity	Higher (Dijkstra computation required)
Scalability	Better than distance vector
Bandwidth Usage	Higher during flooding
Examples	OSPF, IS-IS

5. Dijkstra's Algorithm

Definition

Dijkstra's Algorithm computes the shortest path from a single source node to all other nodes in a weighted graph with non-negative edge weights.

It is the core algorithm used in Link State Routing protocols (OSPF).

Algorithm Steps

Given: Graph G with vertices V and edges E, source node S.

Initialize: dist[S] = 0, dist[all others] = ∞
Create a set of unvisited nodes containing all vertices
Repeat until all nodes are visited:
- Select the unvisited node u with the smallest dist[u] (greedy choice)
- Mark u as visited
- For each unvisited neighbor v of u:
  - If dist[u] + weight(u,v) < dist[v]:
    - Update dist[v] = dist[u] + weight(u,v)
    - Set prev[v] = u (to reconstruct path)

Worked Example

Network:

        2       3
    A ------B------E
    |      /|      |
   6|    1/ |4    5|
    |   /   |      |
    C--      D-----
        3        1

Edges: A-B(2), A-C(6), B-C(1), B-D(4), B-E(3), D-E(1)

Source: A

Iteration	Visited	dist[B]	dist[C]	dist[D]	dist[E]
Initial	{}	∞	∞	∞	∞
1	{A}	2	6	∞	∞
2	{A,B}	2	3	6	5
3	{A,B,C}	2	3	6	5
4	{A,B,C,E}	2	3	6	5
5	All	2	3	6	5

Shortest paths from A:

A → B: cost 2
A → C: cost 3 (via B)
A → E: cost 5 (via B)
A → D: cost 6 (via B)

Time Complexity

Implementation	Time Complexity
Simple array	O(V^2)
Binary heap (priority queue)	O(E log V)
Fibonacci heap	O(E + V log V)

6. Distance Vector vs Link State Routing

Feature	Distance Vector	Link State
Algorithm	Bellman-Ford	Dijkstra
Topology knowledge	Partial (neighbor info only)	Complete (entire network)
Information shared	Full routing table to neighbors	LSAs flooded to all routers
Convergence speed	Slow	Fast
Bandwidth usage	Low (periodic updates)	High initially (flooding)
Memory usage	Low	High (stores full topology)
Computation	Simple	Complex (Dijkstra per router)
Scalability	Poor	Better
Loop risk	High (count-to-infinity)	Low (complete topology view)
Examples	RIP, IGRP	OSPF, IS-IS

Key Takeaways

Distance Vector routing uses Bellman-Ford; routers share tables only with neighbors.
Link State routing uses Dijkstra; routers flood LSAs and compute paths independently.
Bellman-Ford handles negative edge weights; Dijkstra requires non-negative weights.
Count-to-infinity is a major problem in distance vector routing; split horizon and poison reverse are common fixes.
Dijkstra guarantees the shortest path from a single source in O(E log V) with a priority queue.
Link state converges faster than distance vector but requires more memory and computation.

FilesExpand file tree

3. Routing Algorithms.md

Latest commit

History

3. Routing Algorithms.md

File metadata and controls

Routing Algorithms

1. Routing Metrics

2. Distance Vector Routing

Concept

How It Works

Bellman-Ford Equation

Example

Count-to-Infinity Problem

Characteristics of Distance Vector

3. Bellman-Ford Algorithm

Definition

Algorithm Steps

Worked Example

Time Complexity

Bellman-Ford vs Dijkstra

4. Link State Routing

Concept

How It Works

Characteristics of Link State

5. Dijkstra's Algorithm

Definition

Algorithm Steps

Worked Example

Time Complexity

6. Distance Vector vs Link State Routing

Key Takeaways