How internet routing works

The internet is not one network. It is a network of networks: internet providers, universities, companies, cloud platforms and content providers, each running its own equipment under its own rules. When you open a website hosted on another continent, your packets cross several of these networks, and none of them has a map of the whole internet. Yet every router along the way knows where to send each packet next.

As How IP addresses work explains, each router forwards a packet by looking up the destination in its forwarding table. This article is about where those tables come from: how networks tell each other which addresses they can reach, how they choose between paths, and what happens when someone announces a path they should not.

Two kinds of routing

Routing works on two levels, with different goals:

• Inside a network, the operator wants the fastest path. Its routers run an interior gateway protocol, such as OSPF (RFC 2328) or IS-IS, which learns the network’s whole layout and computes the shortest path to every destination inside it.
• Between networks, there is no common layout and no common goal. Each network decides for itself, often for business reasons, which routes it uses and which it passes on. This is the job of the Border Gateway Protocol (BGP), the routing protocol that connects the networks of the internet.

BGP was first specified in 1989 (RFC 1105). The version in use today, BGP-4, was introduced in 1995 and is defined in RFC 4271 from 2006, with many extensions since.

Autonomous systems

In BGP, the unit is the autonomous system (AS): in the words of RFC 1930, “a connected group of one or more IP prefixes run by one or more network operators which has a single and clearly defined routing policy”. An internet provider is usually one AS; so is a large content provider or a university.

Each AS has a number. AS numbers were originally 16 bits long, allowing 65,536 values; RFC 6793 extended them to 32 bits. IANA hands out blocks of AS numbers to the five Regional Internet Registries, which assign them to networks. A few ranges are reserved:

How networks connect

Two networks that want to exchange traffic connect their routers, either over a private link or at an internet exchange point (IXP), a shared facility where many networks meet. At large exchange points, a route server lets each network exchange routes with many others through a single session (RFC 7947).

The connections follow a few kinds of relationship, which RFC 9234 names:

• Provider and customer. A transit provider carries its customer’s traffic to and from the rest of the internet. A small network might be the customer of two providers, for redundancy.
• Peers. Two networks of similar standing exchange traffic for their own networks and their customers, but not for the rest of the internet.

These relationships decide which routes an AS passes on. Routes learned from a customer are passed to everyone, because carrying that customer’s traffic is the whole point. Routes learned from a provider or a peer are passed only to customers: announcing a route learned from one provider to another provider or a peer would offer to carry traffic between them for free. When that happens by mistake, it is called a route leak (RFC 7908).

BGP sessions and messages

Two routers that exchange routes form a BGP session over a TCP connection on port 179. A session between routers in different ASes is called external BGP (eBGP); a session between routers of the same AS, used to spread the routes it learned across its own network, is internal BGP (iBGP).

BGP uses four messages (RFC 4271):

If a router hears nothing from its neighbor for the hold time, it considers the session dead and withdraws everything it learned from it. RFC 4271 suggests a hold time of 90 seconds and keepalives every third of it. A later extension lets a router ask a neighbor to send all its routes again (route refresh, RFC 2918).

Routers announce routes only when something changes, not periodically. A route is a prefix, such as 198.51.100.0/24, together with path attributes that describe it:

Following an announcement

An AS that holds a prefix originates a route for it. Each AS that passes the route on adds its own number to the front of the AS path.

The AS path does two jobs. It tells every network how many networks a route crosses, which is the main measure of distance in BGP. And it prevents loops: a router that finds its own AS number in a path ignores the route, because accepting it would send packets in a circle.

Note what BGP does not know: bandwidth, latency or congestion. A path through three networks may well be slower than one through five. BGP chooses by policy and AS path, not by speed.

Choosing the best route

A router usually learns several routes to the same prefix, one from each neighbor that offers it, and installs only the best one. RFC 4271 defines the order of the comparison. First comes the degree of preference, set by the network’s own policy and usually expressed as LOCAL_PREF. Only routes with equal preference go on to the tie-breakers.

Policy comes first for a reason: it lets each network follow its own interests. A network may, for example, prefer routes learned from its customers over routes from peers, and those over routes from providers, and set LOCAL_PREF accordingly. Only then does path length matter.

Because nothing stops one network from announcing routes it should not, RFC 8212 requires that a BGP router by default accept and announce nothing on an eBGP session until a policy has been configured. An unconfigured router can no longer leak the routes of the whole internet by accident.

Inside a large AS, every router must learn the external routes. Originally, every router had to hold an iBGP session with every other router; route reflectors (RFC 4456) remove this full mesh by passing iBGP routes on to their clients.

When routing goes wrong

In its basic form, BGP has no way to check that an announcement is genuine: a router believes what its neighbors tell it. Two kinds of problems follow from that.

Route leaks. An AS passes on routes it should have kept, for example routes from one provider to another provider (RFC 7908). Traffic then flows through a network that never intended to carry it and may not have the capacity, which can slow down or cut off large parts of the internet.

Hijacks. An AS announces a prefix that belongs to someone else, by mistake or on purpose. Routers that believe the false announcement send the traffic for that prefix to the wrong network, which can drop it, inspect it or impersonate the real destination. A hijack that announces a more specific prefix is especially effective, because routers forward packets along the longest matching prefix:

Securing BGP

Several layers of protection have been added over the years:

• Filtering. Networks should accept from each customer only the prefixes that customer holds, and filter out obviously wrong routes, such as private address ranges (RFC 7454).
• RPKI and origin validation. The Resource Public Key Infrastructure (RPKI, RFC 6480) lets the holder of a prefix publish a signed Route Origin Authorization (ROA) (RFC 9582): a statement that a given AS may originate the prefix, up to a maximum prefix length. Routers compare each announcement with these statements and classify it as Valid, Invalid or NotFound when no statement covers it (RFC 6811). Networks that drop Invalid routes are protected against hijacks by the wrong origin AS. RFC 9319 advises against generous maximum lengths, which would let a hijacker announce more-specific prefixes with the right origin AS.
• Roles against leaks. RFC 9234 lets two neighbors agree on their relationship in the OPEN message and marks routes accordingly, so that a route learned from a provider or a peer cannot silently be passed to another one.
• Path signatures. Origin validation checks only the first AS in the path; a hijacker can still forge the rest. BGPsec (RFC 8205) has every AS sign the announcements it passes on, so that the whole path can be verified. It requires every router along the path to take part.

Anycast: one address in many places

BGP also enables a powerful technique: anycast. The same prefix is announced from many locations at once, and each network simply sends traffic to the nearest announcement, as measured by BGP (RFC 4786). The DNS root servers, for example, use anycast (RFC 7094): users reach a nearby copy of the service, and an attack or failure in one place stays local.

Key points

• The internet is made of autonomous systems, networks with their own routing policy and an AS number. Inside them, interior protocols find the shortest paths; between them, BGP exchanges routes.
• BGP routers form sessions over TCP port 179 and exchange UPDATE messages that announce prefixes with attributes such as the AS path.
• Each AS adds its number to the AS path, which measures distance and prevents loops. Routers choose routes by policy first (LOCAL_PREF), then by AS path length and further tie-breakers.
• Business relationships decide which routes are passed on. Breaking them causes route leaks; false origins cause hijacks.
• RPKI origin validation, filtering, BGP roles and BGPsec make the system more trustworthy.