决策树报文分类算法

吕高锋，谭 靖，乔冠杰，严锦立

(国防科技大学 计算机学院， 湖南 长沙 410073)

报文分类是各种网络服务所需的基本技术之一，如安全防护、策略路由和服务质量(quality of service，QOS)等。因此，报文分类在云服务提供商、互联网服务提供商(internet service provider，ISP)和互联网交换中心(internet exchange point，IXP)的核心网络设备中广泛部署[1]。报文分类的目的是根据网络报文头部的多个字段值来区分报文类型，从而对报文执行相应的差异化操作。

报文分类解决方案可分为两大类：硬件方案和软件方案[2]。其中基于三态内容可寻址存储器(ternary content addressable memory，TCAM)的硬件方案[3-6]在行业中占据主导地位，其利用TCAM将所有规则存储在相联存储器中，然后将报文与这些规则并行匹配，优点是提供了常量的分类时间、实现了线速查找，但存在高成本、高功耗、可扩展性较差等缺点[7]。软件方案主要有决策树算法、元组空间搜索算法[8-10]等，其中决策树算法由于具有吞吐量高、适用于多字段和可流水线化[11]等特点，被认为是最有希望替代TCAM方案的方案之一。

由于报文分类具有重要的研究和实用价值，近十年一直是人们的研究热点。并且网络带宽的持续增长和网络应用复杂性的不断增加[12]，给报文分类带来了高维度和动态性等新挑战，研究人员仍在寻求新的、更高效的报文分类解决方案。近年来决策树报文分类算法研究取得了重要进展，新的算法层出不穷，并且出现了跨领域的趋势，例如与机器学习结合取得了初步成果，但是相关研究的综述性文章[13-15]并未涉及决策树算法新的研究进展，对近年来优秀的研究成果也缺乏系统的分析与总结。

为进一步推动基于决策树的报文分类算法的研究与发展，本文从节点切割技术、规则集分组技术两个维度对决策树算法进行了系统的分析和总结，并对比了各类算法的设计思路和特点。

1 决策树算法分析

1.1 报文分类问题

报文分类器含有一个规则列表，其中每条规则由优先级、匹配域(match field)和匹配报文时采取的动作(action)组成。报文分类问题是从规则列表中找到报文所匹配的规则，并返回其中优先级最高的匹配规则。

对报文分类问题的正式定义[16]如下：

规则列表中含有n条规则，每条规则由d个匹配域(维度)和动作域组成，其中每个匹配域f[i](1 ≤i≤d)都是关于报文头部的第ith字段的表达式。表达式的形式可以为精确匹配、前缀匹配或范围匹配形式。如标准IPv4五元组中的源和目的IP地址属于前缀匹配，源和目的端口号属于范围匹配，协议类型则属于精确匹配。

如果∀i(1 ≤i≤d)，报文P的第ith报头字段值都能满足规则Rt(1 ≤t≤n)的第i个匹配域f[i]，则认为报文P与特定规则Rt匹配。如果报文P同时匹配了多条规则，则返回优先级最高的匹配规则。

表1给出了含有6条规则的二维分类器示例。其中每个维度的位宽为4，“*”表示通配符，优先级数值越小的规则对应的优先级越高。

表1 二维分类器示例

1.2 算法基本思想

报文分类问题可等价为计算几何中的多维空间点定位问题，即报文头部中的字段(如源和目的IP地址、源和目的端口号以及协议类型)表示几何空间中的维度，报文被表示为该空间中的点，而规则被表示为空间中的超立方体。然后，报文分类问题等价于找到包含点(报文)的优先级最高的超立方体(规则)：如果报文P与特定规则R匹配，则表示报文P的点将落入规则R指定的超立方体中。

经过数学推导[17]，在具有n个互不重叠的超立方体的d维几何空间中，当d>3时，多维空间点定位问题理论上具有O(log2n)时间复杂度和O(nd)空间复杂度，或者具有O(log2n)d-1时间和O(n)空间复杂度。而对于五元组或更高维度的报文分类，这两个选择都不具吸引力。因此，需要采取有效的数据结构来组织规则集，决策树算法便是理想的选择之一。

