How to Trace TCP IP Rule Route Evaluation Latency in Linux Using eBPF

Policy-Based Routing (PBR) allows Linux network administrators to direct network traffic through custom routing tables based on incoming interface, source IP prefix, firewall mark (fwmark), or user ID. However, as cloud environments, container networks (such as Calico or Cilium), and VPN endpoints scale, the Routing Policy Database (RPDB, managed via ip rule) can accumulate dozens or hundreds of rules. Because the Linux kernel evaluates these rules sequentially for every outbound socket connection, bloated rule lists introduce latency overhead into initial TCP connection establishment. Using eBPF, systems engineers can trace rule evaluation latency and identify bottlenecked FIB lookups.

Understanding the Linux RPDB Rule Evaluation Chain

When an application calls connect() or transmits a packet on an unrouted socket:

• The kernel calls fib_rules_lookup(), which traverses the linked list of rules ordered by priority (0 to 32767).
• Each rule executes a comparison callback (e.g. matching source CIDR or skb->mark).
• If matched, the kernel performs a trie lookup in the designated routing table (fib_table_lookup()). If no matching route exists, evaluation falls through to subsequent rules.
• High-priority rules that fail frequently waste CPU cycles across every active connection handshake.

Tracing Rule Lookup Latency with bpftrace

Deploy a real-time eBPF script targeting the kernel functions fib_rules_lookup() and fib_rule_match():

# Install bpftrace on Ubuntu/Debian
sudo apt-get update && sudo apt-get install -y bpftrace linux-headers-$(uname -r)

# Trace RPDB rule evaluation duration and matching rule priorities
sudo bpftrace -e '
kprobe:fib_rules_lookup {
    @start[tid] = nsecs;
}
kretprobe:fib_rules_lookup /@start[tid]/ {
    $dur_ns = nsecs - @start[tid];
    @fib_lookup_ns = hist($dur_ns);
    if ($dur_ns > 10000) { // Highlight lookups taking longer than 10 microseconds
        printf("Long FIB rule lookup: %llu ns (PID %d COMM %s)
", $dur_ns, pid, comm);
    }
    delete(@start[tid]);
}
kprobe:fib_rule_match {
    $rule = (struct fib_rule *)arg0;
    @evaluated_rule_prio[$rule->pref] = count();
}'

The resulting histogram exposes the distribution of lookup times and identifies which rule priorities are evaluated most frequently.

Inspecting Policy Rules and Route Resolutions with ip

Inspect the system-wide rule hierarchy and measure resolution performance:

# View current policy routing rules
ip rule show

# Test routing resolution for a target IP
ip route get 1.1.1.1 mark 0x20

# Sample output:
# 1.1.1.1 dev eth1 table 100 src 192.168.1.50 mark 0x20 uid 1000
#     cache <src-direct>

Optimising Routing Policy Architecture

To eliminate FIB rule lookup latency on high-throughput Linux hosts:

1. Consolidate Rules: Replace multiple individual IP match rules with CIDR blocks or ipset lookups to reduce sequential list traversals.
2. Place Frequent Rules at the Top: Assign lower preference numbers (e.g. priority 100–500) to the rules handling 90% of traffic, ensuring fast returns.
3. Utilize Nexthop Objects: Modern Linux kernels (5.3+) support nexthop groups (ip nexthop) that decouple route path calculations from rule lookups, dramatically accelerating FIB evaluation.