| 类型 | 内容 |
|---|---|
| 标题 | Neural packet classification |
| 时间 | 2019 |
| 会议 | SIGCOMM ‘19: ACM SIGCOMM 2019 Conference |
| DOI | 10.1145/3341302.3342221 |
数据包分类-数据包分类
rollout-> rollout摘要
文章提出了使用深度强化学习（RL）方法来解决数据包分类问题。 首先，许多现有解决方案通过拆分树中的节点来迭代构建决策树。 其次，只有在整个树都建立好之后，才能评估这些操作的效果。 这两个特征被具有稀疏和延迟回报的的RL所捕获。 第三，计算数据跟踪和评估决策树在计算上是有效的，从而减轻了Deep RL算法众所周知的高样本复杂性问题。 作者的解决方案NeuroCuts使用简洁的表示形式来编码状态空间和动作空间，并有效地探索候选决策树以针对全局目标进行优化。 它产生针对特定规则集和给定性能指标（例如分类时间，内存占用量或两者的组合）优化的紧凑型决策树。 对Class-Bench的评估表明，NeuroCuts在分类时间方面比现有的手工算法要好18％，并且分类时间和内存占用减少了3倍。
介绍
现有的数据包分类解决方案可以分为两大类。第一类解决方案是基于硬件的。它们利用三元组内容寻址存储器（Ternary Content-Addressable Memories ,TCAMs）将所有规则存储在关联存储器中，然后将一个数据包与所有这些规则并行匹配。因此，TCAMs提供了恒定的分类时间，但TCAMs具有内在的复杂性，这种复杂性导致了较高的成本和功耗。这使得基于TCAMs的解决方案无法实现大型分类器。
第二类解决方案是基于软件的。这些解决方案构建了复杂的内存数据结构，通常是决策树，以有效地执行数据包分类。虽然这些解决方案比基于TCAM的解决方案具有更大的可伸缩性，但它们的速度较慢。
建立有效的决策树很困难。 在过去的二十年中，研究人员针对数据包分类提出了许多基于决策树的解决方案。 尽管进行了多年的研究，但是这些解决方案有两个局限性。 首先，他们依靠手工调整的启发式方法来构建树，包括最大化拆分熵，使用自定义空间量度平衡拆分，对通配符规则进行特殊处理等，这使他们难以理解和优化不同的规则集。 如果启发式方法过于笼统，则无法利用特定规则集的特征。 如果启发式方法是为一组特定的规则设计的，则通常无法在具有不同特征的另一组规则上获得良好的结果。
其次，这些启发式算法没有显式地优化给定的目标（例如树深度）。他们根据与全局目标松散相关的信息（例如，子级中规则数量的差异，每个维度中不同范围的数量）做出决策。因此它们的性能可能不是最佳的。
将学习应用于包分类有两种通用方法。第一种是用神经网络代替决策树，给定一个数据包，输出与该数据包匹配的规则。这种端到端的解决方案有一个主要缺点：它不能保证总是匹配正确的规则。虽然这对于某些应用程序（如流量工程）是可以接受的，但对于其他应用程序（如访问控制）则是不可接受的。另一个问题是，大型规则集需要相应的大型神经网络模型，如果没有gpu这样的加速器，这些模型的评估成本会很高。第二种方法是使用深度学习来构建决策树，最近的工作将深度学习应用于决策树优化。然而，这些解决方案是为不同于数据包分类的机器学习设置而设计的，目的是最大限度地提高准确性。相比之下，用于数据包分类的决策树通过构造提供了完美的准确性，其目标是最小化分类时间和内存占用。
作者的解决方案使用深度强化学习（RL）来建立有效的决策树，设计了NeuroCuts，这是一个用于数据包分类的深层RL解决方案，它可以建立有效的决策树。
将此问题表示为RL问题有三个技术挑战。首先，在算法执行过程中，由于现有节点被分割，树正在生长。这使得对决策树进行编码变得非常困难，因为RL算法需要固定大小的输入。我们注意到如何在树中分割节点的决定只取决于节点本身，而不依赖于树的其余部分，从而解决了这个问题。因此不需要对整个树进行编码，只需要对当前节点进行编码。 第二个挑战是减少奖励的稀缺性以加速学习过程；这里利用问题的分支结构来为树的大小和深度提供更密集的反馈。最后一个挑战是，训练非常庞大的规则可能需要很长时间。为了解决这个问题，作者使用了一个分布式的RL库-RLlib。
以下贡献。
- 证明数据包分类问题非常适合强化学习（RL）
- 介绍了NeuroCuts，这是一种用于数据包分类的深层RL解决方案，可学习构建有效的决策树。
- 证明NeuroCuts的性能优于最新解决方案，中值分类时间缩短了18％，时间和内存使用量减少了多达3倍
- NeuroCuts的代码是开源的，可从https://github.com/neurocuts/neurocuts获得
背景
节点切割大多数现有的包分类解决方案旨在构建一个决策树，该决策树显示出较低的分类时间（即时间复杂度）和内存占用（即空间复杂度）。其主要思想是通过沿着一个或多个维度“切割”决策树中的节点来分割它们。从包含所有规则的根开始，这些算法迭代地分割节点，直到每个叶包含的规则数少于预定义的数目。给定一个决策树，对数据包进行分类减少，将树从根移动到叶，然后选择与该叶相关联的最高优先级规则。如图2所示
规则分区 “盲目”切割节点的一个挑战是，我们可能最终会将一条规则复制到大量节点。 如果规则沿有较大尺寸的一个维度具，则沿该维度进行切割将导致该规则被添加到许多节点。 例如，图2(a)中的规则R1在x维度上的尺寸较大。 因此，沿尺寸x切割时，R1最终将在由切割创建的每个节点处复制。 规则复制会导致决策树具有更大的深度和大小，从而转化为更高的分类时间和内存占用量。
一个解决方案是根据它们的“形状”来划分规则。广义上讲，在特定维度中具有较大大小的规则放在同一个集合中。然后，我们可以为每个分区构建单独的决策树。图3说明了这种技术。图2中的六个规则被分为两个分区。一个分区由规则R1和R4组成，因为这两个规则在维度x中的大小都很大。另一个分区由其他四个规则组成，因为这些规则在维度x中的大小都很小。
图3（a）和图3（b）显示了每个分区对应的决策树。为了对数据包进行分类，根据每个决策树对数据包进行分类，然后在所有匹配规则中选择优先级最高的规则。
总结:现有的解决方案通过使用两种类型的操作来构建决策树：节点切割和规则划分。这些解决方案的主要区别在于它们决定（i）在哪个节点应用操作，（ii）应用哪个操作，以及（iii）如何应用它（例如，沿着哪个维度进行分区）。
基于学习的方法
Why learn ?
现有的数据包分类方法都是依靠人工调整的启发式方法来建立决策树,这有了两个主要的限制。首先，这些启发式方法经常面临性能和成本之间的艰难权衡。为给定的规则集调整这样的启发式是一个昂贵的提议，需要大量的人力和专业知识。如果给定一个不同的规则集，则可能必须重新执行此操作。
其次，现有的算法并没有直接针对全局目标进行优化。理想情况下，一个好的数据包分类解决方案应该对（i）分类时间，（ii）内存占用，或（iii）两者的组合进行优化。不幸的是，现有的启发式算法并没有直接针对这些目标进行优化。这些启发式算法做出贪婪的决策来构建决策树。在每一步，他们都基于简单的统计信息（例如，每个维度中规则的大小、每个维度中唯一范围的数目）来决定是剪切一个节点还是划分规则，这些统计信息与期望的目标相关性很差。因此，得到的决策树往往远远不是最优的。
基于学习的方法可以解决这些限制。这种方法可以学习为一组特定的规则生成一个有效的决策树，而无需依赖于手动调整的启发式。
What to Learn ?
先前的工作已经表明DNN模型可以有效地用来代替B-树进行索引.然而，这种解决方案有两个缺点。首先，基于DNN的分类器不能保证100%的准确性。因为训练DNN是一个随机过程。其次，给定DNN数据包分类结果，验证结果是否正确是很昂贵的。与最近提出的替换B-树的学习索引解决方案不同，数据包分类中的规则是相互重叠的。如果一个规则匹配一个包，我们仍然需要检查其他规则，看看这个规则在所有匹配的规则中是否具有最高的优先级。
How to Learn ?
使用RL来构建决策树，决策树的形式就是当前的状态，操作是分割节点或对规则分组，而回报是分类时间和内存占用。
NEUROCUTS 设计
NeuroCuts Overview
算法设计
状态:在NeuroCuts中，没有尝试解决状态表示问题以处理大量输入，而是利用数据包分类树的底层结构来设计简单而紧凑的状态表示。 这意味着当代理决定如何拆分节点时，它仅观察到该节点的固定长度表示形式。 所有需要的状态都编码在表示形式中； 不观察树的其余部分的信息。
反馈:反馈将基于它所导致的子树的统计数据（即，它的深度或大小），只在树完成时计算反馈。 另一种看待密集报酬问题的方法是，建立决策树的过程不是真正的顺序的，而是树结构的（即，它更准确地建模为分支决策过程）。例如切割一个节点会产生多个子节点，并且报酬计算可能涉及每个子节点未来报酬的总和或最小值，这取决于我们是否在优化树的大小或深度。神经割的一步决策问题和分支决策过程公式是大致等价的。 具有100K规则的数据包分类器的决策树可以有成千上万个节点。树的大小阻碍了多个维度的训练。它不仅需要更多的步骤来完成树的构建，而且随着要处理的规则的增多，每个操作的执行时间也会增加。树的探索空间也更大，需要使用更大的网络模型，生成更多的rollout来进行训练。
状态表示：给定一个树节点，该节点上的操作只需要做出优化该节点上的子树的最佳决策。它不需要考虑决策树中的其他树节点。
…
训练算法：使用actor-critic算法来训练代理。
图5可视化了NeuroCuts构建决策树的学习过程。
图6所示neurocurts策略是随机的，使它能够在训练期间有效地探索许多不同的树变化
结合现有的启发式方法:添加分区操作：(1)Simple：沿单个维度对当前节点进行分区(2)EffiCuts：使用EffiCuts分区启发式算法对当前节点进行分区
扩展以处理大型数据包分类器: 但是对于具有成千上万规则的大型分类器，并行性可以显着提高训练速度。 在图7中展示如何将算法1调整为并行构建多个决策树。
处理分类器更新。 数据包分类器通常由网络运营商基于应用要求来更新，例如，添加用于新设备的访问控制规则。 对于仅几个规则的少量更新，NeuroCuts修改了现有的决策树以反映更改。 根据决策树现有的架构添加新规则。已删除的规则将从终端叶节点中删除。当有足够的更新累积或对分类器进行大更新时，neurocurts会重新运行训练。
实施
决策树实现:为了便于开发，在Python中实现了neurocut的决策树数据结构。为了确保较小的实现差异不会影响结果，使用相同的数据结构来实现每个基线算法（例如HiCuts、EffiCuts等）以及实现NeuroCuts。
性能:NeuroCuts通常会在几百次部署中收敛到其最佳解决方案。 规则集的大小不会显着影响收敛所需的rollout数量，但会影响每个rollout的运行时间。 对于较小的问题（例如1000条规则），这可能需要几分钟的CPU时间。 较大问题的计算开销随分类器的大小而定，即与为生长树而采取的每个操作必须扫描的规则数量成线性关系。 NeuroCuts中的大部分时间都花在了执行树切割上。
优化
rollout截断:在学习的初始阶段，未经优化的策略将创建过大的树木。 由于NeuroCuts直到一棵树完成才开始学习，因此有必要截断rollout以加快训练的初始阶段。 对于较大的分类器，我们发现有必要允许最多部署15000个动作.
深度截断 由于有效的解决方案永远不会涉及深度大于几百的树，因此，一旦树达到一定深度也会将其截断。 根据经验，深度截断只是学习初期的一个因素, NeuroCuts很快学会避免创建非常深的树木。
近端策略优化 为了获得更好的稳定性和更有效的样本学习，作者选择使用近端策略优化（Proximal Policy Optimization,PPO）。PPO通过熵正则化和截断代理目标实现了行动者-批评家式的损失，从而提高了勘探效率和样本效率。使用的PPO超参数见表2。但需要注意的是，RL算法的这种特殊选择并不是神经切断的基础。
评价
将NeuroCuts与四种手动调整的算法进行比较：Hi-Cuts ，HyperCuts，EffiCuts和CutSplit。使用标准基准ClassBench 来生成具有不同特征和大小的数据包分类器。 基准度量标准：分类时间（树深度）和内存占用量（每个规则的字节数）。 由于我们对所有算法都使用相同的基础树数据结构，因此深度较小实际上可以保证遍历效率更高，内存占用量也是如此。
NeuroCuts在分类时间上比baseline有显著改善，同时还生成了更为紧凑的树。 在优化内存时，NeuroCuts也具有竞争力，与EffiCuts相比，在分类时间不变的情况下，空间占用减少了25％。
Time-Optimized NeuroCuts
NeuroCuts分别比HiCuts，HyperCuts，EffiCuts和CutSplit分别提高了20％，38％，52％和56％。 在70％的案例中，NeuroCuts的表现也优于所有基准的最小值，所有基线的中位数改善了18％，平均改善了12％，最佳案例改善了58％。 这些时间优化的树通常与NeuroCuts相对应，它们没有分区操作，也没有简单的顶部节点分区操作。
Space-Optimized NeuroCuts
我们再次将NeuroCuts与图9的基线进行比较，这次选择最优化空间的树并比较内存占用量（每条规则字节）。 正如预期的那样，NeuroCuts的性能明显优于HiCuts和HyperCuts，因为它可以学习利用分区操作。 NeuroCut的空间优化树比EffiCuts的中位数提高了40％，平均改进了44％。 在我们的实验中，NeuroCuts的内存占用量通常不会超过CutSplit，与CutSplit相比，中值内存使用量要高26％，尽管在所有基准上最佳情况下的改进仍然是3倍（66％）。
另外，我们还注意到，NeuroCuts生成的最佳时间优化树的内存占用量显着低于HiCuts和HyperCuts生成的内存占用量，中位空间改进了100倍以上。但是，这些时间优化的树在空间上与空间优化的NeuroCuts，EffiCuts和CutSplit树没有竞争力。
结论
介绍了NeuroCuts，这是一种简单有效的数据包分类问题的Deep RL公式。 与最新的算法相比，NeuroCuts在分类时间和内存占用方面提供了显着的改进。 它可以轻松地整合预先设计的启发式方法，以利用他们的领域知识，优化灵活的目标，并生成易于在任何环境中测试和部署的决策树。 我们希望NeuroCuts可以启发新一代基于学习的数据包分类算法。 作为一个具体的例子，NeuroCuts当前针对最坏情况下的分类时间或内存占用进行了优化。 通过考虑特定的流量模式，NeuroCuts可以扩展到其他目标，例如平均分类时间。 这将使NeuroCuts不仅可以针对特定分类器进行优化，还可以针对给定部署中的特定流量模式进行优化。