对基于FPGA的高速路由查找算法的研究

2009-12-20 22:14:52来源: 西安电子科技大学 关键字: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位作为基址,这样就确定了第二块连续存储区域中的地址。依次类推,分段查找,直到找到下一跳地址为止。

  本算法的插入过程与查找过程相似,先根据前缀对应的分段和索引查找到对应的子表,然后在其涉及的范围内读取各个表项,再根据表项的值确定是否用新的路由前缀信息覆盖该表项。如果在此过程中,该表没有相应的段空间,则需分配对应的存储空间。若该段空间为空,则收回该存储空间。

[1] [2]

关键字:FPGA  高速路由  查找  算法

编辑:小甘 引用地址:http://www.eeworld.com.cn/FPGA/2009/1220/article_866.html
本网站转载的所有的文章、图片、音频视频文件等资料的版权归版权所有人所有,本站采用的非本站原创文章及图片等内容无法一一联系确认版权者。如果本网所选内容的文章作者及编辑认为其作品不宜公开自由传播,或不应无偿使用,请及时通过电子邮件或电话通知我们,以迅速采取适当措施,避免给双方造成不必要的经济损失。

上一篇:基于FPGA的智能误码测试仪
下一篇:一种基于FPGA的AGWN信号生成器的设计

关注eeworld公众号 快捷获取更多信息
关注eeworld公众号
快捷获取更多信息
关注eeworld服务号 享受更多官方福利
关注eeworld服务号
享受更多官方福利
推荐阅读
全部
FPGA
高速路由
查找
算法

小广播

独家专题更多

TI车载信息娱乐系统的音视频解决方案
TI车载信息娱乐系统的音视频解决方案
汇总了TI汽车信息娱乐系统方案、优质音频解决方案、汽车娱乐系统和仪表盘参考设计相关的文档、视频等资源
迎接创新的黄金时代 无创想,不奇迹
迎接创新的黄金时代 无创想,不奇迹
​TE工程师帮助将不可能变成可能,通过技术突破,使世界更加清洁、安全和美好。
TTI携TE传感器样片与你相见,一起传感未来
TTI携TE传感器样片与你相见,一起传感未来
TTI携TE传感器样片与你相见,一起传感未来

夏宇闻老师专栏

你问我答FPGA设计

北京航空航天大学教授,国内最早从事复杂数字逻辑和嵌入式系统设计的专家。

电子工程世界版权所有 京ICP证060456号 京ICP备10001474号 电信业务审批[2006]字第258号函 京公海网安备110108001534 Copyright © 2005-2017 EEWORLD.com.cn, Inc. All rights reserved