ip-backbone

How it is built

Architecture overview

An ISP backbone carries the traffic of millions of customers between cities and to the rest of the internet. It is a set of routers joined by long, expensive links, and it has three jobs: always know the shortest working path between any two routers, forward packets along it at line rate, and keep traffic flowing when a link or router fails, all without a human in the loop. The idea that makes it work is a layered control plane over a simple forwarding plane. A link-state routing protocol (IS-IS or OSPF) gives every router the same map of the network; BGP adds the routes learned from customers and other networks; both are compiled into a forwarding table that the line cards use for every packet. Labels (MPLS or segment routing) let the network carry traffic along a chosen path that is not simply the shortest one.

The core routers (P) only forward labelled packets; the edge routers (PE) face customers and peers, hold the BGP routes and map customer traffic onto the label paths. Reliability comes from detecting a failure in milliseconds, switching to a pre-computed repair path before routing has reconverged, and only then recomputing the best paths.

Parts:

• Interior routing — every router learns the topology and computes shortest paths — Link-state routing (no page yet), built on Dijkstra's algorithm, Message sequence numbers
• Exterior routing — exchanges reachability with customers, peers and transit providers, and applies policy — BGP (no page yet), RPKI route origin validation (no page yet)
• Forwarding plane — the per-packet lookup and replication — Longest-prefix match (no page yet), ECMP (no page yet), Packet header parsing (no page yet), IP multicast
• Label paths — carry traffic along chosen paths — MPLS label switching (no page yet), Segment routing (no page yet)
• Traffic engineering — places traffic so links do not overload — Traffic engineering (no page yet), built on Simplex method, Max flow (Dinic), BFS and DFS
• Fast recovery — detects failures and switches to a repair path at once — Fast reroute (no page yet), BFD (no page yet)
• Queues and QoS — protects important traffic under congestion — Token bucket, Fair queuing (no page yet), Active queue management (no page yet)
• Measurement — finds heavy flows and watches load — Count-min sketch, Exponential smoothing (ETS, Holt-Winters), d-ary heap, Fast hash functions, PRNGs (PCG, xoshiro)

        customers / peers                                        customers / peers
              │ eBGP                                                   │ eBGP
         ┌────┴────┐  iBGP via route reflectors (BGP)            ┌────┴────┐
         │   PE    │◄───────────────────────────────────────────►│   PE    │
         └────┬────┘                                             └────┬────┘
              │  IS-IS/OSPF (link-state) + MPLS or segment routing    │
         ┌────┴────┐        ┌─────────┐        ┌─────────┐       ┌────┴────┐
         │   P     │════════│    P    │════════│    P    │═══════│   P     │
         └─────────┘  ECMP  └────┬────┘  FRR   └─────────┘       └─────────┘
                                 │ BFD on each link
           control plane: LSDB → SPF → RIB (+BGP) → FIB ─► line cards (LPM, labels, queues)

How the parts fit together

Interior routing

Link-state routing (no page yet) floods each router's links and metrics to all others, so every router holds the same database and runs the same computation. IS-IS (RFC 1195, ISO 10589) and OSPF version 2 (RFC 2328) differ in encoding and some details, not in the idea. Flooding must be reliable and ordered: every advertisement has a sequence number and a lifetime (Message sequence numbers); a router accepts only a higher number and reflects it to its neighbours. On a change, the router runs Dijkstra's algorithm from itself, with a priority queue (d-ary heap) as the standard implementation choice, and installs the next hops. The computation is throttled with an initial delay and exponential back-off so a flapping link does not keep the CPU in SPF. The result is the router's view of how to reach every loopback address, which BGP and the labels then build on. The IGP also carries traffic-engineering attributes and segment-routing labels (RFC 5305 for IS-IS, RFC 3630 for OSPF, RFC 8667 and RFC 8665 for segment routing).

Exterior routing

BGP (RFC 4271) is a path-vector protocol: each announcement carries the list of networks it passed through, and each router selects one best path per prefix by a fixed order of attributes and policy, then passes it on. Inside the backbone, iBGP carries the externally learned routes between the edge routers; a full mesh does not scale, so routers peer with a few route reflectors (RFC 4456). Multiprotocol extensions (RFC 4760) carry other address families, among them customer VPN routes (RFC 4364). A full internet table is of order 10⁶ IPv4 prefixes, so BGP (no page yet) implementations need compact attributes sharing and incremental updates.

