Routing Protocols

Navigating the Internet's Highways#

The internet is not a single network. It is an "inter-network" of tens of thousands of independently run networks owned by ISPs, cloud providers, universities, and companies. A packet from a laptop in New York to a server in Tokyo typically crosses 15 to 20 routers, and no single router knows the whole path. Each one only decides the next hop. Routing is the combination of the tables that hold those decisions and the protocols that keep them up to date when links fail or new networks appear.

The Routing Table#

Every router, and every host, has a routing table: a list of destination prefixes and, for each, where to send the packet next. Your laptop has one too. On Linux:

$ ip route show
default via 192.168.1.1 dev wlan0 proto dhcp metric 600
10.8.0.0/24 dev wg0 proto kernel scope link src 10.8.0.2
192.168.1.0/24 dev wlan0 proto kernel scope link src 192.168.1.23 metric 600

$ ip route get 10.8.0.15
10.8.0.15 dev wg0 src 10.8.0.2 uid 1000

default via 192.168.1.1 is the default route (0.0.0.0/0) for anything not matched more specifically. 10.8.0.0/24 dev wg0 is a connected route: the network is directly attached (here, a VPN interface), so no gateway is needed. ip route get asks the kernel which route it would actually use, which settles arguments faster than reading the table by eye.

On Windows, use route print and PowerShell's Find-NetRoute -RemoteIPAddress 10.8.0.15.

Longest Prefix Match#

When several entries match a destination, the router picks the most specific one, the entry with the longest prefix. If a packet matches both 10.0.0.0/8 and 10.0.1.0/24, the /24 wins. This lets a network advertise a broad aggregate while keeping precise overrides for special cases. It is short enough to write out:

import ipaddress

ROUTES = [
    ("0.0.0.0/0",     "203.0.113.1", "wan0"),   # default route
    ("10.0.0.0/8",    "10.255.0.1",  "core0"),  # whole private block
    ("10.0.1.0/24",   "10.0.1.254",  "lab0"),   # one lab subnet
    ("10.0.1.128/25", "10.0.1.130",  "dmz0"),   # half of that subnet
]
TABLE = [(ipaddress.ip_network(p), nh, dev) for p, nh, dev in ROUTES]

def lookup(dst):
    addr = ipaddress.ip_address(dst)
    matches = [route for route in TABLE if addr in route[0]]
    return max(matches, key=lambda route: route[0].prefixlen)

for dst in ["10.0.1.200", "10.0.1.20", "10.9.9.9", "8.8.8.8"]:
    net, next_hop, dev = lookup(dst)
    print(f"{dst:<12} -> {str(net):<15} via {next_hop} dev {dev}")

10.0.1.200   -> 10.0.1.128/25   via 10.0.1.130 dev dmz0
10.0.1.20    -> 10.0.1.0/24     via 10.0.1.254 dev lab0
10.9.9.9     -> 10.0.0.0/8      via 10.255.0.1 dev core0
8.8.8.8      -> 0.0.0.0/0       via 203.0.113.1 dev wan0

10.0.1.200 matches all four entries and lands on the /25. Real routers do the same thing with prefix tries in software or TCAM in hardware, so the lookup stays fast with the roughly one million prefixes in today's IPv4 internet table. If prefix lengths are unfamiliar, the subnetting lesson covers the arithmetic.

Choosing Between Routes: Prefix, Distance, Metric#

A router can learn the same prefix from several sources at once, for example a static route and OSPF. It chooses in this order:

1. Longest prefix always wins first.
2. For the same prefix, the source with the lowest administrative distance (how much the router trusts that protocol).
3. Within one protocol, the lowest metric (OSPF cost, RIP hop count, and so on).

Cisco's default administrative distances are a common reference point:

Engineers use this deliberately. A floating static route is a static route configured with a high distance (say 250), so it stays hidden while OSPF provides a path and takes over only if OSPF loses the route, which makes it a cheap backup link.

Interior Gateway Protocols: Routing Inside One Network#

IGPs run inside a single organisation, such as a campus, a data centre, or an ISP's own backbone.

• OSPF (Open Shortest Path First) is a link-state protocol. Every router floods descriptions of its links, so every router in an area holds the same map of the topology, then runs Dijkstra's shortest-path-first algorithm on it. Link cost is usually derived from bandwidth.
• IS-IS is also link-state and works much like OSPF. It is common in large ISP backbones because it scales well and carries IPv4 and IPv6 in one protocol instance.
• RIP is a legacy distance-vector protocol that counts only hops (maximum 15). It prefers a path through two slow routers over one through three fast routers, and it converges slowly. You mostly meet it in exams and old networks.

Here is what every OSPF router computes, reduced to a few lines. Note that the output of SPF is not a list of full paths. It is a cost and a first hop per destination, which is exactly what goes into the routing table.

import heapq
from collections import defaultdict

# (router, router): OSPF cost
LINKS = {("A", "B"): 1, ("A", "C"): 10, ("B", "D"): 1,
         ("C", "D"): 1, ("C", "E"): 1, ("D", "E"): 10}

graph = defaultdict(dict)
for (x, y), cost in LINKS.items():
    graph[x][y] = cost
    graph[y][x] = cost

