基于哈希表与多比特树的路由查找算法

发布时间：2017-08-04 19:28

  本文关键词：基于哈希表与多比特树的路由查找算法

  更多相关文章： 路由器 路由查找 哈希表 多比特树 最长前缀匹配

【摘要】：网络带宽的急剧增加对处于网络节点的路由器设备数据转发速度提出了更高的要求。为此,将哈希表和多比特树相结合,提出一种新的路由查找算法。根据路由前缀的长度将路由表项分层存储在固定的三层Tree中,采用哈希表存储路由下一跳的信息,根据目的 IP地址在三层Tree结构中按最长前缀匹配的原则进行快速路由表项定位,并通过表项的信息在对应的哈希表中读取下一跳信息,进行数据转发。在多核平台上的测试结果表明,该算法在百万条路由环境下可达到双向10 GB/s的速度,平均查找次数介于1~2次之间,平均延时小于30μs。
【作者单位】： 光纤通信技术和网络国家重点实验室;武汉烽火网络有限责任公司;
【关键词】： 路由器 路由查找 哈希表 多比特树 最长前缀匹配
【基金】：国家“863”计划基金资助项目“软件定义网络体系结构与关键技术研发与示范”(2015AA016100)
【分类号】：TP301.6;TP393.05
【正文快照】： 中文引用格式:范富明,李念军,雷升平,等.基于哈希表和多比特树的路由查找算法[J].计算机工程,2015,41(9):63-67.英文引用格式:Fan Fuming,Li Nianjun,Lei Shengping,et al.Route Lookup Algorithm Based on Hash Table and Multi-bitTree[J].Computer Engineering,2015,41(9):

【参考文献】

中国期刊全文数据库 前7条

1 殷科,邓亚平;基于RAM和TCAM存储结构的高速路由查找算法[J];计算机工程与应用;2005年20期

2 王亚刚;杜慧敏;杨康平;;使用Hash表和树位图的两级IPv6地址查找算法[J];计算机科学;2010年09期

3 华泽;班建民;陆悠;;基于分段地址结构的快速路由查找算法[J];计算机与数字工程;2009年10期

4 汪志莉;沈富可;;一种基于哈希表和Trie树的快速内容路由查找算法[J];计算机应用与软件;2009年10期

5 杜飞;董治国;苗琳;庹宇鹏;;基于无冲突哈希表和多比特树的两级IPv6路由查找算法[J];计算机应用;2013年05期

6 张琦;金胤丞;李苗;章建雄;;Trie树路由查找算法在网络处理器中的实现[J];计算机工程;2014年01期

7 陆笑天;李曦;周学海;纪金松;;基于前驱查找的快速IP路由查找和更新方案[J];计算机工程;2007年13期

【共引文献】

中国期刊全文数据库 前4条

1 邓亚平;周美红;;基于多层混合结构的IPv6路由表查找算法[J];计算机应用;2013年02期

2 杜飞;董治国;苗琳;庹宇鹏;;基于无冲突哈希表和多比特树的两级IPv6路由查找算法[J];计算机应用;2013年05期

3 付仲满;张辉;李苗;刘涛;;Hash算法在网络处理器中的实现[J];计算机工程;2014年09期

4 刘阳;;基于三级索引和Trie的IPv6路由查找算法研究[J];山东农业大学学报(自然科学版);2015年04期

中国博士学位论文全文数据库 前1条

1 王亚刚;IP路由器系统芯片关键技术研究[D];西安电子科技大学;2012年

中国硕士学位论文全文数据库 前10条

1 余晓磊;WSN路由算法的研究[D];华东师范大学;2011年

2 泰冬雪;基于Hadoop的海量小文件处理方法的研究[D];辽宁大学;2011年

3 廖文斌;网间加速技术研究与实现[D];华中科技大学;2011年

4 徐军霞;WSN节点感知区域模型实验研究[D];华中科技大学;2011年

5 张理阳;一种基于哈希策略的路由查找算法[D];长沙理工大学;2011年

6 周小尧;基于网络处理器的分布式入侵检测系统研究与设计[D];中南大学;2007年

7 谢文亮;基于FPGA的入侵检测系统的网络包分类技术研究[D];广州大学;2007年

8 严锦芸;高速网络信息过滤系统设计与实现[D];华中科技大学;2007年

9 程冕;面向网络取证的CDMA2000报文处理与分流技术[D];国防科学技术大学;2012年

10 张云;基于软件路由器的网络环境自动构建技术研究[D];哈尔滨工业大学;2014年

【二级参考文献】

中国期刊全文数据库 前10条

1 李振强;郑东去;马严;;TSB:一种多阶段IPv6路由表查找算法[J];电子学报;2007年10期

2 孔婷;;IPv4网络向IPv6网络的演进[J];福建电脑;2008年01期

3 陈蹊;赵跃龙;;多分枝trie树路由查找算法研究[J];电子设计工程;2010年03期

