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

昆明学院2012届毕业设计（论文）

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

子课题题目

姓名刘晓青

学号 20081101420

所属系信息技术学院

专业年级08级计算机科学与技术

指导教师何英

2012年5月

摘要

由于Internet的速度不断提高、网络流量不断增加和网络规模不断扩大，使得路由器成为制约Internet性能的主要瓶颈之一。随着路由器技术的发展，路由查找速度依然是进一步提高路由器性能的关键要素。本论文首先研究了各种经典的IPv6路由查找算法，并分析了各种路由查找算法的复杂度和存在的问题，对IPv4向IPv6过度的路由查找算法的存在的问题以及路由查找算法的性能参数和复杂度，给出了一种基于hash和trie树高速查找和快速增量更新路由查找算法；其次，对路由缓存优化策略进行改进，并就路由节点进行生物智能化处理，使得路由负载平衡得到改善；最后，通过仿真实验，得出该算法优于以往算法。

关键字：路由查找；最长前缀匹配；Hash表；Trie树；生物智能

Abstract

With the development of the internet,the increasing of throughput and the expanding of network,making the router becomes the one of the main bottleneck restricting the internet performance.With the development of routing technology,the speed of the routing lookup is still a key element to further improvement of router performance.This paper studied various classic IPv6 routing lookup algorithms firstly, then analysis the complexity of the various routing lookup algorithms and some existing problems,find the exiting problems in routing lookup algorithms from IPv4 to IPv6 and the performance parameters and complexity of routing lookup algorithms,i served a high speed lookup and fast incremental update routing lookup algorithms based on hash and trie tree;Secondly,i have been done for route cache optimization strategies improvement and conducted route nodal biological intelligent,make the routing load balancing improving;Finally,via the simulation experiment,i know that this algorithm is better than before.

Keywords :Route lookup；Longest prefix match；Hash table；Tire；Biological intelligence；

目录

第一章绪论 (1)

1.1 研究背景及现状 (1)

1.2 本文研究内容、意义、价值 (1)

第二章相关技术概述 (2)

第三章 HT6路由查找算法的实现 (4)

3.1算法设计 (4)

3.1.1HT6算法基本思想 (4)

3.1.2数据结构设计 (5)

3.1.3 HT6查找设计 (8)

3.1.4路由更新 (11)

3.2算法改进 (13)

3.2.1缓存优化 (13)

3.2.2生物智能节点 (17)

第四章模拟仿真及实验数据分析 (23)

4.1仿真环境搭建 (23)

4.2算法仿真及分析 (24)

第五章总结与展望 (26)

5.1全文总结 (26)

5.2研究展望 (26)

参考文献 (27)

致谢 (28)

第一章绪论

1.1 研究背景及现状

互联网在人类生活中扮演着重要的角色。随着互联网规模不断增长，用于主干网络互联的核心路由器的接口速率需求已经大大提高，这就要求核心路由器在单位时间内能够转发更多的分组，分组转发的重要一步就是查找路由表。

目前的互联网是基于IPv4协议，随着互联网的网络规模不断扩大，IPv4协议在许多方面己经不能满足人们的需要。IPv6是由IETF设计的，用来替代IPv4的下一代互联网协议。和IPv4相比，IPv6最大的特点是它使用了128位超长IP 地址，这就使得IPv4中许多性能优异的路由查找算法不能够应用到IPv6中，或者是应用到IPv6之后，由于内存访问次数或内存消耗的增加，导致算法性能非常低。

1.2 本文研究内容、意义、价值

本文主要研究了IPv6路由查找算法，提出了一种适用于IPv6路由高速查找和快速增量更新实现思路，在此基础上改进了路由缓存，将生物智能应用到路由节点的负载平衡中来，并搭建了仿真实验平台对其特点和性能进行了定量研究。上述工作的意义和价值主要体现在以下方面：第一，本文在前人的基础上提出了新的路由查找算法设计思路，具有创新性。基于该思路设计的查找算法具有更低的时间复杂度和空间复杂度。第二，在此算法的基础上提出了路由缓存优化的策略和基于生物智能的路由节点负载策略对算法的性能进行了大幅度的提升，这对以后研究IPv6路由算法具有明显的借鉴价值。第三，为了更好地分析和对比各种路由查找算法的性能，我们搭建了路由仿真平台。相信第三章算法对学者以及企业级路由应用具有很高的参考价值。

第二章相关技术概述

路由器是工作在网络层(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表按照顶级域名划分

成各个小表，再利用trie树进行查找。

各算法性能分析与比较如表2.1所示(其中W为地址长度，N为路由表前缀数目)：

表2.1 IPv6各算法性能分析比较

在实际开发中，路由查找算法需要满足以下要求。

1.)查找速度快