def spf(source):
    dist = {source: 0}
    first_hop = {source: None}
    heap = [(0, source)]
    while heap:
        cost, node = heapq.heappop(heap)
        if cost > dist[node]:
            continue  # stale heap entry, a cheaper path was already found
        for nbr, weight in graph[node].items():
            new_cost = cost + weight
            if new_cost < dist.get(nbr, float("inf")):
                dist[nbr] = new_cost
                first_hop[nbr] = nbr if node == source else first_hop[node]
                heapq.heappush(heap, (new_cost, nbr))
    return dist, first_hop

dist, hop = spf("A")
for dest in sorted(dist):
    if dest != "A":
        print(f"to {dest}: cost {dist[dest]:>2}, next hop {hop[dest]}")

to B: cost  1, next hop B
to C: cost  3, next hop B
to D: cost  2, next hop B
to E: cost  4, next hop B

Router A reaches C through B and D (cost 3) rather than over its direct link (cost 10). That is correct behaviour, but it surprises people who look at a diagram and expect the direct cable to be used.

A classic OSPF mistake: cost is reference bandwidth / interface bandwidth, and on many platforms the default reference is 100 Mbps. A 1 Gbps link and a 100 Gbps link then both cost 1, so OSPF cannot tell them apart and happily sends traffic over the slow path. Set the reference bandwidth higher, and identically on every router, in any network with fast links.

BGP: Routing Between Organisations#

An Autonomous System (AS) is a network under one administrative authority, identified by an AS number. Your ISP, a cloud provider, and a CDN each have one or more. BGP (Border Gateway Protocol) is how ASes tell each other which prefixes they can reach. It is a path-vector protocol: each advertisement carries the list of ASes it has passed through (the AS_PATH), which also prevents loops, since a router rejects any route that already contains its own AS.

BGP does not pick routes by bandwidth. It picks them by policy. The simplified decision order is:

1. Highest local preference, an operator-set value that encodes business policy ("prefer our paid transit over the backup link").
2. Shortest AS_PATH.
3. Lowest origin type, then lowest MED (a hint from a neighbour about which of its entry points to use).
4. Prefer routes learned over eBGP (from another AS) to those learned over iBGP (from inside your own AS).
5. Lowest IGP cost to the BGP next hop, then tie-breakers such as the lowest router ID.

To see which AS originates a prefix, query an IP-to-ASN service such as whois -h whois.cymru.com " -v 8.8.8.8"; public BGP looking glasses show the AS paths towards it from around the world.

When BGP Goes Wrong: Leaks and Hijacks#

BGP was built on trust between operators. If an AS announces a prefix it does not own, or a more specific slice of it, neighbours that accept the announcement send traffic there, and because of longest prefix match a more specific hijack beats the legitimate route everywhere it spreads. Route leaks (re-announcing routes learned from one provider to another by accident) and hijacks (announcing someone else's space) cause real outages and are sometimes used to intercept traffic.

The defences, which every network that runs BGP should deploy:

• Prefix filters on customer and peer sessions, built from routing registry data, so a neighbour can only announce what it is entitled to.
• RPKI Route Origin Validation: address holders publish signed ROAs stating which AS may originate their prefixes and the maximum prefix length. Routers drop announcements marked invalid. RPKI validates the origin only, not the whole path, so it is necessary but not sufficient.
• Max-prefix limits on sessions, so a neighbour that suddenly announces thousands of routes gets shut down instead of absorbed.
• Monitoring services that alert when your prefixes appear from an unexpected origin.

Multipath, Failover, and Convergence#

Production networks never rely on a single path. ECMP (Equal-Cost Multi-Path) installs several next hops for the same prefix and hashes each flow (usually on source/destination IP and ports) onto one of them. Hashing per flow rather than per packet keeps a TCP connection on one path, avoiding reordering. BFD (Bidirectional Forwarding Detection) exchanges very fast hello packets so a dead link is detected in milliseconds, instead of waiting seconds for routing protocol timers. The load balancers lesson uses the same flow-hashing idea one layer up.

Convergence is the time between a failure and every router agreeing on the new paths; packets can loop or be dropped until it completes.

Troubleshooting Routing Problems#

Most "the network is broken" tickets in routed networks come down to a handful of causes:

• Missing return route. You add a route from network A to network B and pings still fail, because B has no route back to A. Traffic needs a path in both directions. Run tcpdump on the far side: if echo requests arrive but no replies leave, the problem is the return path.
• Asymmetric routing through a stateful firewall. The request leaves through firewall 1 and the reply returns through firewall 2, which never saw the SYN and drops the flow. Linux's reverse-path filter (rp_filter) drops asymmetric packets for the same reason.
• A more specific route you forgot. A stale /32 or VPN-pushed route overrides your default. ip route get <dst> exposes it immediately.
• Routing loops. traceroute shows the same two hops alternating until TTL runs out.

The network troubleshooting lesson covers traceroute, mtr, and packet capture in depth.

Practice#

1. Run ip route show (or route print) and identify your default route, connected routes, and any VPN routes. Use ip route get or Find-NetRoute on three destinations and predict the answer before running it.
2. Extend the SPF script: set the A–C cost to 3 and rerun it. Which destinations now have two equal-cost paths that ECMP could share? Change first_hop to store a set of next hops so the script reports both.