Routing algorithms: Dijkstra and Bellman-Ford

On the previous page we saw that a router looks at its forwarding table and forwards the packet. But who fills in that table? Routing algorithms. This is the network layer’s control plane: seeing the network as a graph and finding the least-cost path to every destination. The exam has two table-filling questions: the Dijkstra table and a distance-vector update. Golden rules:

1. At each step Dijkstra adds the node outside N’ with the smallest distance. Whether it is a neighbour does not matter.
2. Update the neighbours of the added node: $D(v) = \min(D(v),\ D(w) + c(w,v))$.
3. The forwarding table keeps only the first hop (next hop).
4. Bellman-Ford: $D_x(y) = \min_v \{c(x,v) + D_v(y)\}$, where $v$ ranges over neighbours.
5. In DV, bad news spreads slowly (count-to-infinity).

The network as a graph

Routers are nodes, links are edges. Each edge has a cost: delay, inverse bandwidth, or an administrator’s decision. The cost of a path is the sum of the edge costs.

Link-state: Dijkstra’s algorithm

Each router spreads its link states (link-state packets) to the whole network. Everyone has the same map and runs Dijkstra by itself.

Notation: $D(v)$ is the lowest cost known so far from the source to $v$, $p(v)$ is the predecessor node on that path, and $N'$ is the set of finalized nodes.

Start: N' = {source}; for each v, D(v) = c(source,v) (infinite if not a neighbour)
Loop : pick the smallest D(w) outside N', add it to N'
       for each neighbour v of w outside N':
           D(v) = min( D(v), D(w) + c(w,v) )
End  : all nodes are in N'

Example: source A. Edges:

A-B 4   A-C 1   B-C 2   B-D 5   C-D 8
C-E 10  D-E 2   D-F 6   E-F 3

Each cell in the table has the form D,p. * shows that the node is finalized.

step  N'       B      C      D      E      F
0     A        4,A    1,A    inf    inf    inf
1     AC       3,C    *      9,C    11,C   inf
2     ACB      *      *      8,B    11,C   inf
3     ACBD     *      *      *      10,D   14,D
4     ACBDE    *      *      *      *      13,E
5     ACBDEF   *      *      *      *      *

In step 1, C (1) was added: for B, $1 + 2 = 3 < 4$, and the predecessor became C. In step 2, B (3) was added: for D, $3 + 5 = 8 < 9$. In step 3, D (8): for E, $8 + 2 = 10 < 11$. In step 4, E (10): for F, $10 + 3 = 13 < 14$.

The result and A’s forwarding table:

PITFALL · the direct link is not always the shortest. A-B directly is 4, but A-C-B is 3. While filling in the table, don’t take the values in the first row as “final”; a node is finalized only when it is added to N’.

TIP · finding the next hop. Trace the predecessor chain backward: F’s predecessor is E, E’s is D, D’s is B, B’s is C, C’s is A. The last node before reaching the source (C) is the next hop.

Complexity. For n nodes there are n - 1 rounds, and each round scans to find the smallest: $O(n^2)$. Oscillation: if the cost depends on traffic load, everyone switches to the cheap path at the same time, that path becomes expensive, and everyone switches back. The fix: randomly shift the routers’ computation times.

TIP · filling the table quickly on the exam. In each row do three things: (1) circle the smallest value outside N’, (2) write that node into the set N’, (3) update only the cells of its neighbours and copy the other cells unchanged. If there is a tie, the one you pick does not change the result, but be consistent (usually alphabetical). Trying to recompute a cell that doesn’t change is a waste of time.

Message complexity. In LS each router spreads its own link state to the whole network; for n routers and E links that is $O(nE)$ messages. In DV, messages go only between neighbours, but the convergence time varies and loops can form. In terms of robustness LS is better: since each router does its own computation, a router’s error stays limited.

Distance-vector: Bellman-Ford

Each router keeps only its distance vector: the estimated cost to each destination. When it receives vectors from its neighbours, it renews its own vector with the Bellman-Ford equation:

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

If the vector changed, it sends it to its neighbours. If it did not, it stays silent. That is why the algorithm is iterative, asynchronous and distributed.

Example: four nodes, synchronous rounds. Edges: W-X 1, X-Y 3, W-Y 6, Y-Z 2, X-Z 9. Rows are the node’s vector, columns are destinations W X Y Z.

t=0 (direct links only)
  D_W   0  1  6  inf
  D_X   1  0  3  9
  D_Y   6  3  0  2
  D_Z   inf 9 2  0
t=1
  D_W   0  1  4  8       Y: min(6, 1+3)=4   Z: min(inf, 1+9, 6+2)=8
  D_X   1  0  3  5       Z: min(9, 3+2)=5
  D_Y   4  3  0  2
  D_Z   8  5  2  0
t=2
  D_W   0  1  4  6       Z: min(1+5, 6+2)=6   (X's new vector)
  D_X   1  0  3  5
  D_Y   4  3  0  2
  D_Z   6  5  2  0
t=3: no vector changed, converged

W’s best path to Z is W-X-Y-Z, with cost $1 + 3 + 2 = 6$. This information arrived in two rounds, because it is a three-hop path.

Count-to-infinity and poisoned reverse

When a cost decreases, the news spreads quickly. When it increases, there is trouble. Example: A-B 2, B-C 1, A-C 30. In the converged state $D_B(A) = 2$, $D_C(A) = 3$ (C goes to A via B). Now the A-B cost becomes 40.

B: min(40, 1 + D_C(A)=3) = 4     B doesn't know that C's path goes through B itself
C: min(30, 1 + 4) = 5
B: min(40, 1 + 5) = 6
C: 7, B: 8, ...                  grows by 2 each round
...
B: 30, C: min(30, 31) = 30       C finally switched to the direct link
B: min(40, 1 + 30) = 31          stable

The stable state was reached in 15 rounds (in each round B updates first, then C). For almost this whole time, B and C were in a loop pointing at each other. Without the A-C link, the numbers would climb forever; that is where the name comes from.

Poisoned reverse: if C’s path to A goes through B, C tells B $D_C(A) = \infty$. B immediately gets $\min(40, 1 + \infty) = 40$ and no loop forms. However, this trick is not enough in loops of three or more nodes. This is why RIP defines infinity as 16 hops.

Hierarchical routing

In the real Internet there are hundreds of millions of routers; they can’t all run one Dijkstra. Also, each organization wants to manage its own network. The solution: autonomous systems (AS). Inside an AS an intra-AS protocol (OSPF, RIP) runs, and between ASes an inter-AS protocol (BGP). We cover this on the next page.

Common mistakes

S-T 3   S-U 7   T-U 2   T-V 6
U-V 1   U-W 8   V-W 2

P-Q 2   P-R 7   Q-R 1   R-T 3   Q-T 8