Network Routing Fundamentals and Algorithms

What is Network Routing?

Routing is the process of selecting the best path for data packets to travel from a source to a destination across networks. It ensures efficient and reliable delivery of packets in packet-switched networks like the Internet.

The Role of a Router

A router is a Layer 3 device that forwards packets between networks by examining destination IP addresses and selecting the optimal path. It uses routing tables to decide where to send data next.

Static vs. Dynamic Routing

Static routing is a manual method where routes are configured by an administrator and remain fixed. It provides full control but is not scalable. Dynamic routing is automatic, where routers use algorithms to update routes and adapt to network changes, making it suitable for large networks.

The Routing Process

Routing begins when data is divided into packets, each containing a destination IP address. Routers consult routing tables to determine the best path, and packets travel through multiple routers (hops) until they reach the destination, where they are reassembled.

Key Routing Metrics

Routing decisions are based on metrics such as:

• Hop count
• Cost
• Delay
• Bandwidth

The best path is the one with the minimum metric value (the shortest or least-cost path).

Distance Vector Routing

Distance Vector Routing is a dynamic routing method where routers share their routing tables with neighbors periodically. It uses the Bellman-Ford algorithm to calculate the shortest path.

Formula:
The minimum cost path is calculated as:
D(x) = min [ cost(x → v) + D(v) ]

This means a router chooses the path with the minimum total cost through its neighbors.

Link State Routing

Link State Routing is a dynamic routing method where routers share link information only when changes occur. Each router builds a complete network map and uses Dijkstra’s algorithm to find the shortest path.

Formula (Dijkstra):
Shortest Path = minimum cumulative cost from source to destination

Shortest Path Calculation

Routing always tries to minimize total cost using the following logic:

Total Cost = Sum of all link costs along the path

The path with the lowest total cost is selected.

Hop Count and RIP Protocol

Hop count is the number of routers a packet passes through.

Formula:
Hop Count = Number of intermediate routers

This metric is primarily used in the RIP (Routing Information Protocol).

TTL (Time to Live) Mechanism

TTL limits the number of hops a packet can take. Each router decreases the TTL value by 1.

Formula:
TTL(new) = TTL(old) − 1

If TTL = 0, the packet is discarded to prevent infinite loops.

Dijkstra's Algorithm Logic

Dijkstra’s algorithm finds the shortest path by repeatedly selecting the node with the smallest tentative distance and updating its neighbors.

Pros and Cons of Routing

Advantages

• Improves network efficiency.
• Supports large-scale networks.
• Allows automatic path selection using advanced algorithms.

Disadvantages

• Static routing: Not scalable and difficult to manage.
• Dynamic routing: Consumes more bandwidth and system resources.