基于Hash和Trie树的IPv6高速查找和快速增量更新路由算法设计与实现

1、昆明学院2012年毕业设计(论文)设计(论文)主题基于散列和树的IPv6高速检索和高速增量更新路由算法设计和实现次主题名字叫刘晓青取得学位所属信息技术学院专业年级08级计算机科学和技术指导教师何英2012年5月摘要由于互联网速度的提高、网络通信量的增加和网络规模的扩大，路由器已经成为制约互联网性能的主要瓶颈之一. 随着路由器技术的发展，路径搜索速度仍然是进一步提高路由器性能的重要因素。 本文首先研究了各种经典的IPv6路由算法，分析了各种路由算法的复杂性和问题，并分析了从IPv4到IPv6的过度路由算法问题和路由算法的性能参数和复杂性。 提出了基于散列和树形的快速搜索和快速增量更新路由算法，然

2、后改进路由缓存的优化策略，对路由节点进行生物智能处理，改善路由负载平衡，最后进行仿真关键字：路由搜索最长前缀匹配Hash表树生物智能Abstract由于互联网的开发和扩展，makingtherortebecommestheonofthemainbottleneckrestrectingtheinternetperformance.withthedevelopmentofrouting ionlookuptisstillkeyelementtofurtherimplementofthisparterstudentvariousclassicipv6routing loo kup algorith

3、ms firstly， netansialingthecomplementityofthevariousroutinglookupalgorithmsandsomeonexistingproblems infindetheexitingproblessinrolutional IPv6 andtheperformperformanceperf iservedahighspeedlookuptandfastincrentrollationallogrationalgorithmsbasedonhashandtriesetree； Secondly，ihavebendendfortrollecop

4、tionstrationandcondroutenodalbiologicalintelligent，maketherolutionloadbalancingimpr Finally，via the simulation experiment，我知道keywords :路由查找； 长前缀匹配；长前缀匹配； 混列表； 三级； biological智能；目录第一章绪论11.1研究背景和现状11.2本文的研究内容、意义、价值1第二章相关技术概要2第三章HT6路由搜索算法的实现43.1算法设计43.1.1HT6算法基本思想43.1.2数据结构设计53.1.3寻找ht6设计83.1.4路由更新113.2

5、算法改进133.2.1缓存优化133.2.2生物智能节点17第四章模拟及实验数据分析234.1模拟环境构筑234.2算法模拟和分析24第五章总结和展望265.1全文总结265.2研究展望26参考文献27感谢28第一章绪论1.1研究背景和现状互联网在人类生活中发挥着重要的作用。 随着因特网的规模扩大，对用于主干网络互连的核心路由器的接口速度的需求显着增加，要求核心路由器能够在单位时间内传输更多的数据包。 数据包转发的重要步骤是寻找路由表。当前因特网基于IPv4协议，随着因特网的网络规模的扩大，IPv4协议在很多方面无法满足人们的需要。 IPv6由IETF设计，代替IPv4的下一代因特网协议。 I

6、Pv6的最大特征是，与IPv4相比使用128比特的长IP地址，因此IPv4无法将许多优秀的路由算法应用于IPv6，或者在将路由算法应用于IPv6之后，会增加内存访问的数量和存储器消耗，从而导致该算法的1.2本文的研究内容、意义和价值本文主要研究IPv6路由搜索算法，在提出IPv6路由快速搜索和快速增量更新的实现构想的基础上，改进路由缓存，将生物智能应用于路由节点的负载平衡，建立了仿真实验平台，其特征和性能上述工作的意义和价值主要体现在以下方面：第一，本文基于前人提出了新的路由算法设计思路，具有创新性。 基于该构想设计的搜索算法具有较低的时间复杂性和空间复杂性。 第二，基于该算法的路由缓存优化策

7、略和基于生物智能的路由节点负载策略显着提高了算法的性能，对今后研究IPv6路由算法具有明显的参考价值。 第三，我们构建了路径仿真平台以更好地分析和比较各种路径搜索算法的性能。 相信第三章的算法对学者和企业级路由具有很高的参考价值。第二章相关技术概述路由器是在网络层(IP层)上运行的网络通信设备，可以连接到不同类型的网络，也可以选择数据传输路径来传输数据。 路由器主要由路由引擎、转发引擎、路由表、网络适配器、关联的逻辑电路等组成。 传输引擎将数据包从一个网络适配器传输到另一个网络适配器。 包括路由表搜索在内的IP协议构成了转发引擎的主要部分。 因为需要通过路由器并转发的包会搜索路由表，所以路由表

8、的搜索效率往往决定了路由器整体的性能。路由表的搜索效率很高。 路由引擎包含负责更新路由表的更高级别的协议，尤其是路由协议。 由于路由引擎不涉及通过路由器的数据路径，所以它可以被通用CPU代替。IPv6的核心标准是RFC2460互联网协议版本6(IPv6 )规范，其描述了辅助协议的文档RFC2461(IPv6邻居发现协议，ND )和RFC2463 (互联网控制消息协议版本6，IPv6) IPv6地址可以分为单播、单播和多播三种。 单播(单播)地址是与IPv4相同标准的地址，单播地址标识网络接口的anycast地址标识网络接口组，但是以单个单播地址为目标只被传递给该组的一个接口而通常被传递给容易到

