Network Layer and Routing Algorithms: Shortest Path, Distance Vector, and Link State
The Network Layer (Layer 3) is responsible for getting packets from the source host all the way to the destination host across multiple interconnected routers.
1. Routing vs. Forwarding (In Simple Words)
Think of traveling by train from Indore to Mumbai:
- Routing: Planning your entire journey before departure: “Should I go via Bhopal, or via Surat?” (Network-wide calculation of the best path).
- Forwarding: Moving from platform 1 to platform 3 at a junction station when the announcement is made (Local transfer of a packet from a router’s input interface to the appropriate output interface).
2. Types of Routing Algorithms
Classification of Routing Algorithms
📌 1. Static (Non-Adaptive) Routing
- Routes are manually typed into the router by an administrator.
- Does not adapt to network traffic changes or cable cuts.
- Simple, secure, but terrible for large networks.
🔄 2. Dynamic (Adaptive) Routing
- Routers automatically exchange routing tables with neighbors.
- If a link fails or gets congested, routers dynamically calculate a new alternate route!
- Examples: RIP, OSPF, BGP.
3. Dijkstra’s Shortest Path Algorithm
Developed by Edsger Dijkstra, this algorithm finds the shortest path from a single source router to all other routers in a graph:
- Label the starting source node as 0 and mark it as Permanent. Label all other nodes with distance ∞ and mark them as Tentative.
- Examine all tentative nodes directly adjacent to the newly made permanent node. Update their distances:
Formula: New Distance = \min(Current Distance, Distance of Permanent Node + Edge Weight)
- Pick the tentative node with the smallest distance and make it Permanent.
- Repeat steps 2 and 3 until all nodes become permanent.
4. Distance Vector vs. Link State Routing
This is one of the most famous 10-mark comparison questions in university exams:
| Feature | Distance Vector Routing (DVR - e.g., RIP) | Link State Routing (LSR - e.g., OSPF) |
|---|---|---|
| Algorithm Used | Bellman-Ford Algorithm | Dijkstra’s Algorithm |
| What is Shared? | Sends its entire routing table (distances to all destinations). | Sends information only about its directly connected neighbors (state of links). |
| Who is it Sent To? | Shared only with directly adjacent neighbors. | Flooded to ALL routers in the entire network. |
| When is it Sent? | Sent periodically on a timer (e.g., every 30 seconds). | Sent only when a link changes state (up or down). |
| Convergence Speed | Slow; prone to routing loops and the Count-to-Infinity problem. | Fast convergence with zero routing loops. |
| Bandwidth & CPU | Low CPU calculation; higher periodic bandwidth usage. | Higher CPU/RAM usage to build complete network topology tree. |
💡 DAVV Exam Tip
Question (10 Marks): “Explain routing algorithms. Compare Distance Vector Routing and Link State Routing with examples.”
- Define Routing vs Forwarding.
- Explain the Count-to-Infinity problem in Distance Vector Routing.
- Write the 6-point comparison table above and mention RIP for DVR and OSPF for LSR.