14  Routing Labs: Algorithms

In 60 Seconds

Lab implementing core routing algorithms in Python: longest prefix matching for route selection, Dijkstra’s algorithm for link-state shortest paths (OSPF), and Bellman-Ford with split horizon for distance-vector convergence (RIP). Includes comparing OSPF vs RIP based on their algorithmic foundations.

14.1 Learning Objectives

By the end of this chapter, you will be able to:

  • Construct a longest prefix matching implementation to select the most specific route for a destination
  • Execute Dijkstra’s algorithm to compute shortest paths in link-state routing protocols
  • Simulate distance vector convergence using Bellman-Ford algorithm with split horizon
  • Evaluate routing protocols (OSPF vs RIP) based on their algorithmic foundations
  • Diagnose route selection issues by tracing administrative distance and metric calculations

Routing algorithms are the mathematical recipes that networks use to find the best path for data. In these labs, you will experiment with different algorithms and see how they make decisions – like comparing different GPS apps that might choose different routes based on distance, traffic, or toll costs.

“In this lab, we implement routing algorithms in Python,” said Max the Microcontroller. “You will code longest prefix matching, Dijkstra’s algorithm for OSPF, and Bellman-Ford for distance-vector protocols like RIP.”

“Dijkstra’s algorithm finds the shortest path through a graph,” explained Sammy the Sensor. “It is like solving a maze – you explore all nearby intersections first, marking the shortest distance from the start, then gradually expand outward until you reach the destination.”

“Bellman-Ford is different – it is what RIP uses,” added Lila the LED. “Each router shares its distance table with neighbors, and over multiple rounds, everyone gradually learns the best routes. Split horizon prevents telling a neighbor about routes you learned from them – that would create loops!”

“Comparing the two algorithms shows exactly why OSPF converges faster than RIP,” said Bella the Battery. “Dijkstra runs once on the complete topology and gets the answer immediately. Bellman-Ford needs many iterations to converge, and each round only updates routes one hop further. It is the fundamental trade-off between speed and simplicity.”

Lab Series:

Core Concepts:

IoT Routing:

14.2 Prerequisites

Before working through these algorithm implementations, ensure you understand:

14.3 Implementation 1: Routing Table Simulator with Longest Prefix Matching

This implementation demonstrates how routers select the most specific route using longest prefix matching.

14.3.1 Understanding Longest Prefix Match

Longest prefix matching diagram showing destination IP 172.16.50.100 being matched against three routes: 172.16.50.0/24 matches 24 bits (selected as longest match), 172.16.0.0/16 matches 16 bits (not selected), and 0.0.0.0/0 matches 0 bits (default, not selected). The /24 route wins because it has the longest matching prefix.
Figure 14.1: Longest Prefix Match: When multiple routes match a destination, the route with the longest matching prefix (most specific) is selected. For 172.16.50.100, the /24 route beats /16 and default /0 routes.

14.3.2 Python Implementation

"""
Routing Table Simulator with Longest Prefix Matching
Demonstrates how routers select routes based on prefix length
"""

import ipaddress
from dataclasses import dataclass
from typing import Optional, List, Tuple


@dataclass
class Route:
    """Represents a routing table entry"""
    destination: str      # Network in CIDR notation
    next_hop: str         # Next hop IP or 'Connected'
    interface: str        # Outgoing interface
    metric: int           # Route cost
    route_type: str       # 'C'=Connected, 'S'=Static, 'D'=Dynamic, 'G'=Default
    admin_distance: int   # Administrative distance

    def __post_init__(self):
        # Parse network for matching
        self.network = ipaddress.ip_network(self.destination, strict=False)

    def matches(self, ip: str) -> bool:
        """Check if IP matches this route"""
        try:
            addr = ipaddress.ip_address(ip)
            return addr in self.network
        except ValueError:
            return False

    @property
    def prefix_length(self) -> int:
        """Get prefix length for longest match comparison"""
        return self.network.prefixlen


