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
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300

from dataclasses import dataclass, field
from typing import Dict, List, Optional, Tuple, Iterator
from enum import IntEnum
from collections import defaultdict
import threading
import time
 
class LSAType(IntEnum):
    """OSPF LSA Types"""
    ROUTER = 1
    NETWORK = 2
    SUMMARY_NET = 3
    SUMMARY_ABR = 4
    AS_EXTERNAL = 5
    NSSA = 7
 
@dataclass
class LSAKey:
    """
    Unique identifier for an LSA in the database.
    The tuple (type, ls_id, advertising_router) uniquely identifies each LSA.
    """
    lsa_type: LSAType
    ls_id: str  # Link State ID (dotted decimal)
    advertising_router: str  # Router ID of originator
    
    def __hash__(self):
        return hash((self.lsa_type, self.ls_id, self.advertising_router))
    
    def __eq__(self, other):
        if not isinstance(other, LSAKey):
            return False
        return (self.lsa_type == other.lsa_type and 
                self.ls_id == other.ls_id and
                self.advertising_router == other.advertising_router)
    
    def __str__(self):
        return f"Type{self.lsa_type.value}:{self.ls_id}:{self.advertising_router}"
 
@dataclass
class LSAEntry:
    """
    Complete LSA entry in the database.
    Includes both the LSA header information and body.
    """
    key: LSAKey
    sequence: int
    checksum: int
    age: int
    install_time: float  # Time when LSA was installed (for aging)
    body: bytes  # Raw LSA body (type-specific content)
    
    def current_age(self) -> int:
        """Calculate current age based on installation time"""
        elapsed = int(time.time() - self.install_time)
        return min(self.age + elapsed, 3600)  # Cap at MaxAge
    
    def is_expired(self) -> bool:
        """Check if LSA has reached MaxAge"""
        return self.current_age() >= 3600
 
class LinkStateDatabase:
    """
    Implements the OSPF Link State Database.
    
    The LSDB stores all LSAs for an OSPF area, providing:
    - Fast lookup by LSA key
    - Efficient iteration by LSA type
    - Age management and expiration handling
    - Thread-safe access for concurrent operations
    
    Design Note: Uses a two-level structure:
    - First level: Hash by LSA type for type-scoped iteration
    - Second level: Hash by (ls_id, adv_router) for fast lookup
    """
    
    def __init__(self, area_id: str):
        self.area_id = area_id
        
        # Two-level structure: type -> {(ls_id, adv_router) -> LSAEntry}
        self._lsas: Dict[LSAType, Dict[Tuple[str, str], LSAEntry]] =             defaultdict(dict)
        
        # For ordered iteration, maintain sorted list per type
        self._ordered_keys: Dict[LSAType, List[LSAKey]] = defaultdict(list)
        
        # Thread safety
        self._lock = threading.RLock()
        
        # Statistics
        self.stats = {
            "total_lsas": 0,
            "installations": 0,
            "deletions": 0,
            "age_expirations": 0,
        }
    
    def lookup(self, key: LSAKey) -> Optional[LSAEntry]:
        """
        Find an LSA by its unique key.
        Returns None if not found.
        
        Time Complexity: O(1) average
        """
        with self._lock:
            type_db = self._lsas.get(key.lsa_type)
            if type_db is None:
                return None
            return type_db.get((key.ls_id, key.advertising_router))
    
    def install(self, entry: LSAEntry) -> bool:
        """
        Install or update an LSA in the database.
        
        Returns True if LSA was installed (new or newer than existing).
        Returns False if rejected (existing is same or newer).
        
        Time Complexity: O(1) average for install, O(n) if triggers SPF
        """
        with self._lock:
            existing = self.lookup(entry.key)
            
            if existing is not None:
                # Compare: is new LSA newer?
                if not self._is_newer(entry, existing):
                    return False  # Reject - existing is same or newer
            
            # Install the LSA
            inner_key = (entry.key.ls_id, entry.key.advertising_router)
            self._lsas[entry.key.lsa_type][inner_key] = entry
            
            # Update ordered list if new
            if existing is None:
                self._ordered_keys[entry.key.lsa_type].append(entry.key)
                self.stats["total_lsas"] += 1
            
            self.stats["installations"] += 1
            return True
    
    def _is_newer(self, new: LSAEntry, old: LSAEntry) -> bool:
        """
        Compare two LSAs to determine if new is newer than old.
        
        OSPF RFC 2328 Section 13.1:
        1. Higher sequence number is newer
        2. Different checksums: higher checksum is newer
        3. One has MaxAge: that one is newer
        4. Ages differ by > MaxAgeDiff: younger is newer
        5. Otherwise: considered same
        """
        # Higher sequence is newer
        if new.sequence != old.sequence:
            # Handle signed comparison for sequence space
            return self._sequence_compare(new.sequence, old.sequence) > 0
        
        # Different checksums: higher is newer (corruption detection)
        if new.checksum != old.checksum:
            return new.checksum > old.checksum
        
        # MaxAge comparison
        new_age = new.current_age()
        old_age = old.current_age()
        
        if new_age == 3600 and old_age != 3600:
            return True
        if old_age == 3600 and new_age != 3600:
            return False
        
        # Age difference check (MaxAgeDiff = 900 seconds)
        if abs(new_age - old_age) > 900:
            return new_age < old_age  # Younger is newer
        
        return False  # Consider same
    
    def _sequence_compare(self, seq1: int, seq2: int) -> int:
        """Compare sequence numbers in OSPF's lollipop space"""
        # Convert to signed for comparison
        if seq1 > 0x7FFFFFFF:
            seq1 = seq1 - 0x100000000
        if seq2 > 0x7FFFFFFF:
            seq2 = seq2 - 0x100000000
        return seq1 - seq2
    
    def delete(self, key: LSAKey) -> bool:
        """
        Remove an LSA from the database.
        Typically called after MaxAge flooding completes.
        
        Time Complexity: O(n) due to ordered list update
        """
        with self._lock:
            inner_key = (key.ls_id, key.advertising_router)
            type_db = self._lsas.get(key.lsa_type)
            
            if type_db and inner_key in type_db:
                del type_db[inner_key]
                self._ordered_keys[key.lsa_type].remove(key)
                self.stats["total_lsas"] -= 1
                self.stats["deletions"] += 1
                return True
            return False
    
    def iterate_by_type(self, lsa_type: LSAType) -> Iterator[LSAEntry]:
        """
        Iterate over all LSAs of a specific type.
        Used for Database Description packet generation.
        
        Time Complexity: O(n) where n = LSAs of that type
        """
        with self._lock:
            type_db = self._lsas.get(lsa_type, {})
            # Return copies to avoid modification during iteration
            for entry in list(type_db.values()):
                yield entry
    
    def iterate_all(self) -> Iterator[LSAEntry]:
        """
        Iterate over all LSAs in the database.
        Used for SPF computation.
        """
        with self._lock:
            for lsa_type in LSAType:
                yield from self.iterate_by_type(lsa_type)
    
    def get_lsa_count_by_type(self) -> Dict[LSAType, int]:
        """Return count of LSAs per type for monitoring"""
        with self._lock:
            return {t: len(self._lsas.get(t, {})) for t in LSAType}
    
    def check_expired(self) -> List[LSAKey]:
        """
        Find all expired LSAs (age >= MaxAge).
        Returns list of keys for LSAs that need flushing.
        """
        expired = []
        with self._lock:
            for entry in self.iterate_all():
                if entry.is_expired():
                    expired.append(entry.key)
        return expired
    
    def build_topology_graph(self) -> Dict[str, List[Tuple[str, int]]]:
        """
        Convert LSDB into a graph suitable for Dijkstra's algorithm.
        
        Processes Type 1 (Router) and Type 2 (Network) LSAs to build
        an adjacency list representation of the network topology.
        
        Returns: {router_id: [(neighbor_id, cost), ...]}
        """
        graph: Dict[str, List[Tuple[str, int]]] = defaultdict(list)
        
        with self._lock:
            # Process Router-LSAs (Type 1)
            for entry in self.iterate_by_type(LSAType.ROUTER):
                router_id = entry.key.advertising_router
                # Parse body to extract links (simplified)
                # In production, would parse actual LSA body format
                links = self._parse_router_lsa_links(entry.body)
                for neighbor, cost in links:
                    graph[router_id].append((neighbor, cost))
            
            # Process Network-LSAs (Type 2) for transit networks
            for entry in self.iterate_by_type(LSAType.NETWORK):
                # Network acts as pseudo-node connecting attached routers
                network_id = f"net:{entry.key.ls_id}"
                attached = self._parse_network_lsa_routers(entry.body)
                for router in attached:
                    # Cost from network to router is 0 (cost is on router side)
                    graph[network_id].append((router, 0))
                    graph[router].append((network_id, 0))
        
        return dict(graph)
    
    def _parse_router_lsa_links(self, body: bytes) -> List[Tuple[str, int]]:
        """Parse Router-LSA body to extract links (simplified)"""
        # In production, would parse actual OSPF format
        # This is placeholder for demonstration
        return []
    
    def _parse_network_lsa_routers(self, body: bytes) -> List[str]:
        """Parse Network-LSA body to extract attached routers"""
        return []
 
# Example usage
lsdb = LinkStateDatabase("0.0.0.0")  # Area 0
 
# Install some LSAs
entry1 = LSAEntry(
    key=LSAKey(LSAType.ROUTER, "1.1.1.1", "1.1.1.1"),
    sequence=0x80000001,
    checksum=0x3A2F,
    age=0,
    install_time=time.time(),
    body=b""
)
lsdb.install(entry1)
 
print(f"LSDB for Area {lsdb.area_id}:")
print(f"  Total LSAs: {lsdb.stats['total_lsas']}")
print(f"  By Type: {lsdb.get_lsa_count_by_type()}")

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

from dataclasses import dataclass
from typing import Dict, List, Set, Tuple
from enum import Enum
 
class SyncStatus(Enum):
    """LSDB synchronization status with neighbor"""
    SYNCHRONIZED = "synchronized"
    PARTIAL = "partial"       # Some LSAs differ
    DIVERGENT = "divergent"   # Major differences
    UNKNOWN = "unknown"       # Comparison not possible
 
@dataclass
class LSASummary:
    """Summary of an LSA for comparison (from DD packet)"""
    lsa_type: int
    ls_id: str
    advertising_router: str
    sequence: int
    checksum: int
    age: int
 
@dataclass
class SyncReport:
    """Report of LSDB synchronization comparison"""
    status: SyncStatus
    local_only: List[str]     # LSAs only in local database
    remote_only: List[str]    # LSAs only in neighbor's database
    version_mismatch: List[Tuple[str, str]]  # LSA key + which is newer
    total_compared: int
    match_count: int
 
class LSDBVerifier:
    """
    Verifies LSDB synchronization between routers.
    
    Used for:
    - Post-adjacency verification
    - Troubleshooting routing inconsistencies
    - Periodic health checks
    """
    
    def __init__(self, local_lsdb: 'LinkStateDatabase'):
        self.local_lsdb = local_lsdb
    
    def compare_with_summaries(self, 
                                neighbor_summaries: List[LSASummary]
                                ) -> SyncReport:
        """
        Compare local LSDB against neighbor's LSA summaries.
        
        This simulates the comparison done during DD exchange,
        identifying discrepancies that need resolution.
        """
        # Build sets for comparison
        local_keys: Set[str] = set()
        local_map: Dict[str, Tuple[int, int]] = {}  # key -> (seq, checksum)
        
        for entry in self.local_lsdb.iterate_all():
            key = f"{entry.key.lsa_type}:{entry.key.ls_id}:"                   f"{entry.key.advertising_router}"
            local_keys.add(key)
            local_map[key] = (entry.sequence, entry.checksum)
        
        remote_keys: Set[str] = set()
        remote_map: Dict[str, Tuple[int, int]] = {}
        
        for summary in neighbor_summaries:
            key = f"{summary.lsa_type}:{summary.ls_id}:"                   f"{summary.advertising_router}"
            remote_keys.add(key)
            remote_map[key] = (summary.sequence, summary.checksum)
        
        # Find differences
        local_only = list(local_keys - remote_keys)
        remote_only = list(remote_keys - local_keys)
        
        version_mismatch = []
        common_keys = local_keys & remote_keys
        match_count = 0
        
        for key in common_keys:
            local_seq, local_cksum = local_map[key]
            remote_seq, remote_cksum = remote_map[key]
            
            if local_seq == remote_seq and local_cksum == remote_cksum:
                match_count += 1
            else:
                # Determine which is newer
                if local_seq > remote_seq:
                    version_mismatch.append((key, "local_newer"))
                elif remote_seq > local_seq:
                    version_mismatch.append((key, "remote_newer"))
                else:
                    # Same sequence, different checksum - corruption!
                    version_mismatch.append((key, "checksum_mismatch"))
        
        # Determine overall status
        if not local_only and not remote_only and not version_mismatch:
            status = SyncStatus.SYNCHRONIZED
        elif len(version_mismatch) + len(local_only) + len(remote_only) < 5:
            status = SyncStatus.PARTIAL
        else:
            status = SyncStatus.DIVERGENT
        
        return SyncReport(
            status=status,
            local_only=local_only,
            remote_only=remote_only,
            version_mismatch=version_mismatch,
            total_compared=len(local_keys | remote_keys),
            match_count=match_count
        )
    
    def compute_lsdb_checksum(self) -> Dict[int, int]:
        """
        Compute XOR checksum of all LSAs per type.
        
        Used for quick synchronization verification:
        if two routers have the same per-type checksum,
        their databases are likely synchronized.
        """
        type_checksums: Dict[int, int] = {}
        
        for entry in self.local_lsdb.iterate_all():
            lsa_type = entry.key.lsa_type.value
            if lsa_type not in type_checksums:
                type_checksums[lsa_type] = 0
            
            # XOR combines individual checksums
            type_checksums[lsa_type] ^= entry.checksum
        
        return type_checksums
    
    def generate_sync_requests(self, 
                                report: SyncReport) -> List[LSASummary]:
        """
        Generate list of LSAs to request from neighbor
        to achieve synchronization.
        """
        requests = []
        
        # Request LSAs only in remote
        for key in report.remote_only:
            parts = key.split(":")
            requests.append(LSASummary(
                lsa_type=int(parts[0]),
                ls_id=parts[1],
                advertising_router=parts[2],
                sequence=0,  # Any version
                checksum=0,
                age=0
            ))
        
        # Request newer versions from remote
        for key, direction in report.version_mismatch:
            if direction == "remote_newer":
                parts = key.split(":")
                requests.append(LSASummary(
                    lsa_type=int(parts[0]),
                    ls_id=parts[1],
                    advertising_router=parts[2],
                    sequence=0,
                    checksum=0,
                    age=0
                ))
        
        return requests
 
# Example: Verification output
print("LSDB Synchronization Verification")
print("=" * 40)
print("""
Sample Output:
 
Neighbor: 2.2.2.2
Status: PARTIAL
 
Summary:
  Total LSAs Compared: 156
  Matched: 153
  
Differences:
  Local Only (1):
    - Type1:3.3.3.3:3.3.3.3 (Router LSA)
  
  Remote Only (1):
    - Type1:4.4.4.4:4.4.4.4 (Router LSA)
  
  Version Mismatch (1):
    - Type2:10.1.1.1:1.1.1.1 (remote newer: seq 0x80000005)
 
Action: Requesting 2 LSAs from neighbor
""")

! View LSDB summary for all areas
Router# show ip ospf database
 
            OSPF Router with ID (1.1.1.1) (Process ID 1)
 
                Router Link States (Area 0)
 
Link ID         ADV Router      Age         Seq#       Checksum Link count
1.1.1.1         1.1.1.1         423         0x80000005 0x3A2F   3
2.2.2.2         2.2.2.2         312         0x80000004 0x5B1E   2
3.3.3.3         3.3.3.3         198         0x80000003 0x7C0D   4
 
                Net Link States (Area 0)
 
Link ID         ADV Router      Age         Seq#       Checksum
10.1.1.1        1.1.1.1         423         0x80000002 0x1234
 
                Summary Net Link States (Area 0)
 
Link ID         ADV Router      Age         Seq#       Checksum
192.168.10.0    1.1.1.1         523         0x80000001 0x5566
 
! View detailed Router-LSA
Router# show ip ospf database router 1.1.1.1
 
            OSPF Router with ID (1.1.1.1) (Process ID 1)
 
                Router Link States (Area 0)
 
  LS age: 423
  Options: (No TOS-capability, DC)
  LS Type: Router Links
  Link State ID: 1.1.1.1
  Advertising Router: 1.1.1.1
  LS Seq Number: 80000005
  Checksum: 0x3A2F
  Length: 72
  Number of Links: 3
 
    Link connected to: a Transit Network
     (Link ID) Designated Router address: 10.1.1.1
     (Link Data) Router Interface address: 10.1.1.1
      Number of TOS metrics: 0
       TOS 0 Metrics: 10
 
    Link connected to: another Router (point-to-point)
     (Link ID) Neighboring Router ID: 2.2.2.2
     (Link Data) Router Interface address: 10.1.12.1
      Number of TOS metrics: 0
       TOS 0 Metrics: 100
 
    Link connected to: a Stub Network
     (Link ID) Network/subnet number: 192.168.1.0
     (Link Data) Network Mask: 255.255.255.0
      Number of TOS metrics: 0
       TOS 0 Metrics: 1
 
! Compare LSDB with neighbor
Router# show ip ospf database database-summary
 
OSPF Router with ID (1.1.1.1) (Process ID 1)
 
Area 0 database summary
  LSA Type      Count   Delete   Maxage
  Router        15      0        0
  Network       5       0        0
  Summary Net   23      0        0
  Summary ASBR  3       0        0
  Type-5 Ext    1250    0        0
    Total       1296    0        0