Routing algorithms determine the best path for data packets to travel from a source to a destination across networks. They are the foundation of efficient and reliable routing in networking.
Types of Routing Algorithms
Routing algorithms can be classified into the following categories:
1. Static vs Dynamic Routing Algorithms
| Type | Description | Example |
|---|---|---|
| Static Routing | Manually configured routes, do not change dynamically | Small networks, LANs |
| Dynamic Routing | Routes automatically adapt to network changes using routing protocols | RIP, OSPF, BGP |
2. Adaptive (Dynamic) vs Non-Adaptive (Static) Algorithms
| Type | Description | Example |
|---|---|---|
| Adaptive Routing | Routes change dynamically based on network conditions (traffic, failures) | RIP, OSPF, BGP |
| Non-Adaptive Routing | Routes are precomputed and do not change dynamically | Static Routing |
3. Types of Dynamic Routing Algorithms
| Algorithm Type | Description | Example Protocols |
|---|---|---|
| Distance Vector | Selects the shortest path based on hop count, each router shares updates with neighbors | RIP |
| Link-State | Each router builds a complete network map and calculates the best path using Dijkstra’s Algorithm | OSPF, IS-IS |
| Path-Vector | Used in inter-domain routing (BGP), maintains entire path information instead of individual link costs | BGP |
1. Distance Vector Routing Algorithm
How It Works:
- Each router maintains a routing table listing all reachable destinations and the number of hops (distance) to each.
- Routers share their routing tables with neighboring routers at regular intervals.
- The algorithm follows the Bellman-Ford Algorithm to update routes.
Characteristics:
✔ Simple to implement
✔ Works well for small networks
❌ Slow convergence (takes time to update routes)
❌ Prone to routing loops (solved using Split Horizon, Poison Reverse, Hold Down Timers)
Example Protocol: RIP (Routing Information Protocol)
- Uses hop count as a metric (max 15 hops).
- Updates every 30 seconds, causing slow convergence.
🔹 Example of Distance Vector Routing Table (RIP):
| Destination | Next Hop | Hop Count |
|---|---|---|
| 192.168.1.0/24 | 192.168.1.1 | 1 |
| 10.0.0.0/8 | 10.0.0.1 | 2 |
| 172.16.0.0/16 | 192.168.1.2 | 3 |
2. Link-State Routing Algorithm
How It Works:
- Each router gathers full network topology information.
- Uses Dijkstra’s Shortest Path Algorithm to compute the best path.
- Routers send Link-State Advertisements (LSAs) to inform neighbors of network changes.
Characteristics:
✔ Faster convergence than Distance Vector.
✔ More accurate routing decisions (uses entire network view).
❌ Consumes more memory and CPU (stores full topology map).
❌ More complex to configure and maintain.
Example Protocols: OSPF (Open Shortest Path First), IS-IS
- OSPF (Open Shortest Path First):
- Uses Cost (based on bandwidth) instead of hop count.
- Sends updates only when topology changes (efficient).
- Supports hierarchical routing (Areas).
🔹 Example of Link-State Routing Table (OSPF):
| Destination | Next Hop | Cost |
|---|---|---|
| 192.168.1.0/24 | 192.168.1.1 | 10 |
| 10.0.0.0/8 | 10.0.0.1 | 5 |
| 172.16.0.0/16 | 192.168.1.2 | 3 |
3. Path-Vector Routing Algorithm
How It Works:
- Maintains a path (sequence of routers) for each destination.
- Used for inter-domain routing (BGP – Border Gateway Protocol).
- Prevents routing loops by storing entire path history.
Characteristics:
✔ Scalable (used in the internet).
✔ Prevents loops by maintaining path information.
❌ High complexity and overhead.
❌ Slow convergence.
Example Protocol: BGP (Border Gateway Protocol)
- Used for internet routing between ISPs.
- Selects paths based on policy and AS (Autonomous System) numbers instead of shortest distance.
🔹 Example of Path-Vector Routing Table (BGP):
| Destination | AS Path | Next Hop |
|---|---|---|
| 192.168.1.0/24 | 65001 → 65002 → 65003 | 192.168.1.1 |
| 10.0.0.0/8 | 65001 → 65004 → 65005 | 10.0.0.1 |
| 172.16.0.0/16 | 65002 → 65006 | 192.168.1.2 |
Comparison of Routing Algorithms
| Feature | Distance Vector | Link-State | Path-Vector |
|---|---|---|---|
| Metric Used | Hop count | Bandwidth, Cost | AS Path |
| Network Size | Small to medium | Large | Very large (Internet) |
| Convergence Speed | Slow | Fast | Slow |
| Overhead | Low | High | High |
| Example Protocols | RIP | OSPF, IS-IS | BGP |
Routing Algorithm Techniques to Prevent Loops
| Technique | Description |
|---|---|
| Split Horizon | Prevents a router from sending route information back to the source router. |
| Poison Reverse | A router advertises a failed route with infinity to force removal. |
| Hold-Down Timer | Waits before accepting an alternative path after a failure. |
| Route Aggregation | Combines multiple small routes into a single summary route. |
Real-World Routing Example: Internet Routing with BGP
1️⃣ User in New York requests a website hosted in Tokyo.
2️⃣ Local router forwards the packet to the ISP router.
3️⃣ BGP selects the best route based on AS Paths and network policies.
4️⃣ The packet crosses multiple ISPs to reach Tokyo.
5️⃣ The response follows the optimal return path back to New York.
Conclusion
Routing algorithms play a vital role in ensuring efficient packet forwarding, network reliability, and scalability. Different algorithms are used depending on network size and complexity:
- Distance Vector (RIP) for small networks.
- Link-State (OSPF, IS-IS) for large enterprise networks.
- Path-Vector (BGP) for global internet routing.