在基于决策树算法的方案中，对报文分类问题采取几何视图，并构建决策树。树的根节点覆盖了包含所有规则的整个搜索空间，然后递归地将搜索空间切割为更小的子空间，直到每个子空间包含的规则数不大于预定义的阈值时停止切割，并将当前子空间对应的节点设为叶节点。如果规则了跨越多个子空间，则在切割时会发生不必要的规则复制。当有报文到达时，基于报文头部字段中的关键字值遍历决策树，以在叶节点处找到匹配规则。表1中的二维规则集对应的几何视图如图1所示。

图1 表1中规则集的几何视图Fig.1 Geometric view of rules in Tab.1

1.3 算法类型

现有报文分类问题解决方案主要分为硬件方案和软件方案，基本框架如图2所示。

其中硬件方案主要有TCAM和位向量[18-19]，决策树算法属于软件解决方案。构建决策树有两类常用技术：节点切割和规则集分组。

1.3.1 节点切割

节点切割基本思想是将整个多维规则集视为树的根节点，然后沿一个或多个特定的维度切割节点构建决策树。算法从包含所有规则的根节点开始，迭代地切割节点，直到每个叶节点包含的规则数不大于预定义的阈值时停止切割，从而构建单棵决策树。各类决策树算法在节点切割方面的主要区别为：

图2 报文分类解决方案的基本框架Fig.2 Basic framework for the solution of packet classification problems

1)切割维度的选择。选择哪个维度切割最优；一次选择单个维度还是多个维度进行切割。

2)切割端点的选择。包括对节点进行等分切割或者等密切割。等分切割能快速将节点等分为2n个子节点，但会带来严重的规则复制问题，即同一条规则分布在多个子节点中；而等密切割能够缓解规则复制问题，但也存在树深度增加、节点索引复杂等问题。

此外，新提出的比特切割技术使用比特级视图(bit-level view)，利用规则每一位都可表示为0、1或者*(通配符)的特点，选择其中有效比特将规则映射到各个子节点中，从而避免了盲目地切割整个搜索空间。从另一个角度看，等分切割也是一种特殊的比特切割，但只允许使用连续的最高有效位。

1.3.2 规则集分组

事实上，规则集中部分规则之间存在明显的差异。对访问控制列表(access control list, ACL)、防火墙(firewall, FW)和IP链(IP chain, IPC)类型规则集进行统计分析，结果如图3所示。从图中可得，IP地址字段前缀长度为边缘分布，即大部分位于0附近或32附近。

(a) 源IP地址前缀分布(a) Distribution of source IP address

(b) 目的IP地址前缀分布(b) Distribution of destination IP address图3 地址前缀分布Fig.3 Distribution of address

因此不加任何区分直接切割整个搜索空间将导致严重的规则复制，其中一个解决方案便是分治思想，即将具有相似特征的规则放到一个规则子集中，然后应用节点切割技术为每个子集单独构建决策树，最后形成多棵决策树。规则集分组的主要方法有：

1)按字段大小分组。根据规则在每个字段覆盖的范围来划分规则子集，该类方法应用最广泛。

2)按前缀长度分组。根据规则在特定字段的前缀长度来划分规则集。

3)基于聚类算法分组。使用聚类算法来划分规则子集。

4)基于深度神经网络模型分组。将机器学习技术应用到报文分类问题中，如使用深度神经网络模型来学习优化节点切割和规则集分组，以获得最大的奖励函数(分类速度、内存消耗等)，从而构建性能优异的决策树。

按字段大小、前缀长度分组等启发式策略建立在对规则集分布特征观察的基础之上，原理相对简单、容易实现，但对于不同的规则集，往往需要手动调整部分参数以获得理想结果；聚类算法、神经网络模型则可以使用机器学习来替代人工调整，实现对规则子集的自适应划分，但需要经过大量的训练和迭代才能收敛。

1.4 面临的挑战

设计高效的决策树算法面临的最大挑战是规则复制问题和数据结构更新问题。

决策树算法牺牲了线性空间来获得较高的分类速度，是典型的以空间换时间。规则复制问题是困扰决策树类型解决方案的主要问题之一，早期的决策树算法在规则集规模较大的时候产生大量规则复制，甚至耗尽系统内存。规则集分组技术的主要目的就是解决规则复制问题。

