关于ipv6路由查找算法的发展状况研究

《关于ipv6路由查找算法的发展状况研究》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、关于IPv6路由查找算法的发展状况研究随着IPv4地址即将面临枯竭以及IPv6技术的发展，传统的路由查找算法已不能满足基于IPv6的128位地址的快速查找，一方面在算法的移植过程中，算法的适用性受到了很大的约束，另一方面，基于IPv4的32为前缀算法的查找性能已经远远达不到要求。本文就目前存在的经典的软件路由算法进行算法实现分析。最后，在对比中提出了基于IPv6新的路由查找算法研究设计的基本要求。关键词：IPv6；路由查找；算法；trie树　　引言：IP(InterProtocol)协议是TCP/IP协议族中两个最重要的协议之一[1]。虽然各个方面在研究一些补救办法，但是传统的IPv4已经不

2、能完全的满足需求[1][2]，IPv6正是在人们对IPv4协议的地址空间、性能以及安全性等方面提出更高要求的情况下应运而生的[3]。IPv6是由IETF设计的，用来替代IPv4的下一代互联X协议。它和IPv4相比，最大的特点是它使用了128位超长IP地址。2003年IPv6X络已开始进入规模化实施阶段，IPv6将逐步取代IPv4，最终完全过度到IPv6。目前，许多国家和地区都在大力发展IPv6X络，如我国的CER2是世界上规模最大的纯IPv6X络。然而现有的大多数路由查找算法只能适应IPv4环境下的32位前缀，而应用至IPv6中，由于内存访问次数或消耗的增加，导致算法性能非常低。因此，128

3、位的IPv6地址给路由查找带来了新的挑战，而随着IPv6X络规模的日趋扩大，寻找高性能的IPv6路由查找算法也势在必行[3]。1.基于IPv4的软件路由查找算法　　IPv4查找算法主要有基于二分支的算法、基于多分支的算法，X络前缀上的二分搜索算法、多路前缀值范围搜索树算法等[1]。基于二分支的算法有二进制trie树、Redix、Patricia[2]等。其思想是根据前缀值构建二叉树，检索时以目标地址作为索引，遍历二叉树。1.1二进制trie树　　IP路由要求查找最长匹配的前缀地址，即X络地址。基于树形结构的路由查找算法将最长前缀匹配查找模型化为l棵二进制树的过程,即二进制trie树——用结点

4、间的路径表示前缀，一般规定从某节点出发到左孩子结点的路径表示前缀中的对应比特为0。到右孩子结点的路径代表前缀中的对应比特为1。IPv4中地址长度为32，由于CIDR技术的引入，所以二进制trie树的最大深度为32。其一次更新操作只需要首先查询定位并修改一个结点，开销较小。最大不足在于：对于IPv4地址查找最多需要32次访存，而IPv6地址为128次。1.2路径压缩Patricia　　在二进制trie树中可能出现大量的单分支节点。这种单分支结点造成查找过程中浪费大量的空间(空指针)和不必要的访存，从而影响了算法的效率。由于单分支结构代表查找只能按照一条路进行，因此可以对其进行压缩Patrici

5、a[2]，压缩单子节点。其查找过程与二进制trie树类似，但是在节点选取比特时使用的是比特位变量所指示的比特位。Patricia的最大深度有所降低，因此在最坏情况下的查找性能要优于二进制trie树。2.基于IPv6的软件路由查找算法　　在传统的路由查找算法中，有的不能够应用到IPv6中，有的应用到IPv6之后，由于内存访问次数或内存消耗的增加，导致算法性能非常低。而由于Inter的发展和IP移动的要求，传统的IPv4X络已面临地址耗尽的危险，新一代的X络协议IPv6的采用将成为必然的趋势，因此，现在又更多的路由查找算法专门针对IPv6提出。这些算法有：基于B-树的IPv6路由查找算法、TSB

6、算法[3]、基于trie的IPv6路由查找算法、基于哈希表和trie树的快速内容路由查找算法[4]。2.1基于B-树的IPv6路由查找算法　　B-树路由查找算法，用IP地址作为插入和查找的关键字，将表项有序的存储在B-树结构中，同时利用B-树基于外存查找效率高这一优点，在路由表规模庞大的情况下，可以有效地降低访存次数，提高查找效率。由于IPv6地址由128位构成。无法用一个整型数表示．因此要将地址进行分段表示，对于字长为32位的机器。可以分为四段，表示形式为：，分别存储在四个整型数据中，同时附加掩码长度，就可以构成在B-树中插入和查找该表项所需的关键字。关键字Key共由五个字段构成，Key[

7、0]对应掩码长度，分别对应。　　当路由器收到来自一个X络接口的数据包，提取目的IP，在B-树中查找相应的路由表项，按如下方法进行关键字比对：对于B-树结点中比较的关键字X络位部分。若相同，则该结点中记录的路由项是此IP的一个路由选择，按照该路由项中指示的下一跳进行路由。2.2TSB(Tree，SegmentTable，andRouteBucket)算法　　TSB[3]是一种多阶段IPv6路由表查找算法。它对真