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

A Memory-Efficient IPv6 Route Lookup Approach

作　　者：姜东虹 郑子豪 李彦彪 JIANG Donghong;ZHENG Zihao;LI Yanbiao(Computer Network Information Center,Chinese Academy of Sciences,Beijing 100083,China;University of Chinese Academy of Sciences,Beijing 100049,China)

机构地区：[1]中国科学院计算机网络信息中心,中国北京100083 [2]中国科学院大学,中国北京100049

出　　处：《中兴通讯技术》2024年第6期31-38,共8页ZTE Technology Journal

基　　金：国家自然科学基金项目(62072430)。

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

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

分 类 号：TP3[自动化与计算机技术—计算机科学与技术]