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

import random
import time
from enum import Enum
from dataclasses import dataclass
from typing import Dict, Optional
import threading
 
class RouteState(Enum):
    VALID = "valid"
    INVALID = "invalid"
    HOLDDOWN = "holddown"
    
@dataclass
class RouteEntry:
    destination: str
    metric: int
    next_hop: str
    state: RouteState
    last_update: float
    invalid_timer: Optional[float] = None
    holddown_timer: Optional[float] = None
    flush_timer: Optional[float] = None
 
class RIPTimerManager:
    """
    Manages RIP timer mechanisms for routing table entries.
    Demonstrates the complete timer lifecycle of distance vector routes.
    """
    
    # Timer defaults (in seconds)
    UPDATE_INTERVAL = 30
    UPDATE_JITTER = 5  # ±5 seconds randomization
    INVALID_TIMEOUT = 180
    HOLDDOWN_TIMEOUT = 180
    FLUSH_TIMEOUT = 240
    
    def __init__(self, router_id: str):
        self.router_id = router_id
        self.routes: Dict[str, RouteEntry] = {}
        self.running = False
        
    def add_route(self, destination: str, metric: int, next_hop: str):
        """Add or update a route and reset its timers."""
        current_time = time.time()
        
        if destination in self.routes:
            existing = self.routes[destination]
            # Only update if new route is better or from same next-hop
            if metric < existing.metric or next_hop == existing.next_hop:
                existing.metric = metric
                existing.next_hop = next_hop
                existing.state = RouteState.VALID
                existing.last_update = current_time
                existing.invalid_timer = current_time + self.INVALID_TIMEOUT
                existing.holddown_timer = None
                existing.flush_timer = None
                print(f"[{self.router_id}] Updated route to {destination}: "
                      f"metric={metric}, next_hop={next_hop}")
        else:
            self.routes[destination] = RouteEntry(
                destination=destination,
                metric=metric,
                next_hop=next_hop,
                state=RouteState.VALID,
                last_update=current_time,
                invalid_timer=current_time + self.INVALID_TIMEOUT
            )
            print(f"[{self.router_id}] Added route to {destination}: "
                  f"metric={metric}, next_hop={next_hop}")
    
    def process_timers(self):
        """Check and process all timer expirations."""
        current_time = time.time()
        routes_to_remove = []
        
        for dest, route in self.routes.items():
            if route.state == RouteState.VALID:
                # Check invalid timer
                if route.invalid_timer and current_time >= route.invalid_timer:
                    route.state = RouteState.INVALID
                    route.holddown_timer = current_time + self.HOLDDOWN_TIMEOUT
                    route.flush_timer = current_time + self.FLUSH_TIMEOUT
                    route.metric = 16  # Infinity in RIP
                    print(f"[{self.router_id}] Route to {dest} INVALIDATED "
                          f"(no updates for {self.INVALID_TIMEOUT}s)")
                    
            elif route.state == RouteState.INVALID:
                # Transition to holddown after processing
                route.state = RouteState.HOLDDOWN
                
            elif route.state == RouteState.HOLDDOWN:
                # Check flush timer
                if route.flush_timer and current_time >= route.flush_timer:
                    routes_to_remove.append(dest)
                    print(f"[{self.router_id}] Route to {dest} FLUSHED "
                          f"(flush timer expired)")
        
        # Remove flushed routes
        for dest in routes_to_remove:
            del self.routes[dest]
    
    def get_next_update_time(self) -> float:
        """Calculate next update time with random jitter."""
        base_interval = self.UPDATE_INTERVAL
        jitter = random.uniform(-self.UPDATE_JITTER, self.UPDATE_JITTER)
        return base_interval + jitter
    
    def build_update_message(self) -> Dict[str, int]:
        """Build distance vector for transmission to neighbors."""
        dv = {}
        for dest, route in self.routes.items():
            if route.state != RouteState.HOLDDOWN:
                dv[dest] = route.metric
        return dv
 
 
# Example usage demonstrating timer lifecycle
def demo_timer_lifecycle():
    manager = RIPTimerManager("RouterA")
    
    # Simulate receiving route updates
    manager.add_route("10.0.0.0/8", 2, "192.168.1.1")
    manager.add_route("172.16.0.0/12", 3, "192.168.1.2")
    
    print("
--- Initial Routing Table ---")
    for dest, route in manager.routes.items():
        print(f"  {dest}: metric={route.metric}, state={route.state.value}")
    
    # Build update message
    update = manager.build_update_message()
    print(f"
--- Update Message to Send ---")
    print(f"  {update}")
    
    # Next update scheduled with jitter
    next_update = manager.get_next_update_time()
    print(f"
--- Next update in {next_update:.1f} seconds ---")
 
demo_timer_lifecycle()

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

import struct
import socket
 
class RIPv2Message:
    """
    RIPv2 message construction and parsing.
    Demonstrates the exact wire format of RIP updates.
    """
    
    COMMAND_REQUEST = 1
    COMMAND_RESPONSE = 2
    VERSION = 2
    AF_INET = 2
    MAX_ENTRIES = 25  # Maximum route entries per message
    
    def __init__(self, command=COMMAND_RESPONSE):
        self.command = command
        self.version = self.VERSION
        self.entries = []
    
    def add_route(self, network: str, mask: str, next_hop: str, 
                  metric: int, route_tag: int = 0):
        """Add a route entry to the message."""
        if len(self.entries) >= self.MAX_ENTRIES:
            raise ValueError(f"Maximum {self.MAX_ENTRIES} entries per message")
        
        entry = {
            'address_family': self.AF_INET,
            'route_tag': route_tag,
            'ip_address': network,
            'subnet_mask': mask,
            'next_hop': next_hop,
            'metric': metric
        }
        self.entries.append(entry)
    
    def to_bytes(self) -> bytes:
        """Serialize message to wire format."""
        # Header: command(1) + version(1) + zero(2)
        header = struct.pack('!BBH', self.command, self.version, 0)
        
        # Route entries
        entries_bytes = b''
        for entry in self.entries:
            entry_bytes = struct.pack(
                '!HHIIII',
                entry['address_family'],
                entry['route_tag'],
                self._ip_to_int(entry['ip_address']),
                self._ip_to_int(entry['subnet_mask']),
                self._ip_to_int(entry['next_hop']),
                entry['metric']
            )
            entries_bytes += entry_bytes
        
        return header + entries_bytes
    
    @classmethod
    def from_bytes(cls, data: bytes) -> 'RIPv2Message':
        """Parse wire format into message object."""
        if len(data) < 4:
            raise ValueError("Message too short for header")
        
        command, version, _ = struct.unpack('!BBH', data[:4])
        msg = cls(command)
        msg.version = version
        
        # Parse entries (20 bytes each)
        offset = 4
        while offset + 20 <= len(data):
            af, tag, ip, mask, nh, metric = struct.unpack(
                '!HHIIII', data[offset:offset+20]
            )
            
            if af == cls.AF_INET:
                msg.entries.append({
                    'address_family': af,
                    'route_tag': tag,
                    'ip_address': cls._int_to_ip(ip),
                    'subnet_mask': cls._int_to_ip(mask),
                    'next_hop': cls._int_to_ip(nh),
                    'metric': metric
                })
            offset += 20
        
        return msg
    
    @staticmethod
    def _ip_to_int(ip: str) -> int:
        """Convert dotted-decimal IP to integer."""
        return struct.unpack('!I', socket.inet_aton(ip))[0]
    
    @staticmethod
    def _int_to_ip(val: int) -> str:
        """Convert integer to dotted-decimal IP."""
        return socket.inet_ntoa(struct.pack('!I', val))
    
    def display(self):
        """Pretty-print the message contents."""
        cmd_name = "REQUEST" if self.command == 1 else "RESPONSE"
        print(f"RIPv{self.version} {cmd_name}")
        print("-" * 60)
        
        for i, entry in enumerate(self.entries, 1):
            print(f"Entry {i}:")
            print(f"  Network:    {entry['ip_address']}")
            print(f"  Mask:       {entry['subnet_mask']}")
            print(f"  Next Hop:   {entry['next_hop']}")
            print(f"  Metric:     {entry['metric']}")
            print(f"  Route Tag:  {entry['route_tag']}")
            print()
 
 
# Example: Creating a RIP update message
msg = RIPv2Message(command=RIPv2Message.COMMAND_RESPONSE)
msg.add_route("10.0.0.0", "255.0.0.0", "0.0.0.0", 2)
msg.add_route("172.16.0.0", "255.240.0.0", "192.168.1.1", 3)
msg.add_route("192.168.100.0", "255.255.255.0", "192.168.1.2", 1)
 
print("=== Original Message ===")
msg.display()
 
# Serialize and deserialize
wire_data = msg.to_bytes()
print(f"Wire format: {len(wire_data)} bytes")
print(f"Hex: {wire_data.hex()[:80]}...")
 
# Parse back
parsed = RIPv2Message.from_bytes(wire_data)
print("
=== Parsed Message ===")
parsed.display()

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
191
192
193
194
195
196
197
198
199
200

from dataclasses import dataclass
from typing import Dict, List, Tuple, Optional
from enum import Enum
 
class UpdateResult(Enum):
    NO_CHANGE = "no_change"
    ROUTE_ADDED = "route_added"
    ROUTE_UPDATED = "route_updated"
    ROUTE_DELETED = "route_deleted"
 
@dataclass
class RouteEntry:
    destination: str
    metric: int
    next_hop: str
    interface: str
    last_update: float
 
class DistanceVectorProcessor:
    """
    Implements the route update processing logic for distance vector routing.
    """
    
    INFINITY = 16
    
    def __init__(self, router_id: str, interfaces: Dict[str, int]):
        """
        Args:
            router_id: This router's identifier
            interfaces: Dict of {neighbor_id: link_cost}
        """
        self.router_id = router_id
        self.interfaces = interfaces  # Neighbor -> link cost
        self.routing_table: Dict[str, RouteEntry] = {}
        self.changes: List[Tuple[str, UpdateResult]] = []
    
    def process_update(self, neighbor_id: str, distance_vector: Dict[str, int], 
                       current_time: float) -> List[Tuple[str, UpdateResult]]:
        """
        Process a distance vector update from a neighbor.
        
        Args:
            neighbor_id: ID of the neighbor sending the update
            distance_vector: {destination: metric} from neighbor
            current_time: Current timestamp for timer management
        
        Returns:
            List of (destination, change_type) for triggered updates
        """
        self.changes = []
        
        # Validate neighbor
        if neighbor_id not in self.interfaces:
            print(f"[{self.router_id}] WARNING: Update from unknown neighbor "
                  f"{neighbor_id}, ignoring")
            return []
        
        link_cost = self.interfaces[neighbor_id]
        
        print(f"
[{self.router_id}] Processing update from {neighbor_id} "
              f"(link cost: {link_cost})")
        print(f"  Received DV: {distance_vector}")
        
        for destination, received_metric in distance_vector.items():
            self._process_route_entry(
                destination=destination,
                received_metric=received_metric,
                neighbor_id=neighbor_id,
                link_cost=link_cost,
                current_time=current_time
            )
        
        return self.changes
    
    def _process_route_entry(self, destination: str, received_metric: int,
                             neighbor_id: str, link_cost: int, 
                             current_time: float):
        """Process a single route entry from the update."""
        
        # Calculate new metric (add link cost to neighbor)
        new_metric = min(received_metric + link_cost, self.INFINITY)
        
        # Case 1: Destination not in routing table
        if destination not in self.routing_table:
            if new_metric < self.INFINITY:
                self.routing_table[destination] = RouteEntry(
                    destination=destination,
                    metric=new_metric,
                    next_hop=neighbor_id,
                    interface=neighbor_id,
                    last_update=current_time
                )
                self.changes.append((destination, UpdateResult.ROUTE_ADDED))
                print(f"  [ADD] {destination} via {neighbor_id}, metric {new_metric}")
            return
        
        existing = self.routing_table[destination]
        
        # Case 2: Update from the same next-hop (always trust it)
        if existing.next_hop == neighbor_id:
            if new_metric != existing.metric:
                old_metric = existing.metric
                existing.metric = new_metric
                existing.last_update = current_time
                
                if new_metric >= self.INFINITY:
                    self.changes.append((destination, UpdateResult.ROUTE_DELETED))
                    print(f"  [DELETE] {destination} now unreachable "
                          f"(was metric {old_metric})")
                else:
                    self.changes.append((destination, UpdateResult.ROUTE_UPDATED))
                    print(f"  [UPDATE] {destination} metric {old_metric} -> "
                          f"{new_metric} (same next-hop)")
            else:
                # Same metric, just refresh timer
                existing.last_update = current_time
            return
        
        # Case 3: Update from different next-hop with better metric
        if new_metric < existing.metric:
            old_next_hop = existing.next_hop
            old_metric = existing.metric
            existing.metric = new_metric
            existing.next_hop = neighbor_id
            existing.interface = neighbor_id
            existing.last_update = current_time
            self.changes.append((destination, UpdateResult.ROUTE_UPDATED))
            print(f"  [BETTER] {destination} via {neighbor_id} (metric {new_metric}) "
                  f"replaces via {old_next_hop} (metric {old_metric})")
            return
        
        # Case 4: Update from different next-hop with worse/equal metric
        # Do nothing - keep existing route
        print(f"  [IGNORE] {destination} via {neighbor_id} (metric {new_metric}) "
              f"- keeping via {existing.next_hop} (metric {existing.metric})")
    
    def get_distance_vector(self) -> Dict[str, int]:
        """Return current distance vector for sharing with neighbors."""
        return {dest: entry.metric for dest, entry in self.routing_table.items()}
    
    def print_routing_table(self):
        """Display the current routing table."""
        print(f"
=== Routing Table for {self.router_id} ===")
        print(f"{'Destination':<15} {'Metric':<8} {'Next Hop':<12} {'Interface':<12}")
        print("-" * 50)
        for dest, entry in sorted(self.routing_table.items()):
            metric_str = str(entry.metric) if entry.metric < self.INFINITY else "∞"
            print(f"{entry.destination:<15} {metric_str:<8} "
                  f"{entry.next_hop:<12} {entry.interface:<12}")
 
 
# Example: Processing updates at Router B
def demo_update_processing():
    # Router B connected to A (cost 2) and C (cost 1)
    router_b = DistanceVectorProcessor(
        router_id="B",
        interfaces={"A": 2, "C": 1}
    )
    
    # Initial: B knows about itself
    router_b.routing_table["B"] = RouteEntry(
        destination="B", metric=0, next_hop="B", 
        interface="local", last_update=0
    )
    
    # Receive update from A: A knows {A:0, X:3, Y:5}
    print("
" + "=" * 60)
    print("Receiving update from Router A")
    print("=" * 60)
    changes = router_b.process_update(
        neighbor_id="A",
        distance_vector={"A": 0, "X": 3, "Y": 5},
        current_time=1.0
    )
    print(f"
Changes requiring triggered update: {len(changes)}")
    router_b.print_routing_table()
    
    # Receive update from C: C knows {C:0, Z:2, X:1}
    print("
" + "=" * 60)
    print("Receiving update from Router C")
    print("=" * 60)
    changes = router_b.process_update(
        neighbor_id="C",
        distance_vector={"C": 0, "Z": 2, "X": 1},
        current_time=2.0
    )
    print(f"
Changes requiring triggered update: {len(changes)}")
    router_b.print_routing_table()
    
    # B's distance vector to share
    print(f"
B's Distance Vector to advertise: {router_b.get_distance_vector()}")
 
demo_update_processing()