5.3 Link State Routing (Dijkstra's Algorithm) & OSPF Internals

Back to Computer Networks Notes

📚Module 05: Network Layer: Routing Protocols & Control PlaneTopic 5.3⏱️20 min read

🎯High-Yield For:Semester Exams (All Universities) • Placement Technical Rounds • Engineering Foundations

💡 Core Intuition: The Road Map GPS vs Asking for Directions

🍳 The Everyday Analogy: Downloading the Full Highway Map

Consider the difference between two ways of navigating an unfamiliar continent:

• The Distance Vector Approach (Asking Bystanders): You drive without a map. At every intersection, you roll down your window and ask a stranger: "Which road should I take to reach Chicago, and how many miles is it?" You trust their second-hand hearsay without knowing whether a bridge has collapsed $100\text{ miles}$ ahead. If two bystanders get confused, you end up driving in circles indefinitely.
• The Link State Approach (Satellite GPS Navigation): Before turning your engine on, your in-car GPS connects to a satellite and downloads the complete, exact blueprint of every road, bridge, and speed limit in the entire country.
  1. Every road agency periodically reports its local link status: "Interstate 80 between mile marker 40 and 60 is open, speed limit 65 mph."
  2. This update is flooded to every GPS unit across the continent.
  3. Because every car's GPS now possesses an identical, complete replica of the continental road map, each car runs an independent shortest-path calculation locally.
  4. Routing loops are mathematically impossible because every vehicle computes its path on a globally consistent, loop-free mathematical graph.

💻 Bridging to Computer Science: Global Topology vs Local Rumors

In Distance Vector Routing (DVR), a router shares its computed distances to all destinations only with its immediate physical neighbors ("tell your neighbors about the entire world").

In Link State Routing (LSR), the philosophy is reversed: each router shares the status of its directly connected links with every router in the entire network domain ("tell the entire world about your immediate neighbors").

Every router in the network independently runs Dijkstra's Shortest Path First (SPF) algorithm on its local copy of the synchronized Link State Database (LSDB), constructing a shortest-path spanning tree rooted at itself to populate its forwarding table.

---

📑Table of Contents

• 🔬 The 4 Operational Stages of Link State Routing
  • 1. Neighbor Discovery (The Hello Protocol)
  • 2. Measuring Link Costs
  • 3. Constructing the Link State Packet (LSP)
  • 4. Reliable Flooding and LSDB Synchronization
• 🧮 Dijkstra's Shortest Path First (SPF) Algorithm
  • Mathematical Formulation & Invariants
  • Mathematical Formulation & Algorithmic Steps
  • Computational Complexity Analysis
• 📊 Complete Tabular Walkthrough of Dijkstra's Algorithm
  • Resulting Forwarding Table at Router A
• 🏛️ Open Shortest Path First (OSPF) Protocol Architecture
  • 1. Transport Layer Independence (Protocol 89)
  • 2. Hierarchical Areas
  • 3. Designated Router (DR) and Backup Designated Router (BDR)
  • 4. The 5 Standard OSPF Packet Types
• ⚖️ Comprehensive Architectural Comparison: DVR vs LSR
  • 8-Dimensional Metric Breakdown
• 🏭 Real-World Production Context: Enterprise Campus & Data Center OSPF Fabrics
  • 1. Cisco IOS & FRRouting (FRR) Production Configuration
  • 2. Equal-Cost Multi-Path (ECMP) Load Balancing
• 📐 Numerical Applications & Worked Examples
  • Example 1: Full Dijkstra Execution & Cost Evaluation
  • Example 2: OSPF Interface Cost Formula & Reference Bandwidth
  • Example 3: Multi-Access Adjacency Reduction via DR/BDR
• 🎯 Exam & Interview Pitfall Check

---

🔬 The 4 Operational Stages of Link State Routing

Link State Routing decouples network topology discovery from shortest-path computation through four sequential, deterministic phases:

Architecture Flow

The 4 Sequential Phases of Link State Routing

From physical link probe to global topology synchronization and local SPT derivation

🤝Phase 1

Neighbor Discovery

Periodic Hello packets identify live adjacent physical neighbors and negotiate parameters.

→

Adjacency Up

📏Phase 2

Cost Measurement

Computes link metrics based on interface bandwidth, transmission delay, or administrative weight.

→

Metrics Ready

📦Phase 3

LSP Generation

Constructs Link State Packet containing Router ID, neighbor list, link costs, sequence number, and age.

→

Flood Trigger

🌊Phase 4

Reliable Flooding

Floods LSPs across all interfaces with ACK verification, synchronizing identical LSDBs globally.

1. Neighbor Discovery (The Hello Protocol)

When a router powers on, it learns who its immediate physical neighbors are by broadcasting a lightweight Hello packet across all active network interfaces.

• Any router receiving the Hello packet replies with its own identity.
• Two routers become adjacent once they confirm mutual reachability, matching subnet masks, and compatible Hello/Dead timer intervals.

2. Measuring Link Costs

The router assigns a scalar metric (cost) to each active link.

• In simple models, cost can be physical delay, measured by sending an Echo packet that the neighbor timestamps and bounces back ($Cost = \frac{\text{RTT}}{2}$).
• In modern enterprise protocols like OSPF, cost is inversely proportional to bandwidth: $\text{Cost} = \frac{\text{Reference Bandwidth}}{\text{Interface Bandwidth}}$

3. Constructing the Link State Packet (LSP)

Once neighbors are verified and link costs evaluated, the router builds a Link State Packet (LSP). A standard LSP contains five essential fields:

Field	Purpose	Example Value
Source Router ID	Unique 32-bit identifier of the originating router	192.168.1.1
Neighbor List & Costs	Array of directly connected adjacent neighbors and link weights	[(R2, Cost=4), (R3, Cost=2)]
Sequence Number	32-bit counter incremented each time an updated LSP is generated	0x80000001
Age / Time-to-Live	Countdown timer in seconds decremented at each hop and every second in memory	3600 (decrements to 0)
Checksum	Validates LSP payload integrity to prevent corrupt routing advertisements	0x4F2A

4. Reliable Flooding and LSDB Synchronization

The generated LSP is flooded across all active interfaces except the one it arrived on. To guarantee reliable synchronization and prevent infinite broadcast loops:

1. Duplicate Detection via Sequence Numbers: When a router receives an LSP, it checks its local Link State Database (LSDB).
   • If the LSP is new (not in LSDB), the router installs it, immediately floods it out on all other interfaces, and sends an acknowledgment back.
   • If the sequence number is identical to an existing entry in the LSDB, the LSP is recognized as a duplicate and silently discarded.
   • If the sequence number is lower than the existing entry, the received packet is stale; the router discards it and sends its newer LSP back to the source to correct it.
   • If the sequence number is higher, the router overwrites its database with the new record and floods it outward.
2. Age Expiration: Every LSP has an Age field that decrements continuously. When Age reaches $0$, the link state is purged from the database and a purge notification is flooded, removing dead routers.

---

🧮 Dijkstra's Shortest Path First (SPF) Algorithm

Once reliable flooding converges, every router in the network possesses an identical copy of the Link State Database (LSDB). Each router then models the network as a weighted directed graph $G = (V, E)$ and executes Dijkstra's Algorithm to compute the Shortest Path Tree (SPT) with itself as the root node.

Mathematical Formulation & Invariants

Let:

• $V$ be the set of all routers (vertices).
• $E$ be the set of all active physical links (edges).
• $c(u, v)$ be the link cost between router $u$ and neighbor $v$ (with $c(u, v) = \infty$ if no direct link exists).
• $s \in V$ be the source router (root of the tree).
• $P \subseteq V$ be the Permanent Set (routers whose minimum distance from $s$ is finalized).
• $T = V \setminus P$ be the Tentative / Candidate Set (routers whose shortest paths are still being evaluated).
• $D(v)$ be the tentative shortest distance from source $s$ to vertex $v$.
• $p(v)$ be the predecessor of $v$ on the current shortest path from $s$.

Mathematical Formulation & Algorithmic Steps

1. Initialization Phase:

• Initialize the permanent set with the source node: $P = \{s\}$
• Distance to source is zero: $D(s) = 0$
• For all other routers $v \in V \setminus \{s\}$:
  • Tentative distance: $D(v) = c(s, v)$ (where $c(s, v) = \infty$ if no direct link exists)
  • Predecessor pointer: $p(v) = s$ (if $c(s, v) < \infty$, otherwise $\text{NIL}$)

2. Iterative Exploration Loop: While $P \neq V$ (unsettled candidate routers remain):

1. Extract Minimum Candidate: Find an unvisited router $u \in V \setminus P$ with the minimum tentative distance: $D(u) = \min_{w \in V \setminus P} D(w)$
2. Finalize Router: Add $u$ to the permanent set: $P = P \cup \{u\}$.
3. Edge Relaxation Step: For every adjacent neighbor $v \in V \setminus P$ of $u$: $D(v) = \min\Big(D(v), \; D(u) + c(u, v)\Big)$ If the path through $u$ is shorter ($D(u) + c(u, v) < D(v)$), update the predecessor pointer: $p(v) = u$

Computational Complexity Analysis

• Naive Array Implementation: Finding the minimum distance vertex in step 1 requires scanning all remaining vertices in $V \setminus P$, taking $O(|V|)$ per iteration. Over $|V|$ iterations, total time is $O(|V|^2)$.
• Binary Min-Heap / Priority Queue Implementation: Extracting the minimum element takes $O(\log |V|)$ time, and each edge relaxation takes $O(\log |V|)$ time via decrease-key: $\text{Time Complexity} = O\Big((|E| + |V|) \log |V|\Big)$
• For sparse network graphs where $|E| \ll |V|^2$, the heap-based implementation enables sub-millisecond route calculations even across thousands of routers.

---

📊 Complete Tabular Walkthrough of Dijkstra's Algorithm

Architecture Flow

6-Router Mesh Network Topology for Dijkstra SPF Evaluation

Bidirectional link weights between routers A through F

Cost: 2

Cost: 1

Cost: 3

Cost: 2

Cost: 3

Cost: 1

Cost: 2

🏠Source

Router A

Source (Root)

⚡Transit

Router B

c(A,B)=2

⚡Transit

Router D

c(B,D)=3

⚡Transit

Router C

c(A,C)=1

⚡Transit

Router E

c(C,E)=3

🎯Dest

Router F

Destination

💡Click or hover any card or transition arrow above to inspect deep-dive operational mechanics

Direct physical link costs:

• $c(A, B) = 2, \quad c(A, C) = 1$
• $c(B, D) = 3, \quad c(B, E) = 2$
• $c(C, E) = 3$
• $c(D, F) = 1$
• $c(E, F) = 2$

We execute Dijkstra's algorithm to compute the shortest paths from source router $A$ to all destinations:

Step	Permanent Set $P$	Added Node $u$	$D(B), p(B)$	$D(C), p(C)$	$D(D), p(D)$	$D(E), p(E)$	$D(F), p(F)$	Operation & Intuition
0	$\{A\}$	$A$	$2, A$	$\mathbf{1, A}$	$\infty, -$	$\infty, -$	$\infty, -$	Direct links from $A$ evaluated. Min is $C$ ($D=1$).
1	$\{A, C\}$	$C$	$2, A$	1, A	$\infty, -$	$4, C$	$\infty, -$	Inspect $C$'s neighbors: $D(E) = \min(\infty, 1 + 3) = 4$. Min across candidate set is $B$ ($D=2$).
2	$\{A, C, B\}$	$B$	2, A	1, A	$5, B$	$\mathbf{4, C}$	$\infty, -$	Inspect $B$'s neighbors: $D(D) = 2+3=5$; $D(E) = \min(4, 2+2) = 4$ (no change). Min is $E$ ($D=4$).
3	$\{A, C, B, E\}$	$E$	2, A	1, A	$5, B$	4, C	$6, E$	Inspect $E$'s neighbors: $D(F) = 4 + 2 = 6$. Min across candidate set is $D$ ($D=5$).
4	$\{A, C, B, E, D\}$	$D$	2, A	1, A	5, B	4, C	$\mathbf{6, E}$	Inspect $D$'s neighbors: $D(F) = \min(6, 5 + 1) = 6$ (tied). Min is $F$ ($D=6$).
5	$\{A, C, B, E, D, F\}$	$F$	2, A	1, A	5, B	4, C	6, E	All vertices finalized in $P$. Shortest Path Tree complete!

Resulting Forwarding Table at Router A

Traced back from destination predecessors to determine the immediate Next Hop interface from router $A$:

Destination	Total Path Cost	Full Shortest Path	Next Hop from $A$	Egress Interface
B	$2$	$A \to B$	$B$	eth0
C	$1$	$A \to C$	$C$	eth1
D	$5$	$A \to B \to D$	$B$	eth0
E	$4$	$A \to C \to E$	$C$	eth1
F	$6$	$A \to C \to E \to F$ (or $A \to B \to D \to F$)	$C$ (or $B$)	eth1 (or ECMP)

---

🏛️ Open Shortest Path First (OSPF) Protocol Architecture

Open Shortest Path First (OSPF), defined in RFC 2328 (OSPFv2) and RFC 5340 (OSPFv3 for IPv6), is the industry-standard open interior gateway protocol implementing Link State Routing.

Architecture Flow

Step 1 of 4

Hierarchical OSPF 2-Tier Architecture & Area Topologies

Area 0 Backbone inter-connecting Area 1 and Area 2 via Area Border Routers (ABRs)

🌐OSPF Area 0 (Backbone Core)

🏢OSPF Area 1 (Branch Campus)

🗄️OSPF Area 2 (Data Center)

1LSA Type 3

2LSA Type 3

3Area 1 LSDB

4Area 2 LSDB

⚡Internal

Backbone Core R1

Router ID 10.0.0.1

🔀ABR

ABR Router 1

Borders Area 0 & 1

🔀ABR

ABR Router 2

Borders Area 0 & 2

💻Internal

Access Router A1

Floods Area 1 Only

🛡️DR

Designated Router

Multicast 224.0.0.6

💡Click or hover any card or transition arrow above to inspect deep-dive operational mechanics

1. Transport Layer Independence (Protocol 89)

Unlike RIP (which runs on top of UDP port 520) and BGP (which runs on top of TCP port 179), OSPF encapsulates its packets directly inside the IPv4 datagram payload:

• The IPv4 header Protocol field is set to 89.
• OSPF does not rely on UDP or TCP; it implements its own lightweight sequence numbers, retransmission timers, and packet acknowledgments directly at Layer 3.

2. Hierarchical Areas

To scale across massive enterprise networks with thousands of routers, OSPF divides an Autonomous System into Areas:

• Area 0 (Backbone Area): Every Autonomous System must have a central Area 0 (0.0.0.0). All non-backbone areas must physically connect to Area 0.
• Area Border Router (ABR): A router with interfaces in both Area 0 and a regular area. An ABR summarizes internal area topology into concise summary advertisements (LSA Type 3), shielding Area 0 routers from local link flaps in Area 1.
• Autonomous System Boundary Router (ASBR): A router that connects the OSPF network to an external routing domain (e.g., BGP or static routes), injecting external routes (LSA Type 5).

3. Designated Router (DR) and Backup Designated Router (BDR)

On a multi-access broadcast network (such as an Ethernet switch connecting $n$ routers), having every router establish an adjacency with every other router produces: $\text{Total Full-Mesh Adjacencies} = \frac{n(n - 1)}{2} = O(n^2)$ For $n = 10$, this requires $45$ simultaneous neighbor peering sessions and quadratic flooding overhead!

To eliminate this bottleneck, OSPF elects a Designated Router (DR) and a Backup Designated Router (BDR):

• All other routers (called DROthers) establish adjacencies strictly with the DR and BDR, reducing adjacencies to $2n - 3 = O(n)$.
• Multicast Addresses:
  • 224.0.0.5: All OSPF Routers multicast group (listened to by every OSPF router).
  • 224.0.0.6: All DR/BDR multicast group (used by DROther routers to send link updates to the DR/BDR).

Multi-Access Adjacencies: Full-Mesh vs DR/BDR Star Topology

Scaling control-plane state from quadratic O(n²) explosion down to linear O(n) efficiency

Without DR/BDR

Full-Mesh Adjacency Explosion

💥

Dominant Architecture / DomainQuadratic Overhead: O(n²)

• •Every router establishes bidirectional adjacency with every other router.
• •Total peering adjacencies: n(n - 1) / 2.
• •For 10 routers, 45 full adjacencies generate excessive LSA flooding duplicate storms.

"Floods redundant LSAs across all peer links, saturating link capacity."

With DR/BDR

Designated Router Star Optimization

🛡️

Dominant Architecture / DomainLinear Efficiency: O(n)

• •Routers elect a single Designated Router (DR) and Backup (BDR).
• •All other routers (DROthers) peer strictly with DR and BDR via multicast.
• •Total adjacencies reduced to 2n - 3 (only 17 for 10 routers!).

"Centralizes LSA collection and distribution, reducing flooding by up to 75%."

4. The 5 Standard OSPF Packet Types

Type	Packet Name	Primary Function
1	Hello	Discovers and maintains neighbor adjacencies; sent every 10s on broadcast links.
2	Database Description (DBD)	Summarizes local LSDB content so a neighbor can detect missing link-state records.
3	Link State Request (LSR)	Requests the complete contents of specific, newer LSAs detected from a DBD.
4	Link State Update (LSU)	Carries one or more full LSAs flooded across the network in response to an LSR.
5	Link State Acknowledgment (LSAck)	Confirms reliable receipt of an LSU; prevents retransmission timeout stalls.

---

⚖️ Comprehensive Architectural Comparison: DVR vs LSR

Distance Vector Routing (DVR) vs Link State Routing (LSR)

The fundamental architectural trade-off between localized simplicity and global topological precision

Distance Vector

Distance Vector (Bellman-Ford / RIP)

📢

Dominant Architecture / DomainSmall, Simple Networks (<= 15 hops)

• •Routers know only distance and next-hop direction; zero global topology view.
• •Advertises entire routing table periodically (every 30s) strictly to immediate neighbors.
• •Slow convergence; susceptible to Count-to-Infinity and two-node routing loops.
• •Extremely low CPU and memory consumption; O(V) storage requirement.

"Tells its immediate neighbors about the entire world based on second-hand hearsay."

Link State

Link State (Dijkstra / OSPF)

🗺️

Dominant Architecture / DomainLarge, Enterprise & Backbone Networks

• •Every router maintains an identical, complete map of the entire network graph.
• •Floods state of directly connected links globally to all routers on topology change.
• •Instant convergence; mathematically immune to routing loops via Dijkstra SPF trees.
• •Higher CPU and RAM demands; executes Dijkstra O((E + V) log V) on topological flaps.

"Tells the entire world about its directly connected physical neighbors."

8-Dimensional Metric Breakdown

Dimension	Distance Vector Routing (DVR / RIP)	Link State Routing (LSR / OSPF)
Algorithmic Foundation	Distributed Bellman-Ford algorithm	Dijkstra's Shortest Path First (SPF) algorithm
Topological View	Blind to topology; knows only (Cost, Next-Hop)	Full, identical graph of all nodes and edges (LSDB)
Advertisement Scope	Transmitted strictly to direct neighbors	Flooded globally to all routers in the area
Advertisement Content	Full routing table (all known destinations)	Local link state only (status of adjacent links)
Update Triggers	Periodic (e.g. 30s) + Triggered on link changes	Event-driven (on link flap) + periodic refresh (30 min)
Convergence Speed	Slow; step-by-step neighbor propagation	Rapid; flooded immediately at line-rate
Loop Vulnerability	Prone to Count-to-Infinity; requires Split Horizon	Loop-free; SPT is an acyclic tree by definition
Hardware Overhead	Minimal CPU and RAM footprint	High CPU for Dijkstra; memory for full LSDB

---

🏭 Real-World Production Context: Enterprise Campus & Data Center OSPF Fabrics

1. Cisco IOS & FRRouting (FRR) Production Configuration

In enterprise environments and Linux-based network routers (such as FRRouting running inside Kubernetes CNI or edge appliances), OSPF is activated with explicit router IDs and area assignments:

# Verify active OSPF neighbors and adjacency states
$ vtysh -c "show ip ospf neighbor"
Neighbor ID     Pri State           Dead Time Address         Interface
10.0.0.2          1 Full/DR           00:00:34 192.168.1.2     eth0
10.0.0.3          1 Full/BDR          00:00:36 192.168.1.3     eth0

# Inspect local Link State Database (LSDB)
$ vtysh -c "show ip ospf database"
                OSPF Router with ID (10.0.0.1)

                Router Link States (Area 0.0.0.0)
Link ID         ADV Router      Age  Seq#       Cksum
10.0.0.1        10.0.0.1        412  0x80000004 0x2A1C
10.0.0.2        10.0.0.2        389  0x80000003 0x31B0

2. Equal-Cost Multi-Path (ECMP) Load Balancing

When Dijkstra finds multiple paths to a destination with identical cumulative metrics (e.g., two parallel $10\text{ Gbps}$ links with cost $10$), modern hardware switches do not arbitrarily pick one. They install both paths into the ASIC Forwarding Information Base (FIB) and perform Equal-Cost Multi-Path (ECMP) hashing across the 5-tuple, doubling aggregate network throughput without reordering packets within individual TCP flows.

---

📐 Numerical Applications & Worked Examples

Example 1: Full Dijkstra Execution & Cost Evaluation

Problem Statement: A sub-network consists of 5 routers $\{U, V, W, X, Y\}$. The link costs are:

• $c(U, V) = 2, \quad c(U, W) = 5, \quad c(U, X) = 1$
• $c(V, W) = 3, \quad c(V, X) = 2$
• $c(W, X) = 3, \quad c(W, Y) = 1, \quad c(X, Y) = 6$

Compute the minimum cost to reach destination router $Y$ starting from source router $U$, and trace the exact path taken.

Step-by-Step Solution:

1. Initialize from Source $U$ ($P = \{U\}$):

   • $D(V) = 2$, $D(W) = 5$, $D(X) = 1$, $D(Y) = \infty$.
   • Minimum non-permanent candidate: $X$ with $D(X) = 1$.

2. Add $X$ to $P$ ($P = \{U, X\}$): Relax neighbors of $X$ ($V, W, Y$):

   • $D(V) = \min(2, D(X) + c(X, V)) = \min(2, 1 + 2) = 2$ (no change).
   • $D(W) = \min(5, D(X) + c(X, W)) = \min(5, 1 + 3) = 4$ (improved from 5!).
   • $D(Y) = \min(\infty, D(X) + c(X, Y)) = \min(\infty, 1 + 6) = 7$.
   • Current candidate distances: $V: 2, \ W: 4, \ Y: 7$.
   • Minimum candidate: $V$ with $D(V) = 2$.

3. Add $V$ to $P$ ($P = \{U, X, V\}$): Relax neighbors of $V$ ($W$):

   • $D(W) = \min(4, D(V) + c(V, W)) = \min(4, 2 + 3) = 4$ (no change).
   • Current candidate distances: $W: 4, \ Y: 7$.
   • Minimum candidate: $W$ with $D(W) = 4$.

4. Add $W$ to $P$ ($P = \{U, X, V, W\}$): Relax neighbors of $W$ ($Y$):

   • $D(Y) = \min(7, D(W) + c(W, Y)) = \min(7, 4 + 1) = \mathbf{5}$ (improved from 7!).
   • Remaining candidate: $Y$ with $D(Y) = 5$.

5. Final Path and Cost Evaluation:

   • Minimum cost to reach $Y = \mathbf{5}$.
   • Path: $U \to X \to W \to Y$ (Costs: $1 + 3 + 1 = 5$).
   • Notice that the direct link from $X \to Y$ has cost $6$, but routing through intermediate node $W$ yields cost $1 + 3 + 1 = 5$.

---

Example 2: OSPF Interface Cost Formula & Reference Bandwidth

Problem Statement: An OSPF network uses the standard default reference bandwidth of $100\text{ Mbps}$ ($10^8\text{ bps}$).

1. Calculate the OSPF cost for a FastEthernet link ($100\text{ Mbps}$) and a GigabitEthernet link ($1\text{ Gbps}$).
2. Explain the fundamental flaw of this default configuration in modern networks, and determine the new costs if the administrator updates the reference bandwidth to $100\text{ Gbps}$ ($10^{11}\text{ bps}$).

Step-by-Step Solution:

1. Apply OSPF Cost Formula with Default Reference Bandwidth ($10^8\text{ bps}$): $\text{Cost} = \left\lceil \frac{\text{Reference Bandwidth}}{\text{Interface Bandwidth}} \right\rceil$

   • For FastEthernet ($100\text{ Mbps} = 10^8\text{ bps}$): $\text{Cost}_{FE} = \frac{10^8}{10^8} = \mathbf{1}$
   • For GigabitEthernet ($1\text{ Gbps} = 10^9\text{ bps}$): $\text{Cost}_{GE} = \frac{10^8}{10^9} = 0.1 \implies \mathbf{1} \quad (\text{minimum integer cost is } 1)$

2. Identify Architectural Flaw:

   • Both $100\text{ Mbps}$, $1\text{ Gbps}$, and $10\text{ Gbps}$ links are assigned an identical cost of $1$! OSPF cannot distinguish between a $100\text{ Mbps}$ bottleneck and a $10\text{ Gbps}$ fiber link!

3. Recalculate with Reference Bandwidth $= 100\text{ Gbps}$ ($10^{11}\text{ bps}$):

   • FastEthernet ($100\text{ Mbps} = 10^8\text{ bps}$): $\text{Cost}_{FE} = \frac{10^{11}}{10^8} = \mathbf{1,000}$
   • GigabitEthernet ($1\text{ Gbps} = 10^9\text{ bps}$): $\text{Cost}_{GE} = \frac{10^{11}}{10^9} = \mathbf{100}$
   • Ten-GigabitEthernet ($10\text{ Gbps} = 10^{10}\text{ bps}$): $\text{Cost}_{10GE} = \frac{10^{11}}{10^{10}} = \mathbf{10}$
   • Hundred-GigabitEthernet ($100\text{ Gbps} = 10^{11}\text{ bps}$): $\text{Cost}_{100GE} = \frac{10^{11}}{10^{11}} = \mathbf{1}$

---

Example 3: Multi-Access Adjacency Reduction via DR/BDR

Problem Statement: An enterprise network connects $16$ routers to a single central Gigabit Ethernet switch.

1. How many neighbor adjacencies would be required if all routers formed peerings directly with each other?
2. How many adjacencies are formed when OSPF elects a Designated Router (DR) and a Backup Designated Router (BDR)?

Step-by-Step Solution:

1. Full-Mesh Adjacency Formula without DR/BDR: $N_{\text{adj\_full}} = \frac{n(n - 1)}{2} = \frac{16 \times 15}{2} = \mathbf{120\text{ adjacencies}}$

2. Adjacency Formula with DR and BDR:

   • There are $2$ designated routers (DR and BDR) and $n - 2 = 14$ non-designated routers (DROthers).
   • Between DR and BDR: $1$ adjacency.
   • Each of the $14$ DROther routers establishes exactly $2$ adjacencies (one with DR, one with BDR): $N_{\text{adj\_DROther}} = 14 \times 2 = 28\text{ adjacencies}$
   • Total adjacencies formed: $N_{\text{total}} = 1 + 28 = \mathbf{29\text{ adjacencies}} \quad \Big(\text{Formula: } 2n - 3 = 2(16) - 3 = 29\Big)$
   • Result: DR/BDR reduces control-plane overhead by over $75\%$ ($120 \to 29$).

---

🎯 Exam & Interview Pitfall Check

Core Conceptual Questions

• Why does OSPF encapsulate directly into IP (Protocol 89) instead of utilizing UDP or TCP?
  Because OSPF is an interior routing protocol that operates within a single administrative domain. Running over UDP would introduce unnecessary transport overhead without reliability benefits. Running over TCP would introduce head-of-line blocking, connection setup latency, and transport circularity (TCP needs routing tables to deliver packets, while routing tables need TCP to converge). OSPF implements its own reliable hop-by-hop flooding and acknowledgment mechanism tailored specifically for topology exchange.

• Why does Dijkstra's algorithm fail when a graph contains negative-weight edge cycles?
  Dijkstra's algorithm relies on a greedy property: once a node is placed into the Permanent Set $P$, its shortest distance is assumed finalized and is never reconsidered. If negative edges exist, reaching an already-finalized node through a subsequent negative path could yield a strictly smaller total distance, violating Dijkstra's core greedy invariant. (Bellman-Ford must be used when negative edges are present).

Common Interview Traps

• Trap: Believing that OSPF elects a DR/BDR on Point-to-Point serial links.
  Debunked: DR and BDR election occurs strictly on Broadcast and Non-Broadcast Multi-Access (NBMA) networks (e.g. Ethernet). On Point-to-Point links connecting exactly two routers, there are only $n = 2$ routers, so $\frac{2(1)}{2} = 1$ adjacency; electing a DR/BDR would provide zero reduction and is disabled by default.

• Trap: Assuming that all non-backbone areas can interconnect arbitrarily without Area 0.
  Debunked: OSPF strictly enforces a two-tier hierarchy. All non-backbone areas must attach directly to Area 0. Inter-area traffic cannot transit directly from Area 1 to Area 2 without traversing Area 0. If a physical disconnect occurs, a Virtual Link must be explicitly configured through a transit area to restore logical continuity to Area 0.

---

🗺️View Complete Computer Networks Roadmap & Syllabus

← Previous Topic5.2 Count-to-Infinity Problem, Split Horizon & Poison ReverseNext Topic →5.4 Border Gateway Protocol (BGP) & Path Vector Routing