What all of this means

Who this is for. If you already know what BFD and XDP are, skip straight to part 1; nothing here will be new. This part exists for everyone else: people who found the series through the Linux or eBPF side and do not do routing, people who do routing and have never written a BPF program, and anyone who wants to follow the argument without first reading three RFCs. Nothing later in the series assumes you read this, but everything later assumes you know these words.

The problem in one paragraph

Two routers are connected. One of them dies, or the link between them breaks. How fast does the other one find out? If the answer is “thirty seconds”, every packet sent during those thirty seconds is dropped into a hole. The job of the protocol this series is about is to make that answer “thirty milliseconds” instead, and the whole project is about what it takes to keep that promise on an ordinary Linux box that is busy doing other things.

The routing side

BFD (Bidirectional Forwarding Detection). A deliberately stupid protocol whose only job is to notice that a neighbour has stopped answering. Two systems send each other small UDP packets at a fixed interval, and if enough consecutive packets go missing, the link is declared down. It is defined in RFC 5880, with RFC 5881 covering the single-hop case and RFC 5883 the multihop one.

It is stupid on purpose. Because it does one thing, it can do it far faster than the routing protocols themselves, which is why they lean on it.

Detect time, and “3x10ms”. A session is configured with a transmit interval and a multiplier. 3x10ms means “send every 10 milliseconds, declare the link dead after 3 missed”, so a 30ms detect time. Aggressive timers mean fast detection and less tolerance for lateness. That trade is the entire subject of this series.

Flap. A session going down and then back up. Usually the link was fine and the packets were merely late, which makes a flap worse than useless: it tears down working routes.

Session. One BFD conversation between two endpoints. A router with many neighbours runs many sessions at once, which is why the later parts care about what happens at 64 of them.

FRR (FRRouting). The open-source routing suite most Linux routers run. It implements BGP, OSPF, IS-IS, and the rest as separate daemons. bfdd is its BFD daemon, and it is both the thing measured in part 1 and the source of the six upstream bugs this project ended up reporting.

Distributed BFD, and the “dataplane”. FRR can hand the actual packet handling to an external program over a small protocol called bfddp, keeping only session setup and reporting for itself. It exists so hardware vendors can attach their own forwarding hardware. This project attaches to it as a software dataplane, which is why FRR bugs kept turning up: that code path had rarely been driven hard by anyone.

Echo mode. A BFD feature where you send a packet addressed to yourself, the neighbour’s forwarding hardware loops it straight back without its software ever seeing it, and you time the round trip. It tests the neighbour’s data path rather than its software. Covered in part 9.

GTSM, TTL 255. Every IP packet carries a hop counter that decreases each time a router forwards it. If you insist that arriving packets still read 255, you know nobody forwarded them, so the sender must be directly attached. It is a cheap way to reject spoofed traffic from far away.

Discriminator. A number each side picks to identify its end of a session, so packets can be matched to the right conversation.

The Linux side

Kernel space and user space. The kernel is the part of the operating system that owns the hardware. Ordinary programs, including routing daemons, run in user space and must be scheduled onto a CPU before they can do anything. That “must be scheduled” is where the trouble starts.

The scheduler, and starvation. When more work wants CPU than there is CPU, the kernel scheduler decides who runs. A program that is not chosen does not run at all, and a BFD daemon that is not running is not sending packets. Being starved for 300ms is enough to kill a 30ms session.

SCHED_FIFO, and RT throttling. Linux has real-time priorities. A SCHED_FIFO task outranks all ordinary tasks and runs until it yields. To stop a runaway real-time task locking the machine, the kernel reserves a small slice, roughly 50ms per second, for everyone else. If real-time work saturates every core, an ordinary program gets that one slice and nothing more. This is the condition no user-space design in part 3 survives.

Softirq. Work the kernel defers slightly, then runs at higher priority than any ordinary program, including most packet processing. Code that runs in softirq context keeps running when user-space programs are starved, which is exactly the property this project needs.

eBPF. A way to load small, verified programs into the running kernel. The kernel checks them for safety first, so they cannot crash it or loop forever. They are how you add behaviour to the kernel without patching it.

XDP (eXpress Data Path). An eBPF hook at the earliest possible point of packet receive, before the kernel has built any of its normal packet structures. An XDP program looks at a packet and returns a verdict.

If you have never seen one, the shape is the whole idea. This is not from the project, it is the smallest thing that shows what a verdict means:

SEC("xdp")
int hello(struct xdp_md *ctx)
{
        void *data     = (void *)(long)ctx->data;
        void *data_end = (void *)(long)ctx->data_end;
        struct ethhdr *eth = data;

        /* The verifier requires proving every read is in bounds. */
        if ((void *)(eth + 1) > data_end)
                return XDP_PASS;

        if (eth->h_proto == bpf_htons(ETH_P_IPV6))
                return XDP_DROP;   /* discard, never reaches the stack */

        return XDP_PASS;           /* carry on to the normal kernel path */
}

There are three verdicts that matter here: XDP_PASS to continue to the normal stack, XDP_DROP to discard the packet outright, and XDP_TX to send it straight back out the interface it arrived on.

Note the bounds check. Every read from a packet has to be provably in-bounds before the kernel will load the program, which is what makes it safe to run untrusted code in the receive path, and also what makes writing it feel unlike ordinary C.

The crucial limitation, and the hinge of this whole project: XDP can only react to a packet that has arrived. It cannot create one. That is why part 4 stops trying to transmit and starts bouncing the peer’s own packets back instead.

BPF maps. Shared tables that BPF programs and ordinary programs can both read and write. They are how the kernel half and the user-space half of this engine exchange configuration and state.

bpf_timer. A timer that fires inside the kernel and runs a BPF function. Used here to notice sessions that have gone quiet, since silence delivers no packet and therefore triggers no XDP program.

Offload. Moving work off the general-purpose CPU onto something that is always available. Hardware routers offload BFD to dedicated line cards. This project offloads it to the kernel’s receive path, which is the nearest thing an ordinary Linux box has to a line card.

The measurement side

p50, p99, and max. If you sort every measurement, p50 is the middle value and p99 is the value 99% fall below. They describe the typical case and the common bad case. Max is the single worst.

This distinction is not pedantry, it is the finding in part 1: a BFD daemon flapping badly enough to tear down routes had a completely healthy-looking p99, because the events that killed it were rare. Anything that summarises away the maximum hides this class of failure entirely.

Inter-packet gap. The time between one packet leaving and the next. For BFD this is the number that matters, because a long gap is what makes the far end give up.

pcap, and tcpdump. A packet capture is a recording of what actually crossed the wire. tcpdump makes one. Every number in this series comes from a capture taken outside the machine under test, on the virtualisation host, because a starved program’s own logs lie about what it sent and when.

stress-ng. A tool for deliberately loading a machine in specific ways: CPU, context switching, timers. The “stress ladder” in this series is four escalating levels of it.

Topotest. FRR’s integration test framework. It builds a small virtual network of routers and asserts things about their behaviour. Getting one written for a dataplane bug turned out to be most of the work in one of the upstream fixes.

Ready

That is the vocabulary. Part 1 starts by measuring whether the received wisdom about software BFD is actually true.