The idea
A router does not need to know the whole network to find a good path — it only needs to trust what its immediate neighbours tell it about themselves. If a neighbour says “I can reach z at cost 3,” and the link to that neighbour costs 1, then z is reachable at cost 4 via that neighbour. Distance vector routing is exactly this idea, repeated by every router, until the estimates stop changing.
How it works
The Bellman-Ford equation
Let D_x(y) be the cost of the least-cost path from x to y. Then:
- D_x(y)
- Cost of the least-cost path currently known from x to destination y
- c_{x,v}
- Direct link cost from x to a neighbour v
- D_v(y)
- Neighbour v's own estimated least-cost-path cost to y
How it works
The minimum is taken over all neighbours v of x. In words: to get from x
to y, pick whichever neighbour makes (direct cost to that neighbour) plus
(that neighbour’s own best estimate to y) as small as possible.
Worked example
The lecture's Bellman-Ford example
Suppose u’s neighbouring nodes x, v, w know, for destination z:
D_v(z) = 5 and D_w(z) = 3.
Write the Bellman-Ford equation for
uandz, minimising overu’s three neighbours:D_u(z) = min { c_{u,v} + D_v(z), c_{u,x} + D_x(z), c_{u,w} + D_w(z) }Substitute the known values. The lecture’s own working plugs in
c_{u,v} = 2,c_{u,x} = 1,c_{u,w} = 5, alongsideD_v(z) = 5andD_w(z) = 3as given, andD_x(z) = 3:D_u(z) = min { 2 + 5, 1 + 3, 5 + 3 } = 4Read off the minimum.
1 + 3 = 4is the smallest of the three terms, soD_u(z) = 4.The node achieving the minimum is the next hop. That term came from neighbour
x, soxis the next hop onu’s estimated least-cost path toz.
AnswerD_u(z) = 4, achieved via neighbour x — so x is the next hop toward z
Aside
The lecture pairs this example with a network topology diagram (nodes u,
v, w, x, y, z with their link costs) that did not survive
extraction from the slides. The arithmetic above is reproduced exactly as
the lecture prints it — every number used is one the slide states directly —
but the visual layout of which nodes connect to which is not available here.
Check the lecture slide if you need the picture rather than the equation.
How it works
Distance vector — key idea
From time to time, each node v sends its own distance vector estimate,
D_v(z), to its neighbours, where v is the source and z is a
destination. When a node x receives a new DV estimate from any neighbour,
it updates its own DV using the Bellman-Ford equation, for every destination
y:
D_x(y) = min_v { c_{x,v} + D_v(y) } for each node yUnder minor, natural conditions, the estimates D_x(y) converge to the
actual least cost d_x(y).
How it works
Algorithm steps
Each node repeats the same three-step loop:
- Wait for a change — either a local link cost change, or a DV update message from a neighbour.
- Recompute its DV estimates using the DV received from that neighbour.
- If its DV to any destination has changed, notify its neighbours.
How it works
Properties
Iterative, asynchronous. Each local iteration is triggered by a local link cost change or a DV update message from a neighbour — there is no global synchronisation forcing every node to recompute at the same time. Each node’s DV table holds the cost from other nodes as currently estimated.
Distributed, self-stopping. Each node notifies its neighbours only when its own DV actually changes. Those neighbours then notify their own neighbours, again only if necessary. If no notification is received, no action is taken anywhere downstream — the propagation dies out on its own once nothing is left to change.
How it works
The distance vector example — initial state at t=0
The lecture works a nine-node network (nodes a through i) to show the
algorithm running for real. At t=0, node a’s own distance vector holds
only what survived extraction:
Da(a) = 0
Da(b) = 8
Da(d) = 1
Da(f) = 1Aside
The lecture’s own topology diagram for this example — all nine nodes and
every link cost — is garbled in the extracted source, and node a’s table
originally also listed entries for c, e, g, h and i that did not
survive. Only the four values above (a to itself, b, d, f) can be
stated with confidence. Do not treat the missing entries as zero or as
unreachable — they are simply not recoverable from this extraction. Check
the lecture slide for the full nine-node topology and the complete initial
table.
How it works
At t=0, and the first exchange
All nodes start out only knowing distance estimates to their nearest neighbours. At this point every node sends its local distance vector to its own neighbours — this is the trigger for the first round of recomputation.
How it works
Iteration and computation at t=1
At t=1, every node receives the distance vectors its neighbours sent, uses
them to compute its own new distance vector, and then sends that new vector
out in turn.
The lecture works this through for node b (which receives DVs from a,
c and e) and node c (which receives a DV from b). The computation
lines below are reproduced exactly as extracted, including the blanks —
several operands did not survive the extraction.
Worked example
Node b's computation at t=1
b computes its distance to every destination, minimising over its three neighbours
a,c,e, using whichever terms survived extraction (a blank—marks an operand the source does not give):D_b(a) = min { c_{b,a}+D_a(a), c_{b,c}+D_c(a), c_{b,e}+D_e(a) } = min { 1+8, —, — } = 8 D_b(c) = min { c_{b,a}+D_a(c), c_{b,c}+D_c(c), c_{b,e}+D_e(c) } = min { —, 1, — } = 1 D_b(d) = min { c_{b,a}+D_a(d), c_{b,c}+D_c(d), c_{b,e}+D_e(d) } = min { 9, 2, — } = 2 D_b(e) = min { c_{b,a}+D_a(e), c_{b,c}+D_c(e), c_{b,e}+D_e(e) } = min { —, —, 1 } = 1 D_b(f) = min { c_{b,a}+D_a(f), c_{b,c}+D_c(f), c_{b,e}+D_e(f) } = min { —, —, 2 } = 2 D_b(g) = min { c_{b,a}+D_a(g), c_{b,c}+D_c(g), c_{b,e}+D_e(g) } = min { —, —, — } = not given D_b(h) = min { c_{b,a}+D_a(h), c_{b,c}+D_c(h), c_{b,e}+D_e(h) } = min { —, —, 2 } = 2 D_b(i) = min { c_{b,a}+D_a(i), c_{b,c}+D_c(i), c_{b,e}+D_e(i) } = min { —, —, — } = not givenResulting DV in b:
D_b(a) = 8 D_b(f) = 2 D_b(b) = 0 D_b(g) = not given D_b(c) = 1 D_b(h) = 2 D_b(d) = 2 D_b(i) = not given D_b(e) = 1
AnswerResulting DV in b: D_b(a)=8, D_b(b)=0, D_b(c)=1, D_b(d)=2, D_b(e)=1, D_b(f)=2, D_b(h)=2 — D_b(g) and D_b(i) did not survive extraction
Worked example
Node c's computation at t=1
c has only one neighbour in this exchange,
b, so every term reduces toc_{c,b} + D_b(·):D_c(a) = c_{c,b} + D_b(a) = 1 + 8 = 9 D_c(b) = c_{c,b} + D_b(b) = 1 + 0 = 1 D_c(d) = c_{c,b} + D_b(d) = 1 + — = not given D_c(e) = c_{c,b} + D_b(e) = 1 + 1 = 2 D_c(f) = c_{c,b} + D_b(f) = 1 + — = not given D_c(g) = c_{c,b} + D_b(g) = 1 + — = not given D_c(h) = c_{c,b} + D_b(h) = 1 + — = not given D_c(i) = c_{c,b} + D_b(i) = 1 + — = not givenResulting DV in c:
D_c(a) = 9 D_c(b) = 1 D_c(c) = 0 D_c(e) = 2The remaining five entries (
d,f,g,h,i) are not given in the extracted source.
AnswerResulting DV in c: D_c(a)=9, D_c(b)=1, D_c(c)=0, D_c(e)=2 — D_c(d), D_c(f), D_c(g), D_c(h) and D_c(i) did not survive extraction
Aside
Both computations above are reproduced with every surviving number exactly
as the lecture states it — nothing here has been calculated from scratch to
fill a gap. Several operands (marked —) and several resulting entries
(marked “not given”) were lost to garbled PDF extraction. The lecture slides
are the only reliable source for those specific values; do not treat a
“not given” result as zero or as unreachable.
Check yourself
- Bellman-Ford:
D_x(y) = min_v { c_{x,v} + D_v(y) }, minimised over the neighbours ofx. - The neighbour that achieves the minimum is the next hop.
- Distance vector’s key idea: exchange DV estimates with neighbours, recompute with Bellman-Ford whenever one arrives.
- Three steps per node: wait, recompute, notify (only if changed).
- Iterative and asynchronous; distributed and self-stopping.
- In the t=1 worked example, several entries are genuinely missing from the source — “not given” is the correct answer for those cells, not a number you compute yourself.
In the exam
- Write the Bellman-Ford equation exactly, including the
minover neighbours — a question that asks you to “state” it wants the full expression, not a description in words. - Show every substituted term, the way the lecture’s own example does. The next hop comes from identifying which term won the minimum, so leave that step visible.
- Name both properties precisely: iterative/asynchronous is about when a node recomputes; distributed/self-stopping is about whether it tells anyone. These answer different exam phrasings and are easy to blur together.
- The three algorithm steps are wait, recompute, notify-if-changed — a question can ask you to list them in order.
- The nine-node worked example is incomplete on this page by design. If an exam question reuses this exact scenario, the full topology and complete t=1 tables are in the lecture slides, not here — revise from those directly for the entries marked “not given” above.