摘 要：随着IPv4地址即将面临枯竭以及IPv6技术的发展，传统的路由查找算法已不能满足基于IPv6的128位地址的快速查找，一方面在算法的移植过程中，算法的适用性受到了很大的约束，另一方面，基于IPv4的32为前缀算法的查找性能已经远远达不到要求。本文就目前存在的经典的软件路由算法进行算法实现分析。最后，在对比中提出了基于IPv6新的路由查找算法研究设计的基本要求。
关键词：IPv6；路由查找；算法；trie树
引言：IP(Internet Protocol) 协议是TCP/IP协议族中两个最重要的协议之一[1]。虽然各个方面在研究一些补救办法，但是传统的IPv4已经不能完全的满足需求[1][2]，IPv6正是在人们对IPv4协议的地址空间、性能以及安全性等方面提出更高要求的情况下应运而生的[3]。IPv6是由IETF设计的，用来替代IPv4的下一代互联网协议。它和IPv4相比，最大的特点是它使用了128位超长IP地址 。2003年IPv6网络已开始进入规模化实施阶段，IPv6将逐步取代IPv4，最终完全过度到IPv6。目前，许多国家和地区都在大力发展IPv6网络，如我国的CERNET2是世界上规模最大的纯IPv6网络。然而现有的大多数路由查找算法只能适应IPv4环境下的32位前缀，而应用至IPv6中，由于内存访问次数或消耗的增加，导致算法性能非常低。因此，128位的IPv6地址给路由查找带来了新的挑战，而随着IPv6网络规模的日趋扩大，寻找高性能的IPv6路由查找算法也势在必行[3]。
1. 基于IPv4的软件路由查找算法
IPv4查找算法主要有基于二分支的算法、基于多分支的算法，网络前缀上的二分搜索算法、多路前缀值范围搜索树算法等[1]。基于二分支的算法有二进制trie树、Redix、Patricia[2]等。其思想是根据前缀值构建二叉树，检索时以目标地址作为索引，遍历二叉树。
1.1 二进制trie树
IP路由要求查找最长匹配的前缀地址，即网络地址。基于树形结构的路由查找算法将最长前缀匹配查找模型化为l棵二进制树的过程,即二进制trie树——用结点间的路径表示前缀，一般规定从某节点出发到左孩子结点的路径表示前缀中的对应比特为0。到右孩子结点的路径代表前缀中的对应比特为1。IPv4中地址长度为32，由于CIDR技术的引入，所以二进制trie树的最大深度为32。其一次更新操作只需要首先查询定位并修改一个结点，开销较小。最大不足在于：对于IPv4地址查找最多需要32次访存，而IPv6地址为128次。
1.2 路径压缩Patricia
在二进制trie树中可能出现大量的单分支节点。这种单分支结点造成查找过程中浪费大量的空间(空指针)和不必要的访存，从而影响了算法的效率。由于单分支结构代表查找只能按照一条路进行，因此可以对其进行压缩Patricia [2]，压缩单子节点。其查找过程与二进制trie树类似，但是在节点选取比特时使用的是比特位变量所指示的比特位。Patricia的最大深度有所降低，因此在最坏情况下的查找性能要优于二进制trie树。
2. 基于IPv6的软件路由查找算法
在传统的路由查找算法中，有的不能够应用到IPv6中，有的应用到IPv6之后，由于内存访问次数或内存消耗的增加，导致算法性能非常低。而由于Internet的发展和IP移动的要求，传统的IPv4网络已面临地址耗尽的危险，新一代的网络协议IPv6的采用将成为必然的趋势，因此，现在又更多的路由查找算法专门针对IPv6提出。这些算法有：基于B-树的IPv6路由查找算法、TSB算法[3]、基于trie的IPv6路由查找算法、基于哈希表和trie树的快速内容路由查找算法[4]。
2.1 基于B-树的IPv6路由查找算法
B-树路由查找算法，用IP地址作为插入和查找的关键字，将表项有序的存储在B-树结构中，同时利用B-树基于外存查找效率高这一优点，在路由表规模庞大的情况下，可以有效地降低访存次数，提高查找效率。由于IPv6地址由128位构成。无法用一个整型数表示．因此要将地址进行分段表示，对于字长为32位的机器。可以分为四段，表示形式为：
当路由器收到来自一个网络接口的数据包，提取目的IP，在B-树中查找相应的路由表项，按如下方法进行关键字比对：对于B-树结点中比较的关键字网络位部分。若相同，则该结点中记录的路由项是此IP的一个路由选择，按照该路由项中指示的下一跳进行路由。
2.2 TSB(Tree，Segment Table，and Route Bucket)算法
TSB[3]是一种多阶段IPv6路由表查找算法。它对真实路由表中的路由前缀进行分析，灵活地构建数据结构，从而获取更少的内存访问次数，降低存储空间。
根据IPv6特点，对于Ox2001开头的前缀．采用一个段表来查找接下来的16比特，最后阶段则由一个路由桶存放比32比特更长的前缀，而非0x2001开头的前缀，直接用路由桶实现。
2.3 基于哈希表和Trie树的快速内容路由查找算法
基于Hash和trie树的路由查找算法方案[4]在研究经典的Hash名字路由查找算法的基础上，由于基于域名的查找比基于IP查找发生冲突的可能性要大，并且trie树中查找一个关键字的时间和结点数无关，而取决于组成关键字的字符数，如果要查找的关键字的字符序列不是长，则利用trie树查找的时间效率很高，由于顶级域的长度很小，这就可以避免trie搜索深度很大的缺陷。基于Hash和trie树的路由查找算法，是将原来的Hash表按照顶级域名划分成各个小表，相当于用trie树建立了一个一级索引，这样既利用了trie树的结构优势，又利用了Hash表在查找时间效率上的优势，减少了冲突，节约了路由查找的时间，提高了整体性能。
3. 各算法性能分析与比较
在上述提及到的算法进行算法性能分析比较。对于二进制trie树，查找时间复杂度为O(W)，存储容量为O(N*W)。对于路径压缩Patricia，查找时间复杂度为O(W)，存储容量为O(N)，对于N阶B算法-树，查找时间复杂度为O(log2N)，存储容量为O(N*W)，对于TSB算法查找时间复杂度为O(log2W)，存储容量为O(N*log2W)+216，对于Hash算法, 存储容量为O(log2N), 存储容量为O(N)(其中w为地址长度，N为路由表前缀数目，k为查找路数，N为路由表项的总个数，S为查找的步宽)。
通过以上几个小节对路由查找算法的介绍，以及如上性能比较，可以总结出:1.已有的路由查找算法大部分已经不能满
足IPv6路由快速转发的要求。一些算法一次分别比较一个或多个比特，对于地址长度的扩展性较差，在32位地址长度的IPv4地址环境下有较好的性能，但是，对于128位地址长度的IPv6地址来说，它们需要4倍于IPv4的存取次数，几乎不能满足核心路由器快速转发的要求。2.基于IPv6的软件路由查找算法在时间复杂度上有了很大的进步,但是为了提高算法的查找性能，采用的优化技术越来越复杂，这不仅导致算法的更新相当困难，也增加了算法的实现复杂性。
4. 结束语
IPv6是互联网发展的趋势，而寻找研究高性能的IPv6路由查找算法也势在必行。要适应128位地址的IPv6路由器转发需求，仅凭现有的路由查找算法还远远不够，我们必须进一步研究新的高速路由查找算法。在新算法的设计中，要考虑对IPv6的适用性和算法的查找性能，充分考虑已有算法的优缺点，扬长避短，只有这样，才能提出满足通信需要、高性能的新算法。
参考文献：
[1]张宏丽，昝利国．IPv6路由查找算法探究［J］．内蒙古电大学刊，2010（2）：60-61．
[2]赵国锋．基于前缀值的IPv6路由查找算法研究［D］．北京：北京邮电大学，2008：15-23．
[3]陈祥云．IPv6路由查找算法研究［J］． 山东通信技术，2009（3）：14-17．
[4]华泽．一种新的快速IPv6路由查找算法［J］．现代计算机(专业版)，2009（5）：54-57．
