检索结果-南通市图书馆

在线全文

学校读者我要写书评

暂无评论

一种无回溯的最长前缀匹配搜索算法

计算机工程 2008年第10期34卷 52-54页

作者：张飞飞李华伟韩银和中国科学院计算机系统结构重点实验室

研究网络处理器中的搜索算法,提出一种基于Patricia树的无回溯搜索算法,并进行仿真和评估分析。该算法被用于中科院计算所的网络处理器的搜索引擎的设计中,该搜索引擎可以运行在155.9 MHz的XC2VP30 FPGA上,占用421个LUT,当频率为100 MHz... 详细信息

研究网络处理器中的搜索算法,提出一种基于Patricia树的无回溯搜索算法,并进行仿真和评估分析。该算法被用于中科院计算所的网络处理器的搜索引擎的设计中,该搜索引擎可以运行在155.9 MHz的XC2VP30 FPGA上,占用421个LUT,当频率为100 MHz时,每秒可以执行约7 000 000次搜索操作,实现了资源消耗和性能的折中。

关键词：搜索算法最长前缀匹配 Patricia树搜索引擎

在线全文

学校读者我要写书评

暂无评论

一种基于最长前缀匹配的分段式IP查表方法

计算机科学 2007年第6期34卷 72-75页

作者：张文柱王炫西安电子科技大学综合业务网国家重点实验室信息科学研究所西安710071

基于最长前缀匹配,本文提出了一种新的IP转发表搜索方法。该方法在实现过程中依赖的主要硬件是一片逻辑控制器以及高速的DDRII(Double Date RateⅡ)SDRAM(Synchronous Dynamic Random Access Memory)。依据研究IP地址前缀所得出的规律,... 详细信息

基于最长前缀匹配,本文提出了一种新的IP转发表搜索方法。该方法在实现过程中依赖的主要硬件是一片逻辑控制器以及高速的DDRII(Double Date RateⅡ)SDRAM(Synchronous Dynamic Random Access Memory)。依据研究IP地址前缀所得出的规律,将IP地址前缀存储到DDRII中。该搜索方法能够将搜索时间限制在两个DDRII读周期之内,不超过4ns;同时保证转发表更新时间小于512ns。

关键词： IP转发表最长前缀匹配 IP地址前缀

在线全文

学校读者我要写书评

暂无评论

分组IP路由最长前缀匹配查找算法研究

世界科技研究与发展 2011年第6期33卷 1014-1018页

作者：熊忠阳阳佶宏张玉芳重庆大学计算机学院重庆400044

介绍了几种常见的IP路由查找算法,并简单分析其优点与不足。二进制Trie树结构虽占用空间较小,但因其查找时间太长而很少运用于实际生活中,目前常见的算法都是在查找时间与存储空间上寻找折衷点.本文在此基础之上提出了一种基于分组IP路... 详细信息

介绍了几种常见的IP路由查找算法,并简单分析其优点与不足。二进制Trie树结构虽占用空间较小,但因其查找时间太长而很少运用于实际生活中,目前常见的算法都是在查找时间与存储空间上寻找折衷点.本文在此基础之上提出了一种基于分组IP路由最长前缀匹配查找算法,通过将IP前缀按其长度进行分组,并在各组内采用Trie树结构进行存储,最长只需4次存储器访问,且因利用了公共前缀,固能节约存储空间,实验结果表明,本算法在查找时间上取得了非常理想的效果。

关键词：最长前缀匹配分组IP路由查找 Trie树

在线全文

学校读者我要写书评

暂无评论

基于哈希表的最长前缀匹配算法改进

微计算机信息 2009年第30期25卷 143-144,142页

作者：刘舱强邓昌胜余谅四川大学计算机学院成都610064

在实际应用中经常需要查找某IP地址其在数据库中对应的真实的物理地址,而数据库的数据量往往很大,显然直接去查询数据库不能满足大量数据以及高速查找的要求。在最长前缀匹配算法的基础上,提出了一种基于哈希查找表的IP地址查找算法。... 详细信息

在实际应用中经常需要查找某IP地址其在数据库中对应的真实的物理地址,而数据库的数据量往往很大,显然直接去查询数据库不能满足大量数据以及高速查找的要求。在最长前缀匹配算法的基础上,提出了一种基于哈希查找表的IP地址查找算法。将数据库中的信息建立为一个哈希表,并将点分十进制IP地址的部分前缀作为键值,映射到哈希表中的一条记录,从而得到所需的信息。最后用C#语言实现了该算法,实验表明该算法具有很高的效率。

