CS Core & Software Engineering · Computer Networks

How a Packet Finds a Path

Routes as next hops, distance-vector Bellman-Ford, count-to-infinity, and link-state Dijkstra.

The phone and the shop are on different networks, so an address is not enough. This lesson is the walk: a route is a next hop for a prefix, distance-vector routers believe neighbours, and link-state routers flood a map and run Dijkstra. The tea-page packet is forwarded one hop at a time.

CS Core & Software Engineering
Medium level
4 concepts
1 practice questions

1A route is a next hop, not an address

An IP address names a host. A route says what to do with a packet whose destination is not on this network. Meera's phone is 192.168.1.42/24. The shop is 203.0.113.10, which is not in 192.168.1.0/24. So the phone does not ARP for the shop. It sends the packet to its default gateway 192.168.1.1 — 'if the destination is not on my prefix, give it to this next hop.'

The home router looks in its routing table: a list of prefixes and next hops. One row says 203.0.113.0/28 via the ISP. The ISP has its own row toward the shop. Each hop only needs the next hop, not the whole path. Addressing named the two ends. Routing chooses the walk between them.

Figure. The phone never ARPs for the shop. Each box only knows the next hop toward 203.0.113.0/28.

How the tea-page packet leaves home

Same prefix?Shop 203.0.113.10 is not in 192.168.1.0/24, so the phone will not ARP for the shop.
Default gatewayThe phone sends the packet to 192.168.1.1, the next hop off the home network.
Router rowThe home router matches 203.0.113.0/28 and forwards to the ISP. Each hop repeats.

Meera's phone is 192.168.1.42/24 and wants 203.0.113.10. What does it do first?

ARP for 203.0.113.10 on the home Wi-Fi
Send the packet to the default gateway 192.168.1.1
Rewrite its own address to 203.0.113.10

203.0.113.10 is not in 192.168.1.0/24, so the phone sends to its gateway. ARP for the shop would only work if the shop were on the same LAN. Rewriting the phone's address is NAT, later, on the router.

2Distance vector and Bellman-Ford

A distance-vector router does not hold a map of the whole Internet. It holds a table of distances — estimated costs — to prefixes, and it hears those distances only from its neighbours. Bellman-Ford is the update rule: for destination y, router x sets D_x(y) = \min_v\{c(x,v)+D_v(y)\}. c(x,v) is the cost of the link from x to neighbour v. D_v(y) is what v claims y costs from v. x adds the link cost to each neighbour's claim and keeps the cheapest.

RIP is the classic protocol that speaks this way: tell your neighbours your whole distance table. The shop's packets reach Meera because some router on the path chose a neighbour with a smaller claimed cost, not because it ran a map of every link.

Figure. x only sees neighbor costs and each neighbor's advertised distance to y — not a full map. Here via v wins at cost 5.

How an update runs

Hear neighborsEach neighbor v advertises its current D_v(y) for destination y.
Add link costForm c(x,v) + D_v(y) for every neighbor v.
Take the minStore the smallest sum as D_x(y) and the next hop that achieved it.

One Bellman-Ford update at x

Router x reaches destination y via two neighbors. Neighbor v: c(x,v)=2, D_v(y)=3. Neighbor w: c(x,w)=5, D_w(y)=1. What does x install for D_x(y)?

Cost via v = c(x,v) + D_v(y) = 2 + 35
Cost via w = c(x,w) + D_w(y) = 5 + 16
D_x(y) = min{5, 6}5 (next hop v)

Pro tip. The neighbor with the smaller advertised distance is not always best — here w advertises 1 but the link to w costs 5, so v wins.

Distance-vector routing updates distances using which style of equation?

Dijkstra on a full topology map flooded by every router
Bellman-Ford: min over neighbors of link cost plus neighbor's distance
Only the hop count of the longest path

Distance vector is the distributed Bellman-Ford update from neighbors. Dijkstra on a flooded map is link state.

3Count-to-infinity and mitigations

Distance vector can lie to itself after a failure. Suppose the cheap path to the shop dies. A neighbour may still advertise an old, small cost that secretly depended on the dead link. The router believes the neighbour, raises its own cost a little, and advertises that. The neighbour believes it back. The numbers climb — count-to-infinity — while packets loop.

