Link-state and distance vector routing

Both are dynamic (adaptive) routing methods. In link-state routing every router learns the whole map and runs Dijkstra's algorithm; in distance-vector routing every router only exchanges distance tables with its neighbours and uses the Bellman-Ford equation.

Example network used below (link costs shown):

        A
     2 / \ 6
      /   \
     B --3-- C
     |     / |
    7|   2/  |4
     |   /   |
     D --1-- E

Link-state routing (Dijkstra)

1. Each router finds its neighbours (HELLO packets) and measures the cost of each link.
2. It builds a link state packet (LSP): its ID, sequence number, age and the list of neighbours with costs.
3. LSPs are flooded to all routers; each router stores them in a link-state database, so all routers have the same topology.
4. Each router runs Dijkstra with itself as root:
   • Put the source in the permanent set with $D=0$; set other $D$ = link cost or $\infty$.
   • Repeatedly make permanent the tentative node with the least $D$, then for each neighbour $v$ update $D(v) = \min(D(v),\ D(u) + c(u,v))$.

Dijkstra from A:

Routing table of A: to B via B (2), C via B (5), D via B (7), E via B (8). Used in OSPF and IS-IS.

Distance-vector routing (Bellman-Ford)

1. Each router keeps a vector of its best known distance and next hop to every destination; at start it knows only its direct links.
2. Periodically (e.g. every 30 s in RIP) it sends its vector to its neighbours only.
3. On receiving vectors, router $x$ updates each destination $y$ using

$$D_x(y) = \min_{v \in \text{neighbours}} \{\, c(x,v) + D_v(y) \,\}$$

4. Repeating this, the tables converge to the shortest paths.

For A, neighbours are B (cost 2) and C (cost 6), with converged vectors $D_B = (A2, C3, D5, E6)$ and $D_C = (A5, B3, D2, E3)$:

$$\begin{aligned} D_A(C) &= \min(2+3,\ 6+0) = 5 \ \text{(via B)} \\ D_A(D) &= \min(2+5,\ 6+2) = 7 \ \text{(via B)} \\ D_A(E) &= \min(2+6,\ 6+3) = 8 \ \text{(via B)} \end{aligned}$$

This is the same result as Dijkstra, reached in 3 exchange rounds (A's vector after rounds: E = 10, 9, 8).

Comparison