Link State Routing (OSPF)

Two ways to learn routes

A router must decide, for every packet, which link to send it on. In distance-vector routing (RIP) a router tells its neighbours “here is my table of distances” and believes what it hears. Nobody ever sees the whole map, which causes slow convergence and count-to-infinity problems.

Link-state routing does something different: every router learns the entire map and computes its own routes. It is used by OSPF and IS-IS inside organisations and ISPs. It works in five steps:

1. Discover neighbours. A router sends Hello packets on each link and learns who is on the other end.
2. Measure the cost of each link (in OSPF, based on the link’s bandwidth).
3. Build an LSA (link-state advertisement, called an LSP in IS-IS): a short message saying “I am router X, connected to these neighbours with these costs”, with a sequence number.
4. Flood the LSA to every router. Each router stores everything it receives in its link-state database (LSDB).
5. Run Dijkstra on the LSDB, with itself as the source, to get a shortest-path tree, and keep the first hop of each path in its forwarding table.

The example network

Six routers and nine links. The numbers are costs:

Link	Cost	Link	Cost	Link	Cost
A–B	2	B–D	6	D–E	3
A–C	3	C–D	1	D–F	4
B–C	2	C–E	5	E–F	2

Step 4: flooding

Press Flood its LSA for router A. The rule is simple:

When an LSA arrives, if it is new (higher sequence number than the stored copy), store it and send it out of every interface except the one it came in on. If it is old or a duplicate, drop it.

Wave	Who receives A’s LSA for the first time
1	B and C (A’s neighbours)
2	D and E
3	F

Some copies arrive at a router that already has the LSA, such as B’s copy to C, shown as red ✗ in the model. They are dropped, which is why the flood stops by itself. In total 13 copies are sent, which is 2E − (n − 1) = 2 × 9 − 5. Real OSPF also acknowledges LSAs, so the flooding is reliable.

Press Flood all LSAs and watch the LSDB table fill. After wave 1 each router knows its neighbours’ links, after wave 2 it knows the routers two hops away, and after wave 3, the number of hops across the network, every router holds all six LSAs. The databases are now identical.

Step 5: Dijkstra at each router

Every router now has the same map, so it needs no help from anyone. Take router A (press Run Dijkstra):

Step	Settle	Distances after relaxing
1	A (0)	B = 2, C = 3
2	B (2)	C: 2 + 2 = 4, not better than 3; D = 2 + 6 = 8
3	C (3)	D: 3 + 1 = 4 (better than 8), E = 3 + 5 = 8
4	D (4)	E: 4 + 3 = 7 (better than 8), F = 4 + 4 = 8
5	E (7)	F: 7 + 2 = 9, not better than 8
6	F (8)	nothing left

The forwarding table of A keeps only the first hop:

To	Next hop	Cost
B	B	2
C	C	3
D	C	4
E	C	7
F	C	8

Router F runs the same algorithm on the same map and gets its own tree rooted at F. The trees of different routers are different, but they are consistent: if A says “send to F via C”, then C says “send to F via D”, and D says “send to F directly”. Because all routers use the same map and the same tie-breaking rule, packets never loop.

When a link fails

Press Fail link C–D (cost 1). C and D stop hearing each other’s Hello packets, and each floods a new LSA with a higher sequence number that omits the dead link. In one flood every router has the new map. Router A reruns Dijkstra:

To	Before	After	Next hop after
D	4	8	B (A–B–D)
E	7	8	C (A–C–E)
F	8	10	C (A–C–E–F)

The network has converged as soon as the flood has arrived and every router has finished its Dijkstra run. There is no waiting for neighbours to slowly agree and no count-to-infinity.

In practice: OSPF

• Cost defaults to reference bandwidth ÷ interface bandwidth, with a reference of 100 Mbps: a 100 Mbps link costs 1, a 10 Mbps link costs 10.
• Areas. Flooding and Dijkstra do not scale to thousands of routers, so OSPF splits a network into areas, joined by a backbone area 0. LSAs are flooded only within an area.
• Designated router. On a shared Ethernet segment with many routers, one router (DR) represents the segment, so that not every pair needs to exchange LSAs.
• Refresh. LSAs expire if not refreshed (by default every 30 minutes) and are re-flooded immediately when something changes.

