Distance Vector Routing

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190

from dataclasses import dataclass
from typing import Dict, List, Optional, Set
from enum import Enum
 
class SplitHorizonMode(Enum):
    DISABLED = "disabled"
    SIMPLE = "simple"                    # Omit routes learned from interface
    POISON_REVERSE = "poison_reverse"   # Advertise infinity for learned routes
 
@dataclass
class RouteEntry:
    destination: str
    metric: int
    next_hop: str
    learned_interface: str  # Critical for split horizon!
    
@dataclass
class Interface:
    name: str
    neighbor: str
    cost: int
 
class SplitHorizonRouter:
    """
    Router implementation demonstrating split horizon behavior.
    """
    
    INFINITY = 16
    
    def __init__(self, router_id: str, interfaces: List[Interface],
                 mode: SplitHorizonMode = SplitHorizonMode.SIMPLE):
        self.router_id = router_id
        self.interfaces = {iface.name: iface for iface in interfaces}
        self.mode = mode
        self.routing_table: Dict[str, RouteEntry] = {}
        
        # Add route to self
        self.routing_table[router_id] = RouteEntry(
            destination=router_id,
            metric=0,
            next_hop=router_id,
            learned_interface="local"
        )
    
    def build_update_for_interface(self, interface_name: str) -> Dict[str, int]:
        """
        Build routing update for a specific interface, applying split horizon.
        
        Args:
            interface_name: Name of the outgoing interface
            
        Returns:
            Dictionary of {destination: metric} to advertise
        """
        update = {}
        
        for dest, route in self.routing_table.items():
            if self.mode == SplitHorizonMode.DISABLED:
                # No split horizon: include all routes
                update[dest] = route.metric
                
            elif self.mode == SplitHorizonMode.SIMPLE:
                # Simple split horizon: omit routes learned from this interface
                if route.learned_interface != interface_name:
                    update[dest] = route.metric
                # Routes learned from this interface are simply not included
                    
            elif self.mode == SplitHorizonMode.POISON_REVERSE:
                # Split horizon with poison reverse
                if route.learned_interface == interface_name:
                    # Advertise infinity for routes learned from this interface
                    update[dest] = self.INFINITY
                else:
                    update[dest] = route.metric
        
        return update
    
    def receive_update(self, source_interface: str, source_neighbor: str,
                       distance_vector: Dict[str, int]) -> List[str]:
        """
        Process received routing update.
        
        Args:
            source_interface: Interface update was received on
            source_neighbor: Neighbor that sent the update
            distance_vector: Received {destination: metric} pairs
            
        Returns:
            List of destinations that changed (for triggered updates)
        """
        changed = []
        link_cost = self.interfaces[source_interface].cost
        
        for dest, received_metric in distance_vector.items():
            new_metric = min(received_metric + link_cost, self.INFINITY)
            
            if dest not in self.routing_table:
                if new_metric < self.INFINITY:
                    self.routing_table[dest] = RouteEntry(
                        destination=dest,
                        metric=new_metric,
                        next_hop=source_neighbor,
                        learned_interface=source_interface
                    )
                    changed.append(dest)
                    
            else:
                existing = self.routing_table[dest]
                
                # Update if: better metric, or same next-hop with changed metric
                should_update = False
                
                if new_metric < existing.metric:
                    should_update = True
                elif existing.next_hop == source_neighbor:
                    # Must accept update from current next-hop
                    should_update = (new_metric != existing.metric)
                
                if should_update:
                    old_metric = existing.metric
                    existing.metric = new_metric
                    existing.next_hop = source_neighbor
                    existing.learned_interface = source_interface
                    changed.append(dest)
                    print(f"  [{self.router_id}] {dest}: {old_metric} -> {new_metric}")
        
        return changed
    
    def print_routing_table(self):
        """Display current routing table."""
        print(f"\n=== {self.router_id} Routing Table (Mode: {self.mode.value}) ===")
        print(f"{'Dest':<8} {'Metric':<8} {'Next Hop':<10} {'Interface':<12}")
        print("-" * 40)
        for dest, route in sorted(self.routing_table.items()):
            metric_str = str(route.metric) if route.metric < self.INFINITY else "∞"
            print(f"{dest:<8} {metric_str:<8} {route.next_hop:<10} "
                  f"{route.learned_interface:<12}")
    
    def print_outgoing_updates(self):
        """Show what would be advertised on each interface."""
        print(f"\n=== {self.router_id} Outgoing Updates ===")
        for iface_name in self.interfaces:
            update = self.build_update_for_interface(iface_name)
            print(f"  Interface {iface_name}:")
            if update:
                for dest, metric in update.items():
                    metric_str = str(metric) if metric < self.INFINITY else "∞"
                    print(f"    {dest}: {metric_str}")
            else:
                print("    (empty update)")
 
 