关键词： IP 最长前缀匹配哈希表

在线全文

学校读者我要写书评

暂无评论

采用变长多分支树实现最长前缀匹配查找

无线电通信技术 2005年第5期31卷 55-57页

作者：胡广文胡振强刘玉贞中国电子科技集团公司第54研究所石家庄050081

随着Internet的迅猛发展,网络带宽需求不断增加,客观上要求路由器能够每秒钟转发几百万到上千万个以上的分组,分组转发的重要一步就是查找路由表,因此采用何种查找算法从而实现快速的IP地址最长前缀查找LPM是实现高速分组转发的关键。... 详细信息

随着Internet的迅猛发展,网络带宽需求不断增加,客观上要求路由器能够每秒钟转发几百万到上千万个以上的分组,分组转发的重要一步就是查找路由表,因此采用何种查找算法从而实现快速的IP地址最长前缀查找LPM是实现高速分组转发的关键。所采用变长多分支树查找算法将比传统的查找算法明显提高路由查找速度。

关键词：路由查找最长前缀匹配多分支树网络处理器

基于范围匹配的双路流水式IP查找引擎的设计与实现

在线全文

学校读者我要写书评

暂无评论

基于范围匹配的双路流水式IP查找引擎的设计与实现

作者：杨伟毅西安电子科技大学

学位级别：硕士

近年来,网络技术的迅速发展不可避免地造成网络流量的快速膨胀,对互联网的传输能力提出了新的挑战。随着光纤和接口技术等高速链路传输速度的突破,路由器等网络设备的数据报文处理能力成为影响链路传输速度的主要瓶颈。主要表现在两个方... 详细信息

近年来,网络技术的迅速发展不可避免地造成网络流量的快速膨胀,对互联网的传输能力提出了新的挑战。随着光纤和接口技术等高速链路传输速度的突破,路由器等网络设备的数据报文处理能力成为影响链路传输速度的主要瓶颈。主要表现在两个方面,首先,IP查找作为路由器的一项核心技术,其必须要能够响应越来越多的查找请求。其次,因为目前骨干路由器中路由表的规模已经达上百万条,所以IP地址查找需要优化数据结构,尽可能地减少存储开销。虽然国内外有关IP地址查找的研究非常多,但这些研究能在查找速度、存储需求、增量更新性能和可扩展性之间取得平衡的却很少。本论文来自于国家部委项目,研究了以范围匹配为基础的IP地址查找。通过将IP地址前缀转换为范围区间,将范围区间端点压缩后,基于优化的B树(B-Tree)节点数据结构提出了FRBS(Fast Range B-Tree Search)IP查找算法,该算法实现了对于IPv4地址的查找,并且支持动态路由表更新。本文通过分析网络协议需求,规划了动态路由表,基于FRBS IP查找算法设计了FRBS IP查找引擎,实现了动态IP地址查找。该查找引擎包含接收模块、流水式IP查找模块和更新模块,其中的核心模块是流水式IP查找模块,该模块使用5级流水线结构实现了基于范围匹配的IP地址查找。对于IPv4查找的吞吐量能够达到66.6Gbps。同时,通过对流水线结构扩展,采用25级流水线结构,对于IPv4查找的吞吐量能够达到204.8Gbps。本文选取RIPE路由集中的5个路由表作为测试路由表,随机选取其中100k条表项使用FRBS IP查找算法进行前缀分段表与FRBS表构建,对FRBS IP查找引擎进行了功能仿真与验证。在XCVU-13P平台对该IP查找引擎进行了原型验证,在300MHz频率下,对于64Byte的以太帧,其平均吞吐量达到了66.6Gbps,平均查找延迟为76.68ns,平均更新延迟为20.57ns。并与ELOP方案的性能进行了对比分析,相同规模的路由表下,本设计的存储开销分别减少了51%和48%,查找延时减少了12.2ns。同时,还对流水线扩展结构进行了板级测试,根据结果对其性能进行了分析,其平均吞吐量为204.8Gbps,平均查找延迟为125ns。最后,基于UMC HPC 28nm对整个IP查找引擎进行了物理综合,面积为12505635.055717μm^2,存储器128块,共18874368bit,工艺角为-40℃、0.81V、ss工艺角下,setup margin为0.16ns,满足百吉网络交换的带宽要求。本文研究的FRBS IP查找算法和FRBS IP查找引擎着重提高了IP查找硬件的性能和可扩展性,显著提高了IP查找的查找效率,降低了路由表的存储需求,对基于范围匹配的IP查找方面的研究提供了重要参考。

