Recall warm-up
- Why did Distance Vector suffer from count-to-infinity when link B–C broke?
Stuck? Peek at 3.4.3 Count-to-infinity, Split Horizon & Poison Reverse
- Count-to-infinity: Bad news (link failure) causes neighbours to bounce increasing costs back and forth; RIP caps this with infinity = 16 (max valid hops = 15).
- Split Horizon: Do not advertise a route back to the next-hop neighbour v*.
- Poison Reverse: Advertise
Dₓ(y) = ∞to the next-hop neighbour v* (fixes 2-node loops, not 3+ node loops).
- In a weighted router graph with V vertices and positive edge weights, what is the cost of a path?
Stuck? Peek at 3.4.1 Routing vs forwarding, weighted-graph model & shortest paths
- Forwarding = local per-packet lookup (data plane); Routing = network-wide shortest-path computation (control plane).
- Graph model: routers = vertices V, links = edges E with positive cost c(u, v).
- Routing table entry at u for d: stores
(Destination d, Cost D_u(d), Next Hop = first neighbour along shortest path).
- When a broadcast message is sent on a network containing cycles without any duplicate-suppression rule, what happens?
Stuck? Peek at 2.3.1 The multiple access problem; collisions; channel partitioning
- Collision: overlapping transmissions on a shared link; all involved frames lost.
- MAC families: partitioning (TDMA/FDMA), random access (send freely, recover from collisions), taking turns (an orderly schedule).
- TDMA/FDMA: R/N per station, no collisions, idle shares wasted, wait up to (N − 1) slots.
The Hook
What if we abandon "routing by rumour" completely? Instead of telling neighbours your guesses about distant nodes, every router measures the cost to its own direct neighbours, packs that list into a small Link-State Packet (LSP), and floods it to every router in the network.
Once every router has collected the LSP from every other router, every router possesses the exact same complete map of the network — and locally runs Dijkstra's shortest-path algorithm to compute a loop-free shortest-path tree!
Predict First
If Router A sends a Link-State Packet to its neighbours B and C, and B forwards it to C and D while C forwards it back to B and A, why doesn't the LSP bounce around the network forever?
,Because every LSP carries the sender's ID and a monotonically increasing Sequence Number! Each router remembers the highest sequence number it has seen from each source router: if an arriving LSP has a sequence number ≤ the stored one, it is a duplicate (or stale) and is immediately discarded without re-flooding.
Core Concept
Phase 1 of Link State: LSPs & Controlled Flooding
Link State routing (used by OSPF) works in two phases. In Phase 1, each router builds a Link-State Packet (LSP) containing:
- Router ID of the creator,
- List of direct neighbours and link costs
[(v, c(u, v))], - Sequence Number (incremented every time the router generates a new LSP), and
- Age / TTL (decremented periodically and at each hop; when Age hits 0, the LSP is expired so dead routers don't stay in the map forever).
• If seq > highest_seq_seen[s]: record it, and forward a copy out of every interface except I.
• Otherwise (seq ≤ highest_seq_seen[s]): discard it!
Phase 2 of Link State: Dijkstra’s Shortest-Path Algorithm
Once router s has the full graph G = (V, E), it runs Dijkstra's algorithm maintaining a permanent set N' (nodes whose shortest path from s is known for sure) and a tentative distance D(v) for every node:
- Initialise:
N' = {s},D(s) = 0. For each v ≠ s:D(v) = c(s, v)if v is a neighbour of s, else∞. - Loop until N' = V:
a) Pick node u ∉ N' with the smallest tentative D(u), and add u to N'.
b) Relax every neighbour v ∉ N' of u:D(v) = min( D(v), D(u) + c(u, v) )(if improved, setprev[v] = u).
Complete Step-by-Step Dijkstra Trace Table
Let's trace Dijkstra from source A on the 6-router graph above (A–B=2, A–C=5, B–C=1, B–D=4, C–E=3, D–E=1, D–F=5, E–F=2):
| Step | Permanent Set N’ | Picked u | D(B), prev | D(C), prev | D(D), prev | D(E), prev | D(F), prev |
|---|---|---|---|---|---|---|---|
| Init (1) | {A} | A (D=0) | 2, A | 5, A | ∞ | ∞ | ∞ |
| 2 | {A, B} | B (D=2) | 2, A (done) | 3, B (2+1<5!) | 6, B (2+4) | ∞ | ∞ |
| 3 | {A, B, C} | C (D=3) | 2, A | 3, B (done) | 6, B | 6, C (3+3) | ∞ |
| 4 | {A, B, C, D} | D (D=6) | 2, A | 3, B | 6, B (done) | 6, C (6+1=7>6) | 11, D (6+5) |
| 5 | {A, B, C, D, E} | E (D=6) | 2, A | 3, B | 6, B | 6, C (done) | 8, E (6+2<11!) |
| 6 | {A,B,C,D,E,F} | F (D=8) | 2, A | 3, B | 6, B | 6, C | 8, E (done) |
Putting it together
- In Link State routing, each router floods a Link-State Packet (LSP) containing only its direct link costs to all routers in the network.
- Sequence numbers prevent LSPs from looping during flooding, while Age fields expire outdated topology data.
- Every router obtains the complete network graph and runs Dijkstra’s algorithm locally in O(V²) time to build a loop-free shortest-path tree.
Visual
| Destination | Shortest Path from A | Total Cost D(v) | Parent prev[v] | Next Hop from A |
|---|---|---|---|---|
| B | A → B | 2 | A | B |
| C | A → B → C | 3 | B | B |
| D | A → B → D | 6 | B | B |
| E | A → B → C → E | 6 | C | B |
| F | A → B → C → E → F | 8 | E | B |
Worked Examples
In the 6-router network above, why is edge A–C (cost 5) NOT part of Router A's shortest-path tree even though C is a direct neighbour of A?
Show the full solution
Because in Step 2, after B is added to N' with D(B) = 2, relaxing edge B–C (cost 1) gives D(B) + c(B,C) = 2 + 1 = 3 < 5. So the 2-hop path A → B → C is cheaper than the direct link!
In what exact order are nodes added to the permanent set N' when running Dijkstra from A on the 6-router graph (breaking ties alphabetically), and what are their final shortest distances?
Show the full solution
Order: A (0), B (2), C (3), D (6), E (6), F (8). (At Step 4, both D and E have tentative distance 6; breaking ties alphabetically picks D first, then E.)
A network has N routers and E bidirectional links. When a single link's cost changes, the two routers at its ends flood new LSPs across the network. During controlled flooding of ONE new LSP across a connected network of N nodes and E links, what is the upper bound on how many times that LSP is transmitted over links?
Show the full solution
Each of the N routers accepts the new LSP (with its fresh sequence number) at most once and forwards it out of all its incident links except the one it arrived on (or at most once along each direction of each link). Across E links, an LSP travels at most twice per link (once in each direction) → O(E) link transmissions (specifically at most 2E − (N − 1) transmissions)!
GATE Traps
- Predecessor ≠ Next Hop! In our trace,
prev[F] = E, which means E is the node right before F. To find A's next hop, trace back to the child of A (which is B). - LSP Sequence Number is NOT a packet byte number: It is a version counter per originating router so other routers can tell a newer LSP from a duplicate or older LSP.
- Dijkstra requires non-negative edge weights (c(u, v) ≥ 0), which is always satisfied by physical network link costs.
Memory Hook
Flood the puzzle pieces (LSPs with Seq# & Age) to everyone; then each router solves the puzzle alone with Dijkstra!
Connect the Dots
Now we have seen both great families of intra-domain routing: Distance Vector (3.4.2–3.4.3) and Link State (3.4.4). Next question (3.4.5): How do they compare head-to-head on message overhead, convergence speed, loops, and robustness?
Self-Test
- MCQ
In Link State routing, how are Link-State Packets (LSPs) distributed, and what prevents them from looping forever during distribution?
- Sent only to immediate neighbours; Split Horizon prevents loops.
- Flooded to all routers in the routing area; a sequence number (and age field) in each LSP prevents duplicates from being re-forwarded.
- Sent only to a central server; the server deletes duplicates.
- Broadcast using Ethernet FF:FF:FF:FF:FF:FF across all routers; routers never forward them.
- NAT
Using the 6-router graph from this lesson (A–B=2, A–C=5, B–C=1, B–D=4, C–E=3, D–E=1, D–F=5, E–F=2), what is the shortest-path distance from A to F?
Write your answer before opening the key.
- MCQ
In the same 6-router graph, after Router A finishes running Dijkstra’s algorithm, what is the predecessor of E (prev[E]) and what is Router A’s outgoing next-hop router for packets destined to E?
- Predecessor = C, Next hop from A = C
- Predecessor = C, Next hop from A = B
- Predecessor = B, Next hop from A = B
- Predecessor = D, Next hop from A = B
- MSQ
Which of the following fields are carried inside a Link-State Packet (LSP)?
- The ID of the router that created the LSP.
- A list of the router’s direct neighbours and the cost of the link to each.
- A sequence number and an age (TTL) field.
- The router’s complete shortest-path distance to every non-neighbour node in the network.
Rule Card
- LSP contents:
(Router ID, Direct Neighbours & Costs, Sequence #, Age)— distributed to all routers via controlled flooding. - Dijkstra: Greedily add min-D(u) node to permanent set N', then relax neighbours:
D(v) = min(D(v), D(u) + c(u, v)); time O(V²) or O((V+E) log V). - Next hop from source s to d = first node after s on the path traced backwards via
prev[].
Concept Ledger
- link state
- link-state packet (LSP)
- flooding
- LSP sequence number and age
- Dijkstra's algorithm
- tentative and permanent sets
- shortest-path tree
Answer Vault
Try the questions first. Open when you are ready to check.
Warm-up answers
- Because routers only heard numerical distances from neighbours without knowing the full topology or that the neighbour’s path looped back through them.
- The sum of the weights of all edges along that path.
- Packets multiply and circulate around the cycles forever (a broadcast storm).
Self-test answers
- B — LSPs are distributed by controlled flooding; each router checks the originating router’s sequence number and discards any LSP it has already seen.
- A: That is Distance Vector.
- C: Link State is distributed; every router computes its own tree.
- D: Layer-2 broadcast stops at the first router; LSPs are flooded hop-by-hop across routers.
- 8 — The shortest path is A → B (2) → C (+1=3) → E (+3=6) → F (+2=8), total cost = 8.
- B — The shortest path to E is A → B → C → E (cost 2 + 1 + 3 = 6). Thus the node immediately before E (predecessor) is C, while the first hop out of A is B.
- A: Direct A → C → E would cost 5 + 3 = 8 > 6; A goes to B first!
- C: B is the next hop from A, but C is the immediate predecessor of E.
- D: Path A → B → D → E costs 2 + 4 + 1 = 7 > 6.
- ABC — An LSP carries the origin router ID, its direct neighbour link costs, a sequence number, and an age field. Distances to non-neighbours are computed locally by Dijkstra, not put in the LSP.
- D: Advertising distances to all destinations is Distance Vector, not Link State.
Flashcards
- What 4 items are inside a Link-State Packet (LSP)?
Reveal answer
1. Origin Router ID; 2. Direct neighbours + link costs; 3. Sequence number; 4. Age (TTL). - What is the purpose of the Sequence Number vs the Age field in an LSP?
Reveal answer
Sequence Number stops duplicate/old LSPs during flooding; Age expires stale LSPs if a router crashes. - Write the Dijkstra relaxation formula when node u is added to N’.
Reveal answer
For each neighbour v ∉ N’ of u: D(v) = min(D(v), D(u) + c(u, v)). - How do you find source A’s next hop to destination F from Dijkstra’s prev[] array?
Reveal answer
Trace prev[F] backwards until you reach a direct child of A; that child is the next hop.
Exam shortcuts
- Dijkstra Time Complexity: With a simple array scan, O(V²); with a binary min-heap priority queue, O((V + E) log V). — GATE algorithm/networking cross-over questions.
- Parent vs Next-Hop Trap: In Dijkstra's table for source
A, the columnprev[F] = Eis the predecessor (last hop before F), whereasA's forwarding table needs the first hop after A (trace backwards from F:F ← E ← C ← B ← A→ Next Hop is B!). — avoiding the #1 GATE mistake on Dijkstra tables.