Anyone can announce anything, so the backbone checks origins. RPKI route origin validation (no page yet) uses signed statements (route origin authorisations) held in a public-key infrastructure (RFC 6480). A validator outside the router checks them and feeds the routers a list of valid prefix and origin-AS pairs over the RPKI-to-Router protocol (RFC 8210). The router classifies each received route as valid, invalid or not-found (RFC 6811), and policy typically rejects invalid ones.

Forwarding plane

Everything the control plane computes ends in a forwarding table (FIB) that a line card consults per packet. Packet header parsing (no page yet) extracts the fields; Longest-prefix match (no page yet) finds the most specific route (a multibit trie in software, a TCAM or algorithmic memory in hardware); the entry yields a set of next hops. When there are several equal-cost paths, ECMP (no page yet) picks one by hashing the flow's header fields with a Fast hash functions-style function, so packets of one flow stay in order while flows spread (analysis in RFC 2992). Two details matter. Hash polarization: every router using the same hash function and field set sends the same flows the same way and unbalances the later stages, so each router mixes in its own seed (drawn from a PRNGs (PCG, xoshiro)). Resilient hashing: when one next hop disappears only its flows move. A single huge flow cannot be split by ECMP at all, so it caps the benefit. Multicast traffic (streaming, market data, IPTV) is replicated in the network by IP multicast, driven by reverse-path checks against the unicast table.

Label paths

MPLS label switching (no page yet) (RFC 3031) puts a short label in front of the IP packet. The ingress router pushes labels, core routers swap and look up an exact label instead of a prefix, and the egress pops. The path is whatever the label distribution made it: LDP (RFC 5036) follows the IGP's shortest path; RSVP-TE (RFC 3209) sets up explicitly routed, bandwidth-reserving paths. Segment routing (no page yet) (RFC 8402) removes the per-path signalling: the ingress encodes the path as a list of segment identifiers that the IGP already advertised, and core routers keep no per-path state. It runs on an MPLS data plane (RFC 8660) or on IPv6 (RFC 8986), and RFC 9256 defines policies that bind a path (a list of segments) to a service. Customer VPNs ride on these paths: the transport label gets the packet across the core, an inner label tells the egress PE which customer table to use.

Traffic engineering

Shortest paths alone leave some links full and others idle. Traffic engineering (no page yet) places traffic on non-shortest paths under constraints, using link attributes the IGP advertises (reservable bandwidth, administrative colours). A router can compute a constrained shortest path itself (CSPF), or a central path computation element can see the whole network, solve the placement problem and push the paths to routers (PCEP, RFC 5440, topology via BGP-LS, RFC 7752). The central version formulates demand placement as a flow problem: a Simplex method minimises the highest link utilisation subject to capacities; Max flow (Dinic) tells how much traffic a pair of sites can exchange and where the minimum cut (the bottleneck) sits, which is also the planning check for survivability; reachability and hop-count checks use BFS and DFS. The requirements for TE over MPLS are written in RFC 2702.

Fast recovery

When a link fails, routing needs hundreds of milliseconds to seconds to reconverge, and voice and financial traffic must not wait. Two pieces solve it. BFD (no page yet) (RFC 5880) is a lightweight hello protocol that runs per link (or per path) at short fixed intervals with a multiplier, so a failure is detected in tens of milliseconds (order of), long before the IGP's own timers; it is typically offloaded to the line card. Fast reroute (no page yet) pre-computes, for each destination, a backup next hop that is already installed in the forwarding table: loop-free alternates (RFC 5286) when a neighbour that does not loop back exists, remote alternates (RFC 7490) when it does not, and topology-independent LFA over segment routing (RFC 9855), which covers any single-link or node failure by steering the packet through the post-convergence path. Switchover is a local table swap, with a target of under 50 ms. The IGP then reconverges, and the repair is withdrawn.

Queues and QoS

Even a well-provisioned backbone has short congestion. DiffServ (RFC 2475) marks packets into classes at the edge; policing uses a Token bucket to keep each customer to its contract. In the core, Fair queuing (no page yet) (deficit round robin, with a strict-priority queue for the expedited class, RFC 3246) shares link capacity by weight so one class or flow cannot starve the others. Active queue management (no page yet) drops or ECN-marks (RFC 3168) packets before the buffer fills so TCP slows down early: RED uses a smoothed queue length (Exponential smoothing (ETS, Holt-Winters)) and random drops; CoDel (RFC 8289) and PIE (RFC 8033) react to delay instead. RFC 7567 sets the general recommendations.

