Part XXI — Routing protocols in depth

Chapter 13 covered routing tables and longest-prefix match; Chapter 50 gave BGP and anycast in one page. This part is the detail: how routers build those tables, and what goes wrong.

70. How routing protocols work: the two families

70.1 The problem

A router knows its directly-connected networks. Everything else must be learned. Static routes don't scale and don't react to failure. So routers talk to each other — and there are exactly two ways to do it.

70.2 Distance-vector vs link-state

DISTANCE-VECTOR                          LINK-STATE
"routing by rumour"                      "everyone gets the same map"

Each router tells its NEIGHBOURS         Each router floods a description of
the DISTANCE to every destination        ITS OWN LINKS to EVERY router

  A: "I can reach X, cost 3"               A: "I connect to B (cost 1) and C (cost 5)"
  B believes A, adds its own cost,         every router assembles the same
  advertises "X, cost 4"                   topology database, then runs
                                            Dijkstra's shortest-path algorithm
                                            itself

+ simple, low memory                     + fast, loop-free convergence
+ small routers can run it               + full topology visibility
- slow convergence                       - more CPU and memory
- COUNT-TO-INFINITY loops                - needs hierarchy (areas) to scale
- limited visibility                     - more complex to design

RIP, EIGRP*, BGP*                        OSPF, IS-IS

* EIGRP is "advanced distance-vector" (uses DUAL for loop-freedom); BGP is path-vector — a distance-vector variant that carries the whole AS path, which is how it detects loops (§72.3).

70.3 Count-to-infinity, and the fixes

The classic distance-vector failure:

A --- B --- C --- X          C loses X.
                             B still advertises "X, cost 2" (learned from C).
                             C believes B, installs "X via B, cost 3".
                             B now hears cost 3, updates to 4. And so on,
                             counting slowly to infinity while packets loop.

Mitigations you'll see named in exams and configs:

Technique	What it does
Split horizon	Never advertise a route back out the interface you learned it on
Poison reverse	Advertise it back with infinite metric (explicitly "don't use me")
Hold-down timer	Ignore updates about a route for N seconds after it fails
Triggered updates	Send changes immediately rather than waiting for the periodic timer
Max metric = infinity	RIP caps hop count at 15; 16 means unreachable — bounds the counting

Link-state protocols avoid the problem entirely: nobody relies on a neighbour's summary, because everyone computes from the same map.

70.4 IGP vs EGP, and administrative distance

IGP (Interior Gateway Protocol)   inside ONE administrative domain
                                   goal: find the FASTEST path
                                   OSPF, IS-IS, EIGRP, RIP

EGP (Exterior Gateway Protocol)   BETWEEN administrative domains
                                   goal: enforce POLICY and business relationships
                                   BGP (the only one in use)

When a router learns the same prefix from multiple protocols, administrative distance (a trustworthiness ranking, Cisco convention) breaks the tie before metrics are even compared:

Connected            0        <- always wins
Static               1
eBGP                20
EIGRP (internal)    90
OSPF               110
IS-IS              115
RIP                120
iBGP               200
Unreachable        255

Note eBGP (20) beats OSPF (110) but iBGP (200) loses to it — a deliberate design that trips people up. Longest-prefix match still applies first (Ch. 13.2); administrative distance only decides between equal-length prefixes.

70.5 Convergence: the number that matters

convergence time = detect + propagate + compute + install (FIB)

detect     link down (fast: ~ms with carrier loss)
           or hello timeout (slow: seconds)  -> use BFD (below)
propagate  flood the change
compute    run SPF / DUAL / best-path
install    push into hardware forwarding tables

BFD (Bidirectional Forwarding Detection) deserves special mention: a lightweight hello protocol running at sub-second (often 50–300 ms) intervals that tells the routing protocol "the neighbour is gone" far faster than protocol hello timers can. It's the standard way to get sub-second failover, and it works with OSPF, IS-IS, and BGP alike.

Try it yourself

# FRRouting gives you real OSPF/BGP on Linux, free
sudo apt install frr
sudo vtysh -c 'show ip route'          # the RIB, with protocol codes and AD
ip route show proto ospf 2>/dev/null   # kernel FIB entries installed by OSPF
ip route show proto bgp  2>/dev/null