PlanB: Efficient Software IPv6 Lookup with Linearized $B^+$-Tree
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910171911946240 |
|---|---|
| author | Zhang, Zhihao Liu, Lanzheng Chen, Chen Li, Huiba Shu, Jiwu Hsu, Windsor Zhang, Yiming |
| author_facet | Zhang, Zhihao Liu, Lanzheng Chen, Chen Li, Huiba Shu, Jiwu Hsu, Windsor Zhang, Yiming |
| contents | 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, thereby unifying the search across prefix value and lengths. We then adapt a flat-array-based B-tree structure to the needs of LPM to propose the 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$\times$$\sim$14$\times$ higher than state-of-the-art software-based schemes (PopTrie, CP-Trie, Neurotrie and HBS). |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_14650 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | PlanB: Efficient Software IPv6 Lookup with Linearized $B^+$-Tree Zhang, Zhihao Liu, Lanzheng Chen, Chen Li, Huiba Shu, Jiwu Hsu, Windsor Zhang, Yiming Data Structures and Algorithms Networking and Internet Architecture 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, thereby unifying the search across prefix value and lengths. We then adapt a flat-array-based B-tree structure to the needs of LPM to propose the 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$\times$$\sim$14$\times$ higher than state-of-the-art software-based schemes (PopTrie, CP-Trie, Neurotrie and HBS). |
| title | PlanB: Efficient Software IPv6 Lookup with Linearized $B^+$-Tree |
| topic | Data Structures and Algorithms Networking and Internet Architecture |
| url | https://arxiv.org/abs/2604.14650 |