一种存储高效的IPv6路由查找方法

摘要：由于IPv6前缀相比IPv4更长，如何在保证查找性能的同时提高存储效率成为一项关键挑战。现有基于Trie、哈希和三态内容可寻址存储器（TCAM）的路由查找方法在存储效率和查找性能上均存在一定局限性。为此，提出了一种基于前缀拆分模型的集合查找方法（SetSearch），旨在实现高效的IPv6路由查找与存储。SetSearch通过前缀拆分模型实现高效的片内存储，并采用路由二维映射表，避免了叶推导致的IP前段爆炸问题，从而显著降低片外存储开销。此外，SetSearch还通过基于路由二维映射表的集合查找方法，将片外访存次数减少到最多一次。基于5个真实IPv6骨干路由器转发信息表（FIB）数据集的实验评估结果表明，SetSearch在片内存储、片外存储和片外访存次数等方面展现了优异的综合性能。

关键词：IPv6；路由查找；转发信息表；高效存储

Abstract: Given that IPv6 prefixes are longer than IPv4, enhancing storage efficiency without compromising lookup performance has become a critical challenge. Existing route lookup methods—such as Trie-based structures, hashing, and ternary content addressable memory (TCAM)—have limitations in storage efficiency or lookup speed. To address these challenges, this paper proposes SetSearch, a method based on the prefix-split model, to achieve efficient IPv6 route lookup and storage. SetSearch enhances on-chip storage through prefix splitting and uses a two-dimensional routing table to prevent the explosion of IP prefixes caused by leaf-pushing, significantly reducing off-chip storage demands. Furthermore, SetSearch minimizes off-chip memory accesses to a maximum of one by utilizing a set search strategy based on the two-dimensional routing table. Experimental evaluations using five real-world IPv6 backbone router forwarding information bases (FIBs) datasets demonstrate that SetSearch offers superior performance across metrics such as on-chip storage, off-chip storage, and off-chip memory access efficiency.

Keywords: IPv6; route lookup; forwarding information base; memory-efficient