Link-State routing algorithm (LS)

The link-state or shortest path first algorithm is a routing method where each router builds a full map of the network.

It's called link-state because each router describes and shares information about the state of its directly connected links.

It has the reputation of being more complex than distance-vector routing.

Overview

All routers in the network do the following:

1. neighbor discovery:

   • each router discovers directly connected neighbors by detecting active (up) interfaces

2. neighbor establishment:

   • each router meets its neighbors by exchanging Hello packets

3. flooding:

   • each router creates and floods a Link-State Advertisement (LSA) packet
   • the LSP describes each directly connected neighbors and includes neighbor ID, link type, and bandwidth
   • the LSP is sent to all neighbors
   • neighbors store it in a database and forward it to their own neighbors
   • flooding continues until all routers receive it

4. shortest path computation (Dijkstra / SPF):

   • each router builds a full network topology map and calculates best paths
   • an algorithm is then used to find the best route to each destination

Flooding

In link-state routing, routers exchange link-state advertisements (LSAs) to describe their directly connected links.

These advertisements are disseminated throughout the network using flooding.

Flooding is a forwarding mechanism in which each router sends a received LSA on all outgoing links except the one it arrived on, without requiring pre-existing routing tables.

Each LSA contains:

• the originating router's ID
• its directly connected neighbours
• the cost of each adjacent link
• a sequence (version) number
• a Time To Live (TTL)

Flooding works as follows:

1. the originating router creates an LSA and sets a protocol-defined TTL (or hop limit) that is much larger than the network diameter
2. it sends the LSA to all of its neighbours
3. each receiving router:
   • decreases the TTL by 1
   • if TTL = 0, discards the LSA
   • otherwise, checks whether the LSA has a newer sequence number than the most recent LSA received from the same originating router:
     • if it is newer:
       • stores (or updates) the LSA in its link-state database
       • forwards it to all neighbours except the one it arrived on
     • otherwise, discards the LSA
4. the process continues until every reachable router has received the LSA

Flooding generates a large number of duplicate packets because the same LSA may reach a router along multiple paths:

To make flooding efficient and safe:

• the TTL prevents packets from circulating indefinitely if forwarding loops occur ("don't let packets live forever")
• the sequence number allows routers to recognise duplicate or outdated LSAs ("don't process the same information twice")

Example:

• router A creates an LSA describing its directly connected links:
  • c(A,B) = 5
  • c(A,C) = 10
• router A floods the LSA to all of its neighbours
• every router receives the LSA, updates its link-state database, and forwards it
• all routers perform the same process for their own LSAs
• eventually, every router has the same view of the network topology, which can be represented as the following link-state database:

  ------+---------------------------------
        | To:
  From  |  A     B     C     D     E
  ------+---------------------------------
   A    |  *     5    10     *     *
   B    |  5     *     3    11     *
   C    | 10     3     *     2     *
   D    |  *    11     2     *     3
   E    |  *     *     *     3     *
  

Each router then runs Dijkstra's shortest-path algorithm on this common link-state database to compute its own forwarding (routing) table.

Dijkstra's algorithm

Edsger Dijkstra's algorithm, also known as Shortest Path First (SPF), finds the shortest path from a single source node to all other nodes.

Notation:

• C(a,b): cost of the direct link from a to b (or ∞ if no direct link)
• D(a): current best-known distance from the source to node a
• p(a): predecessor of node a on the current best-known path
• N': set of nodes whose shortest path from the source is already known

Initialization algorithm (simplified) for a source node u:

N' = {u}  # Only the source node is known.

for each node `a`:
    if `a` is a neighbor of `u`:
        D(a) = C(u,a)
        p(a) = u
    else:
        D(a) = ∞
        p(a) = undefined

Loop algorithm (simplified):

while N' ≠ N:

    select node `a` not in N' with the smallest D(a):
        Add `a` to N'

    for each neighbor `b` of `a` not in N':
        old_D = D(b)
        D(b) = min(D(b), D(a) + C(a,b))
        if D(b) < old_D:
            p(b) = a

When a node a is added to N', its shortest-path distance D(a) is final and will never change again.

The easiest way to understand is to use an example and compute the shortest-paths from u to all possible destinations:

