PlanB: Efficient Software IPv6 Lookup with Linearized B+-Tree
summary
PlanB turns IPv6 LPM into a one-dimensional predecessor search over elementary intervals and stores them in a linearized B+-tree laid out for cache lines. It uses AVX‑512 vector comparisons, batching, branch‑free traversal and loop unrolling, integrates with DPDK, and updates via background rebuild plus atomic pointer swap. Implementation achieves 390 MLPS single‑core (AMD) and 3.4 BLPS across 12 cores, cuts FIB memory 56–92% (≈36 MB for 1M prefixes).
AI-written summary · about
chapters (12)
- 0:00Introduction
- 2:54IPv6 lookup challenges
- 5:04PlanB’s design overview
- 6:53Range conversion
- 7:35Linearized B+-tree search
- 8:35SIMD optimizations
- 10:45Dynamic updates
- 11:50DPDK integration
- 12:34Performance benchmarks
- 14:28Memory footprint
- 15:34Hardware adaptability
- 16:18Key insight
related talks
41mA BPF map for online packet classification
32meBPF: BPF kernel infrastructure
38mModern B-Tree techniques
39mSRv6LB: Leveraging IPv6, Segment Routing, and VPP
30mCilium's BPF kernel datapath revamped
37mEfficient and Flexible Virtual Machine Networking Through eBPF
16mPeeR: First-Class Scheduling for Latency-Critical eBPF Applications
31mThe Next Chapter in the Sordid Love/Hate Relationship Btwn DBs & OSes