基于hash和trie树的ipv6高速查找和快速增量更新路由算法设计与实现

《基于hash和trie树的ipv6高速查找和快速增量更新路由算法设计与实现》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、昆明学院2012届毕业设计（论文）设计（论文）题目基于Hash和Trie树的IPv6高速查找和快速增量更新路由算法设计与实现子课题题目姓名刘晓青学号20081101420所属系信息技术学院专业年级08级计算机科学与技术指导教师何英2012年5月摘要由于Internet的速度不断提高、网络流量不断增加和网络规模不断扩大，使得路由器成为制约Internet性能的主要瓶颈之一。随着路由器技术的发展，路由查找速度依然是进一步提高路由器性能的关键要素。本论文首先研究了各种经典的IPv6路由查找算法，并分析了各种路由查找算法的复杂度和存在的问题，对I

2、Pv4向IPv6过度的路由查找算法的存在的问题以及路由查找算法的性能参数和复杂度，给出了一种基于hash和trie树高速查找和快速增量更新路由查找算法；其次，对路由缓存优化策略进行改进，并就路由节点进行生物智能化处理，使得路由负载平衡得到改善；最后，通过仿真实验，得出该算法优于以往算法。关键字：路由查找；最长前缀匹配；Hash表；Trie树；生物智能AbstractWiththedevelopmentoftheinternet,theincreasingofthroughputandtheexpandingofnetwork,making

3、therouterbecomestheoneofthemainbottleneckrestrictingtheinternetperformance.Withthedevelopmentofroutingtechnology,thespeedoftheroutinglookupisstillakeyelementtofurtherimprovementofrouterperformance.ThispaperstudiedvariousclassicIPv6routinglookupalgorithmsfirstly,thenanalys

4、isthecomplexityofthevariousroutinglookupalgorithmsandsomeexistingproblems,findtheexitingproblemsinroutinglookupalgorithmsfromIPv4toIPv6andtheperformanceparametersandcomplexityofroutinglookupalgorithms,iservedahighspeedlookupandfastincrementalupdateroutinglookupalgorithmsb

5、asedonhashandtrietree;Secondly,ihavebeendoneforroutecacheoptimizationstrategiesimprovementandconductedroutenodalbiologicalintelligent,maketheroutingloadbalancingimproving;Finally,viathesimulationexperiment,iknowthatthisalgorithmisbetterthanbefore.Keywords:Routelookup；Long

6、estprefixmatch；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研究展望2

7、6参考文献27致谢28第一章绪论1.1研究背景及现状互联网在人类生活中扮演着重要的角色。随着互联网规模不断增长，用于主干网络互联的核心路由器的接口速率需求已经大大提高，这就要求核心路由器在单位时间内能够转发更多的分组，分组转发的重要一步就是查找路由表。目前的互联网是基于IPv4协议，随着互联网的网络规模不断扩大，IPv4协议在许多方面己经不能满足人们的需要。IPv6是由IETF设计的，用来替代IPv4的下一代互联网协议。和IPv4相比，IPv6最大的特点是它使用了128位超长IP地址，这就使得IPv4中许多性能优异的路由查找算法不能够应用

8、到IPv6中，或者是应用到IPv6之后，由于内存访问次数或内存消耗的增加，导致算法性能非常低。1.2本文研究内容、意义、价值本文主要研究了IPv6路由查找算法，提出了一种适用于IPv6路由高速