class RoutingTable:
    """Simulates a router's routing table with longest prefix matching"""

    def __init__(self):
        self.routes: List[Route] = []

    def add_route(self, route: Route):
        """Add a route to the table"""
        self.routes.append(route)
        # Sort by prefix length (descending) for efficient lookup
        self.routes.sort(key=lambda r: r.prefix_length, reverse=True)

    def lookup(self, destination: str) -> Tuple[Optional[Route], List[str]]:
        """
        Find best route for destination using longest prefix matching
        Returns (best_route, list_of_all_matches)
        """
        matches = []
        best_route = None

        for route in self.routes:
            if route.matches(destination):
                matches.append(route.destination)
                if best_route is None:  # First match is longest (sorted)
                    best_route = route

        return best_route, matches[1:] if matches else []

    def display(self):
        """Print routing table in standard format"""
        print("=" * 72)
        print("ROUTING TABLE")
        print("=" * 72)
        print(f"{'Destination':<20} {'Next Hop':<16} {'Interface':<10} "
              f"{'Metric':<8} {'Type':<5} {'AD'}")
        print("-" * 72)

        for route in sorted(self.routes, key=lambda r: r.prefix_length):
            print(f"{route.destination:<20} {route.next_hop:<16} "
                  f"{route.interface:<10} {route.metric:<8} "
                  f"{route.route_type:<5} {route.admin_distance}")


def demonstrate_routing():
    """Demonstrate routing table lookup with various scenarios"""

    # Create routing table
    table = RoutingTable()

    # Add routes (order doesn't matter - sorted by prefix length)
    table.add_route(Route(
        destination="192.168.1.0/24",
        next_hop="Connected",
        interface="eth0",
        metric=0,
        route_type="C",
        admin_distance=0
    ))

    table.add_route(Route(
        destination="10.0.0.0/8",
        next_hop="Connected",
        interface="eth1",
        metric=0,
        route_type="C",
        admin_distance=0
    ))

    table.add_route(Route(
        destination="172.16.0.0/16",
        next_hop="10.0.0.2",
        interface="eth1",
        metric=10,
        route_type="S",
        admin_distance=1
    ))

    table.add_route(Route(
        destination="172.16.50.0/24",
        next_hop="10.0.0.5",
        interface="eth1",
        metric=5,
        route_type="S",
        admin_distance=1
    ))

    table.add_route(Route(
        destination="192.168.100.0/24",
        next_hop="10.0.0.8",
        interface="eth1",
        metric=20,
        route_type="D",
        admin_distance=110  # OSPF
    ))

    table.add_route(Route(
        destination="0.0.0.0/0",
        next_hop="192.168.1.1",
        interface="eth0",
        metric=1,
        route_type="G",
        admin_distance=1
    ))

    # Display routing table
    table.display()

    # Test lookups
    print("\n" + "=" * 72)
    print("ROUTE LOOKUPS (Longest Prefix Matching)")
    print("=" * 72)

    test_destinations = [
        "192.168.1.50",      # Local network
        "172.16.50.100",     # More specific /24 route
        "172.16.30.100",     # Less specific /16 route
        "8.8.8.8",           # Default route
        "192.168.100.50",    # Dynamic route
    ]

    for dest in test_destinations:
        route, other_matches = table.lookup(dest)

        print(f"\n{dest}:")
        if route:
            print(f"  Matched route: {route.destination}")

            if route.next_hop == "Connected":
                print(f"  Next hop: Direct delivery")
            else:
                print(f"  Next hop: {route.next_hop}")

            print(f"  Interface: {route.interface}")

            type_names = {
                'C': 'CONNECTED',
                'S': 'STATIC',
                'D': 'DYNAMIC',
                'G': 'DEFAULT'
            }
            print(f"  Type: {type_names.get(route.route_type, route.route_type)}")

            if other_matches:
                print(f"  Other matches: {other_matches}")
        else:
            print("  No route found!")


if __name__ == "__main__":
    demonstrate_routing()

14.3.3 Expected Output

