基于分割多分枝Trie树的并行路由查找算法

发布时间：2018-05-17 14:32

  本文选题：并行路由查找算法 + Trie树　； 参考：《光通信研究》2014年05期

【摘要】：为解决在多核处理器平台下路由器报文转发时路由查找速度慢的"瓶颈"问题,提出了一种基于分割的多分枝Trie树的并行路由查找算法。该算法将一棵多分枝Trie树根据处理器的核数分割成若干子树,每棵子树又构成一棵单独的多分枝Trie树,子树中取消了前缀查找,采取组成一个大中间节点的方式,在中间节点之间采用固定步长查询,中间节点内部采用二进制Trie树来表示。实验结果表明,该算法具有访存次数少、查询速度快、占用存储空间少和更新开销小等特点,同时适用于IPv4和IPv6地址。
[Abstract]:In order to solve the "bottleneck" problem of routing lookup slow when router packets are forwarded on multi-core processor platform, a parallel routing lookup algorithm based on partitioned multi-branch Trie tree is proposed. The algorithm divides a multi-branched Trie tree into several sub-trees according to the kernel number of the processor. Each sub-tree constitutes a single multi-branched Trie tree, and the prefix search is cancelled in the sub-tree, and a large and medium node is formed. The intermediate nodes are queried with fixed step size and the intermediate nodes are represented by binary Trie tree. Experimental results show that the proposed algorithm has the advantages of less memory access, faster query speed, less storage space and less update overhead. It is also suitable for IPv4 and IPv6 addresses.
【作者单位】： 光纤通信技术和网络国家重点实验室;武汉烽火网络有限责任公司;
【分类号】：TP393.02

【参考文献】

相关期刊论文 前3条

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

2 杨玉梅;黎仁国;;基于二分查找和Trie的IPv6路由查找算法[J];兰州理工大学学报;2012年04期

3 曹折波;李青;;多核处理器并行编程模型的研究与设计[J];计算机工程与设计;2010年13期

【共引文献】

相关期刊论文 前10条

1 周瑞;常旭;林丹峰;杨林峰;;基于多分支Trie的路由查找算法设计与实现[J];大众科技;2013年08期

2 崔阳;吕志平;陈正生;王宇谱;吕浩;;多核环境下的GNSS网平差数据并行处理研究[J];测绘学报;2013年05期

3 李正浩;曾智洪;曾晓赢;史振宁;付仕清;;农村信息化建设中多媒体数据的并行管理框架设计[J];重庆大学学报;2013年12期

4 余涛;吴卫东;;基于多核处理器的L7-Filter规则匹配改进算法[J];计算机应用;2012年03期

5 汪前进;高勇;李存华;;基于多核处理器的多任务并行处理技术研究[J];计算机应用与软件;2012年07期

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

7 黄伟建;牛沛;蔡忠亚;;水质预报系统中垂向湍扩散并行算法实现研究[J];计算机工程与设计;2011年12期

8 程小华;郑昌文;吴佳泽;;基于多核处理器的星空背景弥散效果实现算法[J];计算机工程与设计;2013年01期

9 罗新建;;计算机应用程序编辑模型的发展[J];数字技术与应用;2013年08期

10 李彬彬;李青;;LBM在多核并行编程模型中的应用[J];计算机技术与发展;2011年07期

相关硕士学位论文 前10条

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

2 王世远;基于Linux的XviD编码多核并行化的研究与实现[D];东北大学;2011年

3 石文娟;异构环境下分层并行通用计算模型的设计与实现[D];中国海洋大学;2012年

4 牛沛;并行计算在胶州湾水质预报系统中的应用研究[D];河北工程大学;2012年

5 叶光辉;基于多分支Trie的虚拟路由查找算法研究[D];湖南大学;2012年

6 王东菊;基于Bloom滤波器的快速路由查找算法研究[D];大连理工大学;2013年

7 崔阳;大规模测量平差分布式计算技术及应用研究[D];解放军信息工程大学;2013年

8 刘建志;基于虚拟路由器的IPv6路由策略研究[D];哈尔滨工业大学;2012年

9 余涛;基于多核处理器的L7-Filter规则匹配改进算法[D];武汉科技大学;2013年

10 冯富辉;并行处理技术在通信系统中的应用研究[D];北京交通大学;2014年

【二级参考文献】

相关期刊论文 前10条

1 张彦军;贾世国;薛晓敏;;IPv6下DoS/DDoS SYN Flood入侵和攻击的检测[J];兰州理工大学学报;2008年02期

2 穆晓霞;陈留院;牛振齐;;IPv4到IPv6的迁移技术研究[J];河南师范大学学报(自然科学版);2010年06期

3 刘永锋,杨宗凯;高速路由器中基于树型结构路由查找算法的研究与实现[J];计算机工程与科学;2004年01期

4 谭明锋;高蕾;龚正虎;;IP路由查找算法研究概述[J];计算机工程与科学;2006年06期

5 陈俊;陈孝威;;移动IPv4/IPv6的虚拟机迁移过渡框架[J];计算机应用;2011年05期

6 张宏丽;昝利国;;IPv6路由查找算法探究[J];内蒙古电大学刊;2010年02期

7 马杰;张永平;杨磊;;基于LFT和DAG方式的IPv6路由查找算法[J];计算机工程与设计;2008年05期

8 吴彤,杨嗣超,诸鸿文;路由表快速查找算法[J];通信技术;2000年04期

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

10 刘宏义;;IPv6快速路由查找算法分析与研究[J];微电子学与计算机;2008年04期

【相似文献】

相关期刊论文 前10条

1 王智强,王振兴,张定心;基于Trie的快速路由查找算法[J];信息工程大学学报;2003年03期

2 庄雄雄;吕兰兰;高宋O，

本文编号：1901747