A packet crossing the internet is steered by routing algorithms that every router runs to decide where to send it next. Two families dominate the syllabus: distance vector and link state. Aspirants lose marks by blurring the two and by never hand-running Dijkstra. One decision splits the families: share your distances with your neighbours, or share your links with everybody. Convergence speed, memory cost and the count-to-infinity trap all follow from that single choice.
Routing versus forwarding
These two words are not synonyms, and examiners test the difference. Routing is the network-wide process of computing good paths and filling each router's routing table; it is relatively slow and runs in the background. Forwarding is the local, per-packet action of moving a packet from an input port to the correct output port using the table that routing already built; it happens in nanoseconds. Routing builds the map, forwarding follows it. Both act on the packet's destination prefix, so the subnetting rules in IP Addressing and Subnetting Explained decide which table entry a packet actually matches.
Distance vector routing
In distance vector routing, each router knows only its directly connected neighbours and the cost to reach them. It maintains a vector of estimated distances to every destination and periodically shares that whole vector with its neighbours. Each router then updates its own estimates from what neighbours report.
The Bellman-Ford update
The core rule is the Bellman-Ford equation. For a router x reaching destination y, the estimated cost is the minimum over each neighbour v of (cost from x to v) plus (v's advertised cost to y):
Dx(y) = min over v of ( c(x, v) + Dv(y) )
Each router recomputes this whenever a neighbour's vector changes, and readvertises if its own estimate changed. The estimates converge to true shortest paths, but only gradually, because news spreads one hop per exchange.
Count-to-infinity
Distance vector's weakness is the count-to-infinity problem. When a link fails, the bad news travels slowly, and two routers can keep incrementing their estimates of a now-unreachable destination, each believing the other still has a path.
Trace it on a three-router chain X, Y, Z, every link costing 1, with X as the destination. Y reaches X at 1, and Z reaches X at 2 through Y. Now the X-Y link fails. Before Y's bad news arrives, Z advertises its stale cost of 2, so Y computes 1 + 2 = 3 and advertises that. Z then computes 1 + 3 = 4, Y climbs to 5, Z to 6, and the pair keeps counting, each router adding two to its own estimate every round. RIP caps the climb by defining 16 as infinity, which is why its usable network diameter is only 15 hops.
Partial fixes include split horizon (do not advertise a route back to the neighbour you learned it from) and poison reverse (advertise it back with a cost of infinity rather than staying silent). This slow, loop-prone convergence is the standard exam critique of distance vector.
Link state routing
Link state routing takes the opposite approach. Each router discovers the cost to its own neighbours, then floods that information (a link-state packet) to every router in the network. After flooding, every router holds an identical, complete map of the topology and independently computes shortest paths using Dijkstra's algorithm.
Flooding means each router forwards a received link-state packet on all links except the one it arrived on, so the map propagates network-wide quickly. Because every router has the full topology, link state converges faster and avoids count-to-infinity, at the cost of more memory and flooding overhead.
Distance vector vs link state: the side-by-side
One difference generates every other: a distance vector router knows only what its neighbours tell it, while a link state router holds the whole map and reasons about it alone.
Distance vector | Link state | |
|---|---|---|
What each router knows | Its neighbours and the distance vectors they advertise | The complete topology: every router and every link cost |
What it shares, and with whom | Its entire distance vector, to directly connected neighbours only | Its own link costs, flooded to every router in the network |
Algorithm | Bellman-Ford, applied to advertised distances | Dijkstra, applied to the full map |
Convergence | Slow: news moves one hop per exchange | Fast: one flood, then every router computes at once |
When a link fails | Count-to-infinity, needing split horizon and poison reverse | No count-to-infinity, because nobody relies on a neighbour's summary |
Main cost | Slow, loop-prone settling while estimates catch up | Memory for the whole map, plus flooding traffic |
Textbook protocol | RIP, using hop count as its metric | OSPF, flooding link states and running Dijkstra |
A worked Dijkstra shortest-path tree
Take five routers, A through E, with these link costs:
A-B: 2, A-C: 6, A-D: 8, A-E: 9
B-C: 1, B-D: 2, C-D: 4
C-E: 5, D-E: 1
Run Dijkstra from source A. Start with distance to A as 0 and every other node as infinity, then repeatedly finalise the nearest unfinalised node and relax its neighbours.
Finalise A at 0. Relax neighbours: B becomes 2, C becomes 6, D becomes 8, E becomes 9.
The nearest unfinalised is B at 2. Relax from B: C via B is 2 + 1 = 3, which beats 6, so C becomes 3; D via B is 2 + 2 = 4, which beats 8.
Next nearest is C at 3. Relax from C: D via C is 3 + 4 = 7, which loses to the standing 4; E via C is 3 + 5 = 8, which beats 9, so E becomes 8.
Next is D at 4. Relax from D: E via D is 4 + 1 = 5, which beats 8, so E becomes 5.
Finalise E at 5. All nodes done.
The final shortest distances from A are: B = 2, C = 3, D = 4, E = 5. The shortest-path tree uses the edges that gave each final value: A-B, B-C, B-D, and D-E. Note E is reached through D, not directly through C, because A-B-D-E costs 2 + 2 + 1 = 5 while A-B-C-E costs 2 + 1 + 5 = 8.
Draw this once and confirm every relaxation by hand. Exams give you exactly such a weighted graph and ask for the shortest-path tree or the distance to one node.
Where RIP and OSPF fit
The two families map onto two real protocols you should name. RIP (Routing Information Protocol) is a distance vector protocol using hop count as its metric, simple but limited and slow to converge. OSPF (Open Shortest Path First) is a link state protocol that floods link states and runs Dijkstra, scaling to large networks with faster convergence. RIP is the textbook distance vector example; OSPF is the textbook link state example.
How routing algorithms are tested in GATE, NET, and placements
GATE CS sets Dijkstra numericals (compute the shortest-path tree or a specific distance on a given graph), distance-vector table-update problems (apply Bellman-Ford for a round or two), and count-to-infinity tracing. Distinguishing routing from forwarding is a recurring conceptual item.
UGC NET Computer Science favours the comparisons: distance vector versus link state, which protocol is which, and what flooding and split horizon mean. Definitions and protocol mapping score here.
Placement and company tests ask which algorithm the internet's interior routing uses and why link state converges faster, expecting the full-topology-versus-neighbour-only contrast.
Across all three, the same two skills do the work: a correct Bellman-Ford update and a correct Dijkstra trace. The network layer chapter of the Computer Networks learn module keeps routing next to the addressing and transport topics these questions mix in.
The short version
Routing computes paths, forwarding moves packets. Distance vector shares distance vectors with neighbours via Bellman-Ford and suffers count-to-infinity; link state floods the full topology and runs Dijkstra, converging faster. Map them to RIP and OSPF, then hand-run Dijkstra until the tree is automatic. Once a packet has been routed, the services riding on it are the ones in Application Layer Protocols: DNS, HTTP, and email, and GATE Guidance by Sanchit Sir sequences routing with the rest of the network layer. Learn the Dijkstra trace cold, and routing questions become dependable marks.