========================================================================
ROUTING TABLE
========================================================================
Destination          Next Hop         Interface  Metric  Type  AD
------------------------------------------------------------------------
172.16.50.0/24       10.0.0.5         eth1       5       S     1
192.168.1.0/24       Connected        eth0       0       C     0
192.168.100.0/24     10.0.0.8         eth1       20      D     110
172.16.0.0/16        10.0.0.2         eth1       10      S     1
10.0.0.0/8           Connected        eth1       0       C     0
0.0.0.0/0            192.168.1.1      eth0       1       G     1

========================================================================
ROUTE LOOKUPS (Longest Prefix Matching)
========================================================================

192.168.1.50:
  Matched route: 192.168.1.0/24
  Next hop: Direct delivery
  Interface: eth0
  Type: CONNECTED

172.16.50.100:
  Matched route: 172.16.50.0/24
  Next hop: 10.0.0.5
  Interface: eth1
  Type: STATIC
  Other matches: ['172.16.0.0/16', '0.0.0.0/0']

172.16.30.100:
  Matched route: 172.16.0.0/16
  Next hop: 10.0.0.2
  Interface: eth1
  Type: STATIC
  Other matches: ['0.0.0.0/0']

8.8.8.8:
  Matched route: 0.0.0.0/0
  Next hop: 192.168.1.1
  Interface: eth0
  Type: DEFAULT

192.168.100.50:
  Matched route: 192.168.100.0/24
  Next hop: 10.0.0.8
  Interface: eth1
  Type: DYNAMIC

14.3.4 Key Concepts Demonstrated

  • Longest Prefix Matching: 172.16.50.100 matches both /24 and /16 routes, but /24 is selected
  • Administrative Distance: When multiple protocols learn same route, lower AD wins
  • Default Route: Matches all destinations when no specific route exists
  • Connected Routes: Direct delivery on local network
Try It: Longest Prefix Match Explorer

Explore how routers select the most specific route. Adjust the destination IP octet and prefix lengths to see which route wins.

14.5 Implementation 3: Distance Vector Routing Protocol (RIP Simulation)

This implementation demonstrates the Bellman-Ford algorithm used by RIP and similar protocols.

14.5.1 Understanding Distance Vector

Distance vector routing table exchange diagram showing Router R1 sending its routing table to neighbor R2. R2 receives the table, adds cost to R1, and updates its own routes if the new path is shorter. This exchange happens periodically (every 30 seconds in RIP) until network converges.
Figure 14.3: Distance Vector Exchange: Routers periodically share their routing tables with neighbors. Each router adds the cost to reach the neighbor and updates routes if a shorter path is found.

14.5.2 Python Implementation

"""
Distance Vector Routing Protocol Simulation
Demonstrates Bellman-Ford algorithm with split horizon
"""

from collections import defaultdict
from typing import Dict, List, Tuple, Optional
import copy


