快速流分类算法研究综述李振强（北京邮电大学信息网络中心，北京 100876）摘要本文对流分类算法进行了综述，包括流分类的定义，对流分类算法的要求，以及各种流分类算法的分析比较。

文章的最后指出了在流分类方面还没有得到很好解决的问题，作为进一步研究的方向。

关键词流分类；服务质量；IP背景当前的IP网络主要以先到先服务的方式提供尽力而为的服务。

随着Internet的发展和各种新业务的出现，尽力而为的服务已经不能满足人们对Internet的要求，IP网络必须提供增强的服务，比如：SLA(Service Level Agreement)服务，VPN(Virtual Private Network)服务，各种不同级别的QoS （Quality of Service）服务，分布式防火墙，IP安全网关，流量计费等。

所有这些增强服务的提供都依赖于流分类，即根据包头(packet header)中的一个或几个域（field）决定该包隶属的流(flow)。

典型的，包头中可以用来分类的域包括:源IP地址（Source IP Address）、目的IP地址（Destination IP Address）、协议类型（Protocol Type）、源端口（Source Port）和目的端口（Destination Port）等。

流分类算法描述首先定义两个名词：规则（rule）和分类器(classifier)。

用来对IP包进行分类的由包头中若干域组成的集合称之为规则，而若干规则的集合就是分类器。

构成规则的域（我们称之为组件component）的值可以是某个范围，例如目的端口大于1023。

流分类就是要确定和每个包最匹配的规则。

表1是由6条规则组成的一个分类器。

我们说这是一个5域分类器，因为每条规则由5个组件构成。

我们假定分类器中的规则是有优先级的,越靠前的规则优先级越高,即规则1的优先级最高,规则6的最低。

分类器中的每条规则有d个组件。

R[i]是规则R的第i个组件, 它是包头第i 个域的一个通用表达式。

如果对于任意i, 包头的第i域满足R[i]的表达式，那么该包就匹配规则R。

实际中，规则组件常常用地址/掩码或者操作符/数字的方式表达。

在地址/掩码方式中，如果掩码的某位是0，表示我们不关心地址中的对应位，如果掩码为1，则反之。

操作符/数字表达方式是指如下的形式：等于21，范围 55-1023。

传统路由器中查中下一跳IP地址所使用的最长匹配算法其实就是一维流分类的一个特例。

我们可以认为所有去往同一个网络（network prefix）的包都属于一个流。

包应该转发往的下一跳的IP地址就是规则的行为(action),而前缀的长度决定的规则的优先级，前缀越长优先级越高，即特定主机路由具有最高优先级。

对流分类算法的要求流分类算法具有位数宽、多维（multiple dimension）和允许范围匹配等特性，这就决定了流分类算法的复杂性。

高速路由器对快速分组转发能力的需求又要求流分类算法必须具有很高的吞吐能力（具有“线速”的流分类能力）。

这使得流分类算法的设计具有较高的难度。

一个好的流分类算法应该具有如下的特征：查找速度高：随着网络链路速度的提高，流分类必须具有较高的匹配速度。

内存消耗少：算法需要的内存少，就可以使用价格较高的但速度较快的存储技术，例如SRAM,CACHE等。

能够适用于实际中的规则较多的分类器容易实现：算法应便于采用软件和硬件的方式进行实现，要便于采用流水线结构和并行逻辑进行实现。

预处理时间短：在应用算法进行实际流分类之前，初始化数据结构需要的时间要尽量短。

能够快速更新：动态性好，预处理完成后能够容易的从分类器中删除和向分类器中添加规则。

用于流分类的域具有可扩展性：算法能够对5域（源IP地址、目的IP 地址、源端口、目的端口和协议类型）的任意组合进行分类。

规则的任意性：一个好的算法应该能够支持不同形式的规则，包括前缀，操作符(大于, 等于, 小于，范围等)，统配符等。

国内外研究现状目前流分类算法主要应用了三种数据结构：线性表，树和Hash表。

这三种方法都是在预处理时建立相应的数据结构，流分类时通过一次或多次查找建立的数据结构和一些简单的处理获得最终的分类结果。

使用线性表数据结构的算法包括：Linear Search、Ternary CAM、Crossproducting、Recursive Flow Classification等。

使用树数据结构的算法包括：Hierarchical Tries、Set-Pruning Tries、Grid of Tries、Hierarchical Intelligent Cuttings、Aggregate Bit Vector等。

使用Hash表数据结构的算法包括：Tuple Space Search等。

下面对每一种算法进行简要的分析，指出各自的优缺点。

Linear Search这种算法采用的数据结构最简单，规则以链表的方式降序存储。

分类时数据包从表头开始依次和链表中的各个规则进行比较，直到找到一条匹配的规则或者达到链尾。

尽管该算法存储效率高，简单，但是查找时间长，并且查找时间随规则数的增加而线性增加。

Ternary CAMTernary CAM算法具有最快的分类时间，只需要一个内存访问周期。

但该算法只能由硬件实现，需要的CAM存储器的容量为dNW(d:分类器的维数，N:分类器中规则的个数，W:每一维的宽度,下同)。

