导读:本文包含了路由查找论文开题报告文献综述、选题提纲参考文献及外文文献翻译，主要关键词:路由,前缀,最长,过滤器,布谷鸟,遍历,位图。
路由查找论文文献综述
李亚琼[1]（2018）在《面向高性能网络的加速路由查找方法的研究》一文中研究指出随着互联网技术的迅猛发展,数据中心网络(DCN)和软件定义网络(SDN)等技术应运而生,随之而来的是对网络路由数据包转发处理的速度也提出了更高的要求。主要表现在:第一、在大规模的网络中,SDN控制器中路由转发的效率将直接影响整个网络中数据包的阻塞延迟和终端用户的服务质量。第二、在DCN中,服务器的数量可能是数万、甚至数十万台,将使得主机中路由表的规模变大,导致查表时间及内存的需求不断增加。同时,在转发时需要按最长前缀匹配查找,使得地址查找在数值和长度两个维度上进行,成为路由转发的瓶颈。针对上述问题,本文围绕DCN数据中心网络及SDN中大规模数据查找路由表展开研究。根据路由转发速度提升的需求,结合Hash算法和Trie算法,提出了两种高效前缀匹配算法。通过理论分析和实验验证,结果表明算法有效改进了路由表分组高速查找转发的性能。所做工作主要包括:(1)提出了利用GPU的并行计算特性,加速路由查找的算法。路由检索时,大量的数据包进行路由查询,过程本身具有高并发性。所以提出两种基于GPU加速技术的路由查找算法,对基于CUCKOO FILTER哈希表查找算法的加速和基于LCTrie树形查找算法的加速,并对比分析了两种方式的优缺点。基于GPU并行加速的路由检索算法对比基于CPU处理的路由检索,加速了近30倍,证明了采用GPU架构作为路由查找算法依托平台的可执行性。(2)设计并提出了基于哈希偏移树前缀匹配(Hash offsettrie match on longest prefix,HOTMLP)HOTMLP的路由查找算法。将路由表最长前缀匹配分为公共前缀匹配和特征前缀匹配两个部分,使用哈希表存储了所有路由前缀中公共部分,压缩了存储空间,也减少了匹配步长,再结合Trie精确找到最长的前缀匹配项目。通过理论分析验证,该算法具有查找速度快,易于更新,压缩了存储空间等特点,使用HOTMLP进行最长前缀匹配查找的复杂度为:O(n+2)。其中,IPV4地址的n最大为8,IPV6地址的n最大为32。实验结果表明,该设计可满足核心路由的高速数据路由查找的需求,在主机上测试,吞吐量达到70Gpbs。(3)通过实验平台对本文中所提出的两种算法分别进行了验证和分析。实验结果表明:文中提出的算法实现了查找速度,更新速度和空间利用率的叁方面平衡的优势,支持每秒千万级别分组的处理,适合用于数据流量大的中心网络,也适合用于SDN下大量流表的查找转发。(本文来源于《暨南大学》期刊2018-06-27）
陈国良[2]（2018）在《基于改进IPv6前缀的网络路由查找研究》一文中研究指出随着IPv4地址的耗竭,IPv6的推广速度得到了非常大的提升。具体的表现为,IPv6地址分配量增多,骨干网路由器FIB(Forwarding Information Table转发信息表)中IPv6前缀数增加,骨干网IPv6流量大大增加。路由查找算法的性能一直都是路由器性能的重要影响因素,针对IPv4路由表进行优化的路由查找算法经过了非常久的研究,但是在IPv6的新环境下,以往的算法往往性能不尽如人意。因此,提出新的针对IPv6的路由查找算法非常必要。文中针对IPv6的路由查找提出了一种分段查找与哈希查找相结合的算法,包括两种权衡策略,一种侧重减少查找访存次数,一种侧重减少内存存储开销。(本文来源于《信息技术》期刊2018年05期）
姚明,赵晶晶,贺兴亚,杨云[3]（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期）
秦怡,杨云,闵玉涓,姚明,赵晶晶[4]（2018）在《哈希表和多比特Trie相结合的IPv6分阶段路由查找算法》一文中研究指出IPv6具有128位的地址长度、无分类编址,这使得IPv6网络中的核心路由器路由查找处理负担更重、要求更高,已有的基于IPv4的路由查找算法扩展到IPv6后无法适应新的需求,需要建立新的基于IPv6的路由查找算法.在分析了IPv6地址前缀长度和分布特点的基础上,提出一种哈希表和多比特Trie(retrieval)相结合的IPv6路由查找算法.算法首先根据地址前缀值来进行分类,然后针对常用的地址前缀值,以48比特为路由查找起点,分阶段、高效的进行路由查找,对于非常用的地址前缀值采用直接哈希查找.算法仿真表明,在大多数情况下,只需要一次存储器访问,就能查找到下一跳路由信息,算法查找效率高.算法结构简单,易于硬件实现.(本文来源于《小型微型计算机系统》期刊2018年05期）
姚明[5]（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）
刘斌,张楚文[6]（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期）
李兵[7]（2017）在《IPv4/IPv6双栈兼容路由查找模块设计》一文中研究指出随着计算机网络的迅猛发展,需要网络协议(Internet Protocol,IP)地址的主机越来越多。到2011年,第四代网络协议(IP version 4,IPv4)地址已经耗尽。为解决IPv4地址耗尽问题,第六代互联网协议(IP version6,IPv6)被提出,然而更换一个协议十分复杂,因此IPv4和IPv6将会长时间共存。这要求路由器能够兼容IPv4和IPv6双栈协议。双栈路由器的性能很大程度上取决于数据包的分组转发速率,分组转发重要的是查找路由表,因此快速的路由查找显得尤为重要。本文研究了国内外已有的路由查找算法,分析了各种算法的优缺点和硬件实现的可行性。在分析了IP 4/IPv6前缀的分布特点后,提出了一种一级缓存和一级索引相结合的分组分块硬件路由查找方案。根据提出的方案,本文设计并划分了模块,其中主要包括缓存模块、布隆滤波器模块、前缀处理模块和仲裁模块。为了提高索引效率,本文提出了加权值的相关性检测机制,减少了布隆滤波器(BloomFilter,BF)的假阳性错误概率。为了提高路由查找的可扩展性,本设计选取了哈希链表(Hash Chain Tables,HCT)存储方案并定义了其数据结构。本文对设计模块进行了实现,建立了对应的C语言模型,通过与C语言模型对比完成了设计模块功能验证和可编程门阵列(Field Programmable Gate Array,FPGA)设计。本设计通过XilinxML605开发平台完成FPGA实现,模块的工作频率可达244.069MHz,平均每秒查找次数可达到2260万次,达到IPv4/IPv6双栈路由器OC-192(Optical Carrier 192,10Gb/s)端口的链路速率。结果表明,相对使用叁态内容寻址存储器(Ternary Content Addressable Memory,TCAM)实现的双栈路由查找方案,该查找方案成本低廉,支持动态无阻塞更新,其结构灵活,可扩展性强。本设计适用于链路速率不大于10Gb/s的IPv4/1Pv6双栈路由器中,具有重要的工程应用意义。(本文来源于《东南大学》期刊2017-09-01）
何婧,赵哲,李园利[8]（2017）在《星载快速路由查找算法设计与实现》一文中研究指出针对星载路由器的路由查找功能展开研究,分析比较常用的路由查找算法,利用软硬件协同设计的思想,提出了一种基于Hash桶和压缩Trie树相结合的路由查找算法,详细介绍了该算法的数据结构和实现步骤,对算法的性能进行分析比较。结果表明,该设计可满足宽带卫星通信系统高速数据路由查找的需求,实现10 Gbps数据的线速查找。(本文来源于《空间电子技术》期刊2017年02期）
秦怡[9]（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）
胡俊[10]（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）
路由查找论文开题报告
（1）论文研究背景及目的
此处内容要求：
首先简单简介论文所研究问题的基本概念和背景，再而简单明了地指出论文所要研究解决的具体问题，并提出你的论文准备的观点或解决方法。
写法范例：
随着IPv4地址的耗竭,IPv6的推广速度得到了非常大的提升。具体的表现为,IPv6地址分配量增多,骨干网路由器FIB(Forwarding Information Table转发信息表)中IPv6前缀数增加,骨干网IPv6流量大大增加。路由查找算法的性能一直都是路由器性能的重要影响因素,针对IPv4路由表进行优化的路由查找算法经过了非常久的研究,但是在IPv6的新环境下,以往的算法往往性能不尽如人意。因此,提出新的针对IPv6的路由查找算法非常必要。文中针对IPv6的路由查找提出了一种分段查找与哈希查找相结合的算法,包括两种权衡策略,一种侧重减少查找访存次数,一种侧重减少内存存储开销。
（2）本文研究方法
调查法：该方法是有目的、有系统的搜集有关研究对象的具体信息。
观察法：用自己的感官和辅助工具直接观察研究对象从而得到有关信息。
实验法：通过主支变革、控制研究对象来发现与确认事物间的因果关系。
文献研究法：通过调查文献来获得资料，从而全面的、正确的了解掌握研究方法。
实证研究法：依据现有的科学理论和实践的需要提出设计。
定性分析法：对研究对象进行“质”的方面的研究，这个方法需要计算的数据较少。
定量分析法：通过具体的数字，使人们对研究对象的认识进一步精确化。
跨学科研究法：运用多学科的理论、方法和成果从整体上对某一课题进行研究。
功能分析法：这是社会科学用来分析社会现象的一种方法，从某一功能出发研究多个方面的影响。
模拟法：通过创设一个与原型相似的模型来间接研究原型某种特性的一种形容方法。
路由查找论文参考文献
[1].李亚琼.面向高性能网络的加速路由查找方法的研究[D].暨南大学.2018
[2].陈国良.基于改进IPv6前缀的网络路由查找研究[J].信息技术.2018
[3].姚明,赵晶晶,贺兴亚,杨云.B-树和bloomfilter相结合的IPv6路由查找算法[J].计算机应用研究.2019
[4].秦怡,杨云,闵玉涓,姚明,赵晶晶.哈希表和多比特Trie相结合的IPv6分阶段路由查找算法[J].小型微型计算机系统.2018
[5].姚明.基于IPv6的路由查找算法的研究与设计[D].扬州大学.2018
[6].刘斌,张楚文.一种基于重迭位图的路由查找算法[J].计算机学报.2018
[7].李兵.IPv4/IPv6双栈兼容路由查找模块设计[D].东南大学.2017
[8].何婧,赵哲,李园利.星载快速路由查找算法设计与实现[J].空间电子技术.2017
[9].秦怡.基于IP网络的路由查找算法的研究与设计[D].扬州大学.2017
[10].胡俊.基于pivot-pushing和BloomFilter的快速路由查找算法[D].西安电子科技大学.2017
论文知识图