Distance vector versus link state

	Distance vector (RIP)	Link state (OSPF)
What a router knows	Distances announced by its neighbours	The whole map
What it sends	Its distance table, to neighbours only	Its own links, to everyone (flooding)
Computation	Bellman–Ford, a little at a time	Dijkstra, from scratch on each change
Convergence	Slow after bad news, count-to-infinity	Fast: one flood plus one SPF run
Memory and CPU	Small	Larger (the map and Dijkstra)
Scales to	Small networks (RIP limit: 15 hops)	Large networks, with areas

Code

import heapq

LINKS = {('A', 'B'): 2, ('A', 'C'): 3, ('B', 'C'): 2, ('B', 'D'): 6, ('C', 'D'): 1,
         ('C', 'E'): 5, ('D', 'E'): 3, ('D', 'F'): 4, ('E', 'F'): 2}
ROUTERS = 'ABCDEF'

def neighbours(links, u):
    """{neighbour: cost} of router u, read from the map."""
    out = {}
    for (a, b), w in links.items():
        if u == a:
            out[b] = w
        elif u == b:
            out[a] = w
    return dict(sorted(out.items()))

def flood(links, origin):
    """Flood one LSA. Returns the routers reached in each wave and the number of copies sent."""
    came_from, frontier, waves, copies = {origin: None}, [origin], [[origin]], 0
    while frontier:
        new = []
        for u in frontier:
            for v in neighbours(links, u):
                if v == came_from[u]:
                    continue                       # never send it back where it came from
                copies += 1
                if v not in came_from:             # first copy: store it and pass it on
                    came_from[v] = u
                    new.append(v)                  # (later copies are duplicates and are dropped)
        if new:
            waves.append(sorted(new))
        frontier = sorted(new)
    return waves, copies

def dijkstra(links, src):
    """What every router does with its copy of the map. Returns cost and previous router for each destination."""
    dist = {r: float('inf') for r in ROUTERS}
    prev, settled = {}, set()
    dist[src] = 0
    heap = [(0, src)]
    while heap:
        d, u = heapq.heappop(heap)
        if u in settled:
            continue
        settled.add(u)
        for v, w in neighbours(links, u).items():
            if d + w < dist[v]:
                dist[v], prev[v] = d + w, u
                heapq.heappush(heap, (d + w, v))
    return dist, prev

def forwarding_table(links, src):
    """For every destination: the first hop of the shortest path, and its cost."""
    dist, prev = dijkstra(links, src)
    table = {}
    for dst in ROUTERS:
        if dst == src:
            continue
        hop = dst
        while prev[hop] != src:                    # walk back to the router next to src
            hop = prev[hop]
        table[dst] = (hop, dist[dst])
    return table

print(flood(LINKS, 'A'))
# ([['A'], ['B', 'C'], ['D', 'E'], ['F']], 13)
print(forwarding_table(LINKS, 'A'))
# {'B': ('B', 2), 'C': ('C', 3), 'D': ('C', 4), 'E': ('C', 7), 'F': ('C', 8)}
broken = {k: v for k, v in LINKS.items() if k != ('C', 'D')}      # link C-D fails
print(forwarding_table(broken, 'A'))
# {'B': ('B', 2), 'C': ('C', 3), 'D': ('B', 8), 'E': ('C', 8), 'F': ('C', 10)}

Common mistakes

• Saying link-state routers exchange routing tables. They flood LSAs describing their own links, and each router computes its own table.
• Thinking an LSA goes only to neighbours. It is flooded to every router in the area.
• Forgetting the “except the interface it came from” rule when counting flood copies, or not counting the dropped duplicates.
• Confusing the shortest-path tree with the forwarding table. The tree is the whole path structure; the table keeps only the first hop per destination.
• Believing link-state is free. Every router needs memory for the whole map, CPU for Dijkstra on each change and flood bandwidth. That is why large networks are split into areas.