Step	N'	v	w	x	y	z	Notes
		D(v), p(v)	D(w), p(w)	D(x), p(x)	D(y), p(y)	D(z), p(z)
0	u	2, u	5, u	1, u	∞	∞	Set N' = {u}. Initialize distances from u: D(v), D(w), D(x),D(y), D(z). Set best predecessors of direct neighbors v, w, x to u.
1	ux	2, u	4, x		2, x	∞	Select the shortest-path node not in N': D(x) = 1 → x is selected and added to N' Update shortest-path of neighbors of x: D(v) = min(D(v), D(x) + C(x,v)) = min(2, 1+2) = 2 → unchanged D(w) = min(D(w), D(x) + C(x,w)) = min(5, 1+3) = 4 → updated, x becomes the best predecessor D(y) = min(D(y), D(x) + C(x,y)) = min(∞, 1+1) = 2 → updated, x becomes the best predecessor
2	uxy	2, u	3, y			4, y	Select the shortest-path node not in N': v and y both have the same least cost (2) tie is broken arbitrarily → y is selected and added to N' Update shortest-path of neighbors of y: D(w) = min(D(w), D(y) + C(y,w)) = min(4, 2+1) = 3 → updated, y becomes the best predecessor D(z) = min(D(z), D(y) + C(y,z)) = min(∞, 2+2) = 4 → updated, y becomes the best predecessor
3	uxyv		3, y			4, y	And so on…
4	uxyvw					4, y
5	uxyvwz

The final predecessors obtained from Dijkstra's algorithm are:

| Node | Shortest distance from u | Predecessor |
| ---- | ------------------------ | ----------- |
| u    | 0                        | —           |
| x    | 1                        | u           |
| v    | 2                        | u           |
| y    | 2                        | x           |
| w    | 3                        | y           |
| z    | 4                        | y           |

These predecessor relationships form the shortest-path tree rooted at u:

    u
   / \
  x   v
  |
  y
 / \
w   z

From this shortest-path tree, node u can build its forwarding table.

The forwarding table does not store the complete path to each destination. Routers make forwarding decisions one hop at a time, so they only need to store the next hop (the neighbour that should receive the packet next).

| Destination | Shortest path           | Next hop from u |
| ----------- | ----------------------- | --------------- |
| v           | u → v                   | v               |
| x           | u → x                   | x               |
| y           | u → x → y               | x               |
| w           | u → x → y → w           | x               |
| z           | u → x → y → z           | x               |

For example:

• to reach v, node u forwards directly to v
• to reach x, node u forwards directly to x
• to reach y, w, or z, node u forwards to x, because x is the first hop on each shortest path

Therefore, the forwarding table stored at u is:

| Destination | Next hop |
| ----------- | -------- |
| v           | v        |
| x           | x        |
| y           | x        |
| w           | x        |
| z           | x        |

Pathology that can arise

Consider a network where:

• link costs are equal to the load carried on the link (no traffic = 0)
• so link costs are not symmetric:
  • c(u,v) == c(v,u) only if traffic load is the same in both directions
• early ARPANET routing used this idea, where costs depended on short-term load

Now suppose nodes x, y, and z all send traffic to node w:

• z sends 1 unit of traffic
• x sends 1 unit of traffic
• y sends e units of traffic

Description	Image
x and y both use the counterclockwise path to w (cost 1 + e). After running the LS algorithm: x and y determine the clockwise path is cheaper. Result: x, y, z all route their traffic clockwise.
After running the LS algorithm: all nodes see a zero-cost counterclockwise path to w. Result: x, y, z switch to counterclockwise routing.
After running the LS algorithm: all nodes now see a zero-cost clockwise path. Result: x, y, z switch back to clockwise routing.
And so on…

What can be done to prevent such oscillations?

Oscillations can occur in any algorithm (not just LS routing) that uses link costs based on congestion or delay.

One possible solution is to make link costs independent of current traffic load. However, this is not practical, since routing should help avoid congested links.

Another solution is to avoid having all routers run the LS algorithm at the same time, which can reduce synchronized reactions that cause oscillations.

Because of these problems, later routing algorithms generally avoid basing link costs on short-term congestion or load levels.