-
题名Trie树路由查找算法在网络处理器中的实现
被引量：11
- 1
-
-
作者
张琦
金胤丞
李苗
章建雄
-
机构
中国电子科技集团公司第三十二研究所
-
出处
《计算机工程》
CAS
CSCD
2014年第1期98-102,共5页
-
文摘
Trie树数据结构的实现方法灵活,所需存储器空间小,是实现高速路由查找和分组转发的理想选择。为满足10 Gb/s线速度网络处理器中微引擎的设计要求,提出一种基于最优平衡、多层存储的Trie树路由查找算法。建立一种平衡的压缩树结构,将该树中相邻的多层节点压缩到一个存储节点中。通过构造特定的数据存储结构来减小树的搜索深度,以空间换取时间,从而提高路由查找速度和分组转发效率。在网络处理器的查找微引擎设计中实现Trie路由查找算法,实验结果表明,单个微引擎的查找速度为4.4 Mb/s,能达到节省存储空间、提高查找效率的效果。
-
关键词
网络处理器
路由查找
最长前缀匹配
路径压缩
TRIE树
算法实现
-
Keywords
Network Processor（NP）
router lookup
the longest prefix matching
path compression
Trie tree
algorithm implementation
-
分类号
TP393.07
[自动化与计算机技术—计算机应用技术]
-
-
题名网络处理器中最长匹配算法的优化
被引量：1
- 2
-
-
作者
陈静
吴非
黄祚
-
机构
华中科技大学计算机科学与技术学院信息存储国家专业实验室暨教育部重点实验室
-
出处
《计算机工程》
CAS
CSCD
北大核心
2007年第5期106-108,111,共4页
-
文摘
传统的最长匹配路由算法都是基于双线程并行查找方法来实现的,没有充分利用新一代网络处理器无延时线程切换和可编程的特点。该文基于IXP2350平台对传统的最长匹配算法进行了优化改进,充分利用硬件特性和微引擎中异步内存读写的特点,用单线程来完成整个路由的查找。实验测试结果表明,这种优化改进使路由器的包转发效率提高了20%。
-
关键词
网络处理器
最长匹配算法
嵌入式系统
微引擎
微码
-
Keywords
Network processor
longest prefix match algorithm
Embedded system
Micro engine
Microcode
-
分类号
TP393.05
[自动化与计算机技术—计算机应用技术]
-
-
题名基于代数决策图的路由查找算法
被引量：1
- 3
-
-
作者
徐周波
胡魁
常亮
古天龙
-
机构
桂林电子科技大学广西可信软件重点实验室
-
出处
《计算机工程》
CAS
CSCD
北大核心
2017年第3期99-104,共6页
-
基金
国家自然科学基金(61262030
61572146
+5 种基金
61363030)
广西自然科学基金(2015GXNSFAA139285
2014GXNSFAA118354)
广西可信软件重点实验室基金
广西高等学校高水平创新团队
卓越学者计划项目
-
文摘
为解决路由查找过程中路由表项数不断增加导致存储冗余大和查找效率低的问题,在代数决策图(ADD)的基础上,提出一种改进的路由查找算法。根据符号算法的特性对路由表项进行伪布尔函数表示,综合考虑路由表结构特征和符号算法的优势,基于ADD结构构建基于前缀的路由表,并给出路由表更新、删除、查找算法。通过国际项目管理协会提供的开源路由表进行实验仿真,结果表明该算法能够有效减少路由表操作时的内存访问次数,节省路由表存储空间。
-
关键词
路由表
路由查找
代数决策图
符号算法
最长前缀匹配
伪布尔函数
-
Keywords
routing table
routing lookup
Algebraic Decision Diagram （ ADD ）
symbolic algorithm
longest prefix matching
pseudo Boolean function
-
分类号
TP393
[自动化与计算机技术—计算机应用技术]
-
-
题名一种基于TCAM的PLO_OPT算法的改进
被引量：1
- 4
-
-
作者
王亚刚
杨康平
杜慧敏
-
机构
西安邮电学院计算机系
-
出处
《西安邮电学院学报》
2009年第3期83-86,共4页
-
文摘
在最大前缀长度为L的TCAM(Ternary Content Addressable Memory)中,采用PLO_OPT算法更新路由表项仍然有很大的时间消耗,其时间复杂度为O(L/2)。为了进一步提高路由更新速度,根据路由前缀数量分布图,本文提出了一种PLO_OPT路由更新算法的改进方案,每更新一次表项只需进行一次操作即可,可以使时间复杂度达到O(1),且更有效地利用了存储空间。
-
关键词
TCAM
PLO_OPT算法
最大前缀匹配
路由更新算法
-
Keywords
TCAM
PLO_ OPT algorithm
longest prefix matching
muting updating algorithm
-
分类号
TP393.09
[自动化与计算机技术—计算机应用技术]
-
-
题名WSN中改进的IPv6路由查找算法
被引量：1
- 5
-
-
作者
余晓磊
江红
杨璀琼
-
机构
华东师范大学计算中心
-
出处
《计算机工程》
CAS
CSCD
北大核心
2010年第21期115-117,共3页
-
文摘
针对无线传感器网络(WSN)中的全局单播地址,提出一种IPv6快速路由查找机制。利用布鲁姆过滤器作为存储结构,以合适的存储方法降低错误率,采用最长前缀匹配算法合理分配前缀,以减少静态随机存取存储器的数量,降低成本。实验结果表明,利用该算法可以减少每一次查找的散列探头,从而提高路由表的查找速度,改善WSN的性能。
-
关键词
无线传感器网络
IPV6
最长前缀匹配算法
路由查找
布鲁姆过滤器
-
Keywords
WSN
IPv6
longest prefix match algorithm
routing lookup
Bloom Filter（BF）
-
分类号
TP393
[自动化与计算机技术—计算机应用技术]
-
-
题名快速路由查找算法研究
被引量：4
- 6
-
-
作者
王智强
王振兴
张定心
-
机构
解放军信息工程大学信息工程学院
南京理工大学计算机系
-
出处
《计算机应用研究》
CSCD
北大核心
2004年第2期231-234,240,共5页
-
文摘
随着互联网络光链路速率不断提高,路由查找已成为路由器报文转发的瓶颈。主要介绍近年来提出的各种路由查找方法,并对各种方法的性能及对IPv6适应性进行了分析比较。
-
关键词
路由查找算法
最长前缀匹配
性能比较
-
Keywords
Routing Lookup algorithm
longest matching prefix
Compare Performance
-
分类号
TP393
[自动化与计算机技术—计算机应用技术]
-
-
题名一种无回溯的最长前缀匹配搜索算法
被引量：1
- 7
-
-
作者
张飞飞
李华伟
韩银和
-
机构
中国科学院计算机系统结构重点实验室
-
出处
《计算机工程》
CAS
CSCD
北大核心
2008年第10期52-54,共3页
-
基金
国家自然科学基金资助项目(60606008)
-
文摘
研究网络处理器中的搜索算法,提出一种基于Patricia树的无回溯搜索算法,并进行仿真和评估分析。该算法被用于中科院计算所的网络处理器的搜索引擎的设计中,该搜索引擎可以运行在155.9 MHz的XC2VP30 FPGA上,占用421个LUT,当频率为100 MHz时,每秒可以执行约7 000 000次搜索操作,实现了资源消耗和性能的折中。
-
关键词
搜索算法
最长前缀匹配
Patricia树
搜索引擎
-
Keywords
search algorithm
longest prefix match
Patricia tree
searching engine
-
分类号
TP301.6
[自动化与计算机技术—计算机系统结构]
-
-
题名基于Trie的快速路由查找算法
被引量：1
- 8
-
-
作者
王智强
王振兴
张定心
-
机构
信息工程大学信息工程学院
-
出处
《信息工程大学学报》
2003年第3期10-13,共4页
-
文摘
随着互联网络光链路速率不断提高,路由查找已成为路由器报文转发的瓶颈。本文主要介绍近年来基于Trie的各种路由查找方法,同时对各种方法的性能进行了比较,最后介绍了一种性能优良的基于Trie的路由查找算法———压缩树算法。
-
关键词
路由查找算法
最长前缀匹配
TRIE
压缩树
-
Keywords
routing lookup algorithm
longest matching prefix
Trie
compressed Trie
-
分类号
TP393
[自动化与计算机技术—计算机应用技术]
-
-
题名大容量高带宽路由查找算法设计与FPGA实现
被引量：4
- 9
-
-
作者
彭鼎祥
-
机构
锐捷网络股份有限公司
-
出处
《现代电子技术》
2023年第15期20-24,共5页
-
基金
福建省科技重大专项(闽科技[2017]69号)
福建省数字经济专项(闽财指[2019]918号)。
-
文摘
为了解决目前IP路由查表大容量和高吞吐需求的同时,实现低硬件资源成本,提出一种大容量高带宽IP路由查表算法,并完成FPGA实现。算法将FIB表项的存储映射为字典树的数据结构,进行路径压缩和级别压缩以节省存储资源。将字典树根节点信息存储在片内SRAM,子树节点存储于片外DRAM。查找时,在芯片硬件内采用流水线方式优化资源负载均衡,实现片外DRAM的一次访问即可得到结果,实现了单周期线速查表,并支持增量更新。该算法通过FPGA设计实现,并进行仿真和实机验证。结果表明,该方案可同时支持大容量IPv4和IPv6 FIB表项并行查找,与现有方案相比,做到了更大容量、更高带宽和更低成本。
-
关键词
大容量
高带宽
IP路由表
FIB表
最长前缀匹配
FPGA
字典树算法
流水线
-
Keywords
large⁃capacity
high⁃bandwidth
IP routing table
FIB table
longest prefix match
FPGA
Trie⁃tree algorithm
pipeline
-
分类号
TN91-34
[电子电信—通信与信息系统]
-
-
题名散列索引多分支Trie树快速路由查找算法
- 10
-
-
作者
崔尚森
冯博琴
-
机构
西安交通大学电信学院
-
出处
《计算机应用与软件》
CSCD
北大核心
2005年第9期115-117,共3页
-
文摘
路由器的主要任务是转发IP分组,实现高速分组转发的关键是快速的路由查找算法。我们针对IPv4地址,首先建立前缀长度为8、16和24的3张hash表,在此基础上,再分别针对不同长度的前缀建立最多只涉及其余8比特的多分支Trie树。在这种结构中进行IP路由查找,其存储器访问次数最多为7次,而且还具有易于更新、易于扩展等特点。
-
关键词
最长前缀匹配
路由查找算法
散列表
多分支Trie树
快速路由查找算法
TRIE树
索引
散列
IPv4地址
IP分组
-
Keywords
longest matching prefix Routing lookup algorithm Hash Multibit-trie
-
分类号
TP393.4
[自动化与计算机技术—计算机应用技术]
TP311.12
[自动化与计算机技术—计算机软件与理论]
-
