我們閱讀並認真對待每一份回饋意見。

欲查看所有可用的限定符，請參閱我們的文件。

使用線性化 B+-樹結合 AVX-512 SIMD 和純量備援路徑的 IPv6 最長字首比對 (LPM)。基於以下論文的演算法：

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://github.com/nicexlab/planb .

此儲存庫是該演算法的獨立、乾淨重寫版本，作為一個可移植的、MIT 授權的 C++17 函式庫，並包含參考程式碼中未包含的額外功能：

PlanB 論文是一個紮實的工程構想，但 GitHub 上的參考程式碼並非可以直接整合到其他專案中的東西：它僅限於 Linux 和 AVX-512，沒有授權，沒有 Python 層，也沒有動態 FIB 路徑。planb-lpm 將論文中的演算法重新表達為一個可移植、經過測試且具有寬鬆授權的函式庫，以便該技術能夠真正用於研究、教學和生產軟體。

AVX-512 透過 check_cxx_compiler_flag 自動偵測；在不支援的 CPU 或編譯器上，將使用純量路徑。

taskset -c 2 ./build/planb-lpm examples/sample_fib.txt examples/sample_trace.txt 20 (20 次計時執行 + 1 次預熱，批次路徑使用返回下一跳的實際公開 API)：

單位：MLPS；滾動平均四次 20 次執行掃描的 median。該 FIB 的建置時間約為 25 毫秒，樹深度為 6，橫跨 200k 個邊緣的 531k 個鍵。

論文的消融實驗報告稱，在 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 基數 trie (tests/patricia.hpp)，並透過相同的追蹤進行執行。Patricia 是一種標準的路徑壓縮二進位 trie — 是 PlanB 旨在取代的指標追蹤 LPM 結構的代表。

taskset -c 2 ./build/bench_naive … (相同的 20 次執行規則)：

單位：MLPS。樹與 Patricia 的比較約為 median 的 20 倍，接近論文報告的 1.6–14 倍優於 PopTrie、CP-Trie、Neurotrie 和 HBS 的上限。Patricia 並非這些基準測試之一 — 它是一個傳統的基數 trie 替代品 — 因此當我們與論文的實際演算法進行基準測試時，確切的倍數會有所不同（在路線圖上，請參閱 plan.md）。該二進位檔還會列印一個 50,000 個位址切片的線性掃描數字；這是 O(N) 對比 O(log N)，僅作為健全性檢查，而非比較。

相同的 100,000 個字首工作負載。footprint_bytes() 計算演算法成本（我們的樹的扁平快取對齊佈局 + 下一跳陣列；每個 Patricia 節點一個 Node 結構）；RSS delta 是建置過程中的進程級 VmRSS 變化，並捕捉配置器開銷：

在 100K 時，樹的扁平快取對齊佈局的 RSS 開銷約為指標追蹤 Patricia 的一半。這在規模擴大時並不成立 — 請參閱下面的 FIB 大小掃描：線性化 B+-樹以離散的深度步驟（9^depth 個儲存桶）增長，因此其佔用空間受深度而非字首計數的約束。一旦深度從 6 轉換到 7（約 250K 個字首），樹的演算法大小就會跳到約 38 MB 並保持在那裡，直到深度 7 填滿。Patricia 隨字首線性縮放，因此在 250K 時，樹實際上比 Patricia 更大。論文報告記憶體減少 56–92% 相較於 PopTrie/CP-Trie/Neurotrie/HBS；這些比單純的 Patricia 更重，因此即使在我們的 250K 交叉點，論文的優勢很可能仍然成立。

examples/run_sweep.sh 在五種 FIB 大小上驅動 planb-lpm、bench_update 和 bench_naive，使用一個 1M 位址的追蹤，相同的 20 次執行規則，固定在核心 2。數字是計時執行的 median；吞吐量單位是 MLPS：

(n/m = 未測量；在筆記型電腦上，500K+ 的 Patricia 配置和暴力健全性檢查變得不切實際，因此掃描腳本僅對 ≤250K 執行。500K / 1M 的樹佔用空間由與 250K 相同的深度 7 儲存桶骨架主導，僅隨填充葉節點計數而增長；我們尚未添加單獨的探測。)