class DistanceVectorRouter:
    """Simulates a router running distance vector protocol"""

    INFINITY = 16  # RIP uses 16 as infinity

    def __init__(self, name: str):
        self.name = name
        self.neighbors: Dict[str, int] = {}  # neighbor -> cost
        self.routing_table: Dict[str, Tuple[int, str]] = {}  # dest -> (cost, next_hop)

        # Initialize route to self
        self.routing_table[name] = (0, name)

    def add_neighbor(self, neighbor: str, cost: int):
        """Add a directly connected neighbor"""
        self.neighbors[neighbor] = cost
        self.routing_table[neighbor] = (cost, neighbor)

    def remove_neighbor(self, neighbor: str):
        """Remove a neighbor (link failure)"""
        if neighbor in self.neighbors:
            del self.neighbors[neighbor]

        # Invalidate routes through this neighbor
        for dest, (cost, next_hop) in list(self.routing_table.items()):
            if next_hop == neighbor and dest != self.name:
                del self.routing_table[dest]

    def get_update_for(self, neighbor: str) -> Dict[str, int]:
        """
        Get routing update to send to a specific neighbor
        Implements split horizon: don't advertise routes back
        """
        update = {}
        for dest, (cost, next_hop) in self.routing_table.items():
            # Split horizon: don't advertise route via the neighbor it was learned from
            if next_hop != neighbor:
                update[dest] = cost
            else:
                # Poison reverse: advertise with infinity to prevent loops
                update[dest] = self.INFINITY

        return update

    def process_update(self, from_neighbor: str,
                       update: Dict[str, int]) -> bool:
        """
        Process routing update from a neighbor
        Returns True if routing table changed
        """
        changed = False
        cost_to_neighbor = self.neighbors.get(from_neighbor)

        if cost_to_neighbor is None:
            return False  # Not a neighbor

        for dest, dest_cost in update.items():
            if dest == self.name:
                continue  # Skip routes to self

            new_cost = cost_to_neighbor + dest_cost

            # Cap at infinity
            if new_cost >= self.INFINITY:
                new_cost = self.INFINITY

            current = self.routing_table.get(dest)

            # Update if: new destination OR better cost OR same next_hop with new cost
            if current is None:
                if new_cost < self.INFINITY:
                    self.routing_table[dest] = (new_cost, from_neighbor)
                    changed = True
            elif new_cost < current[0]:
                self.routing_table[dest] = (new_cost, from_neighbor)
                changed = True
            elif current[1] == from_neighbor and new_cost != current[0]:
                # Same next hop, update cost (even if worse)
                if new_cost >= self.INFINITY:
                    del self.routing_table[dest]
                else:
                    self.routing_table[dest] = (new_cost, from_neighbor)
                changed = True

        return changed

    def display_table(self):
        """Print routing table"""
        print(f"\nRouting Table for {self.name}:")
        print("=" * 60)
        print(f"{'Destination':<15} {'Cost':<8} {'Next Hop':<15} {'Status'}")
        print("-" * 60)

        for dest in sorted(self.routing_table.keys()):
            cost, next_hop = self.routing_table[dest]
            status = "Valid" if cost < self.INFINITY else "Invalid"
            cost_str = str(cost) if cost < self.INFINITY else "inf"
            print(f"{dest:<15} {cost_str:<8} {next_hop:<15} {status}")


class DistanceVectorNetwork:
    """Simulates a network of distance vector routers"""

    def __init__(self):
        self.routers: Dict[str, DistanceVectorRouter] = {}

    def add_router(self, name: str):
        """Add a router to the network"""
        self.routers[name] = DistanceVectorRouter(name)

    def add_link(self, router1: str, router2: str, cost: int):
        """Add a bidirectional link"""
        self.routers[router1].add_neighbor(router2, cost)
        self.routers[router2].add_neighbor(router1, cost)

    def remove_link(self, router1: str, router2: str):
        """Remove a link (simulate failure)"""
        self.routers[router1].remove_neighbor(router2)
        self.routers[router2].remove_neighbor(router1)

    def run_convergence(self, max_rounds: int = 20) -> int:
        """
        Run distance vector convergence
        Returns number of rounds to converge
        """
        for round_num in range(max_rounds):
            print(f"\n{'=' * 60}")
            print(f"Round {round_num}")
            print(f"{'=' * 60}")

            any_change = False

            # Collect all updates
            updates: Dict[str, Dict[str, Dict[str, int]]] = {}
            for name, router in self.routers.items():
                updates[name] = {}
                for neighbor in router.neighbors:
                    updates[name][neighbor] = router.get_update_for(neighbor)

            # Apply updates
            for name, router in self.routers.items():
                for neighbor in router.neighbors:
                    neighbor_update = updates[neighbor].get(name, {})
                    if router.process_update(neighbor, neighbor_update):
                        any_change = True

            # Display current state
            for router in self.routers.values():
                router.display_table()

            if not any_change and round_num > 0:
                print(f"\nConverged in {round_num} rounds")
                return round_num

        print(f"\nDid not converge in {max_rounds} rounds")
        return max_rounds


