Link State and Dijkstra

Each router floods a description of its own directly attached links to the whole network. Every router therefore ends up holding an identical database of the complete topology — the exact opposite of distance vector, where nobody has a map and everyone trusts summaries.

Each then runs Dijkstra locally, rooted at itself. Since they all compute from the same map, their results are consistent, which is why routing loops cannot form.

Protocol data unit

What the thing is called at each layer: segment at transport, packet at network, frame at link. Different names for the same bytes with different amounts of header wrapped round them.

Encapsulation

A layer treats everything it receives from above as opaque payload and prepends its own header. It never looks inside, which is precisely what makes layers replaceable.

Peer layers

A layer only ever meaningfully talks to the same layer at the other end. TCP at one end reads the header TCP at the other end wrote, and nothing in between touches it.

Propagation vs transmission delay

Propagation is how long a bit takes to travel the distance — set by physics. Transmission is how long it takes to push all the bits out — set by bandwidth. Only the second improves when you buy a faster link.

Round-trip time (RTT)

Send to reply. Every acknowledgement-based protocol is ultimately paced by this, which is why the interesting question is always how much you can send before one arrives.

1. 1Set the source's distance to 0 and every other node to ∞.
2. 2Pick the unsettled node with the smallest tentative distance and settle it — its distance is now final.
3. 3Relax each of its edges: if reaching a neighbour through this node is cheaper than the neighbour's recorded distance, lower it and record the new parent.
4. 4Repeat until every node is settled.

Settling the smallest is only safe because all costs are non-negative — no later path can be shorter. With negative weights the guarantee fails and Bellman-Ford is required.

The result is a shortest-path tree rooted at this router. But a router does not store paths — it stores, for each destination, only the first hop. Everything beyond that is decided by the next router from its own tree.

Two things are worth noticing in the example. The shortest path is not the one with fewest hops — a two-hop route at cost 3 beats a one-hop route at cost 5. And the direct A–C link is absent from the tree entirely, because nothing needs it.

OSPF and IS-IS are the link-state protocols in real use. Costs are metrics, usually derived from bandwidth rather than physical distance, so a fast long link beats a slow short one.

The cost is memory and CPU: every router stores the whole topology and recomputes on any change. Large networks are therefore divided into areas, with full topology flooded only inside an area and summaries between them — which bounds both the database size and the recomputation.