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

昆明学院2012届毕业设计（论文）设计（论文）题目基于Hash和Trie树的IPv6高速查找和快速增量更新路由算法设计与实现子课题题目姓名刘晓青学号20081101420所属系信息技术学院专业年级08级计算机科学与技术指导教师何英2012年5月摘要由于Internet的速度不断提高、网络流量不断增加和网络规模不断扩大，使得路由器成为制约Internet性能的主要瓶颈之一。随着路由器技术的发展，路由查找速度依然是进一步提高路由器性能的关键要素。本论文首先研究了各种经典的IPv6路由查找算法，并分析了各种路由查找算法的复杂度和存在的问题，对IPv4向IPv6过度的路由查找算法的存在的问题以及路由查找算法的性能参数和复杂度，给出了一种基于hash和trie树高速查找和快速增量更新路由查找算法；其次，对路由缓存优化策略进行改进，并就路由节点进行生物智能化处理，使得路由负载平衡得到改善；最后，通过仿真实验，得出该算法优于以往算法。关键字：路由查找；最长前缀匹配；Hash表；Trie树；生物智能AbstractWiththedevelopmentoftheinternet,theincreasingofthroughputandtheexpandingofnetwork,makingtherouterbecomestheoneofthemainbottleneckrestrictingtheinternetperformance.Withthedevelopmentofroutingtechnology,thespeedoftheroutinglookupisstillakeyelementtofurtherimprovementofrouterperformance.ThispaperstudiedvariousclassicIPv6routinglookupalgorithmsfirstly,thenanalysisthecomplexityofthevariousroutinglookupalgorithmsandsomeexistingproblems,findtheexitingproblemsinroutinglookupalgorithmsfromIPv4toIPv6andtheperformanceparametersandcomplexityofroutinglookupalgorithms,iservedahighspeedlookupandfastincrementalupdateroutinglookupalgorithmsbasedonhashandtrietree;Secondly,ihavebeendoneforroutecacheoptimizationstrategiesimprovementandconductedroutenodalbiologicalintelligent,maketheroutingloadbalancingimproving;Finally,viathesimulationexperiment,iknowthatthisalgorithmisbetterthanbefore.Keywords:Routelookup；Longestprefixmatch；Hashtable；Tire；Biologicalintelligence；目录第一章绪论................................................................................11.1研究背景及现状............................................................11.2本文研究内容、意义、价值........................................1第二章相关技术概述...............................................................2第三章HT6路由查找算法的实现............................................43.1算法设计.........................................................................43.1.1HT6算法基本思想..................................................43.1.2数据结构设计........................................................53.1.3HT6查找设计........................................................83.1.4路由更新..............................................................113.2算法改进.......................................................................133.2.1缓存优化..............................................................133.2.2生物智能节点......................................................17第四章模拟仿真及实验数据分析.........................................234.1仿真环境搭建...............................................................234.2算法仿真及分析...........................................................24第五章总结与展望.................................................................265.1全文总结.......................................................................265.2研究展望.......................................................................26参考文献....................................................................................27致谢............................................................................................281第一章绪论1.1研究背景及现状互联网在人类生活中扮演着重要的角色。随着互联网规模不断增长，用于主干网络互联的核心路由器的接口速率需求已经大大提高，这就要求核心路由器在单位时间内能够转发更多的分组，分组转发的重要一步就是查找路由表。目前的互联网是基于IPv4协议，随着互联网的网络规模不断扩大，IPv4协议在许多方面己经不能满足人们的需要。IPv6是由IETF设计的，用来替代IPv4的下一代互联网协议。和IPv4相比，IPv6最大的特点是它使用了128位超长IP地址，这就使得IPv4中许多性能优异的路由查找算法不能够应用到IPv6中，或者是应用到IPv6之后，由于内存访问次数或内存消耗的增加，导致算法性能非常低。1.2本文研究内容、意义、价值本文主要研究了IPv6路由查找算法，提出了一种适用于IPv6路由高速查找和快速增量更新实现思路，在此基础上改进了路由缓存，将生物智能应用到路由节点的负载平衡中来，并搭建了仿真实验平台对其特点和性能进行了定量研究。上述工作的意义和价值主要体现在以下方面：第一，本文在前人的基础上提出了新的路由查找算法设计思路，具有创新性。基于该思路设计的查找算法具有更低的时间复杂度和空间复杂度。第二，在此算法的基础上提出了路由缓存优化的策略和基于生物智能的路由节点负载策略对算法的性能进行了大幅度的提升，这对以后研究IPv6路由算法具有明显的借鉴价值。第三，为了更好地分析和对比各种路由查找算法的性能，我们搭建了路由仿真平台。相信第三章算法对学者以及企业级路由应用具有很高的参考价值。2第二章相关技术概述路由器是工作在网络层(IP层)的网络通信设备，可以连接不同类型的网络，还能够选择数据传送路径并对数据进行转发。路由器主要由下面几部分组成：路由引擎、转发引擎、路由表、网络适配器和相关的逻辑电路等。转发引擎负责把从一个网络适配器来的数据包转发到另一个网络适配器出去。IP协议，包括对路由表的查找，构成了转发引擎中最主要的部分。由于每个通过路由器并需要其转发的数据包都要对路由表进行查找，所以路由表的查找效率如何往往决定了整个路由器的性能。路由引擎则包括了高层协议，特别是路由协议，它负责对路由表的更新。由于路由引擎不涉及通过路由器的数据通路，可以使用通用的CPU代替。IPv6核心标准是RFC2460网际协议版本6(IPv6)规范，以及描述其辅助协议的文档RFC2461(IPv6邻居发现协议，ND)和RFC2463(互联网控制报文协议版本6，ICMPv6)。IPv6地址可以分为一下三类：单播、任播、多播。单播(unicast)地址是和IPv4相同标准的地址，一个单播地址标识一个网络接口；任播(anycast)地址标识一组网络接口，但目标为一个任播地址的分组只会被送到那个组中的一个接口中去，通常被送到容易到达的接口；多播(multicast)地址也标识一组网络接口，目标为多播地址的分组会被送给那个组中所有的成员IPv6地址的前缀表示，类似于IPv4的无类别地址。地址由网络ID和主机ID组成，网络lD称为前缀，其比特个数称为前缀长度。前缀通常是在地址后加斜杠，斜杠后加前缀长度来表示。Trie采用一种基于树的数据结构，它通过前缀中每一个比特的值来决定树的分支。Trie树结构的查找过程根据目的地址的比特位来进行，每个节点左右分支由目的地址所对应比特位的值来决定，如果比特位为0，则选择左分支，否则选右分支。IPv6算法有：基于B-树的IPv6路由查找算法、TSB算法、基于trie的IPv6路由查找算法、基于哈希表和trie树的快速内容路由查找算法[1]基于B-树的IPv6路由查找算法，用IP地址作为插入和查找的关键字，将表项有序的存储在B-树结构中，同时利用B-树基于外存查找。基于Hash和trie树的路由查找算法是将原来的Hash表按照顶级域名划分3成各个小表，再利用trie树进行查找。各算法性能分析与比较如表2.1所示(其中W为地址长度，N为路由表前缀数目)：算法时间复杂度存储容量二进制trie树O(W)O(N*W)路径压缩PatriciaO(W)O(N)N阶B-算法树O(log2N)O(N*W)TSBO(log2W)O(N*log2W)+216HashO(log2N)O(N)表2.1IPv6各算法性能分析比较在实际开发中，路由查找算法需要满足以下要求。1.)查找速度快2.)存储空间少3.)更新时间短4.)可扩展性5.)实现的灵活性6.)预处理时间短本章主要对路由技术现状的进行介绍和分析，其中重点讲了IPv6路由发展,研究，存在的问题及评价标准，特别是IPv6的路由研究。这一章介绍的路由技术为作者的研究提供了素材和启迪，对HT6算法的设计以及改进提供了技术支援。4第三章HT6路由查找算法的实现3.1算法设计我们希望一个好的路由查找算法能够达到:1.算法实现简单，耗费内存较小2.理想情况下，最好只用一次访存就能达