对基于FPGA的高速路由查找算法的研究
2 目标层的确定
在用NT(k,ω)表示前缀长度为w的情况下,还需要找出k个目标层时对应的最小前缀扩展数。这样,其最优解就是NT(k,ω)。其递推公式如下:
式中,Nu(l,ω)表示将l+1层至ω-1层扩展到ω层的前缀数目,其中若某一层不存在,则将那一层直接忽略。另外,在扩展时还要考虑前缀捕获问题。Nl(ω)是ω层原有的前缀数目。
3 硬件结构
依据该算法设计出的基于4级流水线的并行处理结构如图3所示,该结构分为存储器模块、查找模块和更新模块三个部分。4个存储模块可存储对应表TBL中的数据;查找模块可通过读取对应存储模块中的数据实现查找;更新模块则可将要更新的路由信息添加到对应的存储块中。
在FPGA设计时,每个查找模块都是一个硬件逻辑块,每两个查找模块间都有一个寄存器用以传输数据,每个查找模块都可从输入端或寄存器中读取信息,并解析出IP地址中的相应位,然后计算存储器的访问地址,访问存储器获取数据,并将数据写入寄存器或者输出端。四个查找模块按流水线的工作方式进行处理,能够达到访问一次存储器处理一个IP数据包。
4 实验结果分析
通过对BGP Table中前缀的长度进行分析和统计,可
5 结束语
本文给出了一种基于前缀扩展的分段快速路由查找算法。该算法可以结合硬件实现的优点,并运用多级流水线处理方法,因而具有查找速度快、支持动态更新和实现简单等优点,十分适合于20 Gbps核心路由器环境下的查找机制。
评论