4 刘英臣;傅光轩;;路由查找技术的分析及研究[J];贵州大学学报(自然科学版);2006年03期

5 崔尚森,张白一;一种基于哈希表和Trie树的快速IP路由查找算法[J];计算机工程与应用;2005年09期

6 喻梅;吴普青;赵政;于健;;基于B~+树的分布式哈希表路由结构[J];计算机工程与应用;2008年01期

7 王亚刚;杜慧敏;杨康平;;使用Hash表和树位图的两级IPv6地址查找算法[J];计算机科学;2010年09期

8 吴强,苏金树,王勇军;基于Patricia树的快速多维分组分类算法[J];计算机工程;2004年21期

9 孙庆南;鲁士文;;一种改进的二分法IPv6路由查找算法[J];计算机工程;2006年18期

10 徐海;徐涛;;一种改进的网络选播路由算法[J];计算机工程;2008年01期

中国硕士学位论文全文数据库 前1条

1 郭文文;基于TRIE的软转发路由查找模块的设计实现[D];南京邮电大学;2011年

【相似文献】

中国期刊全文数据库 前10条

1 徐恪,徐明伟,吴建平,吴剑;路由查找算法研究综述[J];软件学报;2002年01期

2 王智强,王振兴,张定心;快速路由查找算法研究[J];计算机应用研究;2004年02期

3 刘英臣;傅光轩;;路由查找技术的分析及研究[J];贵州大学学报(自然科学版);2006年03期

4 郭润伟;;路由查找算法研究与分析[J];科技经济市场;2009年06期

5 朱国胜;余少华;;一种新的二分路由查找方法[J];小型微型计算机系统;2010年09期

6 袁博;汪斌强;王志明;;并行多流水绿色路由查找架构和算法[J];西安电子科技大学学报;2012年02期

7 田园;王萌;缪建军;刘葳;;星上路由查找的设计与分析[J];电子质量;2012年04期

8 徐宇锋,李乐民;快速路由查找算法及其实现[J];通信技术;2001年07期

9 姚兴苗,李乐民,胡光岷;快速路由器的路由查找和流分类算法研究[J];电子科技大学学报;2004年06期

10 周昔平;高德远;樊晓桠;张盛兵;;基于索引和压缩的超高速路由查找及更新算法[J];小型微型计算机系统;2006年06期

中国重要会议论文全文数据库 前3条

1 张荣高;龚雪春;;基于位图映射路由查找算法的研究[A];2006通信理论与技术新进展——第十一届全国青年通信学术会议论文集[C];2006年

2 王燕;;IPv6的快速路由查找算法研究[A];2005年全国开放式分布与并行计算学术会议论文集[C];2005年

3 苗建松;丁炜;;改进的TCAM路由更新方法与实现[A];2006年全国开放式分布与并行计算学术会议论文集（二）[C];2006年

中国重要报纸全文数据库 前3条

1 吴;神码网络加速多业务融合[N];计算机世界;2006年

2 王翌;路由器的三种身份[N];计算机世界;2004年

3 许文;路由器的类型及特点[N];中国计算机报;2006年

中国博士学位论文全文数据库 前6条

1 王振兴;NGI高性能路由器转发处理算法与实现[D];南京理工大学;2004年

2 谭明锋;域间路由协议BGP-4健壮性测试技术的研究[D];国防科学技术大学;2005年

3 郑凯;高性能IP路由查找和分组分类技术的研究[D];清华大学;2006年

4 汪漪;内容中心网络路由查找关键技术研究[D];清华大学;2013年

5 胥小波;新型蜜网体系结构及告警聚类的关键技术研究[D];北京邮电大学;2012年

6 朱国胜;高速分组查找规则匹配算法研究[D];华中科技大学;2010年

中国硕士学位论文全文数据库 前10条

1 张理阳;一种基于哈希策略的路由查找算法[D];长沙理工大学;2011年

2 王智强;高速路由查找算法研究[D];中国人民解放军信息工程大学;2003年

3 张荣高;网络处理器原型系统路由查找算法的研究[D];国防科学技术大学;2006年

4 陈静;路由器中路由查找子系统的实现和优化[D];华中科技大学;2006年

5 王波;基于FPGA的快速路由查找算法研究及实现[D];西安电子科技大学;2009年

6 奚晓华;基于FPGA的可编程高速路由查找算法的研究与实现[D];南京邮电大学;2013年

7 张晓波;路由查找算法的研究及其FPGA实现[D];华东师范大学;2006年

8 杨斌涛;IP路由查找算法的研究[D];电子科技大学;2010年

9 郭玲丽;基于多分支trie的快速路由查找算法[D];西安电子科技大学;2009年

10 郭文文;基于TRIE的软转发路由查找模块的设计实现[D];南京邮电大学;2011年

，

本文编号：621299