决策树算法存在的另一大挑战是规则更新速度较慢。在软件定义网络中，虚拟交换机得到大规模部署，目前主流的虚拟交换机如Open vSwitch，要求算法的数据结构规则更新时间复杂度为常量级别，即时间复杂度为O(1),因此采用了优先级元组空间搜索(priority sorted tuple space search, PSTSS)算法。而决策树算法由于存在规则复制问题，导致数据结构更新困难，甚至在更新时需要重新构造决策树。更新速度较慢已经成为限制决策树算法应用的关键因素之一。

决策树算法目前的研究热点是在保证算法性能的基础上，解决规则复制问题和更新速度问题，在算法吞吐量、内存消耗和更新速度等重要指标之间取得更好的折中。

1.5 测试基准

报文分类算法的测试基准为ClassBench[20]和ClassBench-ng[21]。

ClassBench是2007年由Taylor等提出，用于对报文分类算法进行基准测试的开源工具。ClassBench能够接收规则集参数配置文件，生成精确模拟实际规则集分布特征的规则集。ClassBench中共提供了12个参数文件，支持生成ACL、FW和 IPC三种类型、不同规模的IPv4 五元组规则集。此外，ClassBench还能够针对规则集生成特定长度的报文头部序列，以对算法性能进行测试。

IPv6协议和软件定义网络(software defined network, SDN)技术的发展给报文分类问题带来了新的挑战，而ClassBench仅支持生成IPv4环境下的规则集。针对这一问题，Matoušek等于2017年提出了新的开源基准测试工具ClassBench-ng，能够生成IPv4、IPv6规则集和OpenFlow[22]1.0流表。此外，ClassBench-ng还提供了一种从实际规则集提取参数文件的机制，并可上传至ClassBench-ng工具库，以生成不同应用环境下的规则集，适应不同研究人员的需求。

2 基于节点切割的单棵决策树

节点切割技术采用几何视图，将包含所有规则的整个搜索空间视作根节点，利用启发式等策略选择合适的切割维度和端点切割当前节点，获得子空间，然后递归地将搜索子空间分解为更小的空间，直到满足特定条件停止递归，最终构建基本的单棵决策树。节点切割方案主要有等分切割、等密切割和比特切割。

2.1 等分切割

HiCuts算法[23]是由Gupta等提出的最早用于报文分类的决策树算法，一次选择单个切割维度来等分规则空间，目的是将规则尽可能均匀地分离到树的叶节点中。HiCuts从覆盖整个规则空间的根节点开始，在单个维度上切割搜索空间，以创建一组大小相等的子空间。HiCuts算法中应用了多种启发式策略来选择最优的切割维度和切割次数。

HiCuts算法存在两个主要缺陷：首先， HiCuts算法仅考虑在一个节点处切割一个维度，这将增加树的深度，从而增加了树遍历所需的时间。其次，算法在构建决策树后存在大量的规则冗余，消耗了大量内存。针对上述缺陷， Singh等提出了HyperCuts算法[24]，改进了树的深度和内存消耗问题。HyperCuts算法提出同时切割多个维度，而不是在一个节点处只切割单个维度，从而减少了树的深度。其次，HyperCuts提出了公共规则向上推送的优化方法，允许将所有同级子节点通用的规则向上移动到父节点处，以缓解规则复制问题。

HyperCuts算法虽然在一定程度上缓解了树的深度较大和规则复制问题，但仍存在相当大的规则冗余，尤其是对于大规模的规则集。其问题在于等分切割本身的局限性，即等分切割适用于规则分布均匀的场合，而实际上规则集的分布并不是均匀的。

2.2 等密切割

针对HiCuts和HyperCuts算法等分切割搜索空间导致大量规则冗余的问题，Qi等提出了HyperSplit算法[25]。HyperSplit的思想是构建一个平衡的二叉树，以便规则均匀地分布在其子节点中，并沿着规则边界进行切割，从而防止过多的规则复制。HyperSplit算法在每个内部节点处采用启发式策略选择一个最佳的切割维度和切割端点，将搜索空间拆分成两个大小不等的子空间，其中包含的规则数近似相等。选择切割端点的策略包括规则平衡、范围平衡和加权分段平衡。