Measurement

Operations need to know which flows or prefixes dominate and when load departs from normal. Counting every flow needs too much memory, so routers export sampled records and collectors keep a Count-min sketch: a few rows of counters estimate any key's volume, overestimating a little, and a small heap (d-ary heap) keeps the current top talkers. The same pipeline watches for sudden volume to one destination (a likely denial-of-service attack) against a smoothed baseline.

Data and control flow

Flow 1: one customer packet across the backbone (L3VPN).

1. The ingress PE receives the packet on a customer-facing interface and looks up the destination in that customer's table.
2. The result gives a BGP next hop (the egress PE) and a VPN label; the IGP/label layer gives the transport label for that egress.
3. The PE pushes both labels and hashes the flow to choose one of the equal-cost paths.
4. Each P router swaps the outer label by exact match; the penultimate router pops it.
5. The egress PE reads the VPN label, finds the customer table and forwards the plain packet. Per hop the work is one table lookup and a queue; time in the network is dominated by link propagation (about 5 µs per km in fibre, order of).

Flow 2: a core link fails.

1. BFD declares the link down within tens of milliseconds, or the interface signals loss of light faster.
2. The line card switches every affected entry to its pre-installed backup next hop; traffic flows again.
3. The router floods a new advertisement; every router runs SPF after its throttle delay and installs new best paths.
4. Backup entries are replaced by the post-convergence primaries. Ordered updates avoid a transient loop between routers that switch at different times.

Flow 3: a new route is announced by a neighbour.

1. The BGP session receives the update; inbound policy filters by prefix, AS path and origin validation state.
2. The best-path selection compares it with the existing routes; if it wins, it is installed and advertised to peers and reflectors.
3. The FIB is updated incrementally on the line cards.

Scaling

1. Table size. The IPv4 table keeps growing; levers are compact FIB structures, hierarchical FIBs so a next-hop change touches one entry rather than a million routes, and filtering what the core needs (default routes at the edge).
2. Convergence. Bound by detection, flooding and SPF time. Levers: BFD, fast reroute, prefix-independent convergence, incremental SPF and LSP pacing.
3. Control-plane state. Route reflector hierarchies, IGP levels or areas, and segment routing (no per-path state in the core) keep each router's workload bounded.
4. Link utilisation. First ECMP, then traffic engineering via a central controller; capacity is added when the optimiser cannot find room.
5. Packet rate. Hardware forwarding chips; software routers need Kernel-bypass networking style packet I/O to reach even a fraction of that.

Failure modes

Real implementations

The alternative: a centralised, software-defined network where one controller computes all paths and programs simple switches, instead of distributed routing protocols. It gives global optimisation and simpler failure policy but makes the controller a critical dependency; large operators use a hybrid, with distributed protocols for basic connectivity and a central computation for traffic engineering.

Sources

• IETF RFCs: 4271 (BGP-4), 4456 (route reflection), 4760 (multiprotocol BGP), 4364 (BGP/MPLS IP VPNs), 2328 (OSPFv2), 1195 (IS-IS for IP), 5305 and 3630 (TE extensions), 3031 (MPLS architecture), 5036 (LDP), 3209 (RSVP-TE), 8402 (segment routing), 8660 (SR with MPLS), 8986 (SRv6 network programming), 9256 (SR policy), 5440 (PCEP), 7752 (BGP-LS), 5880 (BFD), 5286 and 7490 (LFA, remote LFA), 9855 (TI-LFA), 6480, 6811, 8210 (RPKI, origin validation, RTR), 2992 (ECMP analysis), 2475, 3246 (DiffServ, EF), 3168 (ECN), 8289 (CoDel), 8033 (PIE), 7567 (AQM recommendations). All at rfc-editor.org (replace the number in the URL).
• S. Floyd and V. Jacobson, Random Early Detection Gateways for Congestion Avoidance, IEEE/ACM Transactions on Networking, 1993. M. Shreedhar and G. Varghese, Efficient Fair Queuing Using Deficit Round-Robin, 1995/96.
• G. Cormode and S. Muthukrishnan, An Improved Data Stream Summary: The Count-Min Sketch and its Applications, Journal of Algorithms, 2005.
• FRRouting documentation: docs.frrouting.org; BIRD: bird.network.cz; SONiC: sonic-net.github.io/SONiC.