GATE DA · Computer Networks Topic 5 — Routing Protocols

Topic 5 — Routing Protocols

Shortest Path (Dijkstra) · Flooding · Distance-Vector · Link-State
(GATE CS&IT · Computer Networks · Network Layer)

0. Topic header & syllabus map

• Subject: Computer Networks
• Layer: Network layer (Layer 3) — the path-finding half of it.
• Where it sits: Comes after IP addressing / CIDR / subnetting & fragmentation (Topic 4), which gave
us prefixes to route to and the longest-prefix-match rule that uses a forwarding table. It leads into
IP support protocols & NAT (Topic 6: ARP/DHCP/ICMP/NAT), which operationalize the next-
hops that routing computes.

If Topic 4 was “how to name and address a network,” Topic 5 is “how every router figures out which
way to send a packet to reach that network — automatically, and even when links fail.”

1. Why this topic exists (motivation + connection)

Topic 4 ended with a forwarding table of the form destination prefix → next-hop, cost, and the
rule “forward on the longest matching prefix.” But it left one giant question unanswered: who fills
in the next-hop column?
For a single router with two links you could type the table by hand. The real Internet has hundreds
of thousands of prefixes, links that fail, change cost, and appear, and no single machine that sees
the whole map at once. Hand-configuration is impossible and would never stay correct. Routing
protocols are the distributed algorithms that automatically compute and continuously repair every
router’s forwarding table.
What the previous topic couldn’t do: - CIDR/subnetting told us how to write a destination and how
forwarding consumes a table — but said nothing about how the table gets built or how it heals after a
link goes down. Longest-prefix match presupposes the prefix → next-hop mapping already exists.
Routing is exactly the process that produces that mapping.
What the next topic builds on this: - Routing yields a next-hop IP address. To actually put bits on
a wire, the router must translate that next-hop IP into a link-layer MAC → ARP (Topic 6). When
routing fails (no route, TTL hits 0, fragmentation needed with DF set) the bad news is reported by
ICMP (you already met ICMP in Topic 4 as the “Time Exceeded”/“Frag needed” messenger). DHCP
hands out the very addresses routing distributes paths for, and NAT lets private RFC-1918 networks
— which still run internal routing — share public addresses.

2. Prerequisites
• Weighted graphs: vertices, edges, edge weights, paths, cost of a path = sum of edge weights.
• IP prefixes & forwarding tables (Topic 4): destinations are prefixes; a table maps destination
→ next-hop.
• Shortest-path algorithms (from Algorithms): Dijkstra and Bellman-Ford — restated here in net-
work terms.
• Data structures: priority queue / min-extraction (Dijkstra), simple arrays/vectors (distance-
vector).

1
GATE DA · Computer Networks Topic 5 — Routing Protocols

• Min/ceil arithmetic and Big-O for complexity and convergence questions.

3. Core idea — intuition first

Model the network as a weighted graph: routers = nodes, links = edges, link cost = edge weight
(hop count, delay, or 1/bandwidth). Routing = find, from each router, the least-cost path to every
destination, then store only the first hop of that path — because the next router will repeat the com-
putation and take it from there. (That’s why a forwarding table only needs a next-hop, not the whole
route.)
Doing this in a distributed way (no node sees the full graph initially) gives two grand philosophies
— and the easiest way to never confuse them is this pair of slogans:

• Distance-Vector = “tell your neighbors about the world.” Each router knows only the cost to its
direct neighbors, and periodically hands each neighbor its entire table of best-known distances
to every destination. Routers fold neighbors’ tables into their own (Bellman-Ford) and converge.
It’s routing by rumor: you learn how far Delhi is by asking your neighbors how far they think it is,
plus the cost to reach them. Weakness: bad news travels slowly (count-to-infinity).
• Link-State = “tell the world about your neighbors.” Each router measures the cost to its direct
neighbors only, then floods that tiny fact to every router. Soon everyone holds the entire map,
and each runs Dijkstra locally to compute its own shortest-path tree. Like every street corner pub-
lishing its immediate connections so each person can draw the whole city and route themselves.

