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

作者：彭鼎祥

来源：现代电子技术, 2023, 46(15): 20-24.

DOI：10.16652/j.issn.1004-373x.2023.15.004

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

为了解决目前IP路由查表大容量和高吞吐需求的同时，实现低硬件资源成本，提出一种大容量高带宽IP路由查表算法，并完成FPGA实现。算法将FIB表项的存储映射为字典树的数据结构，进行路径压缩和级别压缩以节省存储资源。将字典树根节点信息存储在片内SRAM，子树节点存储于片外DRAM。查找时，在芯片硬件内采用流水线方式优化资源负载均衡，实现片外DRAM的一次访问即可得到结果，实现了单周期线速查表，并支持增量更新。该算法通过FPGA设计实现，并进行仿真和实机验证。结果表明，该方案可同时支持大容量IPv4和IPv6 FIB表项并行查找，与现有方案相比，做到了更大容量、更高带宽和更低成本。

• 单位
  锐捷网络股份有限公司