基于Hash和AQT的类决策树包分类算法研究

赵国锋， 陈群丽

（重庆邮电大学，重庆 400065）

0 引言

随着网络上各种业务的快速发展，原有的路由器必须不断提供丰富的多业务能力。近来，新型的网络应用包括区分服务(Differentiated Qualities of Service),虚拟专用网(Virtual Private Network), Qos等等。所有这些业务的实现都依赖于IP分类算法，也就是说IP分类算法的好坏在一定程度上决定了这些业务的性能。因此研究有效的包分类算法及其实现技术是目前网络技术领域的热门课题。

国内外学者针对不同的应用已提出了一些有代表性的软件包分类算法．一类是基于树型结构的算法(Trie-based Algorithms)[1]。该类算法构建一个等级索引树，用关键字按等级依次搜索这个索引树。对于单个域的搜索是有效的，但这种机制的存储要求会随着搜索维数的增加而迅速增加。代表算法有Grid of-tree、AQT等。第二类是基于哈希函数的算法[2-3]。该类算法是根据各域前缀的长度将规则聚合在一起形成元组，但哈希表的技术对于规则个数的可扩展性较差；第三类是并行查找算法。它将多维的匹配问题转换为单维的匹配，为每一维设置一个位向量来标记与这一维相匹配的规则，各维并行执行，最后将各维的位向量相与找到最佳匹配规则。该算法在读取各维的位向量或聚合向量时需要较多的读取次数，尤其是规则库中规则的个数比较大时，所以该算法只适合硬件执行。代表算法有Parallel Bitvectors(BV)、Aggregated Bit-vector(ABV) 等。第四类是启发式算法[4]。该类型算法充分利用规则的结构特点和冗余特点,其时间复杂度一般为O(k)，空间复杂度一般为O(nk)(k为规则的维数)。因此该算法只适用于单维或二维搜索的情况。对于多维的搜索，需要的存储空间太大。代表算法有RFC、Hierarchical Cuttings 等。

现有的经典算法都是从某一个特殊的角度提出解决方案，只能解决某一个方面的问题，且其自身也存在一定的缺陷。本文提出了一种全新的基于Hash和AQT的类决策树包分类算法，并阐述了该算法的具体实现过程。

1 算法设计

IP数据包通常包含源IP地址、目的IP地址、源端口、目的端口和协议类型(一般称为5元组)，还可能包括TCP标志位、服务类型等，在IPv6中还会使用流标签。包分类是基于这些域的多维分类算法，不失一般性，本文讨论基于5元组的包分类算法。不同的域有不同的表示方法。IP地址一般以前缀表示，端口一般用范围表示，而协议类型一般是某个精确取值。通过分析大规模规则集的特征，发现协议类型域只有通配符和有限几种精确取值，据此提出一种基于Hash和AQT的类决策树IP数据包分类算法。

该算法思想如下：首先根据协议类型域的值将规则集划分为若干个子集，这样在每个子集里需要对4维IP数据包进行分类，鉴于Hash函数和AQT算法适合二维分类的特点，将这两个子集又作了细分。利用源端口和目的端口不同的取值都很有限的这一特征，构造无冲突哈希函数。也就是把规则按照不同的源端口、目的端口划分成不同的等价类。然后每个等价类指向一个两维的AQT树。整个规则集按照决策树方式排列。基于Hash和AQT算法的类决策树IP数据包分类算法的分类过程（见图1）如下：

① 查找数据包的时候，先要提取出协议域，根据协议类型域的值查找到规则集中的某个子集；

② 然后根据源端口和目的端口两个域，查找哈希表确定对应的两维的AQT树；

③ 最后按照源IP、目的IP的值沿着AQT树的分枝不断的向底端的叶子结点靠近，直到叶子结点为空或者使LC代码用完，最后得到的最佳规则就是要找的规则；

④ 特殊情况下，对于未知协议类型的数据包采用线性查找方式进行。

2 算法实现

2.1 基于协议类型的初始决策

初始决策的构造在根据协议类型划分得到的子集中进行。因为参与初始决策构造的规则已经由5维降到了4维，并且规则的数量也大大减少，即使是比例最大的TCP规则也不足原有规则数量的一半，所以决策s树的构造过程大大加快，决策树的高度也随之降低。初始决策构造完成后，就可以将IP数据流分配到各自协议的规则子集中进行细化查找。下面是构建基于协议类型的初始决策树的代码：

2.2 基于源端口和目的端口的Hash函数寻找等价类

（1）Hash函数的建立

将源端口和目的端口做一个交叉积，由于这两个域不同的取值有限，所以完 全可以避免空间的爆炸问题，比较好的解决了多维分类Hash函数空间爆炸使空间 复杂度过大的问题。假设源端口和目的端口的不同取值个数分别为:S_p和D _p。

（2）基于源端口和目的端口的Hash函数寻找等价类查找过程

由上一个阶段已经将5维IP数据包降为4维数据，并且将数据包转移到各个协议的子判决层上。进入子判决层后，利用在源端口、目的端口各种不同的取值都很有限的基础上。构造无冲突的哈希函数。也就是把规则按照不同的源端口、目的端口划分成不同的等价类。然后每个等价类指向一个两维的AQT树。

