PlanB

High-performance IPv6 route lookup using linearized B+-tree with AVX-512 SIMD optimization.

Overview

This repository contains optimized implementations for IP routing table lookups:

• btree-route: Route lookup benchmark using linearized B+-tree with batched SIMD processing
• btree-ablation: Ablation study comparing multiple optimization variants

Algorithm

The implementation uses a linearized B+-tree structure (B=8) with:

1. 1D Interval Transformation: Convert IP prefixes to interval edges
2. Linearized Layout: Cache-friendly array representation of the B+ tree
3. Branch-free Search: Avoid conditional branches in inner node traversal
4. AVX-512 SIMD: Use _mm512_cmp_epu64_mask for parallel key comparison
5. Batched Processing: Process 8 addresses simultaneously with prefetching

Requirements

• CPU: AVX-512F support required
• Compiler: GCC 7+ or Clang 6+ with C++17 support

Check AVX-512 support:

lscpu | grep -i avx512
# or
cat /proc/cpuinfo | grep -i avx512f

Build

Using CMake

mkdir build && cd build
cmake ..
make -j$(nproc)

Using Makefile

make

Usage

btree-route

./btree-route <fib_file> <trace_file>

• fib_file: Forwarding Information Base (format: prefix/len next_hop)
• trace_file: IPv6 addresses to lookup (one per line)

btree-ablation

./btree-ablation <fib_file> <trace_file> [output.csv]

Runs ablation study comparing variants:

Variant	Description
baseline	1D interval + std::lower_bound
linearized	B+ tree with scalar comparison loops
branchfree	Branch-free arithmetic search
simd	AVX-512 inner node search
full	SIMD + batched lookup (PlanB)
autovec	Compiler auto-vectorization hints

Citation

If you use this code in your research, please cite:

@inproceedings {planb,
author = {Zhihao Zhang and Lanzheng Liu and Chen Chen and Huiba Li and Jiwu Shu and Windsor Hsu and Yiming Zhang},
title = {PlanB: Efficient Software IPv6 Lookup with Linearized B+-Tree},
booktitle = {23rd USENIX Symposium on Networked Systems Design and Implementation (NSDI'26)},
year = {2026},
}