检索结果-南通市图书馆

在线全文

学校读者我要写书评

暂无评论

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

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

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

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

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

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

在线全文

学校读者我要写书评

暂无评论

基于前缀范围对分搜索的高性能路由查找

计算机学报 2004年第5期27卷 604-610页

作者：王振兴张彦肖孙亚民邬江兴南京理工大学计算机科学系南京210094 解放军信息工程大学信息研究系郑州450002 国家数字交换系统工程技术研究中心郑州450002

高端路由器路由查找大多采用单步TCAM方案 ,要求转发表的存储必须按前缀长度相对地址降序排列 ,这种与地址关联的排序操作影响表项的更新速度和路由查找流程的连续性 .与已有对前缀长度的搜索不同 ,该文提出一种独特的基于前缀范围对分... 详细信息

高端路由器路由查找大多采用单步TCAM方案 ,要求转发表的存储必须按前缀长度相对地址降序排列 ,这种与地址关联的排序操作影响表项的更新速度和路由查找流程的连续性 .与已有对前缀长度的搜索不同 ,该文提出一种独特的基于前缀范围对分搜索的路由查找算法 ,并以多步TCAM实现流水查找 .突出特点是转发表无需排序 ,表项更新快 ,查找速率高且连续性好 ,可满足IPv4 /IPv6核心路由器OC 76 8(40Gbps)端口的线速率转发 .

关键词：对分搜索路由查找流水操作前缀范围查找速率路由器 BSPR 因特网

在线全文

学校读者我要写书评

暂无评论

一种基于重叠位图的路由查找算法

计算机学报 2018年第9期41卷 2106-2119页

作者：刘斌张楚文清华大学计算机系北京100084

路由查找是路由器的核心功能之一,可分为基于硬件和基于软件的查找算法两大类.前者使用专用的可并行硬件实现高速的查找性能,比如FPGA算法、GPU算法和TCAM算法.后者可以部署在通用CPU上,具有更高的灵活性、更低的功耗和成本优势,并且可... 详细信息

路由查找是路由器的核心功能之一,可分为基于硬件和基于软件的查找算法两大类.前者使用专用的可并行硬件实现高速的查找性能,比如FPGA算法、GPU算法和TCAM算法.后者可以部署在通用CPU上,具有更高的灵活性、更低的功耗和成本优势,并且可以利用CPU的Cache实现快速查找.因此,基于软件的路由查找算法已成为软件定义网络和网络功能虚拟化中的关键技术之一.尽管软件查找算法具有很大的优势,它也面临着许多新的挑战.首先,当今骨干网路由器的路由表项数目已达到600K,并且每年保持大约15%的增长率,给路由查找和存储带来了巨大压力.同时,路由表更新速度也逐年稳定增长,并且峰值更新速率已超过10K/s,这就要求路由查找算法具有高速的更新性能.基础的树结构软件查找算法能够支持快速更新,但是过多的访存次数导致查找速度较低,而且其存储开销已经超过16MB,远远高于一般路由器中CPU的Cache大小,进一步影响了查找速度.以Lulea算法为代表的传统位图压缩方法虽然降低了数据结构的存储开销,但是会导致更新困难,复杂而低效的更新操作也会在一定程度上影响查找性能.本文提出了一种基于重叠位图压缩的软件路由查找算法,它通过层次遍历构造重叠式位图结构,比具有高压缩率的Lulea算法占用更小的存储空间(提高Cache的命中率,从而进一步提高查找速度).而且,本算法使用位图分割和多种更新优化技术实现快速的增量更新.实验结果表明本算法能够把包含600K条前缀的路由表压缩到2.3MB,平均比Lulea算法减少26%的存储空间,只有树结构的1/8左右.而且本算法具有良好的拓展性,从2008年的5.06字节/前缀降低到2016年的3.94字节/前缀.实际流量下,本算法平均查找速度达到111.41M/s,是Lulea算法查找速度的2.5倍.同时,在保证10~100K/s的更新速率前提下,实现90~100M/s的查找速度.

关键词：路由查找位图压缩增量更新层次遍历重叠位图

基于前缀区间和前缀层次(PRPL)的IPv6路由查找算法

在线全文

学校读者我要写书评

暂无评论

高技术通讯 2008年第4期18卷 345-349页

作者：赵国锋李振强黄小红马严北京邮电大学计算机科学与技术学院北京100876 北京邮电大学信息网络中心北京100876

通过对前缀区间(PR)和前缀层次(PL)的研究,并结合 IPv6全球单播地址和 IPv6骨干网路由表的特征,提出了一种基于前缀区间和前缀层次(PRPL)的高性能的 IPv6路由查找算法。通过使用合成的不同数据量的 IPv6路由表对该算法进行了测试,测试... 详细信息

通过对前缀区间(PR)和前缀层次(PL)的研究,并结合 IPv6全球单播地址和 IPv6骨干网路由表的特征,提出了一种基于前缀区间和前缀层次(PRPL)的高性能的 IPv6路由查找算法。通过使用合成的不同数据量的 IPv6路由表对该算法进行了测试,测试结果表明该算法的可扩展性非常出色,它能够支持数据量达到200k 的大路由表。与同样环境下的经典算法的测试结果进行了比较,比较结果也表明该算法在平均查找速度和内存消耗方面都有一定的优势。出色的性能和对大路由表的支持,使得该算法能够应用到骨干网IPv6路由器中。