HyperSplit算法提出了等密切割的思路，进一步缓解了规则复制问题，但由于算法构建的决策树为二叉树，且每次只能判断一次维度，因此随着规则集规模的扩大和维度的增加，树的深度也会增加，相应的遍历决策树所需的访存次数也将增加。

2.3 比特切割

Liu等提出的BitCuts算法[26]是对节点切割技术一次新的尝试。不同于等分切割和等密切割算法，BitCuts算法充分利用了规则的二进制特点，即对于精确值和前缀表达式的字段，其每一位取值均为0、1或*，而范围表达式可转换为前缀表达式，然后通过贪心策略迭代地选择其中的有效比特，将规则分离到叶节点中。

BitCuts算法利用了规则的二进制特点，迭代地选择有效比特来构建决策树，在内存访问次数上相比HiCuts、HyperCuts和HyperSplit算法有了大幅度减少，因此吞吐量更高。但比特选择策略的效率很大程度上决定着算法性能。典型的比特选择策略有暴力策略、启发式策略等。

对表1中的规则集分别使用HiCuts算法、HyperCuts算法、HyperSplit算法和BitCuts算法构建决策树，结果如图4～7所示，其中叶节点中最多可包含的规则数量为4。采用不同节点切割方案的决策算法设计思路及特点如表2所示。

图4 HiCuts算法构建的决策树Fig.4 Decision tree built by HiCuts

图5 HyperCuts算法构建的决策树Fig.5 Decision tree built by HyperCuts

图6 HyperSplit算法构建的决策树Fig.6 Decision tree built by HyperSplit

图7 BitCuts算法构建的决策树Fig.7 Decision tree built by BitCuts

表2 节点切割的决策树算法

总的来说，三类节点切割算法中，等分切割优点在于简单快速，分类速度较快，但是内存消耗较大，适用于对分类速度要求高而对内存消耗不敏感的场景。而等密切割则在内存消耗方面占有优势，但算法吞吐量有所下降，适用于对内存要求严格的场景。比特切割是一种更新颖和灵活的切割算法，在时间性能和空间性能之间实现了更好的折中，能够以合理的内存消耗提供较高的分类速度。

3 基于规则集分组的多棵决策树

研究人员在节点切割技术方面开展了深入的研究，充分挖掘了单棵决策树的性能，但仍无法有效解决规则复制问题。针对单棵树的固有缺陷，提出了规则集分组的想法。根据规则集的某些特征来划分子集，将具有相似特征的规则放在一个子集里单独构建决策树，最终形成多棵决策树。将规则集分成子集的规则集分组技术可减少每个子集中的规则重叠，从而改善单棵树中严重的规则复制问题。

规则集分组的主要方法有：按字段大小分组、按前缀长度分组、基于聚类算法分组和基于深度神经网络分组。

3.1 按字段大小分组

EffiCuts算法[27]是使用规则集分组最具代表性的算法。EffiCuts算法基于两个关键结论：①规则大小的变化：规则集中有许多规则重叠，重叠的规则在大小上差异很大。因此，具有重叠的小规则和大规则的单棵树需要精细切割来分隔小规则，但会复制大规则。②规则空间密度的变化。针对重叠规则大小变化的情况，EffiCuts算法提出了“可分离树”的思想，通过将小规则和大规则放在不同的树中减少复制，再应用HyperCuts算法为每个子集构建决策树。例如对于图2中的6条规则，可根据规则在X、Y两个域上的大小，分为4个子集{R1，R2}、{R3，R4}、{R5}和{R6}。

对于字段大小的区分，算法通过规则投影到每个字段上的覆盖区间的大小来界定，定义了一个称为大分数(largeness fraction)的分界点，一般情况下取值为0.5。对于d维规则集，EffiCuts算法最多能产生2d个子集，呈指数级别增长。EffiCuts算法虽然考虑子树过多的情况，采用子树合并方法来消除部分子树，但仍然会生成大量的子树，这将导致较多的内存访问次数，不利于算法的扩展。使用EffiCuts算法为表1中的二维规则集构建的决策树如图8所示。

图8 EffiCuts算法构建的决策树Fig.8 Decision tree built by EffiCuts

HybridCuts算法[28]和SmartSplit算法[29]针对EffiCuts算法中子类别过多的问题进行改进。在这两个算法中仅使用了源IP地址和目的IP地址两个字段而不是全部的字段来划分规则集，限制了规则子集的数量最多为4。

Li等将按字段大小分组扩展到OpenFlow等多维规则集，提出了CutSplit算法[30]。CutSplit的基本思想是基于很少的几个字段对规则集进行分组，然后预切割和后拆分结合构建决策树。CutSplit算法的框架如图9所示。

图9 CutSplit算法框架Fig.9 Framework of CutSplit

算法具体实现为：根据小的维度将整个规则集划分为若干子集，划分依据是从F维中挑选前m个包含最多的小规则数量的维度，保证这m个小维度覆盖绝大部分的规则(≥95%)，并且在算法中定义了阈值向量，使得规则“大”“小”定义更多灵活；在划分子集后，对每个子规则集运用简单、快速的固定小字段等分切割，以得到更小的子空间；对每个子空间运用HyperSplit算法，以尽量减小冗余并且达到最坏情况下的有界性能。

CutSplit算法相比EffiCuts算法，通过精心挑选少数维度划分规则子集，性能有了改善，但存在切割和拆分的边界难以确定、算法性能不稳定等缺点。

TabTree算法[31]是继CutSplit算法之后的一项新的研究成果，其规则集分组方法类似CutSplit，但对于每个子集使用了平衡位选择的方法来构建决策树，而不是预切割和后拆分的组合，从而实现了高速分类和规则快速更新。

3.2 按前缀长度分组

Daly 等提出的ByteCuts算法[32]，根据规则在IP地址字段的前缀长度来划分规则子集。算法将具有相同的核心位集合的所有规则放在同一树中，然后对单棵树使用字节切割(以半字节为单位的比特切割)构建决策树。ByteCuts算法对子树数量与子树大小之间的平衡进行了深入研究：子树数量过多会导致访存次数增加；过少会使得单棵树的体积大，从而在单棵树内部产生更多的规则复制。ByteCuts算法定义了两个阈值：切割效率(决定子树内部冲突率)和树大小，目标是最大化树中规则的数量(最小化树的数量)，同时满足一定的平衡要求。

算法具体实现为：通过两个阈值(切割效率和决策树大小)来选择字段长度对(f，Wf)；然后将为字段f上前缀长度至少为Wf的所有规则放入同一个子集中，并创建单个决策树；对剩下规则重复该过程，直到剩余规则的数量低于某个特定阈值τ(如5%)停止。

ByteCuts算法因以半个字节为单位切割搜索空间，构建决策树数据结构所需时间较短。此外，算法还具有较强的灵活性，可通过调整阈值参数在时间性能和空间性能之间取得较好的折中。

3.3 基于聚类算法分组

Fong 等提出的ParaSplit算法[33]的基本思想是使用聚类算法划分子集，然后对每个子集使用HyperSplit 算法构建决策树。ParaSplit算法首先使用范围-点转换算法，通过将每个字段的起点和终点视为单独的维度，从而将F维空间中的超矩形转化为2F维空间中的点(F维规则被表示为2F维空间中的点)。然后利用K-means聚类算法有效划分规则子集，应用模拟退火算法来寻找最优划分，并对每个子集使用HyperSplit算法构建决策树。在使用K-means聚类算法划分子集时，提出了最小距离、最大距离和距离原点距离三种启发式策略，其中最小距离策略的性能更优。

ParaSplit算法通过聚类算法实现了规则集的自适应划分，但K-means算法的性能受初始k个中心点的选择影响较大，且算法需要上万次的迭代才能获得理想结果，预处理时间较长。

3.4 基于深度神经网络分组

NeuroCuts算法[34]使用了深度神经网络模型来学习构建高效的决策树，算法框架如图10所示。神经网络模型的环境由规则集和当前决策树组成；代理使用一个神经网络模型，选择最佳的切割或规则集分组操作来增量地构建树；当前节点的可用操作(节点切割或规则集分组)在每个步骤由环境通告，代理选择其中一个操作生成决策树。随着时间推移，代理学会优化其决策，以最大化从环境中获得的奖励函数，最终构建性能优异的决策树。奖励函数可以是分类速度、消耗内存或两者的结合。NeuroCuts算法在训练过程中使用了马尔可夫决策过程，并且结合了已有的研究成果，如按字段分组等策略。

图10 NeuroCuts算法框架Fig.10 Framework of NeuroCuts

NeuroCuts算法在报文分类和机器学习结合方面开创先河，是一次有益的大胆尝试，有助于启发新一代基于机器学习的分类算法。

表3给出了采用不同规则集分组方案的决策树算法的设计思路和特点。总的来说，按字段大小分组和按前缀长度分组原理简单，容易实现，较好地利用了规则集的几何分布特征，达到了较好的性能，且更新速度也有优势。但缺点在于需要自定义阈值参数，且在面对不同的规则集时可能需要重新调整参数。按字段大小分组适用于规则集更新频繁，或者面向特定应用领域和特定规则集的场景。

表3 规则集分组的决策树算法

而基于聚类算法分组和基于深度神经网络分组则将报文分类问题与机器学习较好结合在一起，利用机器学习技术来解决经典的网络问题，实现了规则集的自适应分组，通用性较强。但预处理速度较慢，往往需要大量的计算和迭代才能收敛，从而获得理想的性能。适用于规则更新频率较低，但对算法性能要求较高的场景。

4 决策树算法研究方向

网络技术的进步以及网络应用的复杂性和多样性，给报文分类带来了新挑战，研究人员仍致力于提出更高效的决策树报文分类算法。决策树下一步的研究方向主要有以下四个方面：

一是节点切割技术创新。利用规则集分布特征，提出新颖的、更高效的节点切割技术或者规则集分组技术，例如新的比特切割技术等。目前常用的有效比特选择标准有规则可分离性[26]、子节点内规则数量最少化[35]、信息熵[36]和子节点内规则数量平衡[37]等，但以上方法存在预处理时间较长、容易陷入局部最优等缺点，因此研究更好的比特切割技术，有助于提升决策树算法的时间性能和空间性能。

二是规则集分组与节点切割技术结合使用。根据各类规则集分组技术与节点切割技术的特点，积极尝试将它们结合使用以得到性能更优的决策树，这是当前研究的热点，新的研究成果也多集中在该方向上。如按字段大小分组与等分切割结合使用能够取得较好效果[30]，而按前缀长度分组后则更适合使用比特切割来构建决策树。

三是异构的算法架构。即各类软件方案、软件方案和硬件方案的结合使用。如Partition Sort算法[38]就充分利用了元组空间搜索(tuple space search, TSS)算法和决策树算法的优点，从而兼顾了决策树算法的高吞吐量和TSS算法的快速更新。CutTSS算法[39]则创造性地将等分切割与元组空间搜索算法结合使用，因此能够同时支持高速分类和快速更新。此外，软硬件协同处理也是一个研究热点，首先设计高性能的决策树算法，再将决策树映射到FPGA等硬件平台上[40-41]，利用硬件大规模并行、流水线架构的特点来提升算法性能，以兼顾软件算法灵活性和硬件高性能的优点。

四是跨领域研究。将决策树算法与机器学习等技术结合，借助于其他领域的专业知识来解决报文分类问题。如使用深度神经网络模型学习构建高效的决策树是一个新的研究方向，对神经网络模型的研究和改进也有助于提升决策树算法的性能。

5 结论

本文主要介绍了最新的决策树研究成果，从节点切割和规则集分组技术两个方面对决策树算法进行了系统分析和总结。总的来说，构建单棵决策树的技术主要包括等分切割、等密切割和比特切割等，已经得到了较为深入的研究。规则集分组技术主要包括按字段大小分组、按前缀长度分组、基于聚类算法分组和基于深度神经网络分组等，目前仍是研究热点。一个好的规则集分组方案能够有效解决困扰决策树算法已久的规则复制问题，同时提高算法的数据结构更新速度，从而提升算法的应用价值。

随着网络带宽的持续增长和网络应用复杂性的不断增加，决策树报文分类算法的发展趋势是更高的吞吐量、更小的内存消耗和更快的更新速度，并支持高维度扩展，尤其是在数据中心等规则集频繁更新的应用环境中，算法的更新性能显得越来越重要。