基于代数决策图的路由查找算法

发布时间：2018-05-06 01:34

  本文选题：路由表 + 路由查找　； 参考：《计算机工程》2017年03期

【摘要】：为解决路由查找过程中路由表项数不断增加导致存储冗余大和查找效率低的问题,在代数决策图(ADD)的基础上,提出一种改进的路由查找算法。根据符号算法的特性对路由表项进行伪布尔函数表示,综合考虑路由表结构特征和符号算法的优势,基于ADD结构构建基于前缀的路由表,并给出路由表更新、删除、查找算法。通过国际项目管理协会提供的开源路由表进行实验仿真,结果表明该算法能够有效减少路由表操作时的内存访问次数,节省路由表存储空间。
[Abstract]:In order to solve the problem of large storage redundancy and low search efficiency caused by the increasing number of routing table items in the process of routing lookup, an improved routing lookup algorithm is proposed on the basis of algebraic decision graph (ADD). According to the characteristic of symbol algorithm, the pseudo-Boolean function is used to represent the items of routing table. Considering the structural features of routing table and the advantages of symbol algorithm, the prefixes based routing table is constructed based on ADD structure, and the routing table updating, deleting and searching algorithm are given. The simulation results of the open source routing table provided by the International Project Management Association show that the algorithm can effectively reduce the number of memory access to the routing table operation and save the storage space of the routing table.
【作者单位】： 桂林电子科技大学广西可信软件重点实验室;
【基金】：国家自然科学基金(61262030,61572146,61363030) 广西自然科学基金(2015GXNSFAA139285,2014GXNSFAA118354) 广西可信软件重点实验室基金 广西高等学校高水平创新团队 卓越学者计划项目
【分类号】：TN915.05

【参考文献】

相关期刊论文 前5条

1 范富明;李念军;雷升平;吉萌;;基于哈希表与多比特树的路由查找算法[J];计算机工程;2015年09期

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

3 朱云洁;朱凌众;;LPM路由查找算法及其应用[J];硅谷;2010年10期

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

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

【共引文献】

相关期刊论文 前10条

1 徐周波;胡魁;常亮;古天龙;;基于代数决策图的路由查找算法[J];计算机工程;2017年03期

2 陈亮;王建;胡康;;众核网络处理器下高速包转发系统设计与实现[J];计算机应用与软件;2016年12期

3 黄盛林;吕锋昌;王伟;;SAVI DHCPv6数据报文源地址验证方法研究[J];计算机应用研究;2017年01期

4 范富明;李念军;雷升平;吉萌;;基于哈希表与多比特树的路由查找算法[J];计算机工程;2015年09期

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

6 李渊;阮军洲;;基于Hash和Radix树的路由查找算法研究[J];计算机与网络;2015年11期

7 邓全才;张连连;孙志田;;基于OPNET的卫星路由查找算法仿真分析[J];河北建筑工程学院学报;2015年01期

8 刘小园;;访问控制列表在网络优化中的应用[J];软件工程师;2014年06期

9 黄胜;张卫;吴川川;陈胜蓝;;基于多分支优先级树的IP路由查找算法[J];计算机应用;2014年03期

10 高明;金蓉;王伟明;诸葛斌;董黎刚;;ForCES系统中路由协议栈的实现与测试[J];实验室研究与探索;2014年01期

【二级参考文献】

相关期刊论文 前10条

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

2 崔宇;田志宏;张宏莉;方滨兴;;基于前缀区间集合的IPv6路由查找算法[J];通信学报;2013年06期

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

4 田园;张曙光;乔庐峰;邵世雷;王郡峰;;路径压缩查找算法的FPGA实现[J];军事通信技术;2012年03期

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

6 郜国良;李广军;;一种基于Trie的快速IP路由查找算法[J];微电子学与计算机;2011年06期

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

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

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

10 张毅;郭玲丽;;基于FPGA的高速路由查找算法[J];电子元器件应用;2009年09期

【相似文献】

相关期刊论文 前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年

相关重要报纸文章 前1条

1 吴;神码网络加速多业务融合[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 张宁;基于Lua的手游服务器的研究与设计[D];南华大学;2015年

2 贺雨虹;命名数据网络的路由查找算法研究[D];哈尔滨工业大学;2015年

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

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

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

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

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

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

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

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

，

本文编号：1850205