流分类算法的分类及比较

流分类算法的分类及比较

流分类算法可以根据不同的原则进行分类，本文根据对多个区域查找之间的关系把现有的流分类算法分成3类。

1) N表示规则数目，

2) d表示维数，

3) w表示每一维的宽度。

多维查找转换为一维查找的算法

该类算法的特点就是把流分类查找的各个区域连接起来组成一个查找关键字，从而把多维查找的问题转化为一维查找问题。在基于哈希表进行查找的流分类器以及使用TCAM的流分类器中经常使用到这种方法。缺点是得到的查找关键字很大，而且由于多维合成了一维，无法利用规则中各维内部的共性进行优化设计。此类算法的代表是多元空间查找算法(Tuple-Space-Search)[1]，基本思想是把流分类查找问题分解为多个精确匹配问题。

首先把d维的规则映射到一个具有d个分量的空间中，空间的第i个分量表明规则第i维的前缀长度，这样各维前缀长度都相同的规则就对应同一个空间，把它们存储在同一个哈希表中。查找时对所有哈希表进行精确匹配查找。这种算法的空间复杂度为O(N)，时间复杂度由需要访问的哈希表数目决定，使得查找的时间复杂度不能确定。在最糟的情况下，空间数目可能达到O(wd)，使得查找时间不能接受。更新速度很快，只需要一次哈希访问的时间。实际上许多知名硬件厂商在设计自己的流分类实现方案时都采用了哈希技术。

相关区域查找算法
这种算法的特点是前一个区域的查找结果会影响到随后要查找的区域的路径，主要优点是可以使用相对简单的生成树结构，缺点是要想达到较快的查找速度就需要对树的结构进行复制或者在数据中加入链路信息，这样就会增加存储器容量，也会使更新更慢。另外大量对存储器的访问都是互相依赖的，导致了不可预测的延迟。此类算法的代表是分层查找树(Hierarchical Tries)，集合归并查找树(Set-Pruning tries)[2]，查找树网格(Grid-of-tries)和智能分层查找树(Hierarchical Intelligent Cuttings，HiCuts)[3]。分层查找树从d维中任取一维生成第一级二叉树，再从剩下的d−1维中任取一维作为第二维，对该二叉树中每一个与规则表中第一维匹配的结点，按照它的第二维建立第二级二叉树，重复上述过程，直到完成每一维的处理。分层查找树的空间复杂度为O(Ndw)，时间复杂度为O(wd)。它简单，容易实现，但是查找较慢，并且更新也不快。集合归并查找树是对分层查找树的改进，通过把前缀长度小的结点对应的子树复制到所有前缀长度大于它的结点的子树上，如果某个结点出现规则重复，则取优先级高的规则。这个过程是在所有子树上递推进行的。查找时只需要依次找到所有树上的最长匹配，就能找到相应的规则。时间复杂度为O(dw)，空间复杂度为O(Nddw)，可见是以增大存储空间来减少查找时间，扩展性也较差。查找树网格是在分层查找树的基础上，给某些结点增加一个转移指针b(0或1)，它指向另一个子树的一个结点。

存在从子树Ty的Y结点到子树Tx的x结点的转移指针的条件是：

1) Tx和Ty是同一层上的不同子树，并且指向它们的根结点的指针是同一棵树T上的两个不同的结点(r和s)的下一棵指针。

2) 从Ty的根结点到Y再串连上转移指针b的比特串等于从Tx的根结点到x的比特串。

3) Y没有等于转移指针b的子结点。

4) s是T中离r最近的满足上述条件的父结点。查找树网格避免了由于复制规则导致存储空间扩大和分层查找树的回溯问题。在处理两维流分类问题时，时间复杂度为O(w)，空间复杂度为O(Nw)，应此它是一种很好的处理两维流分类问题的算法。在处理多维问题时，它也可以用来优化分层查找树的最后两层子树。HiCuts的实现需要建立一种决策树的数据结构，每个叶结点都存储着一些规则，查找时经过决策树找到一个叶结点，再对这个叶结点中的规则进行线性查找找到匹配的规则。决策树的根节点包含了整个d维空间，具体结构可以通过参数来决定。

参数binth规定了每个叶结点包含的规则的最大数，当一个结点的规则数大于binth时，就把d维中的某一维平均划分成NP(C)份，形成NP(C)个子结点。如果结点包含的规则数小于binth，那么该结点就是一个叶结点。HiCuts的时间复杂度为O(d)，空间复杂度为O(Nd)。可以根据规则的特征调整参数来优化数据结构，降低所需的存储空间，提高查找速度，规则的更新容易实现。缺点是预处理的时间较长，适用于规则较少的情况。

独立区域查找算法
这类算法首先通过一维查找算法对每个区域单独进行查找，产生中间查找结果，再根据中间结果决定最后多维的查找结果。这样就可以利用各个区域的特点使得查找更加有效,另外存储器的访问是独立的，因此可以并发进行。它的性能很大程度上决定于中间查找结果的编码。

代表算法有crossproducting，位向量交集(Bitmap-Intersection)和重复流分类(Recursive Flow Classification，RFC)[4]。Crossproducting先找出各维上不同情况的组合(每种组合都对应于一条规则)，把它们存储在一个Crossproduct表中，查找是在每个维上单独进行的，最后根据各个维的查找结果对Crossproduct表进行查找，找到相应的规则。时间复杂度为O(dw)，空间复杂度为O(Nd)。它的缺点在于存储空间要求很大，成级数变化。另外它的更新不方便，每次增加规则都需要重新计算Crossproduct表。

位向量交集把所有规则的同一维映射到同一条数轴上，那么每条规则在该数轴上都是一个范围或一个点，给它们都定义一个中间向量，它的位宽为N，对应于N条规则，规则按照优先级排列，根据每条规则在该范围的上的匹配情况给它取值，规则匹配时，向量的对应位取1，否则取0。查找时分别先找到每一维上匹配的中间向量，再把它们进行与运算，找到向量中优先级最高的1位，对应的规则就是匹配的规则。时间复杂度为O(dw+N/memwidth)，空间复杂度为O(dN2)。这种算法试图通过增加存储器访问次数来减少所需存储空间，但是效果不明显，而且它并没有解决更新困难的问题。RFC算法在对数据包进行处理时，可以看作是将数据包头部的S比特映射到T比特的类符号的过程。

其中T＝lbN，T<<S，是由N条流分类规则决定的。时间复杂度为O(d)，空间复杂度为O(Nd)。它具有流分类速度快，能直接支持范围和前缀匹配等优点，局限性在于当规则条数、维数和每维宽度增加时，所需的存储空间太大。同时，由于不同的流分类器具有不同的特征，对于特定的流分类器若该方法所基于的特征不具备或不明显，每一维的长度的压缩量会很小，会严重影响流分类的性能。此外，RFC算法规则的更新非常困难，最糟的情况下需要重建整个数据结构。