캐시 친화적인 AVX-512 IPv6 LPM (linearized B+-tree, real BGP benchmarks)

planb-lpm은 PlanB 논문의 IPv6 longest-prefix-match(LPM) 알고리즘을 portable, MIT-licensed C++17 library로 다시 구현한 프로젝트다.

핵심 구성은 다음과 같다.

• header-only core include/lpm6.hpp: AVX-512가 없어도 빌드되며 scalar path로 자동 fallback
• Dynamic FIB lpm6::Dynamic: rebuild-and-swap 방식과 std::atomic<std::shared_ptr>를 사용해 lookup을 wait-free로 처리
• Python bindings: pybind11 기반, pip install -e .로 사용 가능
• Correctness tests: brute-force LPM reference와 synthetic FIB를 비교
• Sample generator: examples/generate_sample.py

벤치마크는 warmup 1회 + timed 20회로 측정하고, min/q1/median/q3/max와 IQR을 함께 공개해 변동성을 드러낸다. 테스트 환경은 Intel i5-1035G7 Ice Lake, Ubuntu 24.04 on WSL, GCC 13.3, -O3이며, 단일 코어에 고정해 측정했다.

결과적으로:

• single과 batch<1>은 거의 동일해 dispatch overhead가 사실상 없다.
• **batch<8>**에서 약 1.5배 수준의 처리량 향상이 나타났다.
• batch<16>은 register pressure 영향으로 일시적인 하락이 있었고, batch<32>는 다시 비슷한 수준으로 회복했다.
• conventional baseline인 Patricia trie 대비 median 기준 약 20배 빠른 결과를 보였다.

메모리 footprint도 비교했다.

• 100K prefixes 기준으로 tree는 4.82 MB, Patricia trie는 6.04 MB 수준
• RSS delta 기준으로도 tree가 더 작았지만, 250K 이상에서는 linearized B+-tree의 depth transition 때문에 footprint가 크게 뛰어 Patricia보다 커질 수 있다.

FIB-size sweep에서는:

• FIB가 커질수록 throughput이 L3 cache를 넘으면서 크게 하락
• 작은 FIB에서는 batch<8>가 유리하지만, 큰 FIB에서는 batch<32>가 더 나은 결과
• rebuild time은 10K에서 1.5 ms, 1M에서 213.4 ms로 대체로 선형적으로 증가

전체적으로, 이 글은 PlanB 계열 IPv6 LPM을 실제로 쓸 수 있는 형태로 정리하고, 속도·메모리·rebuild 비용을 수치로 검증한 기술 공유다.