[路由查找算法论文]Trie树路由查找算法在网络处理器中的实现

时间：2015-01-09 15:25:18 作者：张琦；金胤丞；李苗；

本文作者：张琦；金胤丞；李苗；章建雄；成功正常投稿发表论文到《计算机工程》2014年01期,引用请注明来源400期刊网！

如果您需要快速发表论文服务，请联系在线编辑！

【摘要】：Trie树数据结构的实现方法灵活,所需存储器空间小,是实现高速路由查找和分组转发的理想选择。为满足10Gb/s线速度网络处理器中微引擎的设计要求,提出一种基于最优平衡、多层存储的Trie树路由查找算法。建立一种平衡的压缩树结构,将该树中相邻的多层节点压缩到一个存储节点中。通过构造特定的数据存储结构来减小树的搜索深度,以空间换取时间,从而提高路由查找速度和分组转发效率。在网络处理器的查找微引擎设计中实现Trie路由查找算法,实验结果表明,单个微引擎的查找速度为4.4Mb/s,能达到节省存储空间、提高查找效率的效果。
【论文正文预览】：1概述国际互联网络规模的高速增长对IP(InternetProtocol)路由查找算法处理大容量路由表的适应性提出了更高要求,骨干路由器每秒所需转发的报文数随之剧增,IP路由查找算法的优劣直接影响了当前和未来互联网的整体性能[1]。此外,随着网络系统的发展,现有网络系统的瓶颈越来越
【文章分类号】：TP311.12
【稿件关键词】：网络处理器路由查找最长前缀匹配路径压缩Trie树算法实现
【参考文献】:

