导读:本文包含了路由查找算法论文开题报告文献综述、选题提纲参考文献及外文文献翻译，主要关键词:路由,算法,过滤器,前缀,最长,神经网络,遍历。
路由查找算法论文文献综述
姚明,赵晶晶,贺兴亚,杨云[1]（2019）在《B-树和bloom filter相结合的IPv6路由查找算法》一文中研究指出为了提高IPv6的路由查找效率,针对IPv6路由前缀分布不均匀的问题,提出了一种基于B-树和bloom filter相结合的IPv6路由查找算法(BTBF)。BTBF分为B-树和bloom filter查找两部分,利用B-树查找路由前缀的前16 bit值,然后通过B-树节点中位向量的映射,将下一步链接到bloom filter,再利用bloom filter位数组的值映射提取下一跳。实验结果表明,BTBF算法与其他树型和bloom filter类算法相比有效减少了空间和时间占用,在路由表项数变化较大的情况下也能维持稳定的查找性能。(本文来源于《计算机应用研究》期刊2019年09期）
秦怡,杨云,闵玉涓,姚明,赵晶晶[2]（2018）在《哈希表和多比特Trie相结合的IPv6分阶段路由查找算法》一文中研究指出IPv6具有128位的地址长度、无分类编址,这使得IPv6网络中的核心路由器路由查找处理负担更重、要求更高,已有的基于IPv4的路由查找算法扩展到IPv6后无法适应新的需求,需要建立新的基于IPv6的路由查找算法.在分析了IPv6地址前缀长度和分布特点的基础上,提出一种哈希表和多比特Trie(retrieval)相结合的IPv6路由查找算法.算法首先根据地址前缀值来进行分类,然后针对常用的地址前缀值,以48比特为路由查找起点,分阶段、高效的进行路由查找,对于非常用的地址前缀值采用直接哈希查找.算法仿真表明,在大多数情况下,只需要一次存储器访问,就能查找到下一跳路由信息,算法查找效率高.算法结构简单,易于硬件实现.(本文来源于《小型微型计算机系统》期刊2018年05期）
姚明[3]（2018）在《基于IPv6的路由查找算法的研究与设计》一文中研究指出Internet的快速发展使链路上传输的数据速度达到了 400Gbps,导致路由器的吞吐量和查找最佳出口的工作量也大大增加。路由器对每一个经过的数据报转发的快慢即路由转发速率是影响当前互联网数据吞吐量的关键,路由转发过程中的关键是路由表查找,因此设计一个合适的路由查找算法十分必要。相比于IPv4,IPv6的地址长度更长,这意味着IPv6的路由表表项数会更多,基于前缀长度的IPv4查找算法不能直接扩展到IPv6的查找。论文围绕基于IPv6的路由查找算法展开,分别给出了适用于目前路由表和将来大规模IPv6路由表的路由查找算法。主要工作包括:1、对IPv6单播地址结构和当前骨干路由器路由表分布特点进行了解析,提出了一种B-树和Bloom Filter相结合的IPv6路由查找算法(BTBF)。BTBF首先利用2-3树查找前缀前16bits值,如果正确匹配2-3树节点,那么通过节点中的位数组对于Bloom Filter的映射,将下一步查找转发到Bloom Filter。再计算Bloom Filter计数数组的二进制值通过Hash的方式映射到目的IP地址的存储位置从而获取下一跳。实验结果表明,BTBF相比于其他树形类和Bloom Filter类算法有效减少了查找时间和存储空间占用,能在路由表项数变化较大的情况下维持稳定的查找性能。2、基于二进制比特的Trie型数据结构面对大规模IPv6路由表时查找困难,因此引入了前缀区间的概念以适应大规模动态IPv6路由表查找,提出了一种段表与B-树相结合的IPv6路由查找算法。以α位为分割点将路由前缀分隔为前缀Indexα(P)和后缀Suffixα(P),Indexα(P)保存在段表中,段表为一个顺序表,可以根据的不同分别存储在段表的不同位置,具体的存储形式为Set(i),i前缀Indexα(P)的值。当段表查找阶段匹配成功后可以索引到B-树,然后在B-树中查找后缀Suffixα(P),并利用Cover(x)数组存储被节点区间包含的数据以解决B-树查找歧义问题。将段表和B-树进行结合查找的策略有效地减少了每个查找B-树的节点数,降低了查找深度,提高了查找效率。实验结果表明,该算法与其他的基于前缀区间的Trie树查找算法相比在查找时间和存储空间占用上占有优势,能够满足较大规模的路由表查找性能要求。近年来,研究人员针对IPv6的路由查找算法集中在基于前缀值查找算法研究上,我们在前人的研究基础上对B-树数据结构进行了探索与改进,与其他顺序表或Hash类结构的有机结合,继承了他们一些优秀的思想,并融合进论文算法中,对路由查找算法性能做了进一步的提升。(本文来源于《扬州大学》期刊2018-04-16）
刘斌,张楚文[4]（2018）在《一种基于重迭位图的路由查找算法》一文中研究指出路由查找是路由器的核心功能之一,可分为基于硬件和基于软件的查找算法两大类.前者使用专用的可并行硬件实现高速的查找性能,比如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的查找速度.(本文来源于《计算机学报》期刊2018年09期）
秦怡[5]（2017）在《基于IP网络的路由查找算法的研究与设计》一文中研究指出路由器是组成互联网的重要节点设备,位于ISO/OSI七层模型中的网络层,负责网络中数据的转发工作。它将不同的网络连接起来,并为经过它的数据包选择最佳的出口进行转发。路由器转发数据包的快慢,决定了经过路由器的所有数据包的传输速度。目前,链路上传输的数据已经可以通过光纤来承载,其传输速度可以达到400Gbps,因此当前路由器的性能瓶颈在于路由查找算法。路由器的查找效率决定了路由器的性能,决定了互联网的数据吞吐量。互联网上大多数的流量还是由IPv4网络承载,研究基于IPv4的路由查找算法有其现实意义。如何解决最长前缀匹配问题,是设计路由查找算法的核心问题,目前众多学者主要围绕路由查找算法的最长前缀匹配问题展开研究。IPv6作为IPv4的下一代技术,具有128位的地址长度。它对IPv6网络中的核心路由器处理负担更重、要求更高。已有的基于IPv4的路由查找算法,扩展到IPv6后无法适应新的需求或效率低下,需要建立新的基于IPv6的路由查找算法。论文主要围绕基于IPv4、IPv6路由查找算法展开,分别给出了适用于IPv4和IPv6的路由查找算法。主要工作包括:1、分析了 IPv4的地址结构及其发展史,通过对核心路由器中路由表数据的分析,发现了 IPv4地址前缀分布呈现一定特点:地址前缀长度为24的表项最多。论文针对这个特性,提出了一种哈希表和多比特树相结合的分阶段路由查找算法,算法将路由查找阶段分为两个阶段,分别是哈希表查找阶段和多比特树结构查找阶段。为了减少对存储器的访问,还提出了一种固定高度的多比特树结构:4-3Trie,该结构将路由查找时访问存储器的次数限定在了可接受的范围之内。算法分析和实验仿真表明,该算法通过利用IPv4地址前缀分布的特点,提高了查找效率,具有良好的路由查找性能。2、分析了 IPv6地址结构,通过对从Internet核心路由器的路由表中获取了路由前缀分布数据分析,发现地址前缀长度为16倍数的表项最多,其中尤以地址前缀长度为48的表项最多,其次是地址前缀长度为32的表项。同时分析还发现,在路由表中前缀中以20、24、26、28和2a开头的表项占了绝大多数。在此分析基础上,综合运用了哈希表和多比特树两种结构,提出了一种适用于IPv6的分阶段的路由查找算法,给出了 H16、H32、H32c、H48、H48c和H64六个哈希函数和一套哈希冲突解决策略。同时算法还提出了 6-5-4Trie结构,将树的高度控制在了可接受的范围,并且,算法在压缩树高度的同时,尽可能的降低树的稀疏程度来减少存储空间的浪费。算法分析和实验仿真证明,该算法在查找速度和存储空间上都有优势,能够满足核心路由器的性能要求。路由查找算法是复杂的,众多学者对其进行了深入的研究,我们是在前人研究的基础上进行了改进和探索。相关研究成果已被录用,即将在国内外的核心期刊上发表。(本文来源于《扬州大学》期刊2017-04-10）
胡俊[6]（2017）在《基于pivot-pushing和Bloom Filter的快速路由查找算法》一文中研究指出随着计算机技术和通信技术的快速发展,网络规模不断扩大,Internet用户对网络带宽提出了更高的要求,制约网络带宽的关键因素在于路由器路由查找和分组转发的速度。路由器基于待转发数据包的目的IP地址进行路由查找,根据最长前缀匹配规则,在转发信息表(FIB:Forwarding Information Base)中查询下一跳端口。路由器的内存和CPU资源有限,随着FIB表项个数的不断增加,设计高效准确的路由查找算法是提升路由器转发效率的核心和关键。“基于Bloom Filter的路由查找算法(简称为PBF算法)”是一个将Bloom Filter和Trie树应用到路由查找中的高效算法,但是由于Bloom Filter存在“假阳性”,必须要针对Bloom Filter考察出来的前缀(称这些前缀为“候选前缀”)到片外对比出在FIB表中存在匹配项且长度最长的前缀,影响了路由查找的效率,随着FIB表项个数的增加,PBF算法效率变得越来越低。为了在路由查找时探测出比PBF算法更少的候选前缀,减少由于Bloom Filter假阳性造成的不必要的片外内存访问次数,提高路由器路由查找速度,本文提出并实现了基于pivot-pushing和Bloom Filter的快速路由查找算法(简称为PP&BF算法)。PP&BF算法对根据FIB表在片外构建的原始Trie树的某一层(假设为第p层)进行pivot-pushing操作,实现对Trie树的优化;在进行路由查找时,利用针对优化后的Trie树第p层上的“空心节点”(空心节点代表的网络前缀在FIB表中不存在对应的表项)构建的Bloom Filter的返回值,探测出待查IP地址在FIB表中最长匹配前缀的长度范围,选出比PBF算法更少的候选前缀,达到了减少不必要的片外内存访问次数,提高路由器路由查找速度的目的。经过试验和理论分析确定参数p最优的值后,针对PBF算法和本文提出的PP&BF算法进行了大量对比试验,实验结果表明:PP&BF算法的查询效率要优于PBF算法,在要求算法平均片外访问次数不高于1.003的前提下,PP&BF算法相比PBF算法可以节约10%以上的片上存储空间。(本文来源于《西安电子科技大学》期刊2017-04-01）
魏中贺,潘岩,高鹰,高阳[7]（2016）在《基于IBFBP的IPv6路由查找算法》一文中研究指出总结目前IPv6路由查找算法优缺点,提出了一种新的IPv6路由查找算法(IBFBP).该算法结合改进的布鲁姆过滤器(IBF)与BP神经网络,将IPv6不同长度网络ID作为IBF的输入,以关键字的特征标志创建标志库(LB)进行学习,提前判断是否发生误判.并且将位数组用counter计数数组来代替,支持可删除操作,进而进行BP神经网络学习过程.理论分析和实验结果表明:该算法比已有神经网络路由查找算法需要学习的条目数平均减少了1 500倍,还降低了误判率和搜索成本,提高了查找效率.(本文来源于《华中科技大学学报(自然科学版)》期刊2016年S1期）
丁红艳[8]（2016）在《浅谈路由查找算法》一文中研究指出网络路由器位于通信网络中的网络层,在数据传输过程中起着两方面作用,一是寻址,即根据目的 IP地址找到到达数据包所需要转发的端口编号;二是转发,就是从该端口将数据包转发出去。(本文来源于《同行》期刊2016年08期）
张俊俊,陈庆华,乔庐峰,王晶[9]（2015）在《高性能星载IP交换机路由查找算法的研究与实现》一文中研究指出由于卫星空间环境的特殊性,星载设备在设计上受到了体积、功耗、可靠性等诸多因素的限制限制,因此地面路由器中采用的路由查找算法不能简单的搬到星上路由器中。为此,提出一种将压缩二叉树算法、哈希查找相结合的适合星上的IP路由查找方法。使用Xilinx xc6vlx130t FPGA实现了该查找算法,电路共占用338K字节片上存储器资源和1 256个Slices,可以满足叁模冗余设计要求。在系统工作主频为100 MHz、包长为64字节的情况下,查找电路的峰值查找速度能达到10.24 Gb/s,可以满足10 Gb/s以上的系统设计需求。(本文来源于《通信技术》期刊2015年12期）
贺雨虹[10]（2015）在《命名数据网络的路由查找算法研究》一文中研究指出以IP包交换为核心的互联网结构设计已经流行了数十年,网络之间互联最初的目标是实现硬件资源的共享。然而,随着技术飞速发展和信息的爆炸式增加,信息共享成为了如今的主要需求,硬件共享变得不再那么重要。命名数据网络作为一种全新的网络模式,其目的是为了更好的满足用户快速便捷的访问互联网内容的需求。命名数据网络通过内容名字进行路由查找与转发。与IP网络路由方法相比,名字查找有一些不同的特征。例如可变长度、层次化的名字结构;比IP网络大2~3个数量级的路由表规模;内容频繁的发布删除导致的路由更新。这些特征使得实现快速名字路由查找算法成为一个重大而艰巨的任务。针对这一问题,本课题结合命名数据网络名字的特性,对名字结构及算法进行了改进。本课题先研究了常用的查找树、哈希表、布隆过滤器叁种经典结构的名字路由查找算法。针对查找树存储开销太大,哈希表存在碰撞且不满足最长前缀匹配等问题,并结合名字层次结构的特征,本课题设计了一种基于哈希查找树的路由算法。这种方法通过哈希函数将词元组件而不是整个名字散列成哈希值,从而适用于最长前缀匹配。同时每层词元单独设计哈希函数能保证哈希碰撞控制在一个很低的范围内。然后查找树的状态转移不通过词元而是通过哈希值匹配来确定,使得查找效率得到提升。此外哈希值比名字词元将占用更少的存储空间,从而降低了结构的空间开销。同时哈希计算可以预处理,和名字查找处于并行结构。实验结果表明该结构有效的提升了查找树的空间效率并小幅度提升了查找效率。为了进一步解决名字可变长度导致的查找树结构层次过深,查找效率低下的问题。本课题设计了一种词元查找树结合布隆过滤器的组合数据结构。该算法结构充分考虑到命名数据网络名字分层可变长的结构,将一个完整的名字划分为两个较短的部分处理:前一部分是固定长度的查找树段,后一部分是可变长度的布隆过滤器段。并着重讨论了不同的分层对于算法效率的影响,最终得出一个最优的分层划分。对比实验结果表明,该结构在存储开销和查找速度方面均有良好的表现。(本文来源于《哈尔滨工业大学》期刊2015-12-01）
路由查找算法论文开题报告
（1）论文研究背景及目的
此处内容要求：
首先简单简介论文所研究问题的基本概念和背景，再而简单明了地指出论文所要研究解决的具体问题，并提出你的论文准备的观点或解决方法。
写法范例：
IPv6具有128位的地址长度、无分类编址,这使得IPv6网络中的核心路由器路由查找处理负担更重、要求更高,已有的基于IPv4的路由查找算法扩展到IPv6后无法适应新的需求,需要建立新的基于IPv6的路由查找算法.在分析了IPv6地址前缀长度和分布特点的基础上,提出一种哈希表和多比特Trie(retrieval)相结合的IPv6路由查找算法.算法首先根据地址前缀值来进行分类,然后针对常用的地址前缀值,以48比特为路由查找起点,分阶段、高效的进行路由查找,对于非常用的地址前缀值采用直接哈希查找.算法仿真表明,在大多数情况下,只需要一次存储器访问,就能查找到下一跳路由信息,算法查找效率高.算法结构简单,易于硬件实现.
（2）本文研究方法
调查法：该方法是有目的、有系统的搜集有关研究对象的具体信息。
观察法：用自己的感官和辅助工具直接观察研究对象从而得到有关信息。
实验法：通过主支变革、控制研究对象来发现与确认事物间的因果关系。
文献研究法：通过调查文献来获得资料，从而全面的、正确的了解掌握研究方法。
实证研究法：依据现有的科学理论和实践的需要提出设计。
定性分析法：对研究对象进行“质”的方面的研究，这个方法需要计算的数据较少。
定量分析法：通过具体的数字，使人们对研究对象的认识进一步精确化。
跨学科研究法：运用多学科的理论、方法和成果从整体上对某一课题进行研究。
功能分析法：这是社会科学用来分析社会现象的一种方法，从某一功能出发研究多个方面的影响。
模拟法：通过创设一个与原型相似的模型来间接研究原型某种特性的一种形容方法。
路由查找算法论文参考文献
[1].姚明,赵晶晶,贺兴亚,杨云.B-树和bloomfilter相结合的IPv6路由查找算法[J].计算机应用研究.2019
[2].秦怡,杨云,闵玉涓,姚明,赵晶晶.哈希表和多比特Trie相结合的IPv6分阶段路由查找算法[J].小型微型计算机系统.2018
[3].姚明.基于IPv6的路由查找算法的研究与设计[D].扬州大学.2018
[4].刘斌,张楚文.一种基于重迭位图的路由查找算法[J].计算机学报.2018
[5].秦怡.基于IP网络的路由查找算法的研究与设计[D].扬州大学.2017
[6].胡俊.基于pivot-pushing和BloomFilter的快速路由查找算法[D].西安电子科技大学.2017
[7].魏中贺,潘岩,高鹰,高阳.基于IBFBP的IPv6路由查找算法[J].华中科技大学学报(自然科学版).2016
[8].丁红艳.浅谈路由查找算法[J].同行.2016
[9].张俊俊,陈庆华,乔庐峰,王晶.高性能星载IP交换机路由查找算法的研究与实现[J].通信技术.2015
[10].贺雨虹.命名数据网络的路由查找算法研究[D].哈尔滨工业大学.2015
论文知识图
