Title: Trie-Structure-Guided Compression, Allocation, and Mapping for Storage-Efficient IPv6 Lookup Pipelines
Authors: Donghong Jiang, Zhenhao Yuan, Yanbiao Li, Shi Meng, Yuxuan Chen (Computer Network Information Center, Chinese Academy of Sciences; University of Chinese Academy of Sciences); Taiji Chen (Peking University); Xian Yu, Gaogang Xie (Computer Network Information Center, Chinese Academy of Sciences; University of Chinese Academy of Sciences)
Introduction
IPv6 forwarding tables keep growing, and the memory available for line-rate route lookup is becoming a more serious constraint. Trie-based algorithmic longest-prefix matching (ALPM) is common in high-speed routers, but most previous designs mainly ask how compactly the trie itself can be encoded. A pipelined implementation has another bottleneck: each stage owns a finite amount of memory, and IPv6 trie nodes are not distributed evenly across levels. If one stage fills first, unused memory in other stages cannot help, so the maximum FIB size may be much smaller than the total memory budget suggests.
SCAMP-Trie treats this as a joint design problem. Compression determines the cost of each node, node mapping determines how that cost is spread across stages, and memory allocation determines the capacity available at each stage. The paper argues that these three choices need to be optimized together if the goal is to maximize the FIB that fits in a lookup pipeline.
Key idea and contribution:
The authors first introduce a Trie-based Pipelined Lookup Model (TPLM) that captures per-prefix storage cost, pipeline memory utilization, and maximum prefix capacity in one framework. Measurements of IPv6 tries reveal an inverse-distance pattern: nodes that are farther from descendant leaves are much rarer. SCAMP-Trie uses this InvDist property to define feasible stage ranges. Rare high-InvDist nodes can be placed earlier, while the much more numerous near-leaf nodes and a larger share of memory are shifted toward later stages.
A warning-line-based dynamic mapping algorithm places nodes for a given memory allocation, and simulated annealing searches for a good memory ratio across pipeline stages. To keep compression compatible with that flexible mapping, the trie representation uses flexible child indexing, sub-trie next-hop compression, and half-size node formats. The important point is that compression is no longer allowed to force a rigid node layout that would prevent stage balancing.
Evaluation
The evaluation uses 36 IPv6 FIBs in four scenarios: 23 real FIBs collected from RIPE RRCs, plus 13 synthesized FIBs consisting of seven ISP-edge cases, three cloud-gateway cases based on published AWS, Azure, and Google address-allocation practices, and three host-network cases. SCAMP-Trie reaches 93.2-96.5% memory utilization on backbone FIBs, 72.0-91.1% on ISP FIBs, 84.4-86.9% on cloud gateways, and 73.2-87.3% on host FIBs. Across the full set, the paper reports a 4.0-times average improvement in storage utilization over existing approaches and a 3.0-67.3-times increase in prefix capacity under the same memory budget.
The compression mechanisms are also important on their own: in representative backbone, ISP, cloud, and host FIBs, the combined node formats reduce memory use by 55.6%, 74.1%, 76.9%, and 91.4%. The offline allocation search takes about 71 minutes to converge in the reported experiment, after which the selected ratios remain stable across FIB growth and multi-year snapshots. Incremental updates average 142K per second, with 3.4-19.8 microseconds P99 latency across the 36 FIBs. On a Xilinx XCVU13P FPGA, SCAMP-Trie stores about 240K prefixes using 41.11% BRAM and 0.96% LUTs. The fully pipelined lookup runs at 402.9 MHz and produces one result per cycle; assuming a 256-byte average packet size, that rate corresponds to 768.47 Gbps of lookup capacity rather than measured end-to-end router-port throughput.
Q&A
Q: How does SCAMP-Trie handle routing-table changes? Is there a special mechanism for fast updates?
The authors explained that there is no special update mechanism; instead, the update logic is kept simple enough to support efficient routing-table changes.
Q: How about lookup latency?
The authors explained that the pipeline can complete one lookup per cycle, which enables high lookup throughput.
Personal thoughts
I like the paper’s decision to treat stage imbalance as part of the data-structure problem. A trie can be compact in total bytes and still fit poorly in a real pipeline if one stage becomes the bottleneck. TPLM makes that distinction explicit, and InvDist gives the mapping algorithm a concrete structural signal instead of relying only on generic bin packing. The separate measurements of compression, mapping, allocation, update cost, and FPGA resources make it easier to see where the gains come from.
The main uncertainty is the representativeness of the non-backbone datasets. The RIPE FIBs are real, but the ISP, cloud-gateway, and host cases are synthesized because production tables are not public. The stage-allocation search is also offline and takes about 71 minutes, although the paper shows that the resulting ratios transfer well across time and FIB growth. A production ASIC study with sustained route churn would be the most useful next validation, especially for understanding how often allocation or mapping would need to change in practice.