2.)存储空间少

3.)更新时间短

4.)可扩展性

5.)实现的灵活性

6.)预处理时间短

本章主要对路由技术现状的进行介绍和分析，其中重点讲了IPv6路由发展,研究，存在的问题及评价标准，特别是IPv6的路由研究。这一章介绍的路由技术为作者的研究提供了素材和启迪，对HT6算法的设计以及改进提供了技术支援。

第三章 HT6路由查找算法的实现

3.1算法设计

我们希望一个好的路由查找算法能够达到:

1.算法实现简单，耗费内存较小

2.理想情况下，最好只用一次访存就能达到转发端口

3.如果访存次数大于一次，那么该算法应该满足访存次数很少或者在任何情况下，访存次数能够被限定在一个很小的数值范围内

4.算法更新所耗时间比较小

本文算法基于这几方面提出了HT6算法。

3.1.1HT6算法基本思想

考虑到分离链接散列表装填因子控制在0.674能够使节点平均查找得到最小的开销和多分支trie树检查的比特位数的特点，结合IPv6地址结构，对IPv6地址的48比特采用多分支Trie树进行查找，而剩余的16比特直接采用Hash 查找。在路由前缀表项中增加前缀长度，压缩算法所需的存储空间采用BitAtlas （二进制位向量）来表示连续出现的相同Next-Hop（下一跳）信息，从而使得每个新出现的Next-Hop信息只需存储一次。对于以001作为高3比特单播路由查找，在查找时我们可以忽略这三位，对于其它类型的单播路由，则只需将HT6-算法数据结构的第一层trie树的查找步宽增加到24比特即可。

针对以上分析HT6算法设计的基本思想主要体现在：对于前缀扩展技术不但要有较大幅度的压缩比，而且要易于解压缩查找和路由更新。针对以上要求，我们设计的前缀扩展技术利用节点构造查找步宽为24-8-4-4-8-16的六层多分支Trie树，将具有相同下一跳信息的连续表项组成一个数据块，采用BitAtlas记录每个数据块的起始位置(即下一跳信息发生改变的表项位置)，对于每个数据块中的下一跳信息只在表中存储一次。

3.1.2数据结构设计

数据结构在参考了TrieC[2]算法的基础上提出了HT6算法，该算法采用24-8-4-4-8-16的步宽来构建多分支Tile树，树中各节点的数据结构如下：·根节点采用HTl5／6（步宽为24）的数据结构(忽略IPv6地址的001域)，存储所有长度为[1，24]比特的IPv6地址前缀；

·第二层和第五层均采用HT4／4（步宽为8）的数据结构，分别存储长度为[25，32]比特和[41,48]比特的IPv6地址前缀。对于第三层和第四层则采用HT2／4（步宽为4）的数据结构，分别存储长度为[33，36]比特和[37，40]比特的IPv6地址前缀；

·第五层采用Hash数据结构，存储长度为[49，64]比特的IPv6地址前缀。

为实现路由表的快速增量更新，在Trie树中保存了未进行前缀扩展压缩前的原始前缀长度信息，该信息被保存在NHI(Next-Hop Index)数据结构中。NHI 长为2个字节，NHI[15：16]存储标志(flag)位：flag为“0”表示查找成功，这时NHI[14：6]存储了下一跳信息Next-Hop ID，NHl[5：0]保存了MCPE压缩前的前缀长度(最长64位)；flag为“1”表示需要继续查找下一层Trie树节点，这时NHI[14：0]中存储了指向下一层Trie树节点的指针。NHI的数据结构如表2所示：

表3.1 Next-Hop Index

NHIA(Next-hop Information Array) 表示若干个NHI被连续存储在一个数组中。和BitAtlas相关的参数有两个：TotalEntropy表示BitAtlas中被置“1”的比特数，它指示了NHIA数组的大小；PositionEntropy[K]表示BitAtlas中从比特0至比特K之间被置“1”的比特数，表示NHIA数组中第几个元素是比特K 所对应的NHI，其中0

HTl5/6数据结构如图3.1所示：对于每个HTl5／6节点包含215个表项(称HTl5／6 entry)，每个表项的大小为16个字节。对于表项[63：0]：存储着一个指向

NHIA数组的指针。若BitAtlas域的TotalEntropy小于等于4，则HTl5/6_entry[63：0]存储NHIA数组，且依次为NHIl到NHl4。否则，HTl5/6_entry[63：32]存储TotalEntropy个NHI结构，HTl5/6_entry[31：0]保留。

图3.1 HTl5/6数据结构

