大容量高带宽路由查找算法设计与FPGA实现  

Large⁃capacity and high⁃bandwidth routing table lookup algorithm design and FPGA⁃based implementation

作　　者：彭鼎祥 PENG Dingxiang(Ruijie Networks Co.,Ltd.,Fuzhou 350000,China)

机构地区：[1]锐捷网络股份有限公司,福建福州350000

出　　处：《现代电子技术》2023年第15期20-24,共5页Modern Electronics Technique

基　　金：福建省科技重大专项(闽科技[2017]69号);福建省数字经济专项(闽财指[2019]918号)。

摘　　要：为了解决目前IP路由查表大容量和高吞吐需求的同时,实现低硬件资源成本,提出一种大容量高带宽IP路由查表算法,并完成FPGA实现。算法将FIB表项的存储映射为字典树的数据结构,进行路径压缩和级别压缩以节省存储资源。将字典树根节点信息存储在片内SRAM,子树节点存储于片外DRAM。查找时,在芯片硬件内采用流水线方式优化资源负载均衡,实现片外DRAM的一次访问即可得到结果,实现了单周期线速查表,并支持增量更新。该算法通过FPGA设计实现,并进行仿真和实机验证。结果表明,该方案可同时支持大容量IPv4和IPv6 FIB表项并行查找,与现有方案相比,做到了更大容量、更高带宽和更低成本。In order to meet the requirements of large⁃capacity and high⁃throughput of IP(Internet protocol)routing table lookup and realize low hardware resource cost,a large⁃capacity and high⁃bandwidth IP routing table lookup algorithm is proposed and implemented based on FPGA(field programmable gate array).In the algorithm,the storage of FIB(forwarding information base)entries is mapped into the data structure of a Trie⁃tree,and performs path compression and level compression to save storage resources.The root node information of the Trie⁃tree is stored in the on⁃chip SRAM(static random access memory),and the sub⁃tree nodes are stored in the off⁃chip DRAM(dynamic random access memory).When accessing the table,the pipeline method is adopted in the chip hardware and the resource load balance is optimized,and the result can be obtained only by accessing the DRAM once,which can realize the single⁃cycle line⁃speed lookup table and support incremental update.The algorithm is implemented based on FPGA,and simulated and verified by real machine.The results show this algorithm can support simultaneous lookup of the large⁃capacity IPv4 and IPv6 FIB in parallel.In comparison with the existing schemes,the algorithm can achieve greater capacity,higher bandwidth and lower cost.

关 键 词：大容量 高带宽 IP路由表 FIB表 最长前缀匹配 FPGA 字典树算法 流水线 

分 类 号：TN91-34[电子电信—通信与信息系统]