Uploaded June 2026 | Updated September 2026, 3 weeks ago
PlanB: Efficient Software IPv6 Lookup with Linearized B+-Tree
Zhihao Zhang, Alibaba Cloud, NICE Lab, XMU, and Tsinghua University; Lanzheng Liu, Chen Chen, and Huiba Li, Alibaba Cloud; Jiwu Shu, Tsinghua University; Windsor Hsu, Alibaba Cloud; Yiming Zhang, NICE Lab, SJTU, and NICE Lab, XMU
IP lookup via Longest Prefix Match (LPM) is critical for packet forwarding. Unfortunately, conventional lookup algorithms are inefficient for IPv6 Forwarding Information Bases (FIBs), which are characterized by a set of long prefixes with diverse lengths. We observe that LPM inherently represents a two-dimensional (2D) search problem over both prefix values and prefix lengths, but existing algorithms mostly treat LPM as two separate levels of one-dimensional (1D) searches, causing poor lookup performance and high memory overhead.
This paper presents PlanB, a novel scheme for high-speed IPv6 lookup. We transform the 2D LPM into an equivalent 1D search problem over elementary intervals, unifying the search across prefix value and lengths. We then adapt the flat-array B-tree structure to the needs of LPM to propose linearized B+-tree, based on which we introduce an efficient search algorithm tailored to the properties of the transformed space. To maximize performance, we integrate PlanB with vectorization, batching, branch-free logic, and loop unrolling to fully exploit CPU parallelism. Extensive evaluation shows that PlanB achieves single-core performance of 390 Million Lookups Per Sec (MLPS) with real-world IPv6 FIBs on AMD processor, and scales to full-12-core performance of 3.4 Billion Lookups Per Sec (BLPS). This is 1.6×∼14× higher than state-of-the-art software-based schemes (PopTrie, CP-Trie, Neurotrie and HBS).
View the full NSDI '26 program at usenix.org/conference/nsdi26/technical-sessions
PlanB: Efficient Software IPv6 Lookup with Linearized B+-Tree
Zhihao Zhang, Alibaba Cloud, NICE Lab, XMU, and Tsinghua University; Lanzheng Liu, Chen Chen, and Huiba Li, Alibaba Cloud; Jiwu Shu, Tsinghua University; Windsor Hsu, Alibaba Cloud; Yiming Zhang, NICE Lab, SJTU, and NICE Lab, XMU
IP lookup via Longest Prefix Match (LPM) is critical for packet forwarding. Unfortunately, conventional lookup algorithms are inefficient for IPv6 Forwarding Information Bases (FIBs), which are characterized by a set of long prefixes with diverse lengths. We observe that LPM inherently represents a two-dimensional (2D) search problem over both prefix values and prefix lengths, but existing algorithms mostly treat LPM as two separate levels of one-dimensional (1D) searches, causing poor lookup performance and high memory overhead.
This paper presents PlanB, a novel scheme for high-speed IPv6 lookup. We transform the 2D LPM into an equivalent 1D search problem over elementary intervals, unifying the search across prefix value and lengths. We then adapt the flat-array B-tree structure to the needs of LPM to propose linearized B+-tree, based on which we introduce an efficient search algorithm tailored to the properties of the transformed space. To maximize performance, we integrate PlanB with vectorization, batching, branch-free logic, and loop unrolling to fully exploit CPU parallelism. Extensive evaluation shows that PlanB achieves single-core performance of 390 Million Lookups Per Sec (MLPS) with real-world IPv6 FIBs on AMD processor, and scales to full-12-core performance of 3.4 Billion Lookups Per Sec (BLPS). This is 1.6×∼14× higher than state-of-the-art software-based schemes (PopTrie, CP-Trie, Neurotrie and HBS).
View the full NSDI '26 program at usenix.org/conference/nsdi26/technical-sessions