关键词：路由查找前缀区间前缀层次 IPv6

在线全文

学校读者我要写书评

暂无评论

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

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

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

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

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

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

在线全文

学校读者我要写书评

暂无评论

基于IBFBP的IPv6路由查找算法

华中科技大学学报（自然科学版） 2016年第S1期44卷 94-98页

作者：魏中贺潘岩高鹰高阳齐鲁工业大学网络信息中心山东济南250353

总结目前IPv6路由查找算法优缺点,提出了一种新的IPv6路由查找算法(IBFBP).该算法结合改进的布鲁姆过滤器(IBF)与BP神经网络,将IPv6不同长度网络ID作为IBF的输入,以关键字的特征标志创建标志库(LB)进行学习,提前判断是否发生误判.并且... 详细信息

总结目前IPv6路由查找算法优缺点,提出了一种新的IPv6路由查找算法(IBFBP).该算法结合改进的布鲁姆过滤器(IBF)与BP神经网络,将IPv6不同长度网络ID作为IBF的输入,以关键字的特征标志创建标志库(LB)进行学习,提前判断是否发生误判.并且将位数组用counter计数数组来代替,支持可删除操作,进而进行BP神经网络学习过程.理论分析和实验结果表明:该算法比已有神经网络路由查找算法需要学习的条目数平均减少了1 500倍,还降低了误判率和搜索成本,提高了查找效率.

关键词：改进的布鲁姆过滤器算法神经网络 IPv6 路由查找误判

在线全文

学校读者我要写书评

暂无评论

并行多流水绿色路由查找架构和算法

西安电子科技大学学报 2012年第2期39卷 145-152,167页

作者：袁博汪斌强王志明国家数字交换系统工程技术研究中心河南郑州450002

现有路由器体系在性能、复杂性和节能等方面存在诸多难以克服的问题.随着网络规模的扩展,如何实现低功耗大容量路由查找是绿色高性能路由器设计面临的重大挑战.提出一种FIB多级映射的并行多流水路由查找架构,建立了FIB多级映射路由查找... 详细信息

现有路由器体系在性能、复杂性和节能等方面存在诸多难以克服的问题.随着网络规模的扩展,如何实现低功耗大容量路由查找是绿色高性能路由器设计面临的重大挑战.提出一种FIB多级映射的并行多流水路由查找架构,建立了FIB多级映射路由查找架构的功耗模型,基于FIB多级映射路由查找架构提出了路由表动态映射算法.设计了一种绿色路由查找步长优化算法.真实网络路由表实验结果表明,这种算法可以降低30%的路由查找功耗.

关键词：路由查找低功耗多流水绿色路由器动态映射

在线全文

学校读者我要写书评

暂无评论

基于并行BP神经网络的路由查找算法

通信学报 2012年第2期33卷 61-68页

作者：胥小波郑康锋李丹杨义先钮心忻北京邮电大学信息安全中心北京100876 北京邮电大学灾备技术国家工程实验室北京100876

结合Bloom-filter算法和并行反向传播神经网络,提出了一种新的基于并行神经网络的路由查找算法(BFBP)。该算法满足路由查找的需求,只需学习路由条目的网络ID,且易于扩展到IPv6地址查询。研究结果表明,相比于己有的神经网络路由查找方法... 详细信息

结合Bloom-filter算法和并行反向传播神经网络,提出了一种新的基于并行神经网络的路由查找算法(BFBP)。该算法满足路由查找的需求,只需学习路由条目的网络ID,且易于扩展到IPv6地址查询。研究结果表明,相比于己有的神经网络路由查找方法,该算法需要学习的条目数平均减少了520倍,提高了学习效率,为神经网络应用于路由查找创造了有利条件。

关键词：神经网络路由查找反向传播 Bloom—filter算法

在线全文

学校读者我要写书评

暂无评论

快速路由器的路由查找和流分类算法研究

电子科技大学学报 2004年第6期33卷 663-666页

作者：姚兴苗李乐民胡光岷电子科技大学宽带光纤传输与通信网技术教育部重点实验室成都610054

分析了路由器的体系结构发展,研究了路由查找算法和流分类算法在快速路由器中的应用。研究表明,基于分段压缩的路由查找算法支持IPv6路由查找,具有合理的存储容量和快速的查找时间;采用按值分支树的多维综合流分类算法支持前缀和范围匹... 详细信息

分析了路由器的体系结构发展,研究了路由查找算法和流分类算法在快速路由器中的应用。研究表明,基于分段压缩的路由查找算法支持IPv6路由查找,具有合理的存储容量和快速的查找时间;采用按值分支树的多维综合流分类算法支持前缀和范围匹配,可扩展性强,适合大容量规则数据库。两种算法适合在快速路由器中应用。

关键词：体系结构路由查找流分类快速路由器