Split horizon (do not advertise a route back to the neighbour you learned it from) and poison reverse (advertise that route as infinite to that neighbour) shrink the problem. They do not erase every loop. Link-state routing avoids this pattern by flooding the links and computing on a full map instead of trusting a neighbour's distance.

Figure. Distance-vector loops when a neighbour's stale route is trusted after a link fails — metric climbs toward infinity.

How the failure mode appears

Link breaksThe true path to y is gone, but a neighbor still advertises a finite distance.
Believe the neighborYou adopt that distance plus one hop — now you are part of the loop.
MitigateSplit horizon / poison reverse stop advertising the route back toward the learner that fed it.

Which routing family is classically associated with the count-to-infinity problem?

Link state (e.g. OSPF with Dijkstra)
Distance vector (e.g. RIP with Bellman-Ford)
Neither — only circuit switching counts to infinity

Count-to-infinity is the classic distance-vector failure mode with stale neighbor distances. Link state floods topology and recomputes locally, avoiding that loop pattern.

4Link state and Dijkstra

A link-state router tells everyone about its own links, then computes. It floods — copies the link advertisement to every other router. Each router builds the same topology map and runs Dijkstra: grow a tree of confirmed cheapest paths from itself. OSPF is the classic protocol.

On a tiny map, A to B costs 1, B to C costs 2, A to C costs 4. Dijkstra from A confirms A→B→C at cost 3 and rejects the direct 4. The slogan against distance vector: tell the world about your neighbours, then compute; do not tell neighbours about the world and hope their numbers are honest.

Figure. Solid path A—B—C costs 3; the direct dashed A—C edge costs 4. Dijkstra keeps 3.

How link state computes paths

Flood link statesEach router advertises the costs of its own incident links to the whole network.
Build the mapEvery router assembles an identical graph from the flooded advertisements.
Run DijkstraCompute shortest paths from yourself to every other node on that shared map.

Shortest path A to C

Undirected edges: A—B cost 1, A—C cost 4, B—C cost 2. What shortest-path cost does Dijkstra install from A to C?

Direct path A → C4
Path A → B → C = 1 + 23
Keep the smaller tentative distance3 (via B)

Pro tip. OSPF = link state (Dijkstra); RIP = distance vector (Bellman-Ford). Same three-node graph, different who learns what.

Which routing approach floods link-state information and runs Dijkstra to compute shortest paths?

Distance vector (e.g. RIP)
Link state (e.g. OSPF)
SMTP mail routing

Link state floods topology and runs Dijkstra locally. Distance vector shares distance tables with neighbors using Bellman-Ford. SMTP is an application mail protocol.

Notes

A route is a next hop for a prefix, not another name for an IP address.
Distance vector (Bellman-Ford, RIP) shares distance tables with neighbours and can count to infinity.
Link state (Dijkstra, OSPF) floods link costs so each router computes on a full map.

Formulas

D_x(y)=\min_v\{c(x,v)+D_v(y)\}.
Dijkstra shortest path with a heap is O(E\log V).

Exam traps & shortcuts

Different prefix → send to the default gateway; do not ARP for a remote host.
Distance vector: tell neighbours about the world. Link state: tell the world about your neighbours.

Reference tables

Who you tell, what you compute, and what breaks — the two ways a router learns a path.

Distance vector vs link state
Property	Distance vector	Link state
What you advertise	Whole distance table to neighbors	Own link costs to everyone (flood)
Algorithm	Bellman-Ford	Dijkstra on local map
Classic protocol	RIP	OSPF
Failure mode	Count-to-infinity	Faster reconvergence; no DV loop pattern
Slogan	Tell neighbors about the world	Tell the world about your neighbors

Recap

The shop is not on 192.168.1.0/24, so the packet needs a next hop.

Route: Address names the end. Route names the next hop for a prefix. Phone sends to 192.168.1.1.
Distance vector: D_x(y)=\min_v\{c(x,v)+D_v(y)\}. RIP. Can count to infinity.
Link state: Flood links, run Dijkstra. OSPF. A→B→C cost 3 beats direct 4.

Practise How a Packet Finds a Path

Reading is free and needs no account. Practice, mocks and progress live in the app.

1 exam-style questions on this topic, with explanations
A 3-question practice set that ends the chapter
Timed mocks scored with the real marking scheme
Readiness tracked per topic, kept on your device

Continue with Google — freeNo card, no trial. Works offline once installed.