Flooding is the brute-force baseline — send a received packet out every link except the one it arrived on. It’s
spectacularly robust (needs no tables) and is the mechanism link-state uses to spread its link-state
packets, but uncontrolled it explodes, so we bolt on controls.
Dijkstra is the engine link-state runs; Bellman-Ford is the engine behind distance-vector. Keep
that pairing in your head.

4. Formal treatment
4.0 Routing vs forwarding (a distinction GATE explicitly tests)
• Forwarding = the per-packet, local action: look the destination up in the table, push the packet
out the right interface. Fast — the data plane.
• Routing = the network-wide, background process that computes those tables. Slower — the control
plane.
• Routing builds the routing table; a distilled copy (the forwarding table / FIB) is consulted for
each packet.

4.1 Network as a graph + path cost

• G = (V, E), edge (u,v) has cost c(u,v) ≥ 0. Cost of a path = sum of its edge costs.
• Goal: least-cost (a.k.a. shortest) path from a source to each destination.
• Metrics: hop count (RIP), or cost ∝ 1/bandwidth, or delay (OSPF). The “shortest” path depends
entirely on the metric chosen.

2
GATE DA · Computer Networks Topic 5 — Routing Protocols

Routing: pick least-cost paths over the network graph

B 3
2 D
A 1 1
5
6 E
C
shortest path A E (Dijkstra): A B D E, cost 6

Figure 1. Routing treats the network as a weighted graph and finds least-cost paths; here the shortest path A→E
(Dijkstra) is A–B–D–E with cost 6.

4.2 Classification (vocabulary GATE uses)

• Static (hand-configured) vs dynamic/adaptive (protocol-driven). GATE focuses on dynamic.
• Global / Link-State (each node has the full topology) vs Decentralized / Distance-Vector (each
node has only local info + neighbor exchanges).
• Intra-domain (IGP): RIP (distance-vector), OSPF (link-state). Inter-domain (EGP): BGP (path-
vector, AS-level — GATE-light, see §4.10).

