Skip to content
Tutorials Center
My learning

Topics

Lesson 29 of 79 ยท Routing

Link-State Routing and Dijkstra

See how link-state routers flood their links, build a shared map, and run Dijkstra's algorithm to find shortest paths. Includes OSPF areas and live Python.

A router's forwarding table is only as good as the information behind it. Static routes (see Routing and Forwarding) are fine for a small office, but a network with hundreds of routers and links that fail at random needs the routers to find paths on their own. Two families of algorithms do that job. This lesson covers link-state routing; the next one covers distance-vector routing.

The idea of link-state routing is easy to say: every router learns the whole map of the network, and then every router works out the best path by itself, using the same algorithm on the same map. Because all routers hold identical maps, their independent decisions fit together into consistent paths.

A link-state protocol does the same three things on every router.

  1. Discover neighbors. The router sends small "hello" packets on each link. A neighbor that answers is alive, and the round trip gives a first idea of the link. When hellos stop arriving, the router decides the neighbor or the link is down.
  2. Advertise and flood. The router builds a link-state advertisement (LSA, or LSP in some protocols): "I am router A. I am connected to B at cost 2 and to C at cost 5." It sends this to every neighbor, and each neighbor forwards it to all of its other neighbors, and so on. This is called flooding. Every LSA carries the sender's name and a sequence number, so a router can tell a fresh advertisement from an old copy and can stop forwarding duplicates.
  3. Compute. Each router stores all LSAs in its link-state database (LSDB), which is a complete graph of routers and link costs. It then runs Dijkstra's shortest-path algorithm with itself as the source and turns the result into a forwarding table.
flowchart LR
    A["Router A"] -- "LSA flooded" --> B["Router B"]
    A -- "LSA flooded" --> C["Router C"]
    B -- "forwards copy" --> D["Router D"]
    C -- "forwards copy" --> D
    D -. "duplicate ignored<br/>(same sequence number)" .-> D

An LSA spreads along every link. A router that already holds the same sequence number drops the duplicate, so flooding ends.

The cost of a link is chosen by the administrator or derived from the bandwidth. A common rule is cost = reference bandwidth / link bandwidth, which makes fast links cheap and slow links expensive. A path's cost is the sum of its link costs, and the "best" path is the one with the smallest total.

Routers re-flood a changed LSA at once when a link goes up or down, and they also refresh every LSA from time to time (OSPF does this every 30 minutes by default) so stale information can never live forever.

Dijkstra's algorithm

Dijkstra's algorithm finds the cheapest path from one source to every other node in a graph whose costs are not negative. That matches networks exactly: a link cost is never below zero.

The algorithm keeps a table of the best known cost to each node, and a set of nodes whose cost is final ("settled"):

  1. Set the cost of the source to 0 and every other node to infinity.
  2. Pick the unsettled node with the smallest known cost. It is now settled, because every path through an unsettled node would have to be at least as expensive.
  3. For each neighbor of the settled node, check whether going through it gives a cheaper path. If yes, record the new cost and remember the previous hop.
  4. Repeat from step 2 until all reachable nodes are settled.

Following the "previous hop" pointers backwards from any node gives its path, and all those pointers together form the shortest-path tree rooted at the router. A priority queue (a heap) makes step 2 fast: the running time is about O((V + E) log V) for V routers and E links.

The example below runs Dijkstra on a five-router network and prints the order in which routers are settled, plus each path.

Python Dijkstra on a link-state database

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Notice that A reaches C at cost 3 through B, not at cost 5 over the direct link. The direct link is shorter in hops but longer in cost, and link-state routing minimizes cost, not hop count.

From shortest-path tree to forwarding table

A router does not need the whole path, only the next hop: the first router on the path. For every destination, walk back along the previous-hop pointers until the node whose parent is the source. That node is the next hop, and the pair (destination, next hop, cost) is a row of the routing table. The next router on the path repeats the same calculation on its own tree, and because both use the same map, they agree about the rest of the path.

This also explains what happens on a failure. When a link goes down, its two ends flood new LSAs, every router updates its LSDB and runs Dijkstra again. The next example does it for router A.

Python Recompute routes after a link fails

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

After the failure, A sends traffic for C, D and E through C instead of B. In the last case, destinations that cannot be reached simply disappear from the table, which is exactly how a router learns that a part of the network is unreachable.

OSPF (Open Shortest Path First) is the most widely used link-state protocol inside an organization. OSPFv2 is defined for IPv4 and OSPFv3 for IPv6. Its main ideas:

  • It runs directly on top of IP (protocol number 89), with its own reliable flooding and acknowledgments, and uses multicast addresses 224.0.0.5 (all OSPF routers) and 224.0.0.6 (designated routers).
  • On a shared Ethernet segment with many routers, all of them electing a designated router (DR) and a backup (BDR) avoids a full mesh of adjacencies: each router talks to the DR, which floods updates for the segment.
  • Its default cost comes from the interface bandwidth. Equal-cost paths can be used together, which is called ECMP (equal-cost multipath).
  • It supports authentication of its messages, so a stranger cannot inject false LSAs.

