Link-State Routing and Dijkstra's Algorithm

Routing Algorithms

Routers forward packets using routing tables, and routing tables are produced by various algorithms. Routing algorithms are divided into static and dynamic routing algorithms.

In a static (non-adaptive) routing algorithm, the network administrator configures routing information manually. When the network topology or link states change, the static routes in the routing tables must be modified by hand. Such an algorithm cannot adapt to network changes in time, so it is used only in simple, small networks.

A dynamic (adaptive) routing algorithm is an automated routing algorithm that adapts automatically to changes in the network state and the routing tables. Its routing information is continually updated at regular intervals to obtain the best routes at all times.

Routing algorithms are usually studied on a weighted graph $G = (N, E)$: the nodes $N$ are routers, the edges $E$ are links, and each edge $(x, y)$ has a cost $c(x, y)$ that may represent link length, delay, or monetary cost. A path's cost is the sum of the costs of its edges, and routing aims to find the least-cost path between a source and a destination.

Depending on what each node knows, dynamic algorithms fall into two groups. A global algorithm requires every node to know the complete topology and every link cost. In a decentralized algorithm, each node knows only the costs of links to its direct neighbors and gradually computes least-cost paths by exchanging information with them. The link-state algorithm below is global; the distance-vector algorithm in Section 4.9 is decentralized.

Link-State Routing

A link-state algorithm is a global routing algorithm: all network topology information is known, and Dijkstra's algorithm gives the shortest paths from the source to every node.

To give every node the complete topology, each router places the costs of all its directly attached links in a link-state advertisement (LSA) and floods it through the network. When a router receives an LSA it has not seen, it stores it in its link-state database and forwards it to every neighbor except the one it came from; duplicate copies are discarded. LSAs carry sequence numbers, and an LSA with a higher sequence number replaces an older one. When flooding is complete, every router holds the same network map.

Dijkstra's Algorithm

With source node $u$, the algorithm uses this notation: $D(v)$ is the least cost from $u$ to $v$ known in the current iteration; $p(v)$ is the node before $v$ on that path; and $N'$ is the set of nodes whose least-cost paths are definitively known.

Initialization:
    N' = {u}
    for all nodes v:
        if v is a neighbor of u: D(v) = c(u, v)
        else: D(v) = ∞
Loop:
    find w not in N' such that D(w) is a minimum; add w to N'
    for each neighbor v of w not in N':
        D(v) = min(D(v), D(w) + c(w, v))
until N' contains all nodes

Each iteration adds one node to $N'$ and can only lower the costs of its neighbors:

The table shows the computation with source $u$ on the network used in the lab (ties are broken alphabetically):

When the algorithm terminates, each node has its predecessor along its least-cost path from the source. Each predecessor in turn has its own predecessor, and in this way the complete path from the source to every destination can be constructed.

For example, $z$'s predecessor is $y$, $y$'s is $x$, and $x$'s is $u$, so the least-cost path from $u$ to $z$ is $u \to x \to y \to z$ with cost 4. Keeping only the first hop of each path gives $u$'s forwarding table: packets for $v$ use link $(u, v)$, and packets for $w$, $x$, $y$, and $z$ all use link $(u, x)$.

For $n$ nodes, a plain implementation scans every node outside $N'$ in each iteration, for $O(n^2)$ total; a heap (priority queue) lowers this to $O((n+m)\log n)$, where $m$ is the number of links.

If link costs depend on the traffic carried, link-state routing can oscillate: all routers move traffic onto the currently cheap path at the same time, congesting it, and then all move away again in the next round. Having routers send LSAs at randomized times mitigates this.