9、达的接口的多播地址也标识网络接口的集合，以多播地址为目标的分组如同IPv4的无类地址一样，都是以多播地址为目标的。 地址由网络ID和主机ID构成，网络lD被称为前缀，其位数被称为前缀长度。 前缀通常表示在地址后加斜线，在斜线后加前缀的长度。Trie采用了根据前缀的各个比特的值来决定树枝的基于树的数据结构。 树结构的搜索过程由目的地地址中的比特来实现，对每个节点，左分支和右分支由与目的地地址对应的比特的值来确定，如果比特为0，则选择左分支，否则选择右分支。IPv6算法包括基于B-树的IPv6路由算法、TSB算法、基于trie的IPv6路由算法、散列表和基于trie树的快速内容路由算法1。基于B-

10、树的IPv6路由算法使用IP地址作为插入和检索的关键字，在B-树结构中有秩序地存储表项目，并且使用B-树根据外部访问进行检索。基于Hash和trie树的路由算法将原Hash表按顶级域名分割为小表，使用trie树进行检索。各算法的配置文件和比较如表2.1所示(其中w是地址长度，n是路由表前缀的数量)。演算法时间的复杂性存储容量二进制树O(W )O(N*W )路径压缩PatriciaO(W )O(N )型n阶B-算法树O(log2N )O(N*W )PSO(log2W )O(N*log2W) 216散列函数O(log2N )O(N )型表2.1 IPv6各算法的性能分析比较在实际开发中，路由算法必

11、须满足以下要求：1 )检索速度快2 )存储区域少3 )更新时间短4 )扩展性5 )实现的灵活性6 )预处理时间短本章主要介绍和分析了路由技术的现状，其中重点阐述了IPv6路由发展、研究、存在的问题和评价标准，特别是IPv6路由研究。 本章介绍的路由技术为作者的研究提供了素材和启发，为HT6算法的设计和改进提供了技术支持。第三章HT6路由搜索算法的实现3.1算法设计我们希望好的路径搜索算法能达到：1 .算法实现简单，消耗内存小2 .理想地，优选能够通过一次访问到达转发端口3 .当访问次数为一次以上时，可以将该算法的访问次数少，或者在任何情况下都将访问次数限制在小值的范围内4 .算法更新所花费的时

12、间相对较小本文算法基于这些方面提出了HT6算法。3.1.1HT6算法基本思想考虑到隔离链路散列列表中的填充因子控制可以获得在0.674处的最小开销和多分支trie树检查比特数的特征，在多分支trie树中搜索IPv6地址的48比特，并根据IPv6地址结构，为剩馀的16比特将前缀的长度添加到路由前缀的条目，压缩算法所需的存储区域使用BitAtlas (二进制比特向量)，指示相同的Next-Hop信息将连续出现，因此新出现的Next-Hop信息仅存储一次在以001为上位3比特的单播根检索中，在检索时可以忽略该3比特，在其他类型的单播根中，只要将HT6算法数据结构的第1层trie树的检索步骤宽度增加到

13、24比特即可。以上对HT6算法设计的基本思想主要对前缀扩展技术需要大幅度的压缩率，而且要容易地展开检索和路线更新。 针对以上的请求，我们设计的前缀扩展技术利用节点结构来搜索步长为24-8-4-4-8-16的六层多分支树形树，将具有相同下一跳信息的连续条目合成一个块，使用BitAtlas在各块的开头位置(3.1.2数据结构设计数据结构在参考TrieC2算法的基础上提出了HT6算法，该算法采用24-8-4-4-8-16步长构建多分支Tile树，树中每个节点的数据结构如下根节点采用HTl5/6 (步骤宽度24 )的数据结构(忽略IPv6地址的001域)，并保存 1，24 位长的所有IPv6地址前缀第

14、二层和第五层采用HT4/4 (步宽8 )的数据结构，分别存储 25，32 位长和 41，48 位长的IPv6地址前缀。 第三层和第四层采用HT2/4 (步长4 )的数据结构，并且分别存储长度为 33，36 比特和 37，40 比特的IPv6地址前缀第5层采用散列数据结构，并存储长度为 49，64 比特的IPv6地址前缀。为了实现路由表的快速增量更新，树中存储有不进行前缀扩展压缩前的原始前缀长度信息，该信息被存储在NHI(Next-Hop Index )数据结构上。 如果NHI长度为2个字节，且NHI15:16存储标志位： flag为“0”表示搜索成功，则NHI14:6存储下一跳信息Next-Hop ID，NHl5:0存储MCPE压缩前的前缀长度(最大64位) 表示需要继续搜索下一层的树节点，NHI14:0中存