Computer NetworksLink State Routing

Link State Routing

LevelIntermediate

Duration90 mins

TopicLink State Routing

2 / 5

Link State Advertisement

The Currency of Topology Information

If Dijkstra's algorithm is the computational engine of link state routing, then Link State Advertisements (LSAs) are the fuel that powers it. Every router in a link state network must possess a complete, accurate, and synchronized view of the network topology. LSAs are the mechanism by which each router describes its local connectivity and broadcasts that description to every other router in the network.

Think of it this way: each router is an expert only on its immediate surroundings—the links directly connected to it, the neighbors at the other end of those links, and the costs associated with using those links. The router knows nothing about the topology beyond its neighbors. LSAs solve this information asymmetry by having every router share its local knowledge, enabling all routers to piece together the complete network map.

What You Will Learn

By the end of this page, you will understand LSA structure and contents, the different LSA types in OSPF and their purposes, when and why LSAs are generated, how LSAs are reliably flooded throughout the network, and how they form the foundation of the Link State Database that Dijkstra's algorithm operates on.

Understanding Link State Advertisements

A Link State Advertisement is a data packet that describes a router's local network connectivity. The term "link state" refers to the status of links connected to a router—are they up or down, what is their cost, and who is at the other end?

Conceptual Model:

Imagine a city where each intersection (router) needs a complete map of all streets (links) and intersections. Each intersection does the following:

Surveys its immediate streets (detects connected links)
Writes a description of what it sees (generates LSA)
Gives copies to all immediate neighbors (floods LSA)
Receives descriptions from neighbors (processes received LSAs)
Pieces together the complete city map (builds Link State Database)
Calculates best routes to all destinations (runs Dijkstra)

Essential LSA Characteristics
Characteristic	Description	Why It Matters
Self-Describing	Each LSA describes its originator's local topology	Distributed information generation
Uniquely Identified	LSA ID + Originator ID forms unique key	Prevents confusion between different LSAs
Versioned	Sequence numbers track LSA freshness	Ensures newest information prevails
Aged	LSAs have lifetimes (typically 60 minutes)	Stale information is automatically purged
Authenticated	Optional cryptographic signatures	Prevents malicious LSA injection
Flooded Reliably	Acknowledged hop-by-hop delivery	Guarantees all routers receive each LSA

Converting Mermaid diagram...

LSA Structure and Format

While specific LSA formats vary between protocols (OSPF vs IS-IS), the core structure shares common elements. We'll use OSPF's LSA format as the primary example, as it's the most widely deployed link state protocol in enterprise networks.

OSPF LSA Header (20 bytes):

Every OSPF LSA begins with a standardized 20-byte header containing identification and versioning information:

OSPF LSA Header Fields
Field	Size	Description	Example Value
LS Age	16 bits	Seconds since LSA origination (max 3600)	120
Options	8 bits	Capability flags (E, MC, N/P, etc.)	0x22
LS Type	8 bits	LSA type (1-7 for OSPFv2)	1 (Router-LSA)
Link State ID	32 bits	Identifies the object described	192.168.1.1
Advertising Router	32 bits	Router ID of LSA originator	1.1.1.1
LS Sequence Number	32 bits	Version number (starts at 0x80000001)	0x80000005
LS Checksum	16 bits	Fletcher checksum for integrity	0x3A2F
Length	16 bits	Total LSA length including header	48

Critical Header Fields Explained:

LS Age: The age field starts at 0 when an LSA is originated and increments every second as it resides in the Link State Database. When age reaches MaxAge (3600 seconds = 1 hour), the LSA is considered expired and must be reflooded with MaxAge to purge it from all databases. Originating routers refresh their LSAs before expiration (typically at 30 minutes).

LS Sequence Number: This 32-bit signed integer determines which copy of an LSA is newer. The sequence space uses lollipop semantics:

Starts at 0x80000001 (most negative)
Increments toward 0x7FFFFFFF (most positive)
If wraparound approaches, router must flush old LSA and wait for it to age out

