经典包分类算法总结.doc

经典包分类算法总结
1 RFC算法
RFC算法介绍
RFC(Recursive Flow Classification)算法[1]是一种多维IP分类快速查找算法,通过对实际的过滤规则数据库的考察,发现数据库中的过滤规则都有内在的结构和冗余度,这个特点可以为分类算法所利用。
RFC算法的主要思想是将IP分类问题看成一个将包头中的S比特数据到T比特的classID的一个映射(T=logN且N<<S,N是过滤规则的总数)。如果预先计算出包头中的这S位共种不同情况中每种情况所对应的classID值。那么每一个包只需要一次查表,即一次内存访问就可以得到相应的classID,但是这样会消耗极大的空间。RFC的思想是映射不是通过一步来完成,而是通过多个阶段(phase)完成,。每个阶段的结果是将一个较大的集合映射成一个较小的集合,称其为一次缩减(reduction)。RFC算法共分P个阶段,每个阶段由一些列的并行的查找组成。每个查找的结果值比用于查找的索引值要短(故称为一次缩减)。
图1 RFC的基本构思
图2 一个四阶段的RFC缩减树
,对IP包查找过程如下:
在第一阶段(Phase 0),包头中的K个域被分成若干个块(chunks),每个块被用来作为并行查找的索引;
在后面的几个阶段,每次查找内存的索引值都是由前几个阶段的查找结果合并而成的。一种简单的合并办法就是将查找结果按二进制串连接起来(concatenation),但还有更好的方法可以节省空间;
在最后一个阶段,查找的结果得到一个值。由于我们进行了预先的计算,这个值就是该包对应的classID。
RFC算法性能分析
RFC算法受到两个参数的影响:
选取的阶段的数目P
在给定P的情况下,"缩减"。
在给定P的情况下,给出一种严格的判定方法来选择最优的缩减树很困难。[1]中给出了两种启发性原则:
尽可能合并具有一定“相关性”的块。如我们尽可能早的将同一个IP地址的两个块进行合并。因为具有“相关性”的两个块往往在同一条规则或者在少数几个规则中集中出现。尽早对其进行合并,可以避免后续合并产生不必要的扩展;
2)。
在P和缩减树固定的情况下,随着过滤规则树N的增加,消耗的内存量也增加。同时,对于同样的过滤规则数据库,P=3比P=4消耗更多的内存,但是查找速度前者比后者要快。
RFC算法的优点:(1)易于并行处理,处于同一阶段的预处理表和交叉乘积表可被并行地索引,处于不同阶段的表也可被并行的索引,这些表各自独立,处于不同的存储单元。(2)与其他算法相比,更适用于实际的网络中。
RFC算法的缺点:缺乏一般性,因为它与分类器的结构有关,因此需要针对不同的分类器来进行微调(tuning)才能达到理想中的最佳工作状态。一般的解决方法是在算法设计时便留有许多的参数供日后设定,像在RFC算法中所需要的阶段数,每一阶段中所做的化简比例等都是可以在执行时期设定的。
2 Set-prunning trie
Hierarchical Tries
分层查找树算法就是将分类字段的每一个维分成一层构造一个分层查找树,实际上就是对一维查找树的简单扩展,使用递归方式来生成分层查找树。基本思想是:设一个分类器C={Rj}有k个域,如果k>1,开始构建第一维的查找树,将其称之为F1-trie,它所对应的是分类器中每一条规则第一个域的前缀集{Rjl}。F1-trie中的每个结点表示一个前缀front,然后在front处进行递归构建一个(k—1)维的分层查找树Tp。前缀节点front使用“下一级查找树的指针next"指向下一级分层树Tp。。
假设D是树中一个结点,如果D’是D的前缀,一般称D’是D的祖先。如果D
’是D的最长前缀,则称D’是D的最小祖先。
分类过程:进入分类算法的IP报文D(Dl,D2,⋯,Dd),分层查找树算法首先根据Dl在F1-trie树上进行遍历,从而找到Dl的一条最佳匹配前缀,记下最后一个匹配结点为Z,然后沿着“下一级查找树的指针next”继续遍历(Z—1)维的分层查找树,记录下这条路径上所有匹配的规则。接着要回溯到Z的最小祖先Z’,所谓的最小祖先就是指设Z是树中一个结点,如果Z’是Z的最长前缀,则称Z’是Z的最小祖先。继续沿着Z’的“下一个查找树的指针next”进行遍历,直到Z节点的所有祖先都被遍历一次为止。最后,选择匹配规则中优先级最高的规则为进入分类报文的最佳匹配规则。如图给出了二元组D(00l,110)的分层查找树,其中