刘英臣;傅光轩;;路由查找技术的分析及研究[J];贵州大学学报(自然科学版);2006年03期
吴强,苏金树,王勇军;基于Patricia树的快速多维分组分类算法[J];计算机工程;2004年21期
刘永锋,杨宗凯;高速路由器中基于树型结构路由查找算法的研究与实现[J];计算机工程与科学;2004年01期
谭明锋;高蕾;龚正虎;;IP路由查找算法研究概述[J];计算机工程与科学;2006年06期
华泽;马涛;;基于Trie的路由查找算法设计与实现[J];计算机与现代化;2006年02期
田园;张曙光;乔庐峰;邵世雷;王郡峰;;路径压缩查找算法的FPGA实现[J];军事通信技术;2012年03期
郜国良;李广军;;一种基于Trie的快速IP路由查找算法[J];微电子学与计算机;2011年06期
张毅;郭玲丽;;基于FPGA的高速路由查找算法[J];电子元器件应用;2009年09期
陈蹊;赵跃龙;;多分枝trie树路由查找算法研究[J];电子设计工程;2010年03期
杨玉梅;黎仁国;;基于二分查找和Trie的IPv6路由查找算法[J];兰州理工大学学报;2012年04期
胡宁;王勇军;;基于网络处理器的IPSec协议实现技术研究[J];计算机工程;2006年05期
王勇军;黄清元;;基于网络处理器的MPLS VPN协议的研究与实现[J];计算机工程与科学;2006年06期
郭润伟;;路由查找算法研究与分析[J];科技经济市场;2009年06期
邓亚平;周美红;;基于多层混合结构的IPv6路由表查找算法[J];计算机应用;2013年02期
戴泽华;张连连;邓全才;葛宇;;基于OPNET的二叉树路由查找算法的设计与实现[J];河北建筑工程学院学报;2012年03期
高明;金蓉;王伟明;诸葛斌;董黎刚;;ForCES系统中路由协议栈的实现与测试[J];实验室研究与探索;2014年01期
郜国良;李广军;;一种基于Trie的快速IP路由查找算法[J];微电子学与计算机;2011年06期
张宏丽;武剑;;IP路由技术综述[J];信息与电脑(理论版);2010年03期
余鑫;集群路由器关键技术研究[D];华中科技大学;2005年
周昔平;多线程网络处理器分布式内核结构研究[D];西北工业大学;2006年
郭文文;基于TRIE的软转发路由查找模块的设计实现[D];南京邮电大学;2011年
崔宇;大规模并行网络模拟中高性能远程路由策略的研究[D];哈尔滨工业大学;2010年
曹继军;基于网络处理器的NAT协议研究与实现[D];国防科学技术大学;2004年
赵永精;基于trie的路由查找算法研究[D];兰州理工大学;2007年
刘凤格;基于网络QoS的队列调度算法研究[D];南京理工大学;2007年
曾晟;基于代理应答机制的网关加速的分析与研究[D];北京交通大学;2008年
梁国强;移动Agent技术在GPS/GIS监控系统中的应用[D];大连海事大学;2009年
王薇;基于HASH路由转发表存储结构的研究[D];太原理工大学;2010年
朱凯;FCoE路由管理模块的设计与实现[D];北京邮电大学;2010年
王勇麟;基于TCAM的高效率路由更新算法[D];湖南大学;2012年
周文辉,丁利剑,唐健;Internet路由技术及相关协议[J];电信技术;1999年09期
彭元喜,唐玉华,龚正虎;基于压缩NH表的高速IP路由查找算法的研究[J];电子学报;2002年02期
田园;王萌;缪建军;刘葳;;星上路由查找的设计与分析[J];电子质量;2012年04期
谭明锋;高蕾;龚正虎;;IP路由查找算法研究概述[J];计算机工程与科学;2006年06期
彭元喜,龚正虎;基于LSOT的高速IP路由查找算法[J];计算机学报;2002年01期
李鸥,邬江兴,汪斌强,戚文芽;一种分段式高速IP路由查找方法[J];通信学报;2001年05期
颜顺华;刘宏立;;一种改进的端到端混合QoS模型[J];微电子学与计算机;2009年05期
刘宝起;王长山;李瑞;;基于保证QoS的片上网络路由算法[J];微电子学与计算机;2009年07期
刘祯;刘斌;郑凯;;基于软件的网络处理器的路由高速缓存算法研究[J];软件学报;2007年12期
刘晓峰;华蓓;;聚合组播路由并行查找算法[J];计算机仿真;2008年12期
钱磊;李巍;李云春;王文;;一种基于网络处理器加速的策略路由网关[J];微计算机信息;2009年21期
台祥广;郑康锋;黄玮;李忠献;杨义先;;基于网络处理器的流量过滤及均衡系统的设计与实现[J];信息工程大学学报;2010年05期
;Netronome推出业界首款统一计算网络流处理器[J];电子与电脑;2009年07期
正华;网络处理器研发动态[J];电子产品世界;2001年01期
张人杰,蔡华,余少华;现代高速网络设备核心部件——网络处理器技术分析[J];数据通信;2002年03期
Editorial;Powerful的网络搜寻引擎协助指点迷津——IDT兼容性佳的NSE力求整体支持并重战略生态[J];电子与电脑;2005年11期
罗华,张思东,张宏科;基于IXP2400网络处理器的网络防护系统设计和实现[J];电信快报;2004年11期
陈军;基于IXP2400网络处理器的MPLS转发实现技术分析[J];福建电脑;2005年03期
马思瑶;尹佳斌;孙志刚;;网络处理器设计中的存储瓶颈问题[A];第15届全国信息存储技术学术会议论文集[C];2008年
张瑞;刘仓明;姜金平;宋伟;王文鼐;;基于Bloom滤波器的缓存机制快速路由查找算法[A];2004年全国通信软件学术会议论文集[C];2004年
张治洲;郑康锋;;一种高效的网络处理器资源访问算法[A];第十三届中国科协年会第11分会场-中国智慧城市论坛论文集[C];2011年
邵荣平;孙志刚;张晓明;;基于SOPC的网络处理器原型设计[A];2003中国通信专用集成电路技术及产业发展研讨会论文集[C];2003年
许榕生;;网络安全与网络处理器[A];第11届全国计算机在现代科学技术领域应用学术会议论文集[C];2003年
胡淮杨;郑康锋;;一种基于网络处理器的IPTV负载均衡方案[A];2010通信理论与技术新发展——第十五届全国青年通信学术会议论文集（上册）[C];2010年
周鹏;郑康锋;;基于网络处理器高速深度检测防火墙的研究与设计[A];第十三届中国科协年会第11分会场-中国智慧城市论坛论文集[C];2011年
周卫华;倪县乐;丁炜;;基于IXP1200网络处理器的安全路由器的设计和实现[A];第六届全国计算机应用联合学术会议论文集[C];2002年
程胜;张勖;窦忠辉;丁炜;;基于IXP1200网络处理器的IP路由器的设计和分析[A];第六届全国计算机应用联合学术会议论文集[C];2002年
张建宇;廖唯棨;张行功;邹维;;网络处理器的发展及其在网络安全中的应用[A];全国网络与信息安全技术研讨会'2005论文集（下册）[C];2005年
勤誉;网络处理器击退ASIC 成市场主流[N];电子资讯时报;2004年
胡成臣王元元刘斌;网络处理器的应用之道[N];计算机世界;2006年
杜荣华;网络处理器灵活应变[N];中国计算机报;2003年
;英飞凌发布新型VoIP处理器[N];人民邮电;2006年
烽火网络有限责任公司岳青伦;基于网络处理器的BT业务流识别[N];通信产业报;2006年
任续烨;英特尔发布IXP23XX＼IXP46X NP[N];中国计算机报;2004年
;网络处理器与ASIC[N];网络世界;2003年
向北;手机CPU三国争霸[N];电脑报;2008年
张志斌;为下一代RNC设计奠基[N];网络世界;2004年
李丹;千兆防火墙架构之争[N];计算机世界;2006年
单征;基于分层架构的网络处理器系统性能分析方法研究[D];解放军信息工程大学;2007年
李韬;粗粒度数据流网络处理器设计关键技术研究[D];国防科学技术大学;2010年
许宪成;基于网络处理器的入侵检测系统设计与性能优化研究[D];华南理工大学;2010年
谢立峰;基于网络处理器的网络服务质量和网络安全研究[D];浙江大学;2004年
周曜;移动Ad Hoc网络路径压缩及安全技术研究[D];南京理工大学;2010年
向军;网络处理器并行线速处理关键技术研究[D];华南理工大学;2010年
刘祯;网络处理器存储子系统中Cache机制的研究[D];清华大学;2006年
郑波;基于网络处理器的传输控制模型、算法及实现[D];清华大学;2006年
吴佳骏;多核多线程处理器上任务调度技术研究[D];中国科学院研究生院（计算技术研究所）;2006年
张晓明;网络处理器设计的若干关键技术研究[D];国防科学技术大学;2006年
王毅;网络处理器包传输结构的研究[D];西北工业大学;2004年
王晓华;面向网络处理器的编程模型研究[D];西北工业大学;2005年
邵荣平;网络处理器并行处理技术研究[D];国防科学技术大学;2003年
廖杨;基于多核网络处理器的IP转发系统的设计与实现[D];电子科技大学;2010年
薛卫东;基于网络处理器IXP2350的网络流量控制研究与实现[D];西安科技大学;2010年
吴霖;基于多核网络处理器的P2P高速流量识别系统的设计与实现[D];苏州大学;2010年
文成玉;基于IXA的IP交换技术的研究与分析[D];电子科技大学;2004年
董明峰;面向网络处理器的软件开发平台的研究[D];西北工业大学;2005年
严锦芸;高速网络信息过滤系统设计与实现[D];华中科技大学;2007年
杜敏;基于IXP2400的防火墙应用设计与实现[D];电子科技大学;2004年

【稿件标题】：[路由查找算法论文]Trie树路由查找算法在网络处理器中的实现
【作者单位】：中国电子科技集团公司第三十二研究所;
【发表期刊期数】：《计算机工程》2014年01期
【期刊简介】：《计算机工程》杂志是由中华人民共和国新闻出版总署、正式批准公开发行的优秀期刊，计算机工程杂志具有正规的双刊号，其中国内统一刊号：CN31-1289/TP，国际刊号：ISSN1000-3428。计算机工程杂志社由中国电子科技集团公司主管、主办，本刊为月刊。自创刊以来......更多计算机工程杂志社(http://www.400qikan.com/qk/6013/)投稿信息
【版权所有人】：张琦；金胤丞；李苗；章建雄；