08. Introduction to Routing - Link-State Routing

Modelling

Routers are modelled as nodes and links are modelled as edges. Edges have associated metrics:

• Cost of the link: delay, monetary costs, distance etc.
• Available resources: current capacity etc.

Dijkstra calculates the least-cost path.

Assumptions

Each router has a complete network picture: topology, link costs etc.

To do this, each router reliably floods information about its neighbors to every other router. All routers should have consistent information.

Flooding can sometimes cause broadcast storms; controlled flooding or spanning-tree broadcasts are used to prevent this.

Dijkstra’s Algorithm

After flooding, each router independently calculates the least-cost path from itself to every other router using Dijkstra’s algorithm and generates a forwarding table for every destination.

Definitions:

• $u$: source node
• $S$: nodes whose least-cost path is already known; initially $S=\{u\}$. One node is added to $S$ each iteration
• $c(i, j)$: cost of edge between $i$ and $j$
• $D(v)$: current minimum cost of path from $u$ to node $v$. Initially:
  • $D(V) = c(u, v)$ if $u$ is adjacent to $v$
  • $D(v) = \infty$ otherwise
• $p(v)$: parent/predecessor node of $v$ - vertex before $v$ along the shortest path from $u$ to $v$

Until all nodes are in $S$:

• Find the smallest $D(w)$ where $w$ is not in $S$
• Add $w$ to $S$
• For all $v$ adjacent to $w$ and not in $S$:
  • $D(V) = min{D(V), D(w) + c(w, v)}$
    • i.e. see if the cost of $w$ plus the cost between $w$ and $v$ is less the current cost of $v$

Running this algorithm, a forwarding table can be generating, mapping some destination to the next hop.

Complexity:

• If a min-heap is used, getting the least-cost node $w$ not in $S$ is $O(log(n))$
• For each iteration, $D(v)$ needs to be updated for all of $w$’s neighbors: $O(n)$

Oscillation with Link-State Routing

Since routers have a complete network picture, if one router finds a cheaper path through node $w$, it is likely that other routers will also use a path through $w$. If the algorithm is load-sensitive, this will cause the link cost of paths through $w$ to increase, repeating the cycle.