HT4/4数据结构如图3.2所示：对于每个HT4/4节点包含24个HT4/4_entry表项，每个表项的大小为8个字节。HT4/4_entry[63：48]：存储一个长度为

24BitAtlas。对于表项[23：0]：存储一个指向NHIA数组的指针。若BitAtlas域的TotalEntropy值小于等于3，则HT4/4_entry[23：0]中存储NHIA数组，依次为NHIl到NHI3。否则，HI4/4entry[12：0]存储TotalEntropy个NHI结构，

HT4/4_entry[23：13]保留。当使用第四层HT4/4表项中NHI的flag位为1时，它表示算法必须继续查找第五层，即Hash表.

图3.2 HT4/4数据结构

HT2/4数据结构如图3.3所示：对于每个HT2/4节点包含22个HT2/4_entry表项，每个表项的大小为4个字节。HT2/4_entry[63：8]：存储一个长度为

22BitAtlas。对于表项[12：0]：存储一个指向NHIA数组的指针。若BitAtlas域的TotalEntropy值小于等于2，则HT4/4_entry[12：0]中存储NHIA数组，依次为NHIl到NHI2。否则，HI2/4entry[12：6]存储TotalEntropy个NHI结构，

HT4/4_entry[13：12]和[5:0]保留。

图3.3 HT2/4数据结构

Hash函数采用separate chaining(分离链接法)。Hash表的表项结构如下：

3.1.3 HT6查找设计

HT6算法的查找过程下图所示：

图3.4 HT6算法的查找过程

·首先取查找表作为Tindex读取HTl5/6中的对应表项，计算TotalEntropy 值；

·然后用查找位置的临界表计算查找表的PositionEntropy：

·检查HT15/6表项中NHI的flag位，flag=l表明NHI存储的是指向下一级HT4/4表的指针；

·于是以NHI<<4+DstIP为查找表读取HT4/4中的表项，计算TotalEntropy 值；

·取查找表作为二次查找项计算HT4/4表项的PositionEntropy值；

·检查HT4/4表项中的NHI的flag位，flag=1表明NHI存储的是下一级HT2/4指针；

·以NHI<<16+DstIP为查找表读取HT2/4中的表项，计算TotalEntropy值；

·重复检查HT4/4表项中的NHI的flag位，使NHI每次左移动16位，看

flag是否等于1，如果是表明NHI存储的是下一级HT4/4指针；

·使NHI<<2+DstIP为查找表读取HT4/4中的表项，计算TotalEntropy值；·检查HT4/4表项中的NHI的flag位，flag=0表明查找成功，于是NHI就是要查找的Next-hop ID。否则到Hash表中查找。

查找算法如下：

3.1.4路由更新

HT6算法的更新过程如下图所示：

图3.5 HT6算法的更新过程

首先分析表范围空间，对所有匹配项的NHI域进行更新。

如果NHI的标志位为0，NHI的前缀长度小于或者等于新插入路由表的的前缀长度并且当前表项不等新的下一跳转表项，则用新的表项NHI取代旧的NHI。

若NHI的标志位为1，则继续搜索更新下一级数据结构表。对于BitAtlas 空间的前缀更新，新的表项匹配某个表项BitAtlas域，只有NHI的前缀长度小于或者等于新插入路由表的的前缀长度并且当前表项不等新的下一跳转表项时，才需要更新BitAtlas域和NHI，且需要继续搜索更新下一级路由表项。

HT6更新算法如下：

3.2算法改进

3.2.1缓存优化

路由器总是要求路由查找算法所占用的存储容量应尽可能小，从而可以为算法的实现带来更大的灵活性。针对HT6算法的存储空间的，提出了如下路由缓存策略，如图3.6所示：

图3.6 缓存处理模型

当使用BitAtlas位向量并计算TotalEntropy和PositionEntropy值。我们将计算的TotalEntropy和PositionEntropy值存储到外Hash表中，通过NIC 算法进行处理，使路由表关联信息压缩存储后的结构发送至缓存块的可配置区，通过节点嗅探路由与缓存可配置节点进行会话，尽可能的压缩输入的路由表。

NIC算法过程如下图所示：

图3.7 NIC算法过程

首先将输入到外置Hash表项中的路由表项，通过分析收集和处理收集，分

别加载到填充路由表和压缩路由表表项中。

通过对处理过的路由表项进行内联和逃逸分析，将结果路由表项发送至缓存处理域。

最后将处理过的路由表项输出到缓存块，以供嗅探链路和路由信息进行会话。

NIC算法的实现如下：

使用SIM软件进行模拟，设置BitAtlas值为2.0,仿真结果如图3.8所示：