基于FPGA的高速路由查找算法
加入技术交流群
3 硬件结构
依据该算法设计出的基于4级流水线的并行处理结构如图3所示，该结构分为存储器模块、查找模块和更新模块三个部分。4个存储模块可存储对应表TBL中的数据；查找模块可通过读取对应存储模块中的数据实现查找；更新模块则可将要更新的路由信息添加到对应的存储块中。本文引用地址：https://www.eepw.com.cn/article/191858.htm
在FPGA设计时，每个查找模块都是一个硬件逻辑块，每两个查找模块间都有一个寄存器用以传输数据，每个查找模块都可从输入端或寄存器中读取信息，并解析出IP地址中的相应位，然后计算存储器的访问地址，访问存储器获取数据，并将数据写入寄存器或者输出端。四个查找模块按流水线的工作方式进行处理，能够达到访问一次存储器处理一个IP数据包。
4 实验结果分析
通过对BGP Table中前缀的长度进行分析和统计，可模拟生成50,000条前缀。然后用动态规划求出4个目标层(20，22，24和32)来进行实验分析。实验可采用Stratix系列芯片，并利用Ver-ilog硬件描述语言和QuartusII开发平台进行设计、综合、布局布线，然后在静态时序分析后进行仿真，其时序仿真结果如图4所示。由于查找需要一个时钟周期，而时钟频率为100MHz，所以，每秒可以完成100M次查找。若IP分组为40B长，则可以满足20Gbps的链路速率。
5 结束语
本文给出了一种基于前缀扩展的分段快速路由查找算法。该算法可以结合硬件实现的优点，并运用多级流水线处理方法，因而具有查找速度快、支持动态更新和实现简单等优点，十分适合于20 Gbps核心路由器环境下的查找机制。
评论