IS-IS is a close cousin, used mostly by large service providers. It works with the same ideas of LSDB and Dijkstra but uses its own packet formats.

Areas: keeping the map small

A map with thousands of routers has costs: the LSDB eats memory, every change triggers a flood, and Dijkstra reruns more often. OSPF solves it by dividing the network into areas.

  • Each router knows the full detail of its own area only.
  • Area 0, the backbone, connects all other areas. Every other area must touch area 0.
  • An area border router (ABR) sits between two areas. It hides the inside of one area and summarizes its prefixes to the others, which also combines well with CIDR route aggregation.
flowchart TB
    subgraph Area1["Area 1"]
      R1["R1"] --- R2["R2"]
    end
    subgraph Area0["Area 0 (backbone)"]
      ABR1["ABR 1"] --- ABR2["ABR 2"]
    end
    subgraph Area2["Area 2"]
      R3["R3"] --- R4["R4"]
    end
    R2 --- ABR1
    ABR2 --- R3

Routers inside areas 1 and 2 keep their own detailed maps. The border routers pass summaries across the backbone.

A link that flaps in area 1 now triggers a flood only in area 1. The price is that routers outside the area see summarized costs, so paths between areas can be slightly less than optimal.

Floyd-Warshall: all shortest paths at once

Dijkstra finds the shortest paths from one source. A router only needs that, but sometimes you want the distance between every pair of nodes, for example to plan a network or to precompute all routes. The Floyd-Warshall algorithm does this with a dynamic-programming idea: allow the nodes to be used as intermediate stops one at a time.

  1. Initialize a distance matrix: 0 on the diagonal, the link cost where a direct link exists, and infinity everywhere else.
  2. For each node k in turn, ask for every pair (i, j): is going from i to k and then from k to j cheaper than the best known i to j? If so, update dist[i][j].
  3. After all nodes have been tried as intermediates, the matrix holds the shortest distance for every pair.

It runs in O(V^3) time with O(V^2) memory, so it suits small or dense networks, while running Dijkstra from each node is cheaper on large sparse graphs. It handles negative link costs (but not negative cycles), which network metrics rarely have. Keeping a "next hop" matrix next to the distances gives the actual routes.

Python All-pairs shortest paths with next hops

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The direct link A-B costs 4, but the matrix shows A to B costs 3 by going through C. The same table could be used to fill in a forwarding table for every router at once.

Fixed routing and flooding

Not every routing method computes paths. Fixed (static) routing uses routes entered by hand and never changed by the network. It is simple, predictable and uses no bandwidth for route exchange, which suits small networks and stub sites with one way out. The disadvantage is that it does not adapt: if a link fails, someone must change the table, and it does not scale.

Flooding sends every incoming packet out of every other interface. No routing table is needed, and it always finds the shortest path (and every other path), so it is used when robustness matters most (military networks) and as the way link-state advertisements are spread. The disadvantages are heavy duplicate traffic and the risk of packets circulating forever. These are limited with a hop counter (TTL) that drops a packet after a fixed number of hops, with a sequence number so each router forwards each packet only once, and with selective flooding, which sends only along links heading roughly in the right direction.

Property Link-state Distance-vector
What routers share Their own links, with everybody Their whole table, with neighbors only
What a router knows The complete map Only distance and direction
Algorithm Dijkstra Bellman-Ford
Convergence Fast Can be slow
Memory and CPU Higher Lower
Typical protocols OSPF, IS-IS RIP

The main risk of link-state is that routers with different maps can disagree for a moment and send packets in a loop until the floods catch up. TTLs in the IP header limit the damage.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What does a router flood in a link-state protocol?

    Link-state routers flood link-state advertisements describing their own links. Every router then holds the same map and computes its own paths.
  2. 2. In the first example, why does A reach C through B (cost 3) instead of over the direct link (cost 5)?

    The path cost is the sum of link costs. 2 + 1 = 3 is smaller than 5, so the two-hop path wins.
  3. 3. Why does Dijkstra's algorithm require non-negative link costs?

    Dijkstra settles the cheapest unsettled node because no later path can be cheaper. A negative cost would break that guarantee.
  4. 4. What is the purpose of OSPF areas?

    Areas keep detailed maps and floods inside one area. Border routers send summaries across the backbone, so large networks stay manageable.

Summary

  • Link-state routers discover neighbors, flood LSAs and build an identical link-state database.
  • Each router runs Dijkstra on that map with itself as the root; the shortest-path tree gives next hops.
  • Link costs are summed, so the best path is the cheapest one, not always the shortest in hops.
  • After a failure, new LSAs flood, the databases change and every router recomputes.
  • OSPF runs on IP, elects designated routers on shared segments, supports ECMP and uses areas around a backbone area 0.
  • Link-state converges quickly but needs more memory and CPU than distance-vector.

Next, see the other family of algorithms in Distance-Vector Routing.