def demo_split_horizon_comparison():
    """Demonstrate difference between split horizon modes."""
    
    print("=" * 60)
    print("SPLIT HORIZON MODE COMPARISON")
    print("=" * 60)
    
    # Same topology for each mode: A -- B -- C -- X
    modes = [
        SplitHorizonMode.DISABLED,
        SplitHorizonMode.SIMPLE,
        SplitHorizonMode.POISON_REVERSE
    ]
    
    for mode in modes:
        print(f"\n{'='*60}")
        print(f"Mode: {mode.value.upper()}")
        print('='*60)
        
        # Create Router B
        router_b = SplitHorizonRouter(
            router_id="B",
            interfaces=[
                Interface("eth0", "C", 1),
                Interface("eth1", "A", 1),
            ],
            mode=mode
        )
        
        # B learns routes
        router_b.routing_table["X"] = RouteEntry("X", 2, "C", "eth0")
        router_b.routing_table["C"] = RouteEntry("C", 1, "C", "eth0")
        router_b.routing_table["A"] = RouteEntry("A", 1, "A", "eth1")
        
        router_b.print_routing_table()
        router_b.print_outgoing_updates()
 
demo_split_horizon_comparison()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130

def verify_split_horizon_behavior(router_updates: dict, 
                                    routing_tables: dict) -> dict:
    """
    Analyze update messages to verify split horizon is working.
    
    Args:
        router_updates: {router_id: {interface: {dest: metric}}}
        routing_tables: {router_id: {dest: RouteEntry}}
    
    Returns:
        Analysis results with any violations detected
    """
    violations = []
    correct_behaviors = []
    
    for router_id, interfaces in router_updates.items():
        table = routing_tables.get(router_id, {})
        
        for interface, advertised in interfaces.items():
            for dest, route in table.items():
                learned_from = route.learned_interface
                
                if learned_from == interface:
                    # Should NOT appear in update (simple split horizon)
                    # Or should appear with infinity (poison reverse)
                    if dest in advertised:
                        if advertised[dest] < 16:  # Not infinity
                            violations.append({
                                'router': router_id,
                                'interface': interface,
                                'destination': dest,
                                'issue': f"Route to {dest} learned via {interface} "
                                        f"but advertised with metric {advertised[dest]}",
                                'severity': 'ERROR'
                            })
                        else:
                            correct_behaviors.append({
                                'router': router_id,
                                'interface': interface,
                                'destination': dest,
                                'behavior': 'Poison reverse (correct)'
                            })
                    else:
                        correct_behaviors.append({
                            'router': router_id,
                            'interface': interface,
                            'destination': dest,
                            'behavior': 'Simple split horizon (correct)'
                        })
    
    return {
        'violations': violations,
        'correct_behaviors': correct_behaviors,
        'summary': f"Found {len(violations)} violations, "
                  f"{len(correct_behaviors)} correct behaviors"
    }
 
 
def detect_potential_loops(routing_tables: dict) -> list:
    """
    Detect potential routing loops from routing table inspection.
    """
    loops = []
    
    for router_id, table in routing_tables.items():
        for dest, route in table.items():
            next_hop = route.next_hop
            
            if next_hop in routing_tables:
                next_table = routing_tables[next_hop]
                if dest in next_table:
                    next_route = next_table[dest]
                    
                    # Check if next hop points back to us
                    if next_route.next_hop == router_id:
                        loop = {
                            'destination': dest,
                            'routers': [router_id, next_hop],
                            'type': 'two-node loop'
                        }
                        # Avoid duplicates
                        loop_key = tuple(sorted([router_id, next_hop]) + [dest])
                        if not any(l.get('_key') == loop_key for l in loops):
                            loop['_key'] = loop_key
                            loops.append(loop)
    
    return loops
 
 
# Example usage
from dataclasses import dataclass
 
@dataclass
class RouteEntry:
    destination: str
    metric: int
    next_hop: str
    learned_interface: str
 
# Simulated routing tables
tables = {
    'A': {
        'X': RouteEntry('X', 3, 'B', 'eth0'),
        'B': RouteEntry('B', 1, 'B', 'eth0'),
    },
    'B': {
        'X': RouteEntry('X', 2, 'C', 'eth0'),
        'A': RouteEntry('A', 1, 'A', 'eth1'),
        'C': RouteEntry('C', 1, 'C', 'eth0'),
    }
}
 
# What each router advertises on each interface
updates = {
    'A': {
        'eth0': {'A': 0},  # Correct: X not included (learned from eth0)
    },
    'B': {
        'eth0': {'A': 1, 'B': 0},  # Correct: X and C not included
        'eth1': {'X': 2, 'C': 1, 'B': 0},  # Correct: A not included
    }
}
 
result = verify_split_horizon_behavior(updates, tables)
print("Split Horizon Verification:")
print(f"  {result['summary']}")
for v in result['violations']:
    print(f"  VIOLATION: {v['issue']}")
for c in result['correct_behaviors']:
    print(f"  OK: {c['router']} on {c['interface']}: {c['behavior']}")