LS Checksum: A Fletcher checksum (similar to TCP's but excluding the Age field) protects LSA integrity. Age is excluded so intermediate routers can increment it without recalculating the checksum.

lsa_structure.py
Python
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
from dataclasses import dataclass, field
from typing import List, Tuple, Optional
from enum import IntEnum
import struct
 
class LSAType(IntEnum):
    """OSPF LSA Types (OSPFv2)"""
    ROUTER = 1      # Generated by every router
    NETWORK = 2     # Generated by DR on broadcast networks
    SUMMARY_NET = 3 # Generated by ABR for inter-area networks
    SUMMARY_ABR = 4 # Generated by ABR for inter-area ABSRs
    AS_EXTERNAL = 5 # Generated by ASBR for external routes
    NSSA = 7        # External routes in Not-So-Stubby Areas
 
@dataclass
class LSAHeader:
    """
    OSPF LSA Header (20 bytes)
    
    All LSAs share this common header structure regardless of type.
    The header provides unique identification and versioning.
    """
    ls_age: int              # Seconds since origination (0-3600)
    options: int             # Capability flags byte
    ls_type: LSAType         # LSA type identifier
    link_state_id: str       # 32-bit ID (dotted decimal)
    advertising_router: str  # Router ID of originator
    ls_sequence: int         # Version number (signed 32-bit)
    ls_checksum: int         # Fletcher checksum (16-bit)
    length: int              # Total LSA length in bytes
    
    # Constants
    MAX_AGE: int = field(default=3600, init=False, repr=False)
    INITIAL_SEQUENCE: int = field(default=0x80000001, init=False, repr=False)
    MAX_SEQUENCE: int = field(default=0x7FFFFFFF, init=False, repr=False)
    
    def is_expired(self) -> bool:
        """Check if LSA has reached MaxAge"""
        return self.ls_age >= self.MAX_AGE
    
    def is_newer_than(self, other: 'LSAHeader') -> bool:
        """
        Compare two LSAs to determine which is newer.
        Returns True if self is newer than other.
        
        Comparison order:
        1. Higher sequence number is newer
        2. If equal sequence, higher checksum is newer
        3. If equal checksum, MaxAge is newer (being purged)
        4. If one is MaxAge and one is near MaxAge, newer wins
        """
        if self.ls_sequence != other.ls_sequence:
            return self.ls_sequence > other.ls_sequence
        
        if self.ls_checksum != other.ls_checksum:
            return self.ls_checksum > other.ls_checksum
        
        if self.is_expired() and not other.is_expired():
            return True
        
        if other.is_expired() and not self.is_expired():
            return False
        
        # Within MaxAgeDiff (15 min), compare ages
        age_diff = abs(self.ls_age - other.ls_age)
        if age_diff > 900:  # MaxAgeDiff = 15 minutes
            return self.ls_age < other.ls_age
        
        return False  # Consider equal
    
    def to_bytes(self) -> bytes:
        """Serialize LSA header to bytes"""
        ls_id_parts = [int(x) for x in self.link_state_id.split('.')]
        adv_rtr_parts = [int(x) for x in self.advertising_router.split('.')]
        
        return struct.pack(
            '!HBBBBBBBBBBIH',
            self.ls_age,
            self.options,
            self.ls_type,
            *ls_id_parts,  # 4 bytes
            *adv_rtr_parts,  # 4 bytes
            self.ls_sequence,
            self.ls_checksum,
            self.length
        )
 
@dataclass
class RouterLink:
    """
    Describes a single link in a Router-LSA
    """
    link_id: str       # Neighbor router ID or network address
    link_data: str     # Interface IP or mask
    link_type: int     # 1=P2P, 2=Transit, 3=Stub, 4=Virtual
    num_tos: int       # Usually 0 in modern OSPF
    metric: int        # Cost of this link
    tos_metrics: List[Tuple[int, int]] = field(default_factory=list)
 
@dataclass
class RouterLSA:
    """
    Type 1 Router-LSA: Describes a router's local interfaces
    
    Every OSPF router generates exactly one Router-LSA for each
    area it participates in. This LSA describes all router interfaces
    within that area.
    """
    header: LSAHeader
    flags: int           # V=Virtual link, E=ASBR, B=ABR
    num_links: int       # Number of link entries
    links: List[RouterLink] = field(default_factory=list)
    
    @property
    def is_abr(self) -> bool:
        return bool(self.flags & 0x01)
    
    @property
    def is_asbr(self) -> bool:
        return bool(self.flags & 0x02)
    
    @property
    def has_virtual_link(self) -> bool:
        return bool(self.flags & 0x04)
 
@dataclass
class NetworkLSA:
    """
    Type 2 Network-LSA: Describes a broadcast/NBMA network
    
    Generated by the Designated Router (DR) on multi-access networks.
    Lists all routers attached to the network.
    """
    header: LSAHeader
    network_mask: str      # Subnet mask of the network
    attached_routers: List[str] = field(default_factory=list)
 
# Example: Creating LSAs for a router topology
def create_router_lsa(router_id: str, area_id: str, 
                       links: List[RouterLink]) -> RouterLSA:
    """Factory function to create a Router-LSA"""
    # Calculate length: 24 (header + flags) + 12 per link
    length = 24 + len(links) * 12
    
    header = LSAHeader(
        ls_age=0,
        options=0x22,  # E-bit set (external routing)
        ls_type=LSAType.ROUTER,
        link_state_id=router_id,
        advertising_router=router_id,
        ls_sequence=0x80000001,
        ls_checksum=0,  # Calculate separately
        length=length
    )
    
    return RouterLSA(
        header=header,
        flags=0,
        num_links=len(links),
        links=links
    )
 
# Example topology creation
r1_links = [
    RouterLink("2.2.2.2", "10.1.12.1", 1, 0, 10),  # P2P to R2
    RouterLink("10.1.0.0", "255.255.255.0", 3, 0, 1),  # Stub network
]
r1_lsa = create_router_lsa("1.1.1.1", "0.0.0.0", r1_links)
print(f"Router-LSA for {r1_lsa.header.advertising_router}:")
print(f"  Links: {r1_lsa.num_links}")

OSPF LSA Types: A Comprehensive Classification

OSPF defines multiple LSA types, each serving a specific purpose in describing different aspects of network topology. Understanding these types is essential for troubleshooting OSPF and designing scalable network architectures.

Type Classification by Scope and Purpose:

OSPF LSA Types (OSPFv2)
Type	Name	Originated By	Flooded Within	Purpose
1	Router-LSA	Every router	Area	Describes router's interfaces and neighbors in the area
2	Network-LSA	DR only	Area	Describes multi-access network and attached routers
3	Summary-LSA	ABR	Area (not stub)	Advertises inter-area networks (destinations)
4	ASBR-Summary-LSA	ABR	Area (not stub)	Advertises path to ASBR in another area
5	AS-External-LSA	ASBR	Entire AS (not stub)	Advertises external destinations (redistributed routes)
7	NSSA-External-LSA	ASBR in NSSA	NSSA only	External routes in Not-So-Stubby Areas

Type 1: Router-LSA (The Foundation)

The Router-LSA is the most fundamental LSA type. Every OSPF router generates one Router-LSA per area it participates in. This LSA contains:

Router flags: Indicate if router is ABR (area border), ASBR (AS boundary), or has virtual links
Link entries: One entry per interface, describing:
- Link type (point-to-point, transit network, stub network, virtual link)
- Link ID (varies by type: neighbor RID, DR IP, network address)
- Link Data (interface IP or mask)
- Metric (cost to traverse this link)

Type 2: Network-LSA (Multi-Access Networks)

On broadcast networks (Ethernet) or NBMA networks, multiple routers share connections. Instead of having each router advertise all-to-all connectivity (which would be O(n²) links), OSPF elects a Designated Router (DR) who generates a single Type 2 LSA listing all attached routers. This reduces LSDB size significantly on dense networks.

Converting Mermaid diagram...

Type 3 & 4: Summary LSAs (Inter-Area Routing)

Area Border Routers (ABRs) generate Summary LSAs to advertise destinations across area boundaries:

Type 3 (Summary-LSA): Advertises networks in other areas. ABR summarizes destinations from one area and injects Type 3 LSAs into other areas.
Type 4 (ASBR-Summary-LSA): Advertises the path to Autonomous System Boundary Routers (ASBRs) located in other areas, enabling routers to reach external routes.

Type 5: AS-External-LSA (External Routes)

When routes are redistributed into OSPF from other routing protocols (BGP, EIGRP, static), the ASBR generates Type 5 LSAs. These flood throughout the entire OSPF domain (except stub areas) and include:

External destination prefix
Forwarding address (optional next-hop outside OSPF)
External metric (Type 1 = comparable to OSPF, Type 2 = always preferred less)
Route tag (for policy filtering)

Type 7: NSSA-External-LSA

In Not-So-Stubby Areas (NSSA), Type 5 LSAs cannot enter, but local ASBRs can still inject external routes using Type 7 LSAs. At the NSSA border (ABR to backbone), Type 7s are translated to Type 5s for flooding into normal areas.

OSPFv3 (IPv6) LSA Differences

OSPFv3 introduces new LSA types: • Type 0x2001 (Router-LSA): Per-link, not per-interface • Type 0x2002 (Network-LSA): Similar to Type 2 • Type 0x2009 (Intra-Area-Prefix-LSA): Separates prefix info from topology

The separation of topology (links) from addressing (prefixes) makes OSPFv3 more flexible and protocol-independent.

LSA Generation: When and Why LSAs Are Created

Understanding what triggers LSA generation is crucial for predicting network behavior and troubleshooting convergence issues. LSAs are not generated continuously—they're event-driven with periodic refreshes.

LSA Generation Triggers
Event Type	Trigger Description	LSA Action	Typical Delay
Interface Up	New interface becomes active	New or updated Router-LSA	Immediate (after negotiation)
Interface Down	Interface fails or is disabled	Updated Router-LSA without link	Immediate
Neighbor Change	Adjacency forms or breaks	Updated Router-LSA	After adjacency state change
Cost Change	Interface metric modified	Updated Router-LSA with new cost	Immediate
DR/BDR Election	New DR elected on broadcast net	New Network-LSA by DR	After election completes
Route Redistribution	External route injected	New AS-External-LSA	Per redistribution policy
Periodic Refresh	LSA approaching MaxAge/2	Re-originated with new sequence	Every 30 minutes (LSRefreshTime)
MaxAge Reached	LSA needs purging	Reflooded with MaxAge	At 3600 seconds

The LSA Refresh Mechanism:

OSPF LSAs have a maximum lifetime of 3600 seconds (1 hour). To prevent premature expiration, the originating router refreshes its LSAs before they age out:

LSRefreshTime (default 1800 seconds = 30 minutes): Router re-originates its LSAs
On refresh, sequence number increments
Fresh LSA floods to all neighbors
This ensures LSAs never expire under normal conditions

The LSA Throttling Mechanism:

Rapid topology changes (flapping interface) could generate LSAs faster than the network can absorb them. OSPF implements throttling:

MinLSInterval (default 5 seconds): Minimum time between same LSA originations
MinLSArrival (default 1 second): Minimum time to accept same LSA from neighbor

These prevent LSA storms during instability.

lsa_generation.py
Python
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
from dataclasses import dataclass
from enum import Enum, auto
from typing import Dict, List, Optional
from datetime import datetime, timedelta
import threading
 
class LSAEvent(Enum):
    """Events that trigger LSA generation or update"""
    INTERFACE_UP = auto()
    INTERFACE_DOWN = auto()
    NEIGHBOR_FULL = auto()
    NEIGHBOR_DOWN = auto()
    COST_CHANGED = auto()
    DR_ELECTION = auto()
    REFRESH_TIMER = auto()
    MAX_AGE_REACHED = auto()
 
@dataclass
class LSATimers:
    """OSPF LSA timing parameters"""
    LS_REFRESH_TIME: int = 1800      # Refresh before MaxAge (30 min)
    MAX_AGE: int = 3600              # LSA lifetime (1 hour)
    MIN_LS_INTERVAL: int = 5         # Min between generations
    MIN_LS_ARRIVAL: int = 1          # Min between accepting same LSA
    MAX_AGE_DIFF: int = 900          # For age comparison (15 min)
 
class LSAGenerator:
    """
    Manages LSA generation with proper throttling and scheduling.
    
    This class demonstrates the event-driven nature of LSA generation
    and the throttling mechanisms that prevent LSA storms.
    """
    
    def __init__(self, router_id: str, timers: Optional[LSATimers] = None):
        self.router_id = router_id
        self.timers = timers or LSATimers()
        
        # Track LSA generation state
        self.lsa_sequence: Dict[str, int] = {}  # LSA key -> sequence number
        self.last_generation: Dict[str, datetime] = {}  # LSA key -> last gen time
        self.pending_events: List[LSAEvent] = []
        
        # Thread-safe locking for concurrent access
        self._lock = threading.Lock()
    
    def _get_lsa_key(self, lsa_type: int, link_state_id: str) -> str:
        """Generate unique key for an LSA"""
        return f"{self.router_id}:{lsa_type}:{link_state_id}"
    
    def _is_throttled(self, lsa_key: str) -> bool:
        """Check if LSA generation should be throttled"""
        if lsa_key not in self.last_generation:
            return False
        
        elapsed = (datetime.now() - self.last_generation[lsa_key]).total_seconds()
        return elapsed < self.timers.MIN_LS_INTERVAL
    
    def _get_next_sequence(self, lsa_key: str) -> int:
        """Get next sequence number for an LSA"""
        if lsa_key not in self.lsa_sequence:
            self.lsa_sequence[lsa_key] = 0x80000001  # Initial sequence
        else:
            self.lsa_sequence[lsa_key] += 1
            
            # Handle wraparound (rare but must be handled)
            if self.lsa_sequence[lsa_key] > 0x7FFFFFFF:
                raise ValueError(
                    f"Sequence wraparound for {lsa_key} - "
                    "must flush and wait for MaxAge"
                )
        
        return self.lsa_sequence[lsa_key]
    
    def handle_event(self, event: LSAEvent, affected_lsa_key: str) -> Optional[dict]:
        """
        Process an event that may trigger LSA generation.
        
        Returns LSA data if generation proceeds, None if throttled.
        """
        with self._lock:
            print(f"[{self.router_id}] Event: {event.name} for {affected_lsa_key}")
            
            # Check throttling
            if self._is_throttled(affected_lsa_key):
                print(f"  -> Throttled (min interval not elapsed)")
                self.pending_events.append(event)
                return None
            
            # Generate new LSA
            sequence = self._get_next_sequence(affected_lsa_key)
            self.last_generation[affected_lsa_key] = datetime.now()
            
            lsa_data = {
                "key": affected_lsa_key,
                "sequence": hex(sequence),
                "age": 0,
                "event": event.name,
                "timestamp": datetime.now().isoformat()
            }
            
            print(f"  -> Generated LSA: seq={hex(sequence)}")
            return lsa_data
    
    def schedule_refresh(self, lsa_key: str) -> datetime:
        """Calculate when an LSA needs to be refreshed"""
        if lsa_key not in self.last_generation:
            # Never generated, refresh immediately
            return datetime.now()
        
        refresh_time = self.last_generation[lsa_key] +                        timedelta(seconds=self.timers.LS_REFRESH_TIME)
        return refresh_time
 
# Example: Simulating LSA generation events
generator = LSAGenerator("1.1.1.1")
 
# Interface comes up - generates immediately
lsa1 = generator.handle_event(
    LSAEvent.INTERFACE_UP, 
    generator._get_lsa_key(1, "1.1.1.1")
)
 
# Interface cost changes 2 seconds later - throttled
import time
time.sleep(2)
lsa2 = generator.handle_event(
    LSAEvent.COST_CHANGED,
    generator._get_lsa_key(1, "1.1.1.1")
)  # Returns None - throttled
 
# After 5+ seconds - can generate again
time.sleep(4)
lsa3 = generator.handle_event(
    LSAEvent.NEIGHBOR_FULL,
    generator._get_lsa_key(1, "1.1.1.1")
)  # Succeeds with incremented sequence

LSA Flooding: Reliable Distribution

LSA flooding is the mechanism by which link state information propagates to all routers in the network. Unlike distance vector protocols that only share information with immediate neighbors, link state protocols require every router to have an identical topology database. Flooding ensures this consistency.

Flooding Principles:

Reliable Delivery: Every LSA must be acknowledged; retransmission if not
Scope Control: Different LSA types flood to different extents (area, AS)
Loop Prevention: LSAs are flooded but not back to the source interface
Duplicate Suppression: Already-seen LSAs are not re-flooded

Converting Mermaid diagram...

The Flooding Algorithm:

On receiving an LSA:
1. Look up LSA in local LSDB using (Type, LS-ID, Advertising Router)
2. If not found OR received LSA is newer:
   a. Install/replace in LSDB
   b. Send LSAck to sender
   c. Flood LSA out all interfaces EXCEPT:
      - The interface it arrived on
      - Interfaces where router is not DR/BDR on broadcast nets
3. If received LSA is older:
   a. Send current (newer) LSA back to sender
4. If received LSA is same age:
   a. Send LSAck (duplicate - already have it)
   b. Do not re-flood

Reliable Delivery Mechanics:

OSPF uses several packet types for reliable flooding:

Packet Type	Purpose	Reliable?
LSU (Link State Update)	Carries one or more LSAs	Yes (requires ack)
LSAck (Link State Acknowledgment)	Confirms LSU receipt	Implicit
LSR (Link State Request)	Requests specific LSAs	Yes
DD (Database Description)	Summarizes LSDB for sync	Yes

Flooding on Broadcast Networks

On broadcast networks (Ethernet), flooding is optimized using the DR/BDR system:

• Non-DR/BDR routers send LSAs only to the DR/BDR (224.0.0.6 - AllDRouters) • DR re-floods to all other routers on the segment (224.0.0.5 - AllSPFRouters)

This reduces redundant flooding from O(n²) to O(n) on dense broadcast networks.

Retransmission and Reliability:

If an LSAck is not received within the retransmission interval (default 5 seconds), the LSU is retransmitted. The retransmit list tracks outstanding LSAs per neighbor:

RxmtInterval: Time between retransmissions (typically 5 seconds)
Max retransmissions: Implementation-specific (often 5-10 attempts)
Failure action: Neighbor declared dead, adjacency torn down

This hop-by-hop acknowledgment ensures no LSA is lost in transit, maintaining database synchronization even during transient failures.

Link State Database Synchronization

When two OSPF routers form an adjacency, they must synchronize their LSDBs before exchanging routing information as peers. This synchronization process is elegant and efficient, avoiding the need to transmit entire databases over low-bandwidth links.

Database Exchange Process:

After two-way Hello exchange and neighbor state transitions, adjacency-forming routers enter the Database Description (DD) exchange phase:

Step 1: Master/Slave Election

Router with higher Router ID becomes Master
Master controls DD sequence numbers
This prevents deadlock in exchange

Step 2: DD Exchange

Each router sends DD packets listing LSA headers (not full LSAs)
Headers include: Type, LS-ID, Advertising Router, Sequence, Checksum
Sequence numbers ensure complete exchange

Step 3: Loading

Each router compares received headers against local LSDB
For each missing or older LSA, router adds to Request List
Sends LS Requests for needed LSAs

Step 4: Full Adjacency

Once all requests are satisfied, adjacency reaches FULL state
Routers are now synchronized

OSPF Neighbor State Machine (Adjacency Formation)
State	Description	Trigger to Next State
Down	No Hello received	Hello received
Init	Hello received, but own RID not in neighbor list	Own RID seen in neighbor's Hello
2-Way	Bidirectional communication established	Adjacency required (DR or P2P)
ExStart	Master/Slave election for DD exchange	DD packets exchanged
Exchange	DD packets exchanged, headers compared	All DD packets received
Loading	Requesting missing LSAs	All LSRs satisfied
Full	Fully synchronized	N/A (stable state)

Why Not Exchange Full LSAs Directly?

DD exchange sends only LSA headers (20 bytes each) rather than complete LSAs (variable, often 100+ bytes). For a network with 10,000 LSAs, this means:

• Headers only: ~200 KB exchanged • Full LSAs: ~1+ MB exchanged

Since most LSAs will already match (especially if both routers are established), this optimization dramatically reduces synchronization traffic.

LSA Aging, Refresh, and Purging

The LSA aging mechanism serves as a garbage collection system for the Link State Database, ensuring stale information is eventually removed even if the originating router fails ungracefully.

LSA Lifecycle:

Origination: LSA created with Age = 0
Flooding: LSA distributed; age increments during transport
Installation: LSA stored in LSDB; age continues incrementing
Refresh: Before Age reaches LSRefreshTime, originator re-creates with new sequence
MaxAge: If not refreshed, LSA reaches MaxAge (3600s) and is purged

Age Incrementing:

InfTransDelay: Added to LSA age when transmitting (accounts for transmission time)
Each hop adds 1 second of age (configurable per interface)
LSDB background process increments age every second

Premature Aging (Flushing):

When a router needs to withdraw an LSA (e.g., interface removed), it:

Sets LSA age to MaxAge (3600)
Increments sequence number
Re-floods the MaxAge LSA
All routers remove the LSA from their databases

This is called premature aging or flushing and provides explicit withdrawal.

Converting Mermaid diagram...

LSA Age Constants
Constant	Value	Purpose
MaxAge	3600 seconds	Maximum LSA lifetime
LSRefreshTime	1800 seconds	Time before refresh (half MaxAge)
MinLSArrival	1 second	Minimum time between accepting same LSA
MinLSInterval	5 seconds	Minimum time between originating same LSA
InfTransDelay	1 second (default)	Added to age on transmission
MaxAgeDiff	900 seconds	For LSA comparison (15 min)
CheckAge	300 seconds	Interval to verify age consistency

Summary: Link State Advertisements

We have thoroughly explored Link State Advertisements—the information units that enable distributed topology knowledge in link state routing protocols. Let's consolidate the key insights:

Key Takeaways

•LSAs describe local topology — Each router advertises only what it directly knows: its interfaces, neighbors, and link costs.
•LSA headers provide identification and versioning — Type, LS-ID, Advertising Router uniquely identify; sequence numbers determine freshness.
•Multiple LSA types serve different purposes — Router-LSAs for topology, Network-LSAs for broadcast networks, Summary-LSAs for inter-area, External-LSAs for redistribution.
•LSA generation is event-driven with throttling — Topology changes trigger generation, but rate limiting prevents storms during instability.
•Flooding ensures reliable, consistent distribution — Hop-by-hop acknowledgment guarantees every router receives every LSA.
•Database synchronization uses efficient DD exchange — Headers compared first, only missing LSAs requested.
•Aging ensures stale LSAs are eventually purged — 1-hour lifetime with 30-minute refresh protects against orphaned entries.

What's Next:

With LSAs flooding throughout the network, each router builds a complete picture of the topology. The next page examines the Link State Database (LSDB)—the data structure that stores all received LSAs and represents the router's complete view of the network topology. This database is what Dijkstra's algorithm operates on to compute shortest paths.

Page Complete

You now understand Link State Advertisements in depth—from structure and types through generation triggers, flooding mechanisms, and aging lifecycle. These concepts are fundamental to troubleshooting OSPF, designing scalable networks, and understanding how link state protocols achieve synchronized, loop-free routing.

2 / 5

Loading learning content...

Computer NetworksLink State Routing

Link State Routing

LevelIntermediate

Duration90 mins

TopicLink State Routing

2 / 5

Link State Advertisement

The Currency of Topology Information

What You Will Learn

Understanding Link State Advertisements

Conceptual Model:

Imagine a city where each intersection (router) needs a complete map of all streets (links) and intersections. Each intersection does the following:

Surveys its immediate streets (detects connected links)
Writes a description of what it sees (generates LSA)
Gives copies to all immediate neighbors (floods LSA)
Receives descriptions from neighbors (processes received LSAs)
Pieces together the complete city map (builds Link State Database)
Calculates best routes to all destinations (runs Dijkstra)

Essential LSA Characteristics
Characteristic	Description	Why It Matters
Self-Describing	Each LSA describes its originator's local topology	Distributed information generation
Uniquely Identified	LSA ID + Originator ID forms unique key	Prevents confusion between different LSAs
Versioned	Sequence numbers track LSA freshness	Ensures newest information prevails
Aged	LSAs have lifetimes (typically 60 minutes)	Stale information is automatically purged
Authenticated	Optional cryptographic signatures	Prevents malicious LSA injection
Flooded Reliably	Acknowledged hop-by-hop delivery	Guarantees all routers receive each LSA

Converting Mermaid diagram...

LSA Structure and Format

OSPF LSA Header (20 bytes):

Every OSPF LSA begins with a standardized 20-byte header containing identification and versioning information:

OSPF LSA Header Fields
Field	Size	Description	Example Value
LS Age	16 bits	Seconds since LSA origination (max 3600)	120
Options	8 bits	Capability flags (E, MC, N/P, etc.)	0x22
LS Type	8 bits	LSA type (1-7 for OSPFv2)	1 (Router-LSA)
Link State ID	32 bits	Identifies the object described	192.168.1.1
Advertising Router	32 bits	Router ID of LSA originator	1.1.1.1
LS Sequence Number	32 bits	Version number (starts at 0x80000001)	0x80000005
LS Checksum	16 bits	Fletcher checksum for integrity	0x3A2F
Length	16 bits	Total LSA length including header	48

Critical Header Fields Explained:

LS Sequence Number: This 32-bit signed integer determines which copy of an LSA is newer. The sequence space uses lollipop semantics:

Starts at 0x80000001 (most negative)
Increments toward 0x7FFFFFFF (most positive)
If wraparound approaches, router must flush old LSA and wait for it to age out

lsa_structure.py
Python
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
from dataclasses import dataclass, field
from typing import List, Tuple, Optional
from enum import IntEnum
import struct
 
class LSAType(IntEnum):
    """OSPF LSA Types (OSPFv2)"""
    ROUTER = 1      # Generated by every router
    NETWORK = 2     # Generated by DR on broadcast networks
    SUMMARY_NET = 3 # Generated by ABR for inter-area networks
    SUMMARY_ABR = 4 # Generated by ABR for inter-area ABSRs
    AS_EXTERNAL = 5 # Generated by ASBR for external routes
    NSSA = 7        # External routes in Not-So-Stubby Areas
 
@dataclass
class LSAHeader:
    """
    OSPF LSA Header (20 bytes)
    
    All LSAs share this common header structure regardless of type.
    The header provides unique identification and versioning.
    """
    ls_age: int              # Seconds since origination (0-3600)
    options: int             # Capability flags byte
    ls_type: LSAType         # LSA type identifier
    link_state_id: str       # 32-bit ID (dotted decimal)
    advertising_router: str  # Router ID of originator
    ls_sequence: int         # Version number (signed 32-bit)
    ls_checksum: int         # Fletcher checksum (16-bit)
    length: int              # Total LSA length in bytes
    
    # Constants
    MAX_AGE: int = field(default=3600, init=False, repr=False)
    INITIAL_SEQUENCE: int = field(default=0x80000001, init=False, repr=False)
    MAX_SEQUENCE: int = field(default=0x7FFFFFFF, init=False, repr=False)
    
    def is_expired(self) -> bool:
        """Check if LSA has reached MaxAge"""
        return self.ls_age >= self.MAX_AGE
    
    def is_newer_than(self, other: 'LSAHeader') -> bool:
        """
        Compare two LSAs to determine which is newer.
        Returns True if self is newer than other.
        
        Comparison order:
        1. Higher sequence number is newer
        2. If equal sequence, higher checksum is newer
        3. If equal checksum, MaxAge is newer (being purged)
        4. If one is MaxAge and one is near MaxAge, newer wins
        """
        if self.ls_sequence != other.ls_sequence:
            return self.ls_sequence > other.ls_sequence
        
        if self.ls_checksum != other.ls_checksum:
            return self.ls_checksum > other.ls_checksum
        
        if self.is_expired() and not other.is_expired():
            return True
        
        if other.is_expired() and not self.is_expired():
            return False
        
        # Within MaxAgeDiff (15 min), compare ages
        age_diff = abs(self.ls_age - other.ls_age)
        if age_diff > 900:  # MaxAgeDiff = 15 minutes
            return self.ls_age < other.ls_age
        
        return False  # Consider equal
    
    def to_bytes(self) -> bytes:
        """Serialize LSA header to bytes"""
        ls_id_parts = [int(x) for x in self.link_state_id.split('.')]
        adv_rtr_parts = [int(x) for x in self.advertising_router.split('.')]
        
        return struct.pack(
            '!HBBBBBBBBBBIH',
            self.ls_age,
            self.options,
            self.ls_type,
            *ls_id_parts,  # 4 bytes
            *adv_rtr_parts,  # 4 bytes
            self.ls_sequence,
            self.ls_checksum,
            self.length
        )
 
@dataclass
class RouterLink:
    """
    Describes a single link in a Router-LSA
    """
    link_id: str       # Neighbor router ID or network address
    link_data: str     # Interface IP or mask
    link_type: int     # 1=P2P, 2=Transit, 3=Stub, 4=Virtual
    num_tos: int       # Usually 0 in modern OSPF
    metric: int        # Cost of this link
    tos_metrics: List[Tuple[int, int]] = field(default_factory=list)
 
@dataclass
class RouterLSA:
    """
    Type 1 Router-LSA: Describes a router's local interfaces
    
    Every OSPF router generates exactly one Router-LSA for each
    area it participates in. This LSA describes all router interfaces
    within that area.
    """
    header: LSAHeader
    flags: int           # V=Virtual link, E=ASBR, B=ABR
    num_links: int       # Number of link entries
    links: List[RouterLink] = field(default_factory=list)
    
    @property
    def is_abr(self) -> bool:
        return bool(self.flags & 0x01)
    
    @property
    def is_asbr(self) -> bool:
        return bool(self.flags & 0x02)
    
    @property
    def has_virtual_link(self) -> bool:
        return bool(self.flags & 0x04)
 
@dataclass
class NetworkLSA:
    """
    Type 2 Network-LSA: Describes a broadcast/NBMA network
    
    Generated by the Designated Router (DR) on multi-access networks.
    Lists all routers attached to the network.
    """
    header: LSAHeader
    network_mask: str      # Subnet mask of the network
    attached_routers: List[str] = field(default_factory=list)
 
# Example: Creating LSAs for a router topology
def create_router_lsa(router_id: str, area_id: str, 
                       links: List[RouterLink]) -> RouterLSA:
    """Factory function to create a Router-LSA"""
    # Calculate length: 24 (header + flags) + 12 per link
    length = 24 + len(links) * 12
    
    header = LSAHeader(
        ls_age=0,
        options=0x22,  # E-bit set (external routing)
        ls_type=LSAType.ROUTER,
        link_state_id=router_id,
        advertising_router=router_id,
        ls_sequence=0x80000001,
        ls_checksum=0,  # Calculate separately
        length=length
    )
    
    return RouterLSA(
        header=header,
        flags=0,
        num_links=len(links),
        links=links
    )
 
# Example topology creation
r1_links = [
    RouterLink("2.2.2.2", "10.1.12.1", 1, 0, 10),  # P2P to R2
    RouterLink("10.1.0.0", "255.255.255.0", 3, 0, 1),  # Stub network
]
r1_lsa = create_router_lsa("1.1.1.1", "0.0.0.0", r1_links)
print(f"Router-LSA for {r1_lsa.header.advertising_router}:")
print(f"  Links: {r1_lsa.num_links}")

OSPF LSA Types: A Comprehensive Classification

Type Classification by Scope and Purpose:

OSPF LSA Types (OSPFv2)
Type	Name	Originated By	Flooded Within	Purpose
1	Router-LSA	Every router	Area	Describes router's interfaces and neighbors in the area
2	Network-LSA	DR only	Area	Describes multi-access network and attached routers
3	Summary-LSA	ABR	Area (not stub)	Advertises inter-area networks (destinations)
4	ASBR-Summary-LSA	ABR	Area (not stub)	Advertises path to ASBR in another area
5	AS-External-LSA	ASBR	Entire AS (not stub)	Advertises external destinations (redistributed routes)
7	NSSA-External-LSA	ASBR in NSSA	NSSA only	External routes in Not-So-Stubby Areas

Type 1: Router-LSA (The Foundation)

The Router-LSA is the most fundamental LSA type. Every OSPF router generates one Router-LSA per area it participates in. This LSA contains:

Router flags: Indicate if router is ABR (area border), ASBR (AS boundary), or has virtual links
Link entries: One entry per interface, describing:
- Link type (point-to-point, transit network, stub network, virtual link)
- Link ID (varies by type: neighbor RID, DR IP, network address)
- Link Data (interface IP or mask)
- Metric (cost to traverse this link)

Type 2: Network-LSA (Multi-Access Networks)

Converting Mermaid diagram...

Type 3 & 4: Summary LSAs (Inter-Area Routing)

Area Border Routers (ABRs) generate Summary LSAs to advertise destinations across area boundaries:

Type 3 (Summary-LSA): Advertises networks in other areas. ABR summarizes destinations from one area and injects Type 3 LSAs into other areas.
Type 4 (ASBR-Summary-LSA): Advertises the path to Autonomous System Boundary Routers (ASBRs) located in other areas, enabling routers to reach external routes.

Type 5: AS-External-LSA (External Routes)

External destination prefix
Forwarding address (optional next-hop outside OSPF)
External metric (Type 1 = comparable to OSPF, Type 2 = always preferred less)
Route tag (for policy filtering)

Type 7: NSSA-External-LSA

OSPFv3 (IPv6) LSA Differences

The separation of topology (links) from addressing (prefixes) makes OSPFv3 more flexible and protocol-independent.

LSA Generation: When and Why LSAs Are Created

LSA Generation Triggers
Event Type	Trigger Description	LSA Action	Typical Delay
Interface Up	New interface becomes active	New or updated Router-LSA	Immediate (after negotiation)
Interface Down	Interface fails or is disabled	Updated Router-LSA without link	Immediate
Neighbor Change	Adjacency forms or breaks	Updated Router-LSA	After adjacency state change
Cost Change	Interface metric modified	Updated Router-LSA with new cost	Immediate
DR/BDR Election	New DR elected on broadcast net	New Network-LSA by DR	After election completes
Route Redistribution	External route injected	New AS-External-LSA	Per redistribution policy
Periodic Refresh	LSA approaching MaxAge/2	Re-originated with new sequence	Every 30 minutes (LSRefreshTime)
MaxAge Reached	LSA needs purging	Reflooded with MaxAge	At 3600 seconds

The LSA Refresh Mechanism:

OSPF LSAs have a maximum lifetime of 3600 seconds (1 hour). To prevent premature expiration, the originating router refreshes its LSAs before they age out:

LSRefreshTime (default 1800 seconds = 30 minutes): Router re-originates its LSAs
On refresh, sequence number increments
Fresh LSA floods to all neighbors
This ensures LSAs never expire under normal conditions

The LSA Throttling Mechanism:

Rapid topology changes (flapping interface) could generate LSAs faster than the network can absorb them. OSPF implements throttling:

MinLSInterval (default 5 seconds): Minimum time between same LSA originations
MinLSArrival (default 1 second): Minimum time to accept same LSA from neighbor

These prevent LSA storms during instability.

lsa_generation.py
Python
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
from dataclasses import dataclass
from enum import Enum, auto
from typing import Dict, List, Optional
from datetime import datetime, timedelta
import threading
 
class LSAEvent(Enum):
    """Events that trigger LSA generation or update"""
    INTERFACE_UP = auto()
    INTERFACE_DOWN = auto()
    NEIGHBOR_FULL = auto()
    NEIGHBOR_DOWN = auto()
    COST_CHANGED = auto()
    DR_ELECTION = auto()
    REFRESH_TIMER = auto()
    MAX_AGE_REACHED = auto()
 
@dataclass
class LSATimers:
    """OSPF LSA timing parameters"""
    LS_REFRESH_TIME: int = 1800      # Refresh before MaxAge (30 min)
    MAX_AGE: int = 3600              # LSA lifetime (1 hour)
    MIN_LS_INTERVAL: int = 5         # Min between generations
    MIN_LS_ARRIVAL: int = 1          # Min between accepting same LSA
    MAX_AGE_DIFF: int = 900          # For age comparison (15 min)
 
class LSAGenerator:
    """
    Manages LSA generation with proper throttling and scheduling.
    
    This class demonstrates the event-driven nature of LSA generation
    and the throttling mechanisms that prevent LSA storms.
    """
    
    def __init__(self, router_id: str, timers: Optional[LSATimers] = None):
        self.router_id = router_id
        self.timers = timers or LSATimers()
        
        # Track LSA generation state
        self.lsa_sequence: Dict[str, int] = {}  # LSA key -> sequence number
        self.last_generation: Dict[str, datetime] = {}  # LSA key -> last gen time
        self.pending_events: List[LSAEvent] = []
        
        # Thread-safe locking for concurrent access
        self._lock = threading.Lock()
    
    def _get_lsa_key(self, lsa_type: int, link_state_id: str) -> str:
        """Generate unique key for an LSA"""
        return f"{self.router_id}:{lsa_type}:{link_state_id}"
    
    def _is_throttled(self, lsa_key: str) -> bool:
        """Check if LSA generation should be throttled"""
        if lsa_key not in self.last_generation:
            return False
        
        elapsed = (datetime.now() - self.last_generation[lsa_key]).total_seconds()
        return elapsed < self.timers.MIN_LS_INTERVAL
    
    def _get_next_sequence(self, lsa_key: str) -> int:
        """Get next sequence number for an LSA"""
        if lsa_key not in self.lsa_sequence:
            self.lsa_sequence[lsa_key] = 0x80000001  # Initial sequence
        else:
            self.lsa_sequence[lsa_key] += 1
            
            # Handle wraparound (rare but must be handled)
            if self.lsa_sequence[lsa_key] > 0x7FFFFFFF:
                raise ValueError(
                    f"Sequence wraparound for {lsa_key} - "
                    "must flush and wait for MaxAge"
                )
        
        return self.lsa_sequence[lsa_key]
    
    def handle_event(self, event: LSAEvent, affected_lsa_key: str) -> Optional[dict]:
        """
        Process an event that may trigger LSA generation.
        
        Returns LSA data if generation proceeds, None if throttled.
        """
        with self._lock:
            print(f"[{self.router_id}] Event: {event.name} for {affected_lsa_key}")
            
            # Check throttling
            if self._is_throttled(affected_lsa_key):
                print(f"  -> Throttled (min interval not elapsed)")
                self.pending_events.append(event)
                return None
            
            # Generate new LSA
            sequence = self._get_next_sequence(affected_lsa_key)
            self.last_generation[affected_lsa_key] = datetime.now()
            
            lsa_data = {
                "key": affected_lsa_key,
                "sequence": hex(sequence),
                "age": 0,
                "event": event.name,
                "timestamp": datetime.now().isoformat()
            }
            
            print(f"  -> Generated LSA: seq={hex(sequence)}")
            return lsa_data
    
    def schedule_refresh(self, lsa_key: str) -> datetime:
        """Calculate when an LSA needs to be refreshed"""
        if lsa_key not in self.last_generation:
            # Never generated, refresh immediately
            return datetime.now()
        
        refresh_time = self.last_generation[lsa_key] +                        timedelta(seconds=self.timers.LS_REFRESH_TIME)
        return refresh_time
 
# Example: Simulating LSA generation events
generator = LSAGenerator("1.1.1.1")
 
# Interface comes up - generates immediately
lsa1 = generator.handle_event(
    LSAEvent.INTERFACE_UP, 
    generator._get_lsa_key(1, "1.1.1.1")
)
 
# Interface cost changes 2 seconds later - throttled
import time
time.sleep(2)
lsa2 = generator.handle_event(
    LSAEvent.COST_CHANGED,
    generator._get_lsa_key(1, "1.1.1.1")
)  # Returns None - throttled
 
# After 5+ seconds - can generate again
time.sleep(4)
lsa3 = generator.handle_event(
    LSAEvent.NEIGHBOR_FULL,
    generator._get_lsa_key(1, "1.1.1.1")
)  # Succeeds with incremented sequence

LSA Flooding: Reliable Distribution

Flooding Principles:

Reliable Delivery: Every LSA must be acknowledged; retransmission if not
Scope Control: Different LSA types flood to different extents (area, AS)
Loop Prevention: LSAs are flooded but not back to the source interface
Duplicate Suppression: Already-seen LSAs are not re-flooded

Converting Mermaid diagram...

The Flooding Algorithm:

On receiving an LSA:
1. Look up LSA in local LSDB using (Type, LS-ID, Advertising Router)
2. If not found OR received LSA is newer:
   a. Install/replace in LSDB
   b. Send LSAck to sender
   c. Flood LSA out all interfaces EXCEPT:
      - The interface it arrived on
      - Interfaces where router is not DR/BDR on broadcast nets
3. If received LSA is older:
   a. Send current (newer) LSA back to sender
4. If received LSA is same age:
   a. Send LSAck (duplicate - already have it)
   b. Do not re-flood

Reliable Delivery Mechanics:

OSPF uses several packet types for reliable flooding:

Packet Type	Purpose	Reliable?
LSU (Link State Update)	Carries one or more LSAs	Yes (requires ack)
LSAck (Link State Acknowledgment)	Confirms LSU receipt	Implicit
LSR (Link State Request)	Requests specific LSAs	Yes
DD (Database Description)	Summarizes LSDB for sync	Yes

Flooding on Broadcast Networks

On broadcast networks (Ethernet), flooding is optimized using the DR/BDR system:

• Non-DR/BDR routers send LSAs only to the DR/BDR (224.0.0.6 - AllDRouters) • DR re-floods to all other routers on the segment (224.0.0.5 - AllSPFRouters)

This reduces redundant flooding from O(n²) to O(n) on dense broadcast networks.

Retransmission and Reliability:

If an LSAck is not received within the retransmission interval (default 5 seconds), the LSU is retransmitted. The retransmit list tracks outstanding LSAs per neighbor:

RxmtInterval: Time between retransmissions (typically 5 seconds)
Max retransmissions: Implementation-specific (often 5-10 attempts)
Failure action: Neighbor declared dead, adjacency torn down

This hop-by-hop acknowledgment ensures no LSA is lost in transit, maintaining database synchronization even during transient failures.

Link State Database Synchronization

Database Exchange Process:

After two-way Hello exchange and neighbor state transitions, adjacency-forming routers enter the Database Description (DD) exchange phase:

Step 1: Master/Slave Election

Router with higher Router ID becomes Master
Master controls DD sequence numbers
This prevents deadlock in exchange

Step 2: DD Exchange

Each router sends DD packets listing LSA headers (not full LSAs)
Headers include: Type, LS-ID, Advertising Router, Sequence, Checksum
Sequence numbers ensure complete exchange

Step 3: Loading

Each router compares received headers against local LSDB
For each missing or older LSA, router adds to Request List
Sends LS Requests for needed LSAs

Step 4: Full Adjacency

Once all requests are satisfied, adjacency reaches FULL state
Routers are now synchronized

OSPF Neighbor State Machine (Adjacency Formation)
State	Description	Trigger to Next State
Down	No Hello received	Hello received
Init	Hello received, but own RID not in neighbor list	Own RID seen in neighbor's Hello
2-Way	Bidirectional communication established	Adjacency required (DR or P2P)
ExStart	Master/Slave election for DD exchange	DD packets exchanged
Exchange	DD packets exchanged, headers compared	All DD packets received
Loading	Requesting missing LSAs	All LSRs satisfied
Full	Fully synchronized	N/A (stable state)

Why Not Exchange Full LSAs Directly?

DD exchange sends only LSA headers (20 bytes each) rather than complete LSAs (variable, often 100+ bytes). For a network with 10,000 LSAs, this means:

• Headers only: ~200 KB exchanged • Full LSAs: ~1+ MB exchanged

Since most LSAs will already match (especially if both routers are established), this optimization dramatically reduces synchronization traffic.

LSA Aging, Refresh, and Purging

The LSA aging mechanism serves as a garbage collection system for the Link State Database, ensuring stale information is eventually removed even if the originating router fails ungracefully.

LSA Lifecycle:

Origination: LSA created with Age = 0
Flooding: LSA distributed; age increments during transport
Installation: LSA stored in LSDB; age continues incrementing
Refresh: Before Age reaches LSRefreshTime, originator re-creates with new sequence
MaxAge: If not refreshed, LSA reaches MaxAge (3600s) and is purged

Age Incrementing:

InfTransDelay: Added to LSA age when transmitting (accounts for transmission time)
Each hop adds 1 second of age (configurable per interface)
LSDB background process increments age every second

Premature Aging (Flushing):

When a router needs to withdraw an LSA (e.g., interface removed), it:

Sets LSA age to MaxAge (3600)
Increments sequence number
Re-floods the MaxAge LSA
All routers remove the LSA from their databases

This is called premature aging or flushing and provides explicit withdrawal.

Converting Mermaid diagram...

LSA Age Constants
Constant	Value	Purpose
MaxAge	3600 seconds	Maximum LSA lifetime
LSRefreshTime	1800 seconds	Time before refresh (half MaxAge)
MinLSArrival	1 second	Minimum time between accepting same LSA
MinLSInterval	5 seconds	Minimum time between originating same LSA
InfTransDelay	1 second (default)	Added to age on transmission
MaxAgeDiff	900 seconds	For LSA comparison (15 min)
CheckAge	300 seconds	Interval to verify age consistency

Summary: Link State Advertisements

We have thoroughly explored Link State Advertisements—the information units that enable distributed topology knowledge in link state routing protocols. Let's consolidate the key insights:

Key Takeaways

•LSAs describe local topology — Each router advertises only what it directly knows: its interfaces, neighbors, and link costs.
•LSA headers provide identification and versioning — Type, LS-ID, Advertising Router uniquely identify; sequence numbers determine freshness.
•Multiple LSA types serve different purposes — Router-LSAs for topology, Network-LSAs for broadcast networks, Summary-LSAs for inter-area, External-LSAs for redistribution.
•LSA generation is event-driven with throttling — Topology changes trigger generation, but rate limiting prevents storms during instability.
•Flooding ensures reliable, consistent distribution — Hop-by-hop acknowledgment guarantees every router receives every LSA.
•Database synchronization uses efficient DD exchange — Headers compared first, only missing LSAs requested.
•Aging ensures stale LSAs are eventually purged — 1-hour lifetime with 30-minute refresh protects against orphaned entries.

What's Next:

Page Complete

2 / 5