Shortest-path algorithms
This is an optional deep dive. Routing protocols explains what OSPF and RIP do with these algorithms. Here the algorithms themselves are worked through by hand, so you can read a routing table and know why it looks the way it does.
Dijkstra’s algorithm
Section titled “Dijkstra’s algorithm”A link-state router has the full map and wants the cheapest path from itself to every other router. Dijkstra’s algorithm builds the answer one destination at a time.
Notation
D(v)is the cheapest known cost from the source tov.p(v)is the router just beforevon that path.N'is the set of routers whose cheapest path is final.
Algorithm
- Start with
N' = {source}. SetD(v)to the link cost for direct neighbors and infinity for all others. - Pick the router
woutsideN'with the smallestD(w). Add it toN'. - For every neighbor
vofwoutsideN', updateD(v) = min(D(v), D(w) + c(w,v)). - Repeat from step 2 until every router is in
N'.
After the kth pass, the k closest routers are final. That is why a greedy pick is safe: costs are never negative, so a longer detour cannot become cheaper than an already-final path.
Worked example
Section titled “Worked example”Source A, with these link costs:
| Link | Cost |
|---|---|
| A to B | 2 |
| A to C | 3 |
| B to C | 2 |
| B to D | 4 |
| C to D | 1 |
| C to E | 4 |
| D to E | 1 |
| E to F | 2 |
| Pass | Added to N' | B | C | D | E | F |
|---|---|---|---|---|---|---|
| Start | A | 2, A | 3, A | infinity | infinity | infinity |
| 1 | B | final | 3, A (via B would be 4) | 6, B | infinity | infinity |
| 2 | C | final | 4, C (better than 6) | 7, C | infinity | |
| 3 | D | final | 5, D (better than 7) | infinity | ||
| 4 | E | final | 7, E | |||
| 5 | F | final |
Each cell is cost, predecessor. Tracing the predecessors backward gives the paths:
| To | Path | Cost |
|---|---|---|
| B | A, B | 2 |
| C | A, C | 3 |
| D | A, C, D | 4 |
| E | A, C, D, E | 5 |
| F | A, C, D, E, F | 7 |
The forwarding table keeps only the first hop. For A: destination B goes via B, and C, D, E, and F all go via C. Every router runs the same computation from its own position, on the same map, and gets a consistent set of tables.
If two paths tie, the router can install both and split traffic between them. OSPF calls this equal-cost multipath.
Cost of the computation
Section titled “Cost of the computation”A simple implementation scans all remaining routers on each pass: n + (n-1) + ... + 1 = n(n+1)/2 inspections, which is O(n^2). With a priority queue (a heap) the cost drops to roughly O(E log n), where E is the number of links. Either is small for the networks IGPs handle. The heavier cost in practice is the flooding that keeps every router’s map current, which sends on the order of n x E messages across the network when everything has to be learned from scratch.
Route oscillation
Section titled “Route oscillation”Suppose link costs depend on current load: busy links look expensive.
- Two paths exist from
StoD. Both are idle, andSpicks the shorter. - All of
S’s traffic now uses that path. Its cost jumps. The other path is empty and cheap. - At the next update,
Smoves all its traffic to the other path. The roles reverse. - The pattern repeats forever. Each time, one path is overloaded while the other sits idle.
If many routers recompute at the same moment, the swing is worse. Production protocols avoid it in two ways:
- Load-insensitive costs. OSPF costs come from configuration, usually derived from link speed, and do not change with traffic. Traffic engineering is done by tuning the weights offline or with a controller.
- Randomized timing. Routers jitter their update timers so they do not synchronize.
Load-aware routing exists in SDN and MPLS traffic engineering, where a central system makes the decision once instead of every router chasing the same signal.
Distance vector by hand
Section titled “Distance vector by hand”Distance-vector routers never see the map. Each one holds a vector of costs to every destination and updates it from its neighbors’ vectors using the Bellman-Ford rule:
D_x(y) = min over neighbors v of { c(x,v) + D_v(y) }Convergence example
Section titled “Convergence example”Three routers: X to Y costs 2, Y to Z costs 1, X to Z costs 7.
| Round | X’s vector (to X, Y, Z) | Y’s vector | Z’s vector |
|---|---|---|---|
| Initial | 0, 2, 7 | 2, 0, 1 | 7, 1, 0 |
| After exchange | 0, 2, 3 (via Y: 2 + 1) | 2, 0, 1 | 3, 1, 0 (via Y: 1 + 2) |
One exchange is enough here. Both X and Z found that going through Y beats their direct link. They tell their neighbors about the change, nobody improves further, and the messages stop. There is no halt signal. The algorithm ends when no router has anything new to say.
The next-hop for each destination is the neighbor that produced the minimum. X now sends traffic for Z to Y.
Good news spreads quickly. A cheaper link propagates in a few rounds, because every router can immediately use it.
Why bad news spreads slowly
Section titled “Why bad news spreads slowly”Use the same network as the routing protocols page: R1 is attached to network N; R1 to R2 costs 4, R2 to R3 costs 1, R1 to R3 costs 50. Before the change, R2 reaches N at 4 and R3 at 5 via R2.
The R1 to R2 link rises to 60. The exchange then goes:
| Step | Router | Computation | New cost to N |
|---|---|---|---|
| 1 | R2 | min(60, 1 + 5) | 6, via R3 |
| 2 | R3 | min(50, 1 + 6) | 7, via R2 |
| 3 | R2 | min(60, 1 + 7) | 8, via R3 |
| 4 | R3 | min(50, 1 + 8) | 9, via R2 |
| … |
R2 believes R3’s old advertisement, which actually routes back through R2. The estimates climb by 1 on each router at every exchange: R2 goes 6, 8, 10 and so on, R3 goes 7, 9, 11. When R2 reaches 50, R3’s cost via R2 would be 51, which is worse than its direct link at 50. R3 finally switches, and R2 settles at 51 via R3. That is roughly 45 updates for a change that should have needed one.
Had the link jumped to 10,000, the loop would last thousands of rounds, and packets for N bounce between R2 and R3 the whole time.
What poisoned reverse fixes, and what it does not
Section titled “What poisoned reverse fixes, and what it does not”If R3 reaches N through R2, R3 tells R2 that its cost to N is infinity. Rerun the failure:
- The link rises to 60.
R2seesR3claim infinity, so it keeps the direct route at 60 and tellsR3. R3sees that 1 + 60 = 61 is worse than its direct link at 50, switches to the direct link, and now advertises 50.R2updates to 1 + 50 = 51 viaR3, and begins tellingR3that its own cost is infinity.
A handful of updates instead of dozens. But the trick only protects loops between two neighbors. A loop through three routers (R1, R2, R3 each routing through the next) shows no direct reverse path to poison, and the count-to-infinity returns. Other defenses:
| Defense | How it limits the damage |
|---|---|
| Small maximum metric | RIP treats 16 hops as unreachable, so counting stops at 16. This also limits RIP networks to 15 hops across |
| Split horizon | Do not advertise a route back out the interface it was learned on. Poisoned reverse is the stronger form |
| Triggered updates and hold-down timers | Spread bad news at once, and ignore worse-looking updates for a short period |
| Path information | BGP carries the full AS path, so any router seeing its own number rejects the route. No counting happens |
| DUAL (EIGRP) | Proves a backup path is loop-free before using it |
Robustness
Section titled “Robustness”A misbehaving link-state router can only lie about its own links. Every other router still computes its own table from the whole map, so the damage stays local. A misbehaving distance-vector router can advertise a wrong cost for any destination, and neighbors pass the claim onward. One bad vector can pull traffic from across the network into a black hole. This difference is one reason BGP, which behaves like distance vector, needs so many filters.