Packet Reordering in Kernel

In this lesson, you will learn how to implement sequence-aware algorithms to reconstruct packet order in highly parallelized Linux kernel networking paths.

The Challenge of Parallel Processing

When utilizing multi-core systems, especially with techniques like XDP_REDIRECT or Receive Side Scaling (RSS), packets from the same flow are often processed by different CPUs simultaneously. Because these CPUs operate at different speeds or encounter varying cache contention, packets can arrive at the protocol stack out-of-order. Since TCP and other stateful protocols rely on sequence numbers, delivering out-of-order packets to the stack forces retransmissions and degrades throughput.

Implementing a Reordering Buffer

To manage this in the kernel, we use an eBPF program attached to a TC (Traffic Control) ingress hook. The goal is to buffer "future" packets until the missing "gap" packets arrive.

We maintain a BPF_MAP_TYPE_HASH acting as a sequence buffer. The logic follows these steps:

1. Sequence Check: Extract the sequence number from the TCP header.
2. State Tracking: Compare the incoming sequence against the expected_seq stored in a per-flow map.
3. Buffer or Pass:
   • If the sequence matches expected_seq, pass the packet up the stack and increment the expected value.
   • If the sequence is greater, store it in the map as "pending" and drop the packet (or hold it).
   • If the sequence is less than the expected, discard it as a duplicate.

struct seq_val {
    __u32 expected_seq;
    __u32 pending_pkts[MAX_BUFFER];
};

// Simplified logic within a TC BPF hook
__u32 seq = tcp_hdr->seq;
struct seq_val *val = bpf_map_lookup_elem(&flow_map, &flow_key);

if (seq == val->expected_seq) {
    val->expected_seq += payload_len;
    return TC_ACT_OK; // Pass to stack
} else if (seq > val->expected_seq) {
    bpf_map_update_elem(&reorder_buffer, &seq, &packet_data, BPF_ANY);
    return TC_ACT_SHOT; // Drop/Hold to prevent out-of-order delivery
}

By enforcing strict ordering at the TC layer, you ensure that the downstream kernel networking stack never sees a gap in the stream, maintaining flow integrity despite the parallel nature of your underlying data path.

Key Takeaway: Packet reordering in parallel systems requires an eBPF-based state machine that holds future sequence numbers in a shared map until the missing gap is filled, ensuring sequential flow integrity.