Routing Protocols — How Packets Find Their Way
When you send a packet from your laptop to a server in another country, it passes through dozens of routers. Each router makes an independent forwarding decision: "which interface should I send this out of?" Routing protocols are what keep every router's forwarding table accurate, so packets converge on their destination across a constantly changing network.
Routing Fundamentals
The Routing Table
Every router maintains a routing table — a list of network prefixes and where to send packets destined for each prefix.
Each entry has:
- Destination prefix — the network this entry covers (e.g.,
10.0.0.0/8) - Next hop — the IP address of the next router to send the packet to
- Outgoing interface — which NIC to use
- Metric — a cost value (lower = preferred)
Default Gateway
The default route (0.0.0.0/0) is the catch-all: if no more specific route matches, send the packet here. Your home router is the default gateway for your laptop.
Hop-by-Hop Forwarding
Routing is not source-to-destination path selection by a single entity. Each router along the path independently looks up the destination IP and forwards to the next hop.
Longest prefix match wins: a route for 10.1.2.0/24 beats one for 10.0.0.0/8 when the destination is 10.1.2.5.
Static vs Dynamic Routing
| Static Routing | Dynamic Routing | |
|---|---|---|
| Configuration | Manually entered by admin | Learned automatically via protocol |
| Adaptability | None — must manually update on failure | Adapts when links go up/down |
| Overhead | Zero protocol traffic | Protocol messages use bandwidth/CPU |
| Scale | Good for small, stable networks | Required for large or changing networks |
| Use case | Default routes, stub networks | ISPs, enterprise, the internet |
Routing Algorithm Families
All dynamic routing protocols implement one of two fundamental approaches.
Distance-Vector Routing
Each router knows only the distance (metric) to each destination and which neighbour to send traffic through. Routers share their tables with neighbours periodically.
The underlying algorithm is Bellman-Ford:
"The best distance to destination v is the minimum, across all my neighbours u, of: the cost to reach u plus u's best distance to v."
The Count-to-Infinity Problem
Suppose this network exists:
All routers know: A→C costs 2 (via B). Now the B-C link fails.
Mitigations:
- Split horizon — don't advertise a route back to the neighbour you learned it from.
- Poison reverse — advertise the route back with infinite cost to explicitly signal unreachability.
- Maximum hop count — treat a metric above 15 (RIP) as unreachable.
Link-State Routing
Each router floods information about its directly connected links to every other router. Every router builds a complete map (topology graph) of the network and runs Dijkstra's shortest-path algorithm locally.
Advantages over distance-vector:
- No count-to-infinity — each router has the full picture.
- Faster convergence — link failures flood immediately.
- More CPU/memory intensive.
RIP — Routing Information Protocol
RIP is the classic distance-vector protocol. It uses hop count as the metric (each router = 1 hop).
- Maximum metric: 15 hops. 16 = unreachable. This limits RIP to small networks.
- Sends full routing table to neighbours every 30 seconds.
- Convergence is slow — in a large network, a failure can take minutes to propagate.
- RIPv2 adds subnet mask support and MD5 authentication.
RIP is rarely used today except in small office environments or embedded devices. Its main educational value is illustrating distance-vector fundamentals.
OSPF — Open Shortest Path First
OSPF (RFC 2328) is the dominant link-state IGP (Interior Gateway Protocol) for enterprise and service-provider networks.
How OSPF Builds the Topology
1. Neighbour Discovery via Hello Packets
OSPF routers send Hello packets every 10 seconds on each interface (multicast to 224.0.0.5). Routers exchange Hello packets to form adjacencies.
2. DR/BDR Election on Broadcast Networks
On a shared segment (Ethernet), all routers forming full adjacency with every other router would generate O(n²) LSAs. Instead, OSPF elects:
- DR (Designated Router) — collects and redistributes LSAs on the segment.
- BDR (Backup Designated Router) — takes over if DR fails.
- All other routers form adjacency only with the DR and BDR.
Election is based on OSPF priority (default 1), then highest Router ID wins.
3. Flooding LSAs (Link State Advertisements)
Each router generates an LSA describing its links and floods it to every router in the area using reliable flooding with acknowledgements.
4. SPF Calculation
Once LSDBs (Link State Databases) are synchronised, every router runs Dijkstra to build a shortest-path tree rooted at itself.
Areas
Large OSPF deployments use areas to limit LSA flooding:
- Area 0 is mandatory — the backbone. All other areas connect to it.
- ABR (Area Border Router) connects two areas and summarises routes between them.
- Flooding within an area is contained; only summarised routes cross area boundaries.
OSPF converges in seconds, scales to thousands of routers, and supports VLSM, route summarisation, and authentication.
BGP — Border Gateway Protocol
BGP (RFC 4271) is the routing protocol of the internet. Every ISP, cloud provider, and large enterprise uses BGP to exchange routing information across administrative boundaries.
Autonomous Systems
The internet is divided into Autonomous Systems (ASes) — networks under single administrative control.
Each AS has a globally unique AS Number (ASN) assigned by regional internet registries (ARIN, RIPE, APNIC). ASNs are 16-bit (1–65535) or 32-bit (up to ~4 billion).
iBGP vs eBGP
| iBGP | eBGP | |
|---|---|---|
| Peers | Within the same AS | Between different ASes |
| TTL | 255 (no direct link required) | 1 (direct link usually required) |
| Next-hop | Not changed | Changed to the peering router |
| Loop prevention | Don't re-advertise to other iBGP peers | AS_PATH — reject if own AS is in path |
BGP Path Attributes
BGP is policy-based routing — it chooses paths based on attributes, not just hop count.
Key attributes (evaluated in order during best-path selection):
| Attribute | Type | Description |
|---|---|---|
| WEIGHT | Cisco proprietary, local | Highest preferred. Not advertised to peers. |
| LOCAL_PREF | Well-known discretionary | Prefer exit point within the AS. Higher = better. |
| AS_PATH | Well-known mandatory | List of ASes the route traversed. Shorter = better. |
| ORIGIN | Well-known mandatory | IGP < EGP < incomplete |
| MED | Optional non-transitive | Metric suggested to neighbouring AS for ingress. Lower = better. |
| NEXT_HOP | Well-known mandatory | IP address of the next-hop router |
Example AS_PATH:
Why BGP Is Policy-Based, Not Shortest-Path
An ISP may prefer a longer AS_PATH if:
- The shorter path goes through a competitor's network.
- The shorter path has lower bandwidth or higher cost.
- A customer pays more for traffic to go a specific way.
This is normal. The internet routes traffic by business relationships as much as by topology.
BGP Hijacking
Because BGP relies on trust — routers accept route advertisements from peers — a misconfigured or malicious router can advertise prefixes it doesn't own.
Famous incidents:
- 2008 Pakistan Telecom accidentally announced YouTube's prefixes (
208.65.153.0/24), blackholing YouTube globally for ~2 hours. - 2010 China Telecom announced ~50,000 prefixes (including US government and military) — traffic briefly routed through China.
- 2018 MyEtherWallet BGP hijack redirected crypto wallet DNS traffic to steal funds.
Mitigations:
- RPKI (Resource Public Key Infrastructure) — cryptographic proof that an AS is authorised to originate a prefix.
- IRR (Internet Routing Registry) — WHOIS-like database for checking prefix ownership.
- BGP prefix filtering — only accept prefixes from peers that match their registered allocations.
- Maximum prefix limits — disconnect a peer that sends more prefixes than expected.
A Packet from London to Tokyo
Here's what happens when you reach a server in Tokyo from London, traced through ASes:
Each eBGP handoff is between different ASes with different routing policies. The path chosen may not be the geographically shortest — it's the one that BGP's best-path algorithm selected given all attributes.
Python: Basic Traceroute with Sockets
This mimics the real traceroute tool: it sends UDP probes with increasing TTL values. Each router that decrements TTL to zero returns an ICMP "Time Exceeded" message, revealing its IP address and the round-trip time.
Summary
| Protocol | Type | Algorithm | Scope | Metric | Use Case |
|---|---|---|---|---|---|
| RIP | Distance-vector | Bellman-Ford | IGP | Hop count (max 15) | Small/legacy networks |
| OSPF | Link-state | Dijkstra | IGP | Cost (bandwidth-based) | Enterprise, SP interior |
| BGP | Path-vector | Policy + attributes | EGP | AS_PATH + attributes | Internet between ASes |
The internet's routing infrastructure is a decentralised, policy-driven system built on trust and business relationships. Understanding BGP helps you reason about latency anomalies, regional outages, and why traffic sometimes takes surprising paths across the globe.