esutcu/planb-lpm

源码：https://github.com/esutcu/planb-lpm

planb-lpm

IPv6最长前缀匹配（LPM），使用线性化B+树，基于AVX-512 SIMD及标量回退方案。算法源自：

Zhihao Zhang, Lanzheng Liu, Chen Chen, Huiba Li, Jiwu Shu, Windsor Hsu,
Yiming Zhang.
PlanB: Efficient Software IPv6 Lookup with Linearized B+-Tree.
NSDI ’26. arXiv:2604.14650 (https://arxiv.org/abs/2604.14650).
作者参考代码：.

本仓库是该算法的一个独立、纯净室实现，以可移植、MIT许可的C++17库形式呈现，并额外提供了参考实现中未包含的功能：

• 可移植仅头文件核心 (include/lpm6.hpp)，无需AVX-512即可编译，并透明地回退到标量路径。
• 动态FIB (lpm6::Dynamic)，采用论文中的重建与交换模型，使用std::atomic；查找操作是无等待的。
• Python绑定，通过pybind11实现 (pip install -e .)。
• 正确性测试 (tests/test_correctness.cpp)，在合成FIB上针对暴力LPM参考验证树结构。
• 示例FIB/追踪生成器 (examples/generate_sample.py)。

为何存在

PlanB论文是一个扎实的工程思路，但GitHub上的参考代码无法直接集成到其他项目中：它仅支持Linux和AVX-512，没有许可证，也没有Python层和动态FIB路径。planb-lpm 将论文中的算法重新实现为一个可移植、经过测试、许可宽松的库，使该技术能在研究、教学和生产软件中真正可用。

用例

• 研究/仿真 — 为ns-3或自定义包级模拟器提供即插即用的快速LPM后端，或作为比较更新LPM结构的参考。
• 控制平面工具 — SDN控制器和路由监控服务，需要在大FIB上回答“哪个前缀覆盖此地址？”而不引入完整路由栈。
• 网络分析 — IPv6扫描器、流量分类器和日志富化管道，用覆盖前缀标记流。
• 教学 — 一个紧凑、可读的现代SIMD查找结构实现，适用于网络和计算机体系结构课程。

构建

cmake -B build -DCMAKE_BUILD_TYPE=Release
cmake --build build -j
ctest --test-dir build --output-on-failure

选项：

AVX-512通过 check_cxx_compiler_flag 自动检测；在不支持的CPU或编译器上，将使用标量路径。

运行基准测试

python3 examples/generate_sample.py 100000 1000000 42
./build/planb-lpm examples/sample_fib.txt examples/sample_trace.txt 20

方法

• 合成FIB，包含100,000个前缀。前缀长度分布按RIPE rrc00-25 表加权（大致为/48 45%，/32 11%，/40 10%，/44 10%，/36 4%，其余），由 examples/generate_sample.py 生成。
• 合成追踪，包含100万个均匀随机的64位地址（IPv6地址的上半部分，这是驱动 /0../64 LPM 的全部）。
• 每次基准测试执行一次预热（丢弃）和20次计时。 报告20次运行的最小值、Q1、中位数、Q3、最大值及四分位距，以显示方差，而非隐藏在平均值下。
• 使用 taskset -c <core> 固定到单个核心，以减少调度器噪音。二进制文件会打印其运行的CPU、亲和性掩码宽度、cpufreq 调节器和Intel睿频状态，以确保结果可重现。（在WSL上，/sys 探测不可用，这些行会被静默省略。）
• 硬件：笔记本电脑 Intel i5-1035G7（Ice Lake，4核8线程，AVX-512），Ubuntu 24.04 on WSL，GCC 13.3，-O3。这是消费级CPU；论文的数字来自24核Xeon 8331C和Zen5 Ryzen 9 370HX。

结果

taskset -c 2 ./build/planb-lpm examples/sample_fib.txt examples/sample_trace.txt 20（20次计时运行+1次预热，批量路径使用真实的公共API返回下一跳）：

单位：MLPS；中位数来自四次20次运行滑动平均。该FIB的构建时间约为25毫秒，树深度为6，跨20万条边共有53.1万个键。

观察：

• batch<1> ≈ single — 批量入口在M=1时未增加额外开销，确认调度成本可忽略。
• M=8为最佳点：相比single，单核吞吐量提升约1.5倍。M=32基本持平；更进一步需要在更大的批量展开和寄存器分配上做工作。
• M=16的下降是真实且可重现的——可能是在#pragma GCC unroll 16边界上的寄存器压力与7层遍历相互作用所致。这是一个已知待调查项。 论文的消融实验报告批处理在AMD Zen5上带来3–4.5倍的提升；我们在Ice Lake上只看到约1.5倍。部分差距在于论文的lookup_batch_checksum风格快速路径（我们的二进制文件使用也写入下一跳的公共API），部分是由于Ice Lake和Zen5之间AVX-512持续频率的差异。论文报告在Xeon上单核191–197 MLPS，在Zen5上374–393 MLPS——真正的服务器应能达到接近这些数字。

与常规基线的对比

bench_naive 二进制文件在同一FIB上构建Patricia基数树（tests/patricia.hpp），并运行相同的追踪。Patricia是标准路径压缩二叉树——代表了PlanB旨在替代的指针追逐型LPM结构。

taskset -c 2 ./build/bench_naive ...（相同的20次运行规则）：

单位：MLPS。Tree对Patricia的中位数优势约为20倍，这大致在论文报告的1.6–14倍优势（对比PopTrie、CP-Trie、Neurotrie和HBS）的上限区间内。Patricia并非这些基线之一——它是一个常规基数树的替代——因此当我们针对论文的实际算法进行基准测试时（路线图上的计划，见plan.md），具体的倍率会发生变化。该二进制文件还会在5万个地址的切片上打印线性扫描数字；那是O(N) vs. O(log N)，仅用于合理性检查，而非比较。

内存占用

相同10万前缀的工作负载。footprint_bytes() 计算算法开销（树的扁平键+下一跳数组；每个Patricia节点一个Node结构体）；RSS delta 是进程级别的 VmRSS 在构建前后的变化，捕获分配器开销：

在10万级别，树的扁平缓存对齐布局的RSS约为指针追逐型Patricia的一半。这不适用于大规模——参见下面的FIB规模扫描：线性化B+树按离散深度步长增长（9^depth个桶），因此其足迹受深度下限约束，而非前缀数。一旦深度从6过渡到7（约25万前缀），树的算法大小跃升至约38 MB，并保持到深度7填满为止。Patricia随前缀数线性增长，因此在25万时树实际上大于Patricia。论文报告相比PopTrie/CP-Trie/Neurotrie/HBS的内存减少56–92%；这些结构比普通Patricia更重，因此即使在我们25万的交叉点，论文的优势很可能依然成立。

FIB规模扫描

examples/run_sweep.sh 驱动 planb-lpm、bench_update 和 bench_naive 跨越五个FIB大小，共享一个100万地址追踪，相同20次运行规则，固定到核心2。数字是计时运行的中位数；吞吐量单位MLPS：

（未测量=未测量；Patricia分配和暴力合理性检查在500K+的笔记本电脑上变得不切实际，因此扫描脚本仅在≤250K时运行它们。树在500K/1M时的占用由与250K相同的深度7桶骨架主导，仅随已填满的叶子数增长；我们尚未添加单独的探测。）

观察：

• 吞吐量随FIB超出L3而下降。 笔记本有约6 MB L3；树的扁平占用在100K时低于此值（4.8 MB），从250K起超过。单次查找吞吐量从10K到100K下降4.6倍，从100K到250K再下降2.3倍，一旦溢出L3，主要由内存流量主导。
• 批处理在大规模时帮助最大。 在10K时，batch<8>优于batch<32>（165 vs 148 MLPS）——一切都在L1/L2中，大规模展开只会增加寄存器压力。在1M时，batch<32>是最佳路径（22 vs 14）；长延迟的DRAM访问受益于更多正在执行的负载。
• 深度转换很重要。 深度从5到6发生在10K到100K之间，从6到7发生在100K到250K之间。每增加一级，每次查找就多一次缓存行间接引用，并使哨兵填充的键数增加（从6到7，531K → 4.78M），这推动了树超越Patricia的内存交叉点。
• 重建大致呈线性扩展。 10K/100K/250K/500K/1M分别为1.5/17.7/51.8/107.9/213.4毫秒；论文的Zen5数字为1M时850毫秒，因此我们的Ice Lake笔记本在重建路径上实际快约4倍（可能是因为我们的树构建省略了论文在重建时间中包括的一些预处理）。

数据集警告：这些是使用RIPE加权长度分布的合成FIB，而非真实的BGP表。真实BGP具有更强的前缀长度聚类和广告范围的空间局部性，两者都会改变缓存行为——参见下一节在实际RIPE RIS RIB上的复现。

真实BGP复现（RIPE RIS rrc00）

examples/mrt_to_fib.py 解析TABLE_DUMP_V2 / RIB_IPV6_UNICAST MRT转储（RFC 6396）为planb-lpm FIB。在2026年4月19日的rrc00全表latest-bview.gz上，我们得到254,197个唯一IPv6前缀——正好在论文评估中引用的rrc00范围（≈235K）内。相同的100万均匀随机64位追踪，相同的20次运行规则，固定到核心2：

单位：MLPS。树深度7，4.78M个哨兵填充键，38.4 MB算法占用（与合成250K行相同的骨架）。构建时间为63毫秒，在bench_update下的完整重建中位数为40毫秒（论文在Zen5上1M为850毫秒→按比例约213毫秒/250K；我们的Ice Lake笔记本在40毫秒时快约5倍——可能是因为论文在重建数字中包含了更多预处理）。

吞吐量在真实BGP上大约比相同大小的合成数据高约3倍（single为67 vs 20 MLPS）。合成分布按长度加权，但每个前缀的地址是均匀选择的；真实BGP将广告集中在地址空间的一小部分，因此对真实RIB的均匀随机查找追踪往往命中相同的热树路径，并留在L2中。这与我们预期的“真实数据更差”方向相反——它主要告诉我们，追踪是限制因素，而非FIB。

对Patricia的意外

在真实BGP上，Patricia基线也变得更快——而且快得更多：

Patricia从合成100K上的2.4 MLPS跃升至真实BGP上的95 MLPS——同一台机器上提高40倍，现在超过了树。这里有两件事：

1. 在BGP表上，均匀64位查找在Patricia中提前退出。 大多数随机上半64位地址落入少数高度覆盖的根区域（想想/6、/8、/12）——Patricia在1–2次指针追逐后返回，留在L1中。树总是执行7次缓存行获取，无论最终哪个前缀获胜。
2. 我们的Patricia是替代品，而非论文的基线之一。 论文的1.6–14倍优势是针对PopTrie / CP-Trie / Neurotrie / HBS的——这些结构在每个节点上增加了SIMD和位图加速，而普通的指针树没有；在均匀查找上，它们付出的代价比我们的Patricia更高。与真正论文基线的差距几乎肯定大于我们与Patricia的差距。

诚实的结论：在这种硬件上，在真实BGP表上，针对均匀64位追踪，普通Patricia基数树与树大致相当。树的优势体现在非均匀追踪（真实数据包捕获集中在长前缀上，Patricia需要深入遍历）或与论文的实际基线比较时。两者都在路线图上。

多核扩展

bench_mt 跨T个线程运行batch<8>，每个线程固定到不同的逻辑CPU，所有线程共享一个不可变的lpm6::Tree。线程在每个运行期间同步释放，以测量L3/DRAM争用，而非规避。相同的20次运行规则。笔记本：4个物理核心/8个逻辑核心（SMT）：

效率 = 聚合值在T时 ÷ (T × 聚合值在T=1时)。单位MLPS。

观察：

• T=2是超线性的（在BGP FIB上为1.07×）。在1T时，单个内存绑定查找链在DRAM等待期间使功能单元空闲；在2个核心上使用2T时，硬件有更多正在进行的负载，可以隐藏更多延迟。类似效果在合成数据上也可见。
• 4个物理核心中的4个是最干净的扩展范围。 在4T时，效率约为0.76–0.85×，主要受共享L3限制，一旦热集不再适合每个核心。
• 8T使用SMT（超线程）。 每线程吞吐量崩溃（两个兄弟线程在同一个物理核心上争夺L1/L2和AVX-512端口带宽），但聚合值仍然上升，因为第二个兄弟线程占据了停顿周期。与单核基线的效率降至0.60–0.69×。
• 真实BGP的相对扩展比合成1M更差。 BGP在T=1时的热集已经达到约130 MLPS并留在L2中；更多线程将其推出，每个线程都要付出L3代价。合成1M即使在T=1时也是DRAM绑定的（占用38 MB ≫ L3），因此添加线程相对更便宜——DRAM子系统已是瓶颈。 论文报告在12个Xeon核心上达到3.4 BLPS（§5.4）。我们8线程的笔记本（4个真实核心+SMT）在相同规模的BGP表上达到0.63 BLPS——大约比论文低5倍，这与12个真实核心对比4个真实核心，加上Xeon更宽的L2/更高的持续AVX-512频率相符。适当的比较需要服务器级机器；参见plan.md中的Phase 2.6。

重建/更新成本

PlanB的更新模型是批量的：N个待决的前缀更改被合并为一个完整重建（论文§3.6）。bench_update 在10万前缀的FIB上测量重建时间和每操作延迟：

树重建      : 最小值 17.2 中位数 18.8 最大值 25.0 ms (IQR 1.2)
动态插入(包含重建