4.3 Flooding
• Pure (uncontrolled) flooding: every node sends each incoming packet out all links except the
incoming one. Every reachable node receives it; guaranteed delivery if a path exists, and it needs
no routing tables (maximally robust). But it generates a storm of duplicates and loops forever
unless controlled.
• Controls:
– Hop count / TTL: decrement per hop, drop at 0 → bounds the packet’s life.
– Sequence numbers: each node remembers (source, seq#) already seen and discards dupli-
cates → kills loops; each node forwards a given packet only on first receipt.
– Reverse-Path Forwarding (RPF): forward only if the packet arrived on the link the node would
use to send back to the source → approximates a broadcast tree (used in broadcast/multicast).
• Uses: initial LSP distribution in link-state, network-wide broadcast, robust/military networks,
building broadcast trees.
• Counting transmissions (controlled, duplicate-suppressed): if each node forwards a packet ex-
actly once, to all neighbors except the one it first received from, then for a connected graph with
N nodes and E edges:

Total packet transmissions = Σ_v deg(v) − (N − 1) = 2E − (N − 1)

Why: the source forwards over deg(source) links; every other node forwards over deg(v) − 1 links
(all but its incoming link). Summing: 2E (handshake lemma) minus 1 for each of the (N−1) non-
source nodes. (Independent of which node is the source.)

3
GATE DA · Computer Networks Topic 5 — Routing Protocols

4.4 Dijkstra’s shortest-path algorithm (the link-state engine)

Single-source shortest paths, non-negative edge weights.
State: a finalized set S, tentative distances D[v], predecessor pred[v] (for path reconstruction).
1. D[source] = 0; D[all others] = ∞; S = ∅
2. while some node is not in S:
3. pick u ∉ S with the smallest D[u]; add u to S (u is now "finalized")
4. for each neighbor v of u not in S: (RELAX)
5. if D[u] + c(u,v) < D[v]:
6. D[v] = D[u] + c(u,v); pred[v] = u

• Forwarding table: each router runs Dijkstra with itself as source; for each destination, the next-
hop = the first node on the path (follow pred[] back until you reach a neighbor of the source).
• Complexity: O(V²) with a linear min-scan; O((V + E) log V) with a binary heap. Number of
“extract-min” iterations = V; total relaxations ≤ E.
• CRITICAL assumption: weights must be ≥ 0. Dijkstra can produce wrong answers with negative
edges (a finalized node might later get a cheaper path). Link costs are non-negative in practice,
which is why link-state can safely use Dijkstra.

4.5 Link-state routing (e.g., OSPF)

Each router: 1. Discovers neighbors and the cost to each (periodic HELLO packets). 2. Builds a
Link-State Packet (LSP/LSA): { router-ID, list of (neighbor, cost), sequence number,
age/TTL }. 3. Reliably floods the LSP to all routers. Duplicates/stale copies are suppressed by the
sequence number (newer wins) and age (old LSPs expire). 4. Once it holds every router’s LSP, each
router has an identical, complete topology database and runs Dijkstra locally → shortest-path tree
→ forwarding table.
Properties: - Fast convergence; NO count-to-infinity (every router computes independently from
the full map, so no slow rumor chains). - Higher memory (full topology) and higher CPU (Dijkstra)
than distance-vector. - LSP flooding overhead, but mostly only on change (plus periodic refresh).
- Loop-resistant thanks to a consistent global view (only brief transient loops). - A useful counting
fact: in a network of N routers and L links, there are N distinct LSPs (one per router) and 2L total link-
entries across all LSPs (each link is reported by both its endpoints). - OSPF essentials (GATE-light):
hierarchical areas, cost ∝ 1/bandwidth, runs directly over IP (protocol 89).

4.6 Distance-vector routing (Bellman-Ford; e.g., RIP)

The core update (the Bellman-Ford equation) — memorize this:
D_x(y) = min over each neighbor v of { c(x, v) + D_v(y) }

where D_x(y) = least cost from x to y; c(x,v) = cost of the direct link x→v; D_v(y) = the distance to
y that neighbor v advertises.

Each router x: 1. Knows c(x,v) to each direct neighbor v. 2. Keeps a distance vector D_x = [
D_x(y) for every destination y ] (plus the next-hop achieving each min). 3. Periodically (and
on change) sends its whole vector to all neighbors. 4. On receiving a neighbor’s vector, recomputes
via Bellman-Ford; if anything changed, sends an update.
Properties: - Low memory, simple (just vectors + next-hops). - Good news travels fast (a new
shorter path propagates in ≤ diameter rounds), bad news travels slowly → the count-to-infinity
problem. - “Routing by rumor”: trusts neighbors’ summaries without ever seeing the topology. -
RIP essentials (GATE-tested): metric = hop count, infinity = 16 (so the maximum usable path length
= 15 hops; 16 means unreachable), updates every 30 s, runs over UDP port 520. The small infinity (16)
is precisely what bounds count-to-infinity.

4
GATE DA · Computer Networks Topic 5 — Routing Protocols

4.7 The count-to-infinity problem (almost guaranteed on GATE)

When a destination/link fails, distance-vector routers can keep believing a path still exists through
each other, incrementing the cost by 1 each round (…→ 4 → 5 → 6 …) until it crawls up to “infinity.”
The unreachability (bad news) propagates only one hop per exchange, so a routing loop persists for
many rounds.
Root cause: a router accepts a neighbor’s advertised distance to a destination without knowing that
the advertised path runs back through itself.
Mitigations: - Small infinity (RIP = 16): caps the counting so it terminates quickly instead of literally
forever. - Split horizon: never advertise a route back to the neighbor you learned it from. - Split horizon
with poison reverse: advertise it back, but with cost = infinity (an explicit “do not route through
me to reach there”). - Route poisoning + triggered updates + hold-down timers: push bad news
immediately and freeze a flapping route for a while.
Crucial nuance (a favorite trap): split horizon and poison reverse eliminate the two-node loop, but
they do NOT guarantee freedom from count-to-infinity in loops of three or more routers. Link-state
avoids the whole problem entirely.

4.8 Distance-Vector vs Link-State (the comparison GATE asks)

Aspect Distance-Vector (RIP) Link-State (OSPF)

What a node knows Best distance to every destination The entire topology (full map)
via its neighbors; only local link
costs natively
What it sends Its whole distance vector Its own link-states (neighbor list +
costs)
To whom Only its direct neighbors All routers (flooded)
Algorithm Bellman-Ford Dijkstra
Convergence Slow; count-to-infinity Fast; no count-to-infinity
Memory Low High (full topology DB)
Message scope Local (neighbors) Global (flood)
Failure behaviour Loops, slow bad news Consistent view, quick recompute
Examples RIP, IGRP OSPF, IS-IS

Mnemonic again: DV = “tell neighbors about the world” (whole vector, to neighbors). LS =
“tell the world about your neighbors” (your links, to everyone).

4.9 Hierarchical routing (GATE-light, conceptual)

Flat routing doesn’t scale (table size, computation, message volume). Group routers into re-
gions/areas/Autonomous Systems: a router keeps full detail within its region and only summa-
rized info about others. This shrinks tables dramatically, at the cost of occasionally non-optimal
inter-region paths. Realized as OSPF areas and, at Internet scale, the AS hierarchy glued together by
BGP.

4.10 Path-vector / BGP (one paragraph — minimal GATE weight)

BGP is the inter-AS protocol. It’s distance-vector-like but advertises the entire AS-path rather than
just a distance. Carrying the full path lets a router reject any path that already contains its own AS
(instant loop prevention) and lets operators apply policy. GATE CN touches this only conceptually.

5
GATE DA · Computer Networks Topic 5 — Routing Protocols

5. Worked problems (GATE-style)

Q1 — Dijkstra trace (NAT + path)
Graph (undirected, edge costs shown): A–B = 1, A–C = 4, B–C = 2, B–D = 6, C–D = 3, C–E =
5, D–E = 1. Find the shortest distance from A to every node, and the shortest path (and next-hop)
from A to E.
Solution — run Dijkstra from A:

Step Finalize (D) Updated tentative distances

init — A=0, B=∞, C=∞, D=∞, E=∞

1 A=0 B=1, C=4
2 B=1 C=min(4,1+2)=3(via B), D=1+6=7
3 C=3 D=min(7,3+3)=6(via C), E=3+5=8
4 D=6 E=min(8,6+1)=7(via D)
5 E=7 done

Distances: A=0, B=1, C=3, D=6, E=7. Shortest path to E (follow predecessors): E ← D ← C ← B ←
A ⇒ A–B–C–D–E, cost 7 (beats A–C–E=9, A–B–C–E=8, A–B–D–E=8, A–C–D–E=8). Next-hop from
A to E = B. ∎

Q2 — One Bellman-Ford update (NAT, trap variety)

Router X has neighbors A, B, C with link costs c(X,A)=2, c(X,B)=1, c(X,C)=5. They advertise
distances to destination Z: D_A(Z)=3, D_B(Z)=7, D_C(Z)=1. Find D_X(Z) and the next-hop.
Solution. Apply D_X(Z) = min_v { c(X,v) + D_v(Z) }: - via A: 2 + 3 = 5 - via B: 1 + 7 = 8 - via C:
5+1=6
D_X(Z) = 5, next-hop = A. ∎ Trap: C advertises the smallest distance (1), so the careless pick is
C — but the expensive link c(X,C)=5 makes it worse. You minimize link + advertised, not the
advertised value alone.

Q3 — Distance-vector convergence over rounds (table)

Network: A–B=1, B–C=1, C–D=1, A–D=7. Each router starts knowing only its direct links and ex-
changes vectors synchronously each round. Show convergence; what is the final cost (and path)
A→D?
Round 0 (direct only):

node A B C D

A 0 1 ∞ 7
B 1 0 1 ∞
C ∞ 1 0 1
D 7 ∞ 1 0

Round 1 (each node applies Bellman-Ford to neighbors’ Round-0 vectors):

6
GATE DA · Computer Networks Topic 5 — Routing Protocols

node A B C D notable

A 0 1 2 7 C via B (1+1)
B 1 0 1 2 D via C (1+1)
C 2 1 0 1 A via B (1+1)
D 7 2 1 0 B via C (1+1)

Round 2 (using Round-1 vectors):

node A B C D notable

A 0 1 2 3 D via B (1+2): 7→3

B 1 0 1 2 stable
C 2 1 0 1 stable
D 3 2 1 0 A via C (1+2): 7→3

Round 3: no changes ⇒ converged. A→D cost = 3 along A–B–C–D; the expensive direct link A–D=7
is abandoned once the cheaper multi-hop path is learned. This is exactly “good news travels fast” —
full convergence in 2 rounds. ∎

Q4 — Count-to-infinity, and how split horizon helps (trace)

Network N is attached to router A; link A–B has cost 1. Initially D_A(N)=1 (direct) and D_B(N)=2 (via
A). The link from A to N fails (A–B stays up). Trace the distances without split horizon, then explain
the fix.
Without split horizon (synchronous rounds; A’s direct route to N is now ∞):

round D_A(N) D_B(N) why

0 1 2 steady state before

failure
1 3 2 A loses direct; believes
B’s “2” ⇒ 1+2=3 (loop!)
2 3 4 B believes A’s “3” ⇒
1+3=4
3 5 4 A ⇒ 1+4=5
4 5 6 B ⇒ 1+5=6
… ↑ ↑ climbs to RIP’s 16 =
unreachable, then both
declare N down

The two routers form a loop and “count to infinity” because A wrongly accepts a route to N that
actually leads back through A.
With split horizon: B learned N from A, so B never advertises N back to A. When A–N fails, A has
no false alternative → it sets D_A(N)=∞ immediately and tells B, which also goes to ∞ next round.
Bad news now propagates in ~1–2 rounds. Caveat (trap): this clean fix works for this 2-node loop;
in loops of 3+ routers, split horizon/poison reverse may still not fully prevent count-to-infinity. ∎

7
GATE DA · Computer Networks Topic 5 — Routing Protocols

Q5 — Flooding transmission count (NAT)

A connected network has N = 6 routers and E = 8 links. A single packet is flooded with duplicate
suppression (each node forwards once, to all neighbors except the one it first received from). How
many packet transmissions occur?
Solution. Total = 2E − (N − 1) = 2(8) − (6 − 1) = 16 − 5 = **11** transmissions. ∎ (Check
the logic on a triangle: 2·3 − 2 = 4 — source→2 neighbors, each neighbor→1 other = 4. 3)

Q6 — Conceptual MCQ/MSQ (pure recall, high frequency)

Which statements are TRUE? (i) RIP uses Dijkstra. (ii) OSPF floods link-state packets to all routers. (iii)
Distance-vector can suffer count-to-infinity. (iv) Dijkstra works correctly with negative edge weights.
(v) In link-state, each router sends its full distance-to-all-destinations table to neighbors.
Solution. - (i) False — RIP uses Bellman-Ford (distance-vector); OSPF uses Dijkstra. - (ii) True. -
(iii) True. - (iv) False — Dijkstra requires non-negative weights. - (v) False — that’s distance-vector.
Link-state floods its own link costs (neighbor list) to everyone, not a distance table.
True: (ii), (iii). ∎

6. Common GATE question types on this topic

• Trace Dijkstra: shortest distances, shortest-path tree, a specific path, or the next-hop for a desti-
nation.
• One Bellman-Ford update: compute D_x(y) and the next-hop from neighbor vectors + link costs
(watch the “smallest advertised ≠ best” trap).
• Distance-vector convergence: vectors after k rounds; final routing tables; number of rounds to
converge.
• Count-to-infinity: trace the climbing costs; effect of split horizon / poison reverse; how many
rounds to reach infinity / RIP’s 16.
• Flooding: number of packets/transmissions (2E − (N−1)); controlled vs uncontrolled; role of
sequence numbers/TTL.
• Link-state mechanics: number of LSPs (N) and link-entries (2L); why no count-to-infinity; relia-
bility of flooding.
• DV vs LS comparison: what’s exchanged, with whom, memory, convergence, algorithm used.
• RIP/OSPF facts: RIP infinity = 16 / max 15 hops / 30-s updates; OSPF = link-state + Dijkstra.
• Which algorithm does protocol X use? (RIP→Bellman-Ford, OSPF→Dijkstra, BGP→path-
vector.)

7. Traps, pitfalls & common mistakes

• Swapping DV and LS. DV sends its whole distance vector to neighbors; LS floods its own link
list to everyone. Anchor with the two slogans in §3.
• Bellman-Ford update trap: minimize c(x,v) + D_v(y), not just the smallest advertised D_v(y).
(Q2.)
• Dijkstra + negative weights = wrong answers. It needs c ≥ 0. (Use Bellman-Ford for negatives
— though real link costs are non-negative.)
• Count-to-infinity is a Distance-Vector disease, not Link-State.
• Split horizon / poison reverse fix 2-node loops but NOT all 3+-node loops. Don’t over-claim.
• Good news fast, bad news slow in DV — convergence time is not symmetric. LS converges fast

8
GATE DA · Computer Networks Topic 5 — Routing Protocols

either way.
• Next-hop is the FIRST hop on the shortest path, never the destination itself; reconstruct via pre-
decessors.
• RIP off-by-one: infinity = 16, so the largest usable path = 15 hops.
• Flooding without TTL/sequence numbers loops forever — uncontrolled flooding is unbounded.
• Stale LSPs in link-state are resolved by sequence number + age, not by arrival order — don’t
assume “last received = newest.”
• Forwarding ≠ routing: per-packet lookup (data plane) vs table computation (control plane).
• Metric dependence: “shortest” in hops can differ from “shortest” in delay or cost — always note
the metric.
• Flooding count formula assumes a connected graph and “forward once to all-but-sender”; if the
question changes the rule, recount from the method, not the formula.

8. Connection forward
Routing has now filled in the next-hop IP for every destination prefix — the column Topic 4 left blank.
But a next-hop IP can’t be put on a wire directly: the router must resolve it to a link-layer MAC address
→ ARP (Topic 6). When routing breaks (no route, TTL = 0, fragmentation-needed-with-DF), ICMP
carries the diagnostic back to the source — the same ICMP you first met behind Path-MTU discovery
in Topic 4. DHCP auto-assigns the addresses these routes lead to, and NAT lets entire private (RFC-
1918) networks — which still run their own internal routing — share a handful of public addresses.
So Topic 6 is the “make it actually work and tell us when it doesn’t” layer wrapped around the routing
you just built.

9. One-line cheat-sheet summary

Model the net as aweighted graph; Distance-Vector = Bellman-Ford

D_x(y)=min_v{c(x,v)+D_v(y)}, sends its whole vector to neighbors, slow + count-to-
infinity (RIP, ∞=16, max 15 hops, fix with split-horizon/poison-reverse); Link-State =
flood your neighbor-costs to everyone then run Dijkstra (non-negative weights only), fast
+ no count-to-infinity (OSPF); flooding delivers via every-link-but-incoming, controlled
cost = 2E − (N − 1).

Next topic (in order)

Topic 6 — IP support protocols & NAT (ARP, DHCP, ICMP, and Network Address Translation). Ask
for it when you’re ready and I’ll generate it in the same format.