PlanB: Efficient Software IPv6 Lookup with Linearized B + B^{+} -Tree

Zhihao Zhang, Lanzheng Liu, Chen Chen, Huiba Li*, Jiwu Shu, Windsor Hsu, Yiming Zhang · 2026

Read PlanB: Efficient Software IPv6 Lookup with Linearized B + B^{+} -Tree by Zhihao Zhang, Lanzheng Liu, Chen Chen, Huiba Li*, Jiwu Shu, Windsor Hsu, Yiming Zhang (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-14650.txt.

Description

Zhang and six colleagues present PlanB, a high-speed software IPv6 lookup scheme by longest prefix match. They recast longest prefix match, two-dimensional over values and lengths, as a one-dimensional search over elementary intervals. A flat-array B-tree for this transformed space gives the linearized B-plus tree. Its search adds vectorization, batching, loop unrolling, and branch-free logic. On IPv6 forwarding tables, PlanB hits 390 million lookups per second on one core. It scales to 3.4 billion per second on 12 cores, up to 14 times higher than rivals.

Catalog record

CREATORZhihao Zhang, Lanzheng Liu, Chen Chen, Huiba Li*, Jiwu Shu, Windsor Hsu, Yiming Zhang
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE63243
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2604.14650

Browse the full library · About the Tower of Babel