2.3 基于源IP、目的IP的AQT树搜索规则

由上一步中，已经利用源端口、目的端口两个域输入已经构建好的无冲突 Hash函数，然后查找哈希表确定对应的两维的AQT树。再按照源IP、目的IP的值沿着AQT树的分枝不断的向底端的叶子结点靠近，直到叶子结点为空或者使LC代码用完，最后得到的最佳规则就是要找的规则。

AQT算法是将二维数据解释为平面空间的矩阵，使用四叉树作为其实现的基本数据结构，用递归空间分解技术将分类规则存储于四叉树的结点中。四树中的结点最多可以有四个孩子，四个指针分别标示为00,01, 10, 11。

3 仿真实验与算法性能分析

3.1 实验条件及结果

为检测本文算法性能，本文在普通 PC上进行了性能测试，测试环境为P4 1.7 内存384 MB。测试了由ClassBench产生的5维共1000个规则集。AQT中的可调因子α取2。表1为实验中所选取的1000个规则集中的部分实例。

表1 规则集实例

3.2 算法性能分析

本文所提出的基于Hash和AQT的类决策树IP数据包分类算法首先要经过1次查表处理基于协议类型的初始决策，而后经过K次访问内存进行查找无冲突的Hash函数，最后沿AQT的分枝不断下降到达叶子结点，最后找到相应的规则。由此可见，AQT决策树的树深是一个是个决定因素，其查找性能主要由决策树的树深决定，平均性能由决策树的平均树深决定，最差性能由决策树的最大树深决定。时间性能上来看， Hash函数时间性能为O(K)，AQT时间性能为O(N2)。因此本文算法的复杂度为O(1 +K1+N2)。其中K为访问Hash函数访问内存数，N2为规则数，搜索时间测试见图2。

从空间性能测试(见图3)来看，1位的协议类型所占空间基本可以忽略不计，而2维的目的端口和源端口是利用Hash函数来查找的，因此这部分空间O(N1)相对来说也较小，其中N1是规则数。剩下的2维源IP和目的IP是由AQT算法来实现的，这部分的空间性能为O(αW1)，W1为IP地址的长度，α为可调因子。因此本文算法的总空间性能就是O(N1+αW1)。

图2 搜索时间测试

图3 空间性能测试

更新时间性能来看，初始的协议类型的初始决策容易，更形主要是在后续的2维Hash函数更新和2维AQT决策树更新上面。2维Hash函数更新性能为O(1)，2维AQT决策树更新性能为其中N2为规则数，α为可调因子。因此，算法的更新性能为其中N2为AQT算法的IP规则数，α为可调因子。各部分算法比较见表2所示。

表2 Hash、AQT和本文算法性能比较

表2中N,K为总的规则数和查找内存次数；W为总长度；而N1,N2,W1,K1都是各部分的规则数、长度和次数；其中N＞N1，N＞N2，W＞W1和W＞W2。

4 结语

本文算法是在协议类型域有限的基础上实现初始分类决策，不仅继承了Hash算法优秀时间性能、AQT算法优秀的空间性能和更新性能，而且克服了原有的Hash算法和AQT算法不易应用于多维分类等不足，将Hash函数、AQT算法与决策树有机结合起来[5-10]。通过实验和性能分析得出，本文算法最大化的提高了时间性能、空间性能。

[1] Simone M,Giancarlo C,Riccardo B,et al. A Low-complexity Packet Classification Algorithm for Multiple Description Video Streaming over IEEE802.11E Networks Image Processing[C]//ICIP 15th IEEE International Conference. USA:ICIP, 2008:3072-3075.

[2] 江朝勇.IP数据包分类算法的研究[D]. 重庆:重庆邮电大学, 2006.

[3] 钱萌,董小明.基于统计决策树的包分类算法[J].华东理工大学学报:自然科学版,2008,34(03):432-435.

[4] Phang S Y, Lee H J, Lim H. Design and Implementation of V6GEN and V6PCF: A Compact IPv6 Packet Generator and a New Packet Classification Framework for IPv6[C]//Convergence and Hybrid Information Technology, 2008. ICCIT'08. Third International Conference on 2008.Busan:Pongseo Univ.,2008:38-43.

[5] 余磊. IP包分类算法研究[D].重庆:重庆邮电大学, 2007.

[6] 戴雪龙，王永纲，张万生.并行层压缩树包分类算法[J].中国科学技术大学学报,2006,36(03):297-300.

[7] 周晓飞,杨静宇 姜文瀚.核最近邻凸包分类算法[J].中国图象图形学报,2007,12(07):1209-1222.

[8] 甘利杰.路由器中的包分类算法研究[J].计算机科学,2006, 33(11):54-57.

[9] 关爱芳.网络处理器中包分类引擎设计[D].西安:西北工业大学,2007.

[10] 刘铎.快速包分类算法的研究[D].合肥:中国科学技术大学.2006.