資料集注意事項：這些是具有 RIPE 加權長度分佈的合成 FIB，而非真實的 BGP 表格。真實的 BGP 具有更強的字首長度聚類和廣告範圍內的空間局部性，這兩者都會改變快取行為 — 請參閱下一節關於實際 RIPE RIS RIB 的重現。

examples/mrt_to_fib.py 解析 TABLE_DUMP_V2 / RIB_IPV6_UNICAST MRT 轉儲 (RFC 6396) 成 planb-lpm FIB。在 2026-04-19 的 rrc00 全表最新視圖 (bview.gz) 上，我們獲得了 254,197 個唯一的 IPv6 字首 — 正好在論文評估中引用的 rrc00 範圍內（約 235K）。相同的 1M 單純隨機 64 位元追蹤，相同的 20 次執行規則，固定在核心 2：

單位：MLPS。樹深度 7，4.78M 個哨兵填充鍵，38.4MB 的演算法佔用空間（與合成 250K 行相同的骨架）。建置時間為 63 毫秒，bench_update 下的完整重建 median 為 40 毫秒（論文在 Zen5 上為 850 毫秒/1M → 約 213 毫秒/250K 規模；我們的 Ice Lake 筆記型電腦在 40 毫秒內約快 5 倍 — 可能因為論文將更多預處理捆綁到重建數字中）。

相較於真實 BGP，Patricia 基線也變得更快 — 提升幅度更大：

Patricia 在同一台機器上從 100K 合成數據的 2.4 MLPS 跳升到真實 BGP 的 95 MLPS — 提升了 40 倍，並且現在領先於樹。有兩件事在發生：

誠實的結論：在此硬體上，在真實 BGP 表格上，針對單純的 64 位元追蹤，單純的 Patricia trie 大致與樹相當。樹的優勢體現在非單純追蹤（真實封包擷取集中在 Patricia 深度遍歷的長字首）或論文的實際基線。兩者都在路線圖上。

bench_mt 運行 batch<8>，跨 T 個執行緒，每個執行緒固定在一個獨立的邏輯 CPU 上，所有執行緒共享一個不可變的 lpm6::Tree。執行緒在每次執行時以鎖步方式釋放，因此測量的是 L3 / DRAM 爭用，而非規避。相同的 20 次執行規則。筆記型電腦：4 個實體核心 / 8 個邏輯核心 (SMT)：

效率 = T 個執行緒的總計 / (T × 1 個執行緒的總計)。單位 MLPS。

論文報告在 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 在 100,000 個字首的 FIB 上測量重建時間和每個操作的延遲：

論文報告在 AMD Zen5 伺服器上重建 1M 字首 FIB 需要 850 毫秒；線性縮放意味著我們的 100K 設定約為 85 毫秒，我們在 Ice Lake 上看到約 19 毫秒，因此重建路徑在硬體雜訊範圍內相當。

將這些數字視為一個可重現性檢查，表明該演算法在通用硬體上的表現符合論文預期，而非作為競爭性評估。

此儲存庫中的所有檔案均為 MIT 授權下的原創作品 — 請參閱 LICENSE.md。作者的參考實現在 https://github.com/nicexlab/planb 未被引入；請參閱上述論文以了解演算法本身。

0.1.0 版本的樹已在 Ubuntu 24.04 / GCC 13.3 (Intel Ice Lake) 的以下配置中建置和測試：

核心演算法來自 Zhang 等人的 PlanB 論文（見文件頂部）；此儲存庫中的所有原始碼均為獨立重寫。

歡迎任何大小的貢獻 — Bug 報告、新硬體上的基準測試結果、替代 SIMD 後端、語言綁定、文件修訂。請參閱 CONTRIBUTING 以了解開發工作流程、提交約定，以及如何在開啟 pull request 前運行完整的驗證套件（純量備援、ASAN/UBSAN、-Werror、pip install -e .）。