关键词：范围匹配 B树 IP地址查找最长前缀匹配

同方学位论文库评论

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

基于Bloom滤波器的快速路由查找方法

哈尔滨工程大学学报 2014年第10期35卷 1247-1252页

作者：于明王振安王东菊大连理工大学信息与通信工程学院辽宁大连116024

针对IP路由查找中的最长前缀匹配问题,提出了一种基于Bloom滤波器的快速路由查找方法。首先,通过建立首字节索引表,减少了需要并行查询的Bloom滤波器的数量。其次,基于IP地址前缀长度分布的不均匀性对Bloom滤波器组的设置进行了优化,降... 详细信息

针对IP路由查找中的最长前缀匹配问题,提出了一种基于Bloom滤波器的快速路由查找方法。首先,通过建立首字节索引表,减少了需要并行查询的Bloom滤波器的数量。其次,基于IP地址前缀长度分布的不均匀性对Bloom滤波器组的设置进行了优化,降低了查询过程对Bloom滤波器总数的需求。最后,将基本Bloom滤波器位向量中的每一比特位与一个计数器相关联,实现了对路由更新的支持。理论分析表明,与现有方法相比,利用该方法进行路由查找可以实现更低的选路表平均探测次数,并在最坏情况下具有更低的平均探测次数上界。实验结果验证了该方法的有效性及相关理论分析的正确性。

关键词：路由查找最长前缀匹配前缀汇聚 Bloom滤波器并行查询路由表 IP网络互联网

一种基于并行Bloom Filter的高速URL查找算法

在线全文

学校读者我要写书评

暂无评论

电子学报 2015年第9期43卷 1833-1840页

作者：周舟付文亮嵩天刘庆云中国科学院信息工程研究所信息内容安全技术国家工程实验室北京100093 北京理工大学计算机学院北京100081

URL查找是众多网络系统中重要的组成部分,如URL过滤系统、Web缓存等.随着互联网的迅速发展,URL查找面临的主要挑战是实现大规模URL集合下的高速查找,同时保证低存储和低功耗.本文提出了一种基于并行Bloom Filter的URL查找算法,CaBF.该... 详细信息

URL查找是众多网络系统中重要的组成部分,如URL过滤系统、Web缓存等.随着互联网的迅速发展,URL查找面临的主要挑战是实现大规模URL集合下的高速查找,同时保证低存储和低功耗.本文提出了一种基于并行Bloom Filter的URL查找算法,CaBF.该算法高度并行化,提供大规模URL集合下的高速最长前缀匹配,并很好地适应集合中不同数量的URL组件.理论分析和真实网络数据集上的实验表明,该算法相比现有算法可以降低假阳性概率达一个数量级(或者在满足相同假阳性概率的前提下降低存储和硬件逻辑资源消耗).此外,该方法的体系结构很容易映射到FPGA等硬件器件上,提供每秒超过150M次的URL查找速度.

关键词： URL查找布鲁姆过滤器最长前缀匹配现场可编程门阵列

在线全文

学校读者我要写书评

暂无评论

基于非重叠前缀集合的并行路由查找系统

电子学报 2004年第8期32卷 1277-1281页

作者：梁志勇徐恪吴建平柴云鹏清华大学计算机科学与技术系北京100084

快速的路由查找机制是高性能路由器设计的关键 .最长匹配查找是路由查找的难点所在 .本文提出一个并行路由查找系统 .它使用一种路由表划分方法 ,可将路由表中的前缀划分为若干个集合 ,集合内前缀没有重叠 .从而把路由表前缀的最长匹配... 详细信息

快速的路由查找机制是高性能路由器设计的关键 .最长匹配查找是路由查找的难点所在 .本文提出一个并行路由查找系统 .它使用一种路由表划分方法 ,可将路由表中的前缀划分为若干个集合 ,集合内前缀没有重叠 .从而把路由表前缀的最长匹配查找转化为若干个集合内前缀的唯一匹配查找 .基于这种方法 ,本文还提出一个通用的并行路由查找框架 ,框架适用于大多数路由查找算法 .并行查找框架可简化查找算法的设计 ,提高查找算法的速度 .使用二分查找算法 ,并行查找系统可以达到log2 (2N/B)的查找复杂度 (N为路由表前缀数目 ,B为大于 4的整数 ) .同时 ,并行查找系统对IPv6也具有很好的扩展性 .

关键词：最长前缀匹配二分查找路由查找路由更新