The idea
Distance vector routing works by trusting neighbours’ summaries, and it never has to know the whole network. That is its strength and its weakness at once: a router cannot make a genuinely bandwidth-aware decision if all it sees is a hop count, and passing full routing tables around costs bytes on every link, every interval. Link state routing takes the opposite bet — give every router the entire map, and let each one compute its own paths directly.
How it works
Problems with distance vector
The lecture names two specific problems that motivate link state routing:
- The metric was just a hop count — line bandwidth was never considered.
- Exchanging routing tables was an overhead — passing a full table to every neighbour, every interval, costs bandwidth of its own.
How it works
Link state algorithm requirements
In a link state algorithm, every router must:
- Discover its neighbours and learn their network addresses.
- Measure the delay or cost to each neighbour, considering things like traffic levels and link state.
- Construct a Link State Packet (LSP) with this new information, containing: node id, list of links, sequence number, and age.
- Flood this packet to all other routers.
- Form the shortest path tree to each router.
- Compute the routing table from that shortest path tree.
How it works
Dijkstra's algorithm — overview and notation
Dijkstra’s algorithm is:
- Centralised. Every node already knows the full network topology and
every direct link cost
c_{x,y}— accomplished by the link state broadcast in the requirements above. All nodes have the same information. - A least-cost-path computer. It computes the least-cost path from one source node to every other node, which is exactly what a forwarding table for that source needs.
- Iterative. After
kiterations, the least-cost path tokdestinations is known.
Notation:
c_{x,y}— direct link cost fromxtoy;= ∞ifxandyare not direct neighbours.D(v)— the current estimate of the cost of the least-cost path from the source to destinationv.p(v)— the predecessor node along the path from the source tov.N'— the set of nodes whose least-cost path is definitively known.
How it works
Pseudocode
1. Initialization:
2. N' = {u} /* compute least cost path from u to all other nodes */
3. for all nodes v
4. if v adjacent to u /* u initially knows direct-path-cost only to direct neighbors */
5. then D(v) = c_{u,v} /* but may not be minimum cost! */
6. else D(v) = ∞
7.
8. Loop
9. find w not in N' such that D(w) is a minimum
10. add w to N'
11. update D(v) for all v adjacent to w and not in N' :
12. D(v) = min ( D(v), D(w) + c_{w,v} )
13. /* new least-path-cost to v is either old least-cost-path to v or known
14. least-cost-path to w plus direct-cost from w to v */
15. until all nodes in N'- D(v)
- Current best-known cost from the source to node v
- D(w)
- Cost from the source to the node w just added to N'
- c_{w,v}
- Direct link cost from w to v
Worked example
Dijkstra's algorithm — Example 1
The lecture’s step-by-step table, reproduced exactly as extracted:
Step N’ v, p(v) w, p(w) x, p(x) y, p(y) z, p(z) 1 u,x2,u2 u,x,y2,u5,u1,u3 u,x,y,v2,u4 2,x5 u,x,y,v,w3,yfinal u,x,y,v,w,z3,y4,yResulting forwarding table in
u, which the lecture states directly regardless of the intermediate step ordering above:Destination Outgoing link Route v(u,v)Route from utovdirectlyx(u,x)Route from uto all other destinations viaxy(u,x)via xw(u,x)via xz(u,x)via x
AnswerForwarding table at u: v via (u,v) directly; x, y, w and z all routed via (u,x)
Aside
This table’s row order and column alignment are disturbed in extraction —
for example, the row labelled step 2 lists values (v=2,u, w=5,u,
x=1,u) that look like the algorithm’s initialisation step rather than
its second iteration, and the topology diagram that would confirm the exact
link costs did not extract cleanly either. Every individual D(·), p(·)
pair above is reproduced exactly as printed, but the step-by-step sequence
connecting them should not be taken as authoritative. The final forwarding
table is stated cleanly in the source and is not affected by this. If a
question needs the precise iteration order, check the lecture slide image
directly rather than this page.
Worked example
Dijkstra's algorithm — Example 2 (class exercise)
Step 0 is given. With
N' = {u}, the initial direct costs fromuare:Step N’ D(v), p(v) D(w), p(w) D(x), p(x) D(y), p(y) D(z), p(z) 0 u7,u3,u5,u— — So
c_{u,v} = 7,c_{u,w} = 3,c_{u,x} = 5, andyandzare not direct neighbours ofu.Steps 1 through 5 are posed as an exercise — the lecture’s own heading is “Table to complete,” followed by “Resulting forwarding table in u?” and “Resulting least-cost-path tree from u?” as questions for the student.
AnswerLeft as an exercise in the lecture — only the initial step is given
Aside
The full topology for Example 2 — every link cost beyond u’s three direct
neighbours — is garbled in extraction and cannot be reliably reconstructed
from what remains. Rather than invent a plausible-looking topology and work
through it, this page stops at the given step 0. Complete the remaining
steps from the lecture slide’s own topology diagram, applying the same
pseudocode and update rule given above.
Where marks get lost
D(v) can only improve, never get worse
The update rule takes a min, so a node’s distance estimate never
increases during the algorithm. If your own working shows a D(v) going up
between iterations, that is a sign of an arithmetic slip, not a valid step.
How it works
Complexity discussion
Algorithm complexity. With n nodes, each of n iterations needs to
check all nodes w not yet in N'. That gives n(n+1)/2 comparisons
overall: O(n²). More efficient implementations bring this down to
O(n log n).
Message complexity. Each router must broadcast its link state
information to the other n routers. Efficient broadcast algorithms exist
that cross only O(n) links to disseminate a message from one source, but
since every one of the n routers does this, the overall message
complexity across the network is O(n²).
Check yourself
- Distance vector’s two weaknesses: hop-count-only metric, and full-table exchange overhead.
- A link state router discovers neighbours, measures link cost, builds an LSP, floods it, builds the shortest path tree, then the routing table.
- An LSP carries node id, links, sequence number, age.
- Dijkstra’s update rule:
D(v) = min(D(v), D(w) + c_{w,v}), applied to every neighbour of the node just added toN'. - Both algorithm complexity and network-wide message complexity land at O(n²), with O(n log n) reachable for the algorithm with a better implementation.
In the exam
- Name both distance vector problems when asked to justify link state — hop-count-only metric and table-exchange overhead, both required for a full answer.
- Reproduce Dijkstra’s notation exactly:
c_{x,y},D(v),p(v),N'. A question asking you to “define the notation” wants all four. - The update rule is a minimum, not a replacement. State it as
D(v) = min(D(v), D(w)+c_{w,v}), notD(v) = D(w)+c_{w,v}). - Know both complexity figures and which is which: O(n²) is the straightforward algorithm complexity and also the network-wide message complexity; O(n log n) is only reachable with a more efficient implementation of the algorithm itself.
- This page’s Example 1 table has a disturbed row order — trust the final forwarding table over the intermediate rows if the two seem to conflict, and check the lecture slide if a question depends on the exact iteration sequence.