def demonstrate_distance_vector():
    """Demonstrate distance vector protocol with convergence and failure"""

    # Create network
    network = DistanceVectorNetwork()

    # Add routers
    for name in ['R1', 'R2', 'R3', 'R4']:
        network.add_router(name)

    # Add links
    #
    #     R1 ---- 1 ---- R2
    #     |              |
    #     2              1
    #     |              |
    #     R3 ---- 3 ---- R4
    #

    network.add_link('R1', 'R2', 1)
    network.add_link('R1', 'R3', 2)
    network.add_link('R2', 'R4', 1)
    network.add_link('R3', 'R4', 3)

    print("=" * 60)
    print("Initial Network Topology")
    print("=" * 60)
    print("""
    R1 ---- 1 ---- R2
    |              |
    2              1
    |              |
    R3 ---- 3 ---- R4
    """)

    print("\n" + "=" * 60)
    print("Running Distance Vector Protocol (convergence)")
    print("=" * 60)

    rounds = network.run_convergence()

    # Simulate link failure
    print("\n" + "=" * 60)
    print("Link Failure: R1-R2 link goes down")
    print("=" * 60)

    network.remove_link('R1', 'R2')

    print("\nImmediate effect (before reconvergence):")
    for router in network.routers.values():
        router.display_table()

    print("\n" + "=" * 60)
    print("Reconverging after link failure")
    print("=" * 60)

    network.run_convergence()


if __name__ == "__main__":
    demonstrate_distance_vector()

14.5.3 Expected Output

============================================================
Initial Network Topology
============================================================

    R1 ---- 1 ---- R2
    |              |
    2              1
    |              |
    R3 ---- 3 ---- R4


============================================================
Running Distance Vector Protocol (convergence)
============================================================

============================================================
Round 0
============================================================

Routing Table for R1:
============================================================
Destination     Cost   Next Hop        Status
------------------------------------------------------------
R1              0      R1              Valid
R2              1      R2              Valid
R3              2      R3              Valid

[... continues through convergence ...]

Converged in 3 rounds

============================================================
Link Failure: R1-R2 link goes down
============================================================

Immediate effect (before reconvergence):

Routing Table for R1:
============================================================
Destination     Cost   Next Hop        Status
------------------------------------------------------------
R1              0      R1              Valid
R3              2      R3              Valid

[... reconvergence ...]

14.5.4 Key Concepts

  • Bellman-Ford Algorithm: Distance vector routing uses distributed Bellman-Ford
  • Split Horizon: Don’t advertise routes back to the router you learned them from
  • Poison Reverse: Advertise unreachable routes with infinite cost
  • Convergence: Network takes multiple rounds to learn all routes
  • Count-to-Infinity Problem: Solved by maximum hop count (16 for RIP)
Try It: Distance Vector Convergence Simulator

See how a 3-router chain converges using the Bellman-Ford algorithm. Adjust link costs and observe how many rounds are needed for all routers to learn complete routes.

14.6 Algorithm Comparison

Comparison table of link-state (Dijkstra) vs distance vector (Bellman-Ford) routing algorithms. Link-state: global topology knowledge, faster convergence, more memory, OSPF/IS-IS. Distance vector: local neighbor knowledge, slower convergence, less memory, RIP/EIGRP.
Figure 14.4: Algorithm Comparison: Link-state protocols (Dijkstra) use complete topology knowledge and converge fast at the cost of more memory, while distance vector protocols (Bellman-Ford) use only neighbor information and converge more slowly but are memory-efficient.
Aspect Link-State (OSPF) Distance Vector (RIP)
Knowledge Complete topology Neighbor routes only
Algorithm Dijkstra’s Bellman-Ford
Convergence Fast (seconds) Slow (minutes)
Memory High (store topology) Low (store routes)
Bandwidth High (flood LSAs) Low (periodic updates)
Scalability Excellent Limited (15 hop max)
Loop Prevention SPF calculation Split horizon, poison reverse
Use Case Enterprise, ISP Small networks, IoT
Try It: Algorithm Complexity Calculator

Compare the computational complexity of Dijkstra (OSPF) vs Bellman-Ford (RIP) as network size changes. See how the performance gap widens with scale.

How does algorithmic complexity affect routing protocol scalability? Compare Dijkstra (OSPF) vs Bellman-Ford (RIP) for a growing network.

Small network (10 routers, 20 links):

  • Dijkstra (OSPF): \(O((V + E) \log V) = (10 + 20) \times \log_2(10) = 30 \times 3.32 = 100\text{ operations}\)
  • Bellman-Ford (RIP): \(O(V \times E) = 10 \times 20 = 200\text{ operations}\)
  • Dijkstra is 2× faster but difference negligible (< 1 ms on modern CPU)

