Link state routing

Why it exists

With distance vector routing no router knows the network, only what its neighbours say, and bad news spreads slowly. Link state routing takes the opposite approach: every router learns the whole map of the network and computes the best paths itself. It converges faster and has no count to infinity, at the price of more memory and flooding. It is the basis of OSPF.

Prerequisites

You need Dijkstra's algorithm (Dijkstra) and the way destinations are given as prefixes (CIDR).

Precise definitions

Link state routing has five steps in every router (quoted from the textbooks):

1. Discover the neighbours by sending hello packets on each link and learning their identities.
2. Measure the cost of each link (delay, bandwidth based, or a configured number).
3. Build a link state packet (LSP) (called an LSA in OSPF) containing the router's identity, a sequence number, an age and the list of neighbours with the costs.
4. Flood the LSP to all routers: a router that receives a new LSP (higher sequence number than the stored one from the same origin) stores it and forwards it on every link except the one it came from; old or duplicate copies are discarded.
5. Compute routes: each router now holds the same link state database (the complete graph) and runs Dijkstra's algorithm with itself as the source. The result is a shortest path tree; for each destination the router keeps only the next hop (the first router on the path) in its forwarding table.

Every router computes from the same map, so the routes are consistent and loop-free. When a link changes, the router at its end floods a new LSP and all routers recompute.

How it works

Dijkstra at one router

Router A holds the map of six routers with the link costs A-B $7$, A-C $9$, A-F $14$, B-C $10$, B-D $15$, C-D $11$, C-F $2$, D-E $6$, E-F $9$. Dijkstra settles routers in order of distance: B ($7$), C ($9$), then F ($11$, reached through C: $9 + 2$, better than the direct $14$), D ($20$ through C: $9 + 11$, better than $22$ through B) and E ($20$ through F). From the previous router column the tree is read off backwards. For E: previous F, previous C, previous A: path A-C-F-E.

The forwarding table keeps only the next hop: to D, E and F the packet goes to C first. This table together with the same computation at every other router gives hop-by-hop forwarding that follows exactly the shortest paths (checked by following the tables from every router to every other on random networks).

Flooding

The network has $N = 6$ routers and $E = 9$ links. When a router floods its LSP: it sends it on all its links; every other router forwards the first copy on all links except the one it arrived on, and ignores later copies. The number of transmissions is

here $2 \times 9 - 5 = 13$ per LSP and $6 \times 13 = 78$ in all if every router floods its own LSP. The formula counts every link twice, once in each direction, minus the $N - 1$ links on which a router's first copy arrived (those are not sent back). Sequence numbers prevent the same LSP from circulating forever and tell a router whether a packet is newer than what it stores.

Distance vector against link state

(The table is the textbook comparison, quoted; the points on convergence were confirmed by the simulations of both pages.)

OSPF

The OSPF protocol is the standard link state protocol inside an autonomous system. It runs directly over IP, divides large networks into areas to limit the flooding, and may use equal-cost multipath (all of this is quoted; see protocols overview).

Worked examples

Cheat box

Traps and GATE patterns

Connections

The computation is single-source shortest paths (Dijkstra); the alternative using only neighbours' vectors is distance vector routing. The two types of protocol, and the path-vector protocol between networks, are surveyed on the protocols overview page.

PYQs

Consider the routing protocols given in List-I and the
names given in List-II:

List-I
List-II
(i) Distance vector routing (a) Bellman-Ford
(ii) Link state routing
(b) Dijkstra

For matching of items in List-I with those in List-II,
which ONE of the following options is CORRECT?

Which
of
the
following
statements
is/are
INCORRECT about the OSPF (Open Shortest Path
First) routing protocol used in the Internet?

Consider the following three statements about link
state and distance vector routing protocols for a large
network with 500 network nodes and 4000 links.

S1: The computational overhead in link state
protocols is higher than in distance vector protocols.
S2: A distance vector protocol (with split horizon)
avoids persistent routing loops, but not a link state
protocol.
S3: After a topology change, a link state protocol will
converge faster than a distance vector protocol.

Which one of the following is correct about S1, S2,
and S3?

Self-check

Revision card

References