Nobody types in the internet's routes. Routers tell each other what they can reach, rebuild their tables when a link dies, and agree on a path within seconds. Inside one network that conversation is about distance. Between networks it's about who you're willing to carry traffic for.
Common mix-up: BGP does not look for the fastest path. It picks the path its operator's policy prefers. "Shortest AS path" is only one tie-breaker, it comes after the operator's own preference, and a path through two networks can easily be thousands of miles longer than a path through five.
Chapter 10 showed that every router forwards by looking up its own table. Somebody has to fill those tables. In a home network, that's trivial: one connected LAN, one default route, done. In a network of a few dozen routers it stops being trivial fast.
With static routes, every router needs a line for every network it doesn't touch directly. Ten routers, each with a couple of LANs, means each router carries about twenty hand-typed lines, two hundred in total, and every one has to be right. Add a router and you edit all of them. Worse, static routes don't notice failure. If the link a static route points down goes dark, the route stays, and packets keep marching into the hole until a person fixes it. A backup path does nothing unless someone is awake to switch to it.
Dynamic routing protocols fix both problems by having routers talk. Each router announces what it's connected to; each listens to its neighbors; each computes its own table from what it hears. Add a router and it introduces itself. Cut a link and the routers on both ends notice, tell everyone, and traffic shifts to the next-best path automatically. The time that takes is called convergence, and shortening it is half of what routing engineers worry about.
There are two scales to this. Inside one organization's network, an interior gateway protocol (IGP) such as OSPF or IS-IS finds the shortest path by some measure of distance. Between organizations, the exterior protocol is BGP, and every network on the internet speaks it. They solve different problems, and the difference is the most interesting thing in this chapter.
OSPF isn't the only link-state IGP. IS-IS, standardized by ISO (ISO/IEC 10589) and adapted for IP in RFC 1195, does the same job with the same Dijkstra calculation, and many large internet providers prefer it because it runs directly on the link layer and was easy to extend for IPv6. EIGRP, originally Cisco-only and later published as RFC 7868, is an advanced distance-vector protocol. RIP, the oldest of all, is covered below. Concepts transfer between them almost one-for-one.
There are two basic designs, and the easiest way to keep them apart is with an analogy about directions.
Distance vector is asking for directions. Each router tells its neighbors, "I can reach network N at distance 3." A neighbor that hears this adds the cost of the link between them and thinks, "Then I can reach N at 4, through you." It never sees the network's shape, only the totals its neighbors report. RIP (RFC 2453) is the classic: distance is hop count, every router broadcasts its whole table every 30 seconds, and 16 means unreachable, so a RIP network can't be wider than 15 hops.
The weakness is gossip. Suppose A reaches N through B, and B's link to N dies. Before B can tell anyone, A announces its old route to N, "distance 2", and B, having lost its own, believes it: "then N is 3 away, through A." A hears that B's distance rose and raises its own to 4. They bounce the number upward until it hits infinity, which is why RIP's infinity is a small 16. That's count to infinity. Fixes like split horizon (don't advertise a route back to the neighbor you learned it from) and poison reverse (advertise it back as unreachable) help in simple topologies but not in all of them.
Link state is handing everyone the map. Each router describes only its own surroundings: "I am R4; I have a link to R2 with cost 1 and a link to R5 with cost 10." That description is flooded, unchanged, to every router in the area. Once every router holds every description, every router holds the same complete map, and each one computes shortest paths over it independently. Nobody relies on anyone else's arithmetic. OSPF and IS-IS work this way.
| Design | What a router shares | Who it tells | Strength | Weakness |
|---|---|---|---|---|
| Distance vector | Its whole table: totals per destination | Neighbors only | Simple, little memory | Slow, loop-prone convergence |
| Link state | Only its own links and their costs | Everyone in the area (flooded) | Fast, loop-free once converged | More memory and CPU |
| Path vector (BGP) | Routes plus the list of networks they crossed | Configured peers | Policy control, loop detection by path | Slow by design; trust-based |
OSPF, Open Shortest Path First, is specified for IPv4 as version 2 in RFC 2328 and for IPv6 as version 3 in RFC 5340. Its life cycle has four steps.
1. Meet the neighbors. Each router sends a small Hello packet out of every OSPF interface, by default every 10 seconds on Ethernet, to the multicast address 224.0.0.5. Routers that hear each other's hellos and agree on a few settings (area, timers, subnet) become neighbors. If a neighbor goes silent for the dead interval, four hellos or 40 seconds by default, it's declared down.
2. Describe yourself. Each router writes a link-state advertisement (LSA) listing its links and their costs, stamped with a sequence number and an age.
3. Flood. Every LSA is passed on, reliably and unchanged, until every router in the area has a copy. Together they form the link-state database (LSDB), and in a healthy network every router's LSDB is identical. On a shared Ethernet segment with many routers, one is elected designated router (DR), with a backup (BDR), so everyone syncs with the DR instead of with everyone else.
4. Compute. Each router runs Edsger Dijkstra's 1959 shortest-path algorithm with itself as the root. The result is a shortest-path tree reaching every other router, and from it the routing table: for each destination, the first hop along the tree and the total cost.
The "distance" OSPF minimizes is cost, a number on each interface. RFC 2328 leaves the value to the operator, but nearly every implementation sets it automatically from bandwidth: cost = reference bandwidth ÷ interface bandwidth. Cisco's default reference bandwidth is 100 Mbps, so a 10 Mbps link costs 10 and a 100 Mbps link costs 1. Then the trouble: a 1 Gbps link would cost 0.1, but costs are whole numbers no smaller than 1, so 100 Mbps, 1 Gbps and 10 Gbps links all cost 1, and OSPF can't tell a fast path from a slow one with the same number of hops. The standard advice is to raise the reference bandwidth on every router to at least the fastest link in the network. Try it in the instrument below.
Flooding the whole map to every router has a price: in a very large network, the LSDB gets big, and every flap anywhere makes every router recompute. OSPF's answer is areas. The network is split into areas, each with its own full map, all attached to a central backbone area 0. Routers at the edges, area border routers, pass summaries between areas: not "here is the shape of area 2", only "these prefixes are in area 2 at this cost." A link flapping inside area 2 causes Dijkstra to rerun only inside area 2.
OSPFv2 has several LSA types. The common ones: Type 1, router LSA (a router's own links, flooded within its area); Type 2, network LSA (written by the DR, listing the routers on a shared segment); Type 3, summary LSA (prefixes from another area, written by an area border router); Type 4, ASBR summary (how to reach a router that injects outside routes); Type 5, AS-external (routes from outside OSPF, such as a default route or redistributed static routes). Each LSA is refreshed every 30 minutes and expires at an age of one hour if not refreshed.
Dijkstra's algorithm, step by step: give the root distance 0 and every other router infinity. Repeatedly pick the unsettled router with the smallest known distance and mark it settled; its distance is now final. For each of its neighbors, if going through it is cheaper than the neighbor's current distance, lower that distance and remember the path. When every reachable router is settled, the remembered paths form the tree. With a priority queue it runs in O((V + E) log V) time, a few milliseconds for thousands of routers. The instrument below shows the settle order.
Seven routers. Tap a router to make it the root; tap a link to select it, then change its bandwidth or cut it. Costs are computed from bandwidth and the reference bandwidth, then Dijkstra builds the root's shortest-path tree (thick orange) and its routing table. Numbers on routers are total cost from the root; the small numbers show the order Dijkstra settled them in.
| Destination | Cost | Next hop | Path |
|---|
Convergence is everything that happens between a failure and the moment every router's table reflects it. For a link-state protocol it has four parts: detect the failure, flood the news, compute new trees, and install the new routes into the forwarding hardware.
Detection is usually the slow part. If a fiber is cut, the interface goes down within milliseconds and the router knows at once. But if the link stays up while the far end dies (a crashed router behind a switch, say), OSPF only finds out when hellos stop, which with default timers takes up to 40 seconds. That's why most networks add BFD, Bidirectional Forwarding Detection (RFC 5880): a tiny, fast heartbeat, often every 50 to 300 milliseconds, that tells OSPF the neighbor is gone in under a second.
Flooding takes milliseconds per hop. Running Dijkstra takes milliseconds. Writing thousands of routes into hardware can take longer, and careful implementations update the most important prefixes first. A well-tuned modern network converges in well under a second; with default timers and no BFD it might take most of a minute.
During convergence, routers briefly disagree. One has the new map, its neighbor still has the old one, and for a few hundred milliseconds a packet can bounce between them: a microloop. TTL ends those packets, exactly as in Chapter 10. Techniques like loop-free alternates precompute a backup next hop so a router can switch the instant it detects a failure, before the rest of the network has caught up.
A link that is flapping, going up and down every second, would make every router recompute constantly and could flood the network with LSAs. So implementations throttle: the first change triggers SPF almost immediately, but further changes in quick succession wait longer and longer (an exponential backoff) before the next run. Interfaces can be dampened the same way. It's the same lesson as the flapping adapter in Chapter 10: a network that changes constantly costs everyone listening.
The internet isn't one network. It's tens of thousands of independently run networks, each an autonomous system (AS): a set of routers and prefixes under one administration with one routing policy. Each has an AS number (ASN) assigned through the regional internet registries. ASNs started as 16-bit numbers, about 65,000 of them, ran short, and were extended to 32 bits (RFC 6793). Some ranges are reserved: 64496 to 64511 for documentation (used in the examples here), and 64512 to 65534 for private use.
The Border Gateway Protocol, version 4 (RFC 4271), is how ASes tell each other which prefixes they can reach. Two BGP routers form a session over TCP port 179 and exchange UPDATE messages: announcements of reachable prefixes with their attributes, and withdrawals of ones no longer reachable. Unlike OSPF, BGP doesn't discover neighbors automatically; every session is configured by hand, because every session is a business relationship.
BGP is a path-vector protocol. Every announcement carries an AS_PATH: the list of ASes the announcement has passed through. When AS 64496 announces 203.0.113.0/24, the path is just "64496". When its neighbor 64497 passes it on, it prepends itself: "64497 64496". That list does two jobs. It prevents loops (a router that sees its own ASN in a path rejects the route), and it gives a rough distance measure (fewer ASes is usually better).
A session between routers in different ASes is eBGP (external). Sessions between routers inside the same AS, so that all of its border routers share what they've learned, are iBGP (internal). iBGP routers don't pass routes learned from one iBGP peer on to another, which means they'd all need a session with each other, n × (n − 1) / 2 sessions for n routers; large networks use route reflectors (RFC 4456) to avoid that full mesh.
Here's the part that makes BGP unlike every other routing protocol. Networks pay each other. A customer pays its provider to carry its traffic to and from the rest of the internet. Two networks of similar size often peer: they exchange traffic between their own customers for free, because both benefit. Those relationships produce simple, money-shaped rules that most ASes follow:
The tool for "prefer" is LOCAL_PREF, a number an AS attaches to routes as they arrive and shares only internally. Higher wins, and it's checked before path length. So a network will happily send traffic over a six-AS path through a paying customer rather than a two-AS path through a provider. This is the whole reason the internet's paths aren't the shortest ones.
When a router has several routes to the same prefix, it walks down a fixed list of tie-breakers and stops at the first one that separates them (RFC 4271, section 9.1, plus near-universal vendor practice):
Cisco and some others put a vendor-specific weight before LOCAL_PREF, local to the one router. Many implementations also prefer routes the router originated itself, right after LOCAL_PREF.
Operators steer incoming traffic with AS path prepending: announcing a prefix with your own ASN repeated, "64496 64496 64496", so that path looks longer and the rest of the internet prefers your other links. It's a blunt tool, since LOCAL_PREF anywhere upstream overrides it. Communities (RFC 1997) are tags attached to routes, such as "don't export this to peers" or "prepend twice toward Europe", that let customers ask their providers to apply policy on their behalf.
Four routes to 203.0.113.0/24 arrive at one router. Edit any attribute, pick a scenario, then step through the decision. At each step the routes that lose are struck out; the first step that leaves a single route decides the winner.
| Route | AS_PATH | LOCAL_PREF | ORIGIN | MED | Session | IGP cost | Router ID |
|---|
BGP was designed in an era when every network operator knew the others personally, and it shows. A router believes what its neighbors tell it. Nothing in the base protocol checks that the AS announcing a prefix actually holds it. Combine that with longest-prefix match, which gives traffic to the most specific announcement, and a single mistake can redirect a slice of the internet.
A hijack is announcing someone else's prefix. In February 2008, Pakistan Telecom, ordered to block YouTube domestically, announced a more specific /24 inside YouTube's address block. The announcement leaked out to its provider, and because a /24 beats the /22 YouTube was announcing, much of the world sent YouTube's traffic to Pakistan for about two hours. Hijacks are also done on purpose, to intercept traffic or steal cryptocurrency.
A route leak is announcing real routes to the wrong people, breaking the export rules above. In June 2019, a small network that had routes from one provider re-announced them to another, Verizon, which accepted and spread them. Those routes had been made more specific by a "BGP optimizer" product, so they won. Traffic for large parts of Cloudflare, Amazon and others squeezed through a small network that couldn't carry it, for a couple of hours.
The opposite failure is self-inflicted withdrawal. On 4 October 2021, a maintenance command took down Facebook's backbone; its DNS servers, seeing they'd lost the backbone, withdrew their own BGP announcements as designed. With those prefixes gone from the internet's tables, Facebook, Instagram and WhatsApp vanished for about six hours, and the engineers who could fix it had trouble reaching the buildings because the badge systems depended on the same network.
The main defense today is RPKI, the Resource Public Key Infrastructure (RFC 6480). The registries that hand out address space also issue certificates proving who holds it. A holder signs a Route Origin Authorization (ROA): "prefix 203.0.113.0/24, up to length /24, may be originated by AS 64496." Routers then perform route origin validation (RFC 6811): every received route is marked valid (a ROA matches), invalid (a ROA covers the prefix but the origin AS is wrong or the prefix is longer than allowed), or not found (no ROA). Networks that drop invalids stop most accidental hijacks dead, including the more-specific trick, because the ROA's maximum length forbids it.
Origin validation only checks the last AS in the path. It doesn't stop someone from forging a path that ends in the right origin, or a leak of genuine routes. Newer work addresses those: ASPA records describe each AS's providers so leaks can be spotted, and BGPsec signs the path itself, though it has seen little deployment.
Providers filter what their customers may announce, built from routing registry data (IRR) or from the customer's own ROAs. Many cap the number of prefixes a session may send, so a leak of a full table trips the limit and drops the session. The MANRS initiative (Mutually Agreed Norms for Routing Security) bundles these practices into a public commitment. RFC 9234 adds BGP roles, so a router knows whether a session is to a customer, peer or provider and can refuse to leak automatically.
Normally one prefix lives in one place. Anycast (RFC 4786) deliberately breaks that: the same prefix is announced from many sites around the world, each running an identical copy of a service. Every network on the internet sees several routes to that prefix and, following its normal best-path rules, picks one, usually a topologically nearby site. Users in Tokyo reach the Tokyo copy; users in Frankfurt reach Frankfurt, all at the same address.
DNS is the classic use. There are 13 root server identities, lettered A to M, but each is anycast from many locations, well over a thousand instances in total. Public resolvers and content delivery networks use the same trick. Anycast also absorbs attacks: a flood aimed at one address is spread across every site announcing it.
It works best for short exchanges like DNS queries. A long TCP connection could in principle be switched to another site mid-stream if routing changes, which would break it, though in practice routes are stable enough that large CDNs run TCP over anycast routinely. Anycast is "nearest" only in BGP's sense, which, as this chapter has stressed, is policy and AS count rather than distance.