Large network (1,000 routers, 5,000 links):

  • Dijkstra: \((1{,}000 + 5{,}000) \times \log_2(1{,}000) = 6{,}000 \times 9.97 = 59{,}820\text{ operations}\)
  • Bellman-Ford: \(1{,}000 \times 5{,}000 = 5{,}000{,}000\text{ operations}\)
  • Dijkstra is 83× faster (60K vs 5M operations)

Convergence time (1 GHz CPU, 10 cycles/operation): - Dijkstra: \(59{,}820 \times 10 / 10^9 = 0.598\text{ ms}\) - Bellman-Ford: \(5{,}000{,}000 \times 10 / 10^9 = 50\text{ ms}\)

Real-world impact: In a campus network with 1,000 routers, OSPF reconverges in < 1 ms after link failure (users don’t notice). RIP takes 50 ms per iteration × 15 hops max = 750 ms (noticeable lag during VoIP calls). This is why OSPF dominates large networks despite higher protocol complexity!

Common Pitfalls

Dijkstra’s algorithm assumes non-negative edge weights. Routing metrics that can decrease (like rapidly improving link quality) can produce incorrect results with naive Dijkstra. Use Bellman-Ford for metrics that can decrease.

A routing algorithm that works for a chain topology may fail for a grid or mesh topology. Test algorithms with at least: chain, star, mesh, and ring topologies with various failure conditions.

O(n²) complexity of Dijkstra means computation scales poorly for large networks, but ‘large’ means thousands of nodes in IP networks. IoT networks with 50–200 nodes rarely hit algorithmic scalability limits — other bottlenecks appear first.

14.7 Summary

  • Longest prefix matching ensures routers select the most specific route for a destination, with /24 routes taking precedence over /16 and default /0 routes
  • Dijkstra’s algorithm (link-state) computes optimal paths using complete topology knowledge, enabling fast convergence
  • Bellman-Ford algorithm (distance vector) uses only neighbor information, trading faster setup for slower convergence
  • Split horizon and poison reverse prevent routing loops in distance vector protocols
  • Administrative distance determines which routing source to trust when multiple protocols provide routes to the same destination
  • Link failure recovery demonstrates how both algorithms recompute paths when network topology changes

14.8 Knowledge Check

Scenario: A 5-node IoT test network experiences intermittent connectivity issues. Occasionally, packets get “stuck” in the network, circulating between routers until TTL expires. You need to identify whether the routing algorithm implementation has a flaw.

Network Topology:

R1 ---- R2 ---- R3
 |       |       |
 +------ R4 -----+

Distance Vector Routing Tables (After Convergence - Should Be Stable):

R1: dest R3 -> next R2, cost 2
R2: dest R3 -> next R3, cost 1
R3: dest R1 -> next R2, cost 2
R4: dest R3 -> next R2, cost 2

Problem Report: Packets from R1 to R3 sometimes loop R1→R2→R4→R1 repeatedly

Step 1: Trace Routing Updates

Enable debug logging on R1, R2, R4 to capture routing table exchanges:

# R2 sends update to R4
R2 → R4: {'R1': 1, 'R3': 1, 'R4': 0}  # R2's distances to all nodes

# R4 processes update (Bellman-Ford)
R4 calculates: Distance to R3 via R2 = 1 (R2_to_R3) + 1 (R4_to_R2) = 2 ✓
R4 updates: dest R3 -> next R2, cost 2

# BUT THEN: R1-R2 link temporarily fails!

Step 2: Analyze Failure Behavior (The Bug Appears)

When R1-R2 link fails:

R1 routing table:
  dest R3 -> next R2, cost 2  (STALE! R2 unreachable now)

R1 doesn't immediately remove stale route because:
- No "poison reverse" implemented (split horizon only)
- No triggered updates on link down
- Relies on periodic updates (30s timer)

Meanwhile, R4 sends periodic update to R1:
R4 → R1: {'R3': 2, ...}  # R4 can reach R3 in 2 hops

R1 processes:
  Distance to R3 via R4 = 2 (R4_to_R3) + 1 (R1_to_R4) = 3
  Current route: R3 via R2 cost 2 (but R2 down!)
  R1 KEEPS stale route (cost 2 < 3) -- BUG!

Step 3: The Routing Loop

Packet from R1 to R3:

1. R1 forwards to R2 (stale route)
2. R1-R2 link down, packet goes nowhere...

   Wait, implementation has fallback:
   "If primary next-hop unreachable, try any neighbor"

3. R1 sends to R4 (fallback)
4. R4 forwards to R2 (its route)
5. R2 forwards back to R1 (thinks R1 closer)
6. R1→R4→R2→R1→R4→R2... (LOOP!)

Step 4: Algorithmic Root Cause

The distance vector implementation has two flaws:

Flaw 1: No Triggered Updates

# WRONG (current code):
def remove_neighbor(self, neighbor: str):
    if neighbor in self.neighbors:
        del self.neighbors[neighbor]
    # Missing: immediately invalidate routes via this neighbor!

# CORRECT:
def remove_neighbor(self, neighbor: str):
    if neighbor in self.neighbors:
        del self.neighbors[neighbor]

    # Invalidate routes using this neighbor
    for dest, (cost, next_hop) in list(self.routing_table.items()):
        if next_hop == neighbor:
            self.routing_table[dest] = (self.INFINITY, neighbor)
            self.send_triggered_update()  # Immediately notify neighbors

Flaw 2: Fallback Routing Without Loop Detection

# WRONG (current code):
def forward_packet(self, dest):
    next_hop = self.routing_table.get(dest)[1]
    if not self.can_reach(next_hop):
        # Fallback to any neighbor -- DANGER!
        next_hop = random.choice(list(self.neighbors.keys()))

# CORRECT:
def forward_packet(self, dest):
    next_hop = self.routing_table.get(dest)[1]
    if not self.can_reach(next_hop):
        # Drop packet -- no valid route
        return "DROP"
    # Never "guess" with fallback routing

Step 5: Verification After Fix

Apply fixes and re-run convergence simulation:

# R1-R2 link fails
print("Link failure: R1-R2")
network.remove_link('R1', 'R2')

# With triggered updates:
R1 immediately invalidates: dest R3 -> next R2, cost INFINITY
R1 broadcasts: {'R3': INFINITY} to neighbors R4

R4 receives poison route from R1
R4 updates: dest R3 -> next R3, cost 2 (via R4-R3 direct link)
R4 sends triggered update to R1

R1 receives: {'R3': 2} from R4
R1 calculates: Distance to R3 via R4 = 2 + 1 = 3
R1 installs: dest R3 -> next R4, cost 3

Convergence time: 2 routing update cycles (~2 seconds)
Routing loop: ELIMINATED ✓

Packet Trace After Fix:

Packet from R1 to R3:
1. R1 → R4 (cost 3 route)
2. R4 → R3 (direct link)
3. Delivered successfully

No loop, no dropped packets!

Key Lessons:

  1. Triggered updates are not optional – prevent stale route retention
  2. Poison reverse broadcasts INFINITY for failed routes immediately
  3. Never implement “fallback routing” – drop packets if no valid route exists
  4. Algorithm correctness matters more than optimization – loops break entire network
  5. Test failure scenarios explicitly – most routing bugs appear during link failures

Testing Checklist for Routing Algorithm Implementations:

This lab builds upon:

This lab connects to:

Applications using these algorithms:

  • OSPF uses Dijkstra for enterprise networks
  • RIP uses Bellman-Ford for small networks
  • RPL adapts distance vector for constrained IoT devices
  • BGP uses modified Bellman-Ford for internet routing

Routing Protocol Implementations:

Algorithm Resources:

Related Topics:

14.9 What’s Next

Previous Up Next
Routing Labs: Advanced Routing Labs and Quiz RPL Core Concepts

Return to Routing Labs: Overview for quiz questions testing your understanding of routing concepts.

For practical application, continue to: