一种改进的NAT-PT地址映射表查找算法

王相林,王慧娟

(杭州电子科技大学计算机学院,浙江杭州310018)

0 引 言

IPv4网络向IPv6网络过渡已经成为一种迫切需要,NAT-PT(网络地址转换和协议转换)[1]是一种较好的过渡机制,它通过采用网络地址转换和协议转换技术来实现IPv6网络和IPv4网络的互通。随着转换条目日渐增多,存储空间变大,使得建立和维护地址映射表所需的CPU时间变长,因此地址映射表查找算法的性能问题已成为NAT-PT的瓶颈。该文通过分析路由查找算法和IPv4网络中使用的网络地址转换(Network Adress Translation,NAT)技术,提出了一种基于哈希表和多位树的地址映射表查找算法,该算法具有较好的时间复杂度和空间复杂度,加快了地址转换的速度,可以很好的满足NAT-PT的高性能要求。

1 NAT-PT中的网络地址转换(NAT)技术

NAT-PT处于IPv4和IPv6网络的交界处,不需要对现有的节点进行改动,就能实现IPv4和IPv6节点之间的互通[1]。NAT模块的主要功能是建立和维护地址映射,IPv6网络向IPv4网络转发数据包时,IPv6首先要访问IPv4的DNS系统获得地址解析,从地址池中获取一个IPv4地址,把IPv6的源地址转换成IPv4地址,然后把该转换条目记录在地址映射表中。当IPv4网络向IPv6网络转发数据包时,查找地址映射表中的换条目进行转换[2]。

2 传统的地址映射表查找算法及其缺陷

目前,常用的地址映射表查找算法主要有以下4种:线性查找、哈希表查找、检索树查找和路径压缩树查找[3、4]。

线性表结构是最简单的查找数据结构,每一次查找需要遍历线性表中的所有表项,不利于条目的增减,而且查找时间和条目的长度成线性关系,适用于网络环境比较慢的情况。哈希表算法的扩展性不好,而且找到一个冲突尽可能小的良好性能的哈希函数并不容易。检索树是用树的路径表示表项中存放的地址,处于第L层的节点代表了比特均相同的地址空间,这L个比特串就是由从根节点到这个节点路径上的L比特组成,如图1所示。其内存访问的最坏的情形为IP地址的长度,在这种架构下需要大量的内存空间。路径压缩树压缩掉了检索树结构中的单子节点,减小了树的平均深度。最差情况下,一次查找所需要操作是Q(w2)(w为树的深度),这种查找算法如果成功,效率将很高,否则会因为回溯,效率很低,如图2所示。可见单一地应用传统算法,地址映射表的查询效率较低,影响包的转发率和延时,已经不能满足NAT-PT高性能转换的要求,设计一个合理的算法以保证网关在系统繁忙时的性能很有必要。

3 基于哈希表和多位树的地址映射表查找算法设计

3.1 算法设计思想和实现过程

如果每次关键字查询并不只是一位而是同时使用多位,能大大提高树的检索速度,例如IPv4地址,一次检查4位,8次内存访问就可以。每一步被检查的位数称作步长,有动态步长和固定步长之分,允许多位同时查找的树称作多位树。多位树一次遍历多位,不支持任意长度的前缀,需要把前缀集合扩展成等价的数据结构新集合。多位树如图3所示,步长为2-1,树的高度减少了,相应地访问内存的次数也减少了。

图1 检索树

图2 路径压缩树

图3 多位树

通过分析6Bone上前缀长度的分布情形,并结合IPv6的地址分配政策,发现前缀长度等于24位的前缀大约占了58.48%,而且IPv6全球单播地址的前3位是001,所以用路由前缀的第4—24位的值构建一个哈希表,哈希表中的表项指向一个对应的改进后的多位树的根节点,树中所有节点均具有相同的前4-24位。兼顾内存存取次数与存储空间的需求,把剩余地址构造成动态步宽的多位树,以限制最坏情况下查找的访问次数。这种改进方法将会需要更多一点的内存,但是相应的查找速度也会得到提高,这也就是在内存和速度之间寻找平衡。因为IPv4地址和IPv6的多播地址只用到最后32位,可以直接由地址组织成哈希表和步宽为8的多位树进行地址映射的查找。同时考虑到计算机的整个存储系统的各种存储介质在速度和容量上存在的差异,把实时性要求比较高的查找表内容置入Cache,将其建成静态条目,可以获得更高的查找速度,也减少了数据结构所占据的存储容量。改进后的哈希

表和多位树的数据结构如图4所示,Cache机制如图5所示。

图4 哈希表和多位树的数据结构

图5 Cache机制

Hash表和多位树的数据结构定义如下:Struct Hash{//Hash表的数据结构

u_int32_t key;//以地址前24位值构建的哈希表的关键字struct Treenode*T//树的根节点,该树具有相同的前24位比特值};

Struct Treenode{//多位树的数据结构Unsigned int stride;//查找的步长

Bool flag;//flag为标志位,值为1或0

Union{

u_int32_t ip4addr;

u_int16_t ip6addr[8];

}u;

Struct Treenode*leaf[256];//指向分支节点的指针};

查找一个IP地址时,先在cache中查找,若未命中,以前24位的地址作为key值从哈希表中查找匹配表项,找到相应的根节点,然后从多位树的根节点开始查找,查找的每一步根据stride的值查找地址中的多个比特,当该节点中flag的值为1时,表示已经找到精确匹配的地址映射条目,无需再继续查找;当flag值为0时,表示还未找到匹配项,继续查找,直到节点中指针leaf=NULL,查找结束,若存在精确匹配项,则返回当前节点中地址的映射地址。若不存在匹配项,则新建并记录一个转换条目。

对于IPv6向IPv4转发的数据包,具体实现过程如下:

(1)根据数据包中IPv6目的地址在Cache中搜索,如果命中,则得到映射地址IPv4地址,转4,否则转2;

(2)通过IPv6地址关键字在哈希表和多位树中查找,若搜索成功,则得到映射地址IPv4地址。转4,否则转3;

(3)由程序产生地址池IPv4地址,在哈希表和多位树中增加一个NAT转换条目,如果是实时应用或静态条目则更新Cache;

(4)修改数据包中的目的地址为IPv4地址,并记录新增转换条目,发送数据包,结束。

对于IPv4向IPv6转发的数据包,具体实现过程如下[5、6]:

(1)根据数据包中IPv4目的地址在Cache中查找,如果命中,则得到映射地址IPv6地址,转3,否则转2;

(2)在哈希表和多位树中查找,若找到匹配项目,则得到映射地址IPv6地址,转3,否则对数据包做非NAT处理,结束;

(3)修改包中的目的地址为IPv6地址,发送数据包,结束。整个查找算法的流程如图6所示:

图6 查找算法流程图

3.2 算法性能分析

将NAT转换条目按目的地址组织哈希表,并辅之以多位树,直接使用24位比特的关键字key做为Hash表的查找索引,只需要一次存储器访问。同时采用多位树的数据结构,每次查询时使用动态步宽的关键字,大大减少了存储器的访问次数,因而提高了查找效率。并且引入Cache机制,将实时性要求比较高的转换条目置入存储容量更小,读取速度更快的Cache,将其建成静态条目,不仅加快了搜索速度,而且减少了条目的数量,占用的存储空间也更少。

将各算法的复杂度如表1所示。其中w为关键字的比特位数,n为存储表项的数目,k为多位树的步宽。哈希索引表只需一次内存访问,查找复杂度为常量O(1),多位树的查找操作的复杂度为O(w/k),故总的查找复杂度为O(w/k)。每一个前缀有长度为w/k的路径和大小为2k的一层子树组成,故被消耗的内存的空间为O(2Knw/K)[7、8]。从表1中可以看出,当路由表项n较大时,基于树的查找复杂度远远小于线性表和哈希表,基于表的查找算法已经显示出不足。尽管本算法的空间复杂度不如路径压缩树,但因为引入cache,空间复杂度可作为次要考虑因素,且改进后的算法具有很好的查找效率,通过适当增加一定的内存加快查找速度是值得的。

表1 算法复杂度对比表

4 结束语

该文从NAT-PT的实际应用出发,提出了一种基于哈希表和多位树的地址映射表查找算法,与传统的线性查找、哈希表查找、检索树查找和路径压缩树查找算法相比,能大大加快地址转换的操作,且所需存储空间较少。特别是在有大量数据流经NAT-PT网关时,改进算法的效率明显优于传统算法,很好的满足了NAT-PT网关在系统繁忙时的高性能要求。当转换条目更多时,还可以对地址映射表的数据结构进行优化,比如采用两级哈希表或者对多位树进行层次压缩。

[1] Tsirtsis G,Srisuresh P.Network Address Translation-Protocol Translation(NAT-PT)[S].RFC 2766,2000.

[2] Srisuresh P,Egevang K.Traditional IPNetwork Address Translator(Traditional NAT)[S].RFC 3022,2001.

[3] 赵凯辉.基于NAT-PT技术的翻译网关的研究与实现[D].南京:东南大学,2005.

[4] 华伟臣.IPv6路由器快速路径查找算法[D].成都:四川大学,2006.

[5] 韩玲,段晓东.一种基于NAT/PT的IPv6与IPv4转换网关[J].计算机工程,2004,30(14):86-112.

[6] 陈行,陶军,吴强.基于混合映射机制的NAT-PT的研究与实现[J].计算机科学,2009,36(5):33-64.

[7] 姚兴苗,李乐民.一种快速IPv6路由查找方案[J].计算机学报,2005,28(2):214-216.

[8] Ruiz-Sanchez M A,Biersack E W.Survey and taxonomy of IP add ress lookup algorithms[J].IEEE Network,2001,15(2):8-20.