首页
|
新闻
|
新品
|
文库
|
方案
|
视频
|
下载
|
商城
|
开发板
|
数据中心
|
座谈新版
|
培训
|
工具
|
博客
|
论坛
|
百科
|
GEC
|
活动
|
主题月
|
电子展
注册
登录
论坛
博客
搜索
帮助
导航
默认风格
uchome
discuz6
GreenM
»
FPGA/CPLD可编程逻辑
» 基于FPGA的高速路由查找算法
返回列表
回复
发帖
发新话题
发布投票
发布悬赏
发布辩论
发布活动
发布视频
发布商品
基于FPGA的高速路由查找算法
发短消息
加为好友
yuchengze
当前离线
UID
1062083
帖子
5837
精华
0
积分
2921
阅读权限
70
在线时间
222 小时
注册时间
2016-6-30
最后登录
2018-9-9
金牌会员
UID
1062083
性别
男
1
#
打印
字体大小:
t
T
yuchengze
发表于 2016-8-23 10:19
|
只看该作者
基于FPGA的高速路由查找算法
高速路
,
路由器
,
命中率
,
因特网
,
路由表
0 引言
随着网络流量的不断增加和路由表容量的不断增大,路由查找已经成为制约因特网的主要瓶颈。尽管采用CIDR技术能产生聚集路由,但路由器的路由表项还是很大,使得路由查找成为高,速路由器的瓶颈。因此,提高路由查找速度已成为高速路由器的关键技术。
目前实现路由查表的方法主要有软件和硬件两类。其中基于软件查表方法的查找次数最少为5次,这显然已经不能满足高速链路的要求;而基于Cache的查找方法,其查找依赖于流量的模式,即IP数据流具有局部性,随着网络数据量的增大,命中率也会降低。而基于硬件的Stanford算法则结构简单,易于硬件实现,而且查找速度快,其最少需要访问一次存储器,最多需要访问2次存储器。但其占用存储空间大(为33 MB),表项更新单元数多。在最坏情况下,更新一个表项需要操作64 k个存储单元。
本文采用多表结构,将查找过程分为4级。
因为采用串行查找实现时,查找一个IP数据包最少需要访问一次存储器,最多需要访问4次。而根据四块存储器独立工作的特性,采用流水线的方式进行并行化设计,则可以保证访问一次存储器就能完成一次数据包的查找。为了保证占用较小的空间且四个存储块的容量相对均衡,本文用一个动态规划算法来求解四个目标层的值。此外,这种设计结构也支持动态更新,并且更新单元数较少。
1 查找算法
本系统的基本算法采用分段查找及前缀扩展技术来将IPv4的32位IP地址分成4段,假设i是其中一段(1≤i≤4),length i代表第i段所对应的IP地址长度。每一段内容存储在一块物理地址连续的内存区域中,称为TBLi。那么,在第一段区域TBL1中,使用前缀扩展技术,即可把所有长度小于等于length1的前缀扩展成长度为length1的前缀。图1所示是该四级路由算法的结构框图。
显然,该结构中的第一段有2length1个表项,析出IP地址的前length1位的值为第一块内存的偏移地址,其对应表项的数据格式如图2所示。若前缀长度小于等于length1,则表项的第一位标识为0,其余bit位表示下一跳的转发信息。若前缀长度大于length1,则表项的第一位标识为1,其余位填写扩展表的索引值可以作为指向TBL2的指针。在其余的三个段中,可采用同样的方法进行前缀扩展。
本算法的查找过程是在匹配一个IP地址时,从第一段开始进行分段查找,每查找一段,则解析出对应段长度的IP,并取相应内存区域的地址。例如进行第二段查找时,可将其值作为偏移量,再加上相应的基址,就可获得该段对length1+1位开始,然后解析出length2长度的IP地址作为偏移量。之后再用TBL1表项里的索引,将其左移length2位作为基址,这样就确定了第二块连续存储区域中的地址。依次类推,分段查找,直到找到下一跳地址为止。
本算法的插入过程与查找过程相似,先根据前缀对应的分段和索引查找到对应的子表,然后在其涉及的范围内读取各个表项,再根据表项的值确定是否用新的路由前缀信息覆盖该表项。如果在此过程中,该表没有相应的段空间,则需分配对应的存储空间。若该段空间为空,则收回该存储空间。
2 目标层的确定
在用NT(k,ω)表示前缀长度为w的情况下,还需要找出k个目标层时对应的最小前缀扩展数。这样,其最优解就是NT(k,ω)。其递推公式如下:
式中,Nu(l,ω)表示将l+1层至ω-1层扩展到ω层的前缀数目,其中若某一层不存在,则将那一层直接忽略。另外,在扩展时还要考虑前缀捕获问题。Nl(ω)是ω层原有的前缀数目。
3 硬件结构
依据该算法设计出的基于4级流水线的并行处理结构如图3所示,该结构分为存储器模块、查找模块和更新模块三个部分。4个存储模块可存储对应表TBL中的数据;查找模块可通过读取对应存储模块中的数据实现查找;更新模块则可将要更新的路由信息添加到对应的存储块中。
在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核心路由器环境下的查找机制。
收藏
分享
评分
回复
引用
订阅
TOP
返回列表
模拟电路
X86
汽车电子
综合技术交流
PowerPC
LED技术
MCU 单片机技术
消费电子
嵌入式技术
DSP技术
电商论坛
Pine A64
资料下载
方案分享
FAQ
行业应用
消费电子
便携式设备
医疗电子
汽车电子
工业控制
热门技术
智能可穿戴
3D打印
智能家居
综合设计
示波器技术
存储器
电子制造
计算机和外设
软件开发
分立器件
传感器技术
无源元件
资料共享
PCB综合技术
综合技术交流
EDA
MCU 单片机技术
ST MCU
Freescale MCU
NXP MCU
新唐 MCU
MIPS
X86
ARM
PowerPC
DSP技术
嵌入式技术
FPGA/CPLD可编程逻辑
模拟电路
数字电路
富士通半导体FRAM 铁电存储器“免费样片”使用心得
电源与功率管理
LED技术
测试测量
通信技术
3G
无线技术
微波在线
综合交流区
职场驿站
活动专区
在线座谈交流区
紧缺人才培训课程交流区
意见和建议