CAM存储器价格高，耗电量大，不能直接支持范围匹配，因而对d, N, W的扩展性均较差，只能用于较小的流分类问题。

CrossProducting[6]CrossProducting算法将多维的流分类问题建立在多个一维流分类基础上，利用多个一维流分类的结果查找CrossProducting表获得最终的流分类结果。

该方法便于实现，时间复杂度是dW，空间复杂度为Nd，对规则维数和数量的可扩展性较差。

Recursive Flow Classification[1]RFC是由Pankaj Gupta和Nick McKeown提出的一种适合多域流分类问题的算法，具有流分类速度快，直接支持范围和前缀匹配等优点。

但当d, N, W 增加时，所需存储空间太大。

如果该算法所基于的特征在所用的分类器中不具有或不明显，每一维长度的压缩量将很小，这将严重影响流分类的性能。

该算法的另一个缺点是动态性差，添加一条新规则在最坏的情况下需要重建整个数据结构，因而不适合规则频繁变化的流分类器。

Hierarchical TriesHierarchical Tries是对一维查找树的一种简单扩展，它从d维中任选一维生成第一级查找二叉树，对该二叉树中的每一个与分类器中第一维匹配的结点，按分类器中规则的第二维建立另一个二叉树，反复上述过程直到完成每一维的处理，就构成了多维分层查找树。

该方法简单、直接，也便于硬件实现，但查找时间较长，对d的扩展性差，也不直接支持范围匹配。

Set-Pruning Tries[7]Set-Pruning Tries通过对多维分层查找树中某些结点进行多次复制，减少多维分层查找树的层次，提高查找效率。

但所需存储空间增加较多，对规则维数的扩展性差。

Grid of Tries[6]Grid of Tries的主要思路是将Set-Pruning Tries中重复的子树删去，只保留一颗子树，这样存储空间的需求量由NddW降为NdW，时间复杂度仍为dW，但该方法动态性差，减少规则需要对整个树进行重建，并且只适用于d=2的情况。

Hierarchical Intelligent Cuttings[2]Hierarchical Intelligent Cuttings的基本思想是以规则的每一字段为一层次将分类器中所有规则按范围空间进行循环分组，直到每一组中都只有少于NUM 条的规则，查找时在少于NUM条规则中通过线性匹配来找到匹配规则。

在HiCuts中，整个分类器只建立一棵树：根节点表示整个d维空间，树中每个节点代表了查找空间的一部分，叶结点存储了位于这个查找空间的B条规则，B<=NUM。

HiCuts能够根据分类器本身的特征自动调节流分类算法使用的数据结构，最大限度的利用优化数据结构、减少冗余，降低算法的存储容量要求，提高流分类的速度。

该算法对存储容量要求低，直接支持范围匹配，动态性好，规则的增删容易：产出规则时，只要把该规则打上“删除”标记即可，不用修改HiCuts树；增加规则时，在相应空间的叶结点加上该规则号，如果叶结点增加后的规则数大于NUM，则对该叶结点执行空间划分过程。

在规则空间均匀分布的情况下，HiCuts有很好的性能，但由于构造HiCuts 树时是循环依次对每一维进行空间划分，如果一个d维分类器中的大部分规则只通过某一维来划分，而其他维的值相似或相同，HiCuts树的深度和结点会大大增加，预处理时间和占用的内存空间都会成倍增加，大大影响算法的性能。

Aggregate Bit Vector[8]ABV的基本思想是“分割-合并”，它将一个d维的流分类问题分割为d 个1维匹配的子问题，然后将子问题的结果进行合并得到最后的匹配规则。

ABV为每一字段建立一棵非完全二叉树，二叉树的每个节点都表示了一个范围，二叉树的最高高度不大于该域的比特位数W。

ABV利用比特向量记录符合该结点范围的规则，然后根据归并参数A对比特向量进行A位一组的逻辑或操作。

通过归并ABV算法减少了访存次数，当分类器维数较大，规则较多时，采用多层归并可以大大减少算法的访存次数，提高匹配速度。

但是归并带来的好处是受条件限制的。

当规则无序排列使得归并后的向量为全1时，并不会减少访存的次数。

所以，在ABV的预处理阶段需要对分类器中的规则按字段进行排序，但这会大大增加预处理时间。

ABV算法具有较好的动态性，对分类器中规则的增删改比较容易。

删除规则时，只需遍历二叉树把向量中对应的比特位置0；修改与删除类似；增加规则时，可以占用被删除规则的位置或加到最后比特位的后面，并且能够较好的实现规则的冲突检测，这是ABV算法一个突出特性。

Tuple Space Search[10]Tuple space search算法使用Hash表将一次匹配分解成几次严格匹配查询。

该算法将一个d维规则映射成一个d元元组，d元元组的每个组件存储规则相应域前缀的长度。

该算法的时间复杂度是M(M是分类器中d元元组的个数)，存储复杂度是O(N)，因为每一个规则只在一个Hash表中存储。

该算法支持规则的动态更新，在d元元组较少时有良好MF分类性能。

但是该算法只支持前缀匹配，并且Hash算法的使用使得匹配和更新的时间具有不确定性，在最坏情况下，M= O(Wd)。