692  Routing Labs: Algorithms

692.1 Learning Objectives

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

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

Lab Series: - Routing Labs: Overview - Lab series introduction and quiz - Routing Labs: Fundamentals - Basic routing table commands and traceroute - Routing Labs: Advanced - ESP32 packet forwarding and convergence simulation

Core Concepts: - Routing Fundamentals - Core routing theory and concepts - Routing Comprehensive Review - Advanced routing strategies

IoT Routing: - RPL Fundamentals - Low-power routing protocol - RPL Labs - Hands-on RPL implementation

692.2 Prerequisites

Before working through these algorithm implementations, ensure you understand:

692.3 Implementation 1: Routing Table Simulator with Longest Prefix Matching

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

692.3.1 Understanding Longest Prefix Match

%%{init: {'theme': 'base', 'themeVariables': { 'primaryColor': '#2C3E50', 'primaryTextColor': '#fff', 'primaryBorderColor': '#16A085', 'lineColor': '#16A085', 'secondaryColor': '#E67E22', 'tertiaryColor': '#7F8C8D'}}}%%
flowchart TD
    DEST["Destination: 172.16.50.100"]

    DEST --> CHECK1{"Match<br/>172.16.50.0/24?"}
    CHECK1 -->|"Yes: 24 bits"| WIN1["SELECTED<br/>(Longest: /24)"]

    DEST --> CHECK2{"Match<br/>172.16.0.0/16?"}
    CHECK2 -->|"Yes: 16 bits"| LOSE2["Not selected<br/>(Shorter: /16)"]

    DEST --> CHECK3{"Match<br/>0.0.0.0/0?"}
    CHECK3 -->|"Yes: 0 bits"| LOSE3["Not selected<br/>(Default: /0)"]

    style DEST fill:#E67E22,stroke:#2C3E50,color:#fff
    style WIN1 fill:#16A085,stroke:#2C3E50,color:#fff
    style LOSE2 fill:#7F8C8D,stroke:#2C3E50,color:#fff
    style LOSE3 fill:#7F8C8D,stroke:#2C3E50,color:#fff

Figure 692.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.

692.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()

692.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

692.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

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

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

692.5.1 Understanding Distance Vector

%%{init: {'theme': 'base', 'themeVariables': { 'primaryColor': '#2C3E50', 'primaryTextColor': '#fff', 'primaryBorderColor': '#16A085', 'lineColor': '#16A085', 'secondaryColor': '#E67E22', 'tertiaryColor': '#7F8C8D'}}}%%
sequenceDiagram
    participant R1 as Router R1
    participant R2 as Router R2
    participant R3 as Router R3

    Note over R1,R3: Round 1: Exchange tables

    R1->>R2: Table: {R1:0, R3:5}
    R2->>R1: Table: {R2:0, R4:2}
    R2->>R3: Table: {R2:0, R4:2}
    R3->>R2: Table: {R3:0, R1:5}

    Note over R1,R3: Round 2: Update with new info

    R1->>R2: Table: {R1:0, R3:5, R4:3}
    R2->>R3: Table: {R2:0, R1:1, R4:2}

    Note over R1,R3: Converged!

Figure 692.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.

692.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()

692.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 ...]

692.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)

692.6 Algorithm Comparison

%%{init: {'theme': 'base', 'themeVariables': { 'primaryColor': '#2C3E50', 'primaryTextColor': '#fff', 'primaryBorderColor': '#16A085', 'lineColor': '#16A085', 'secondaryColor': '#E67E22', 'tertiaryColor': '#7F8C8D'}}}%%
graph TD
    subgraph LS["Link-State (Dijkstra)"]
        LS1["Complete topology<br/>knowledge"]
        LS2["Faster convergence"]
        LS3["Higher memory<br/>usage"]
        LS4["OSPF, IS-IS"]
    end

    subgraph DV["Distance Vector (Bellman-Ford)"]
        DV1["Only neighbor<br/>knowledge"]
        DV2["Slower convergence"]
        DV3["Lower memory<br/>usage"]
        DV4["RIP, EIGRP"]
    end

    style LS1 fill:#16A085,stroke:#16A085,color:#fff
    style LS2 fill:#16A085,stroke:#16A085,color:#fff
    style LS3 fill:#E67E22,stroke:#E67E22,color:#fff
    style LS4 fill:#2C3E50,stroke:#2C3E50,color:#fff
    style DV1 fill:#E67E22,stroke:#E67E22,color:#fff
    style DV2 fill:#E67E22,stroke:#E67E22,color:#fff
    style DV3 fill:#16A085,stroke:#16A085,color:#fff
    style DV4 fill:#2C3E50,stroke:#2C3E50,color:#fff

Figure 692.4
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

692.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

692.8 What’s Next

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

For practical application, continue to: