作者

1 Eric Liang：加州大学伯克利分校RISELab成员之一，方向为强化学习的分布式系统和应用程序，曾在Google/Databricks工作。https://rise.cs.berkeley.edu/blog/author/ekhliang/

4 Ion Stoica：加州大学伯克利分校EECS系的教授，RISELab成员之一。他从事云计算和网络计算机系统的研究，也是ACM院士。https://rise.cs.berkeley.edu/blog/author/istoica/

2 Hang Zhu：约翰·霍普金斯大学计算机科学系的博士研究生，毕业于清华大学，是Xin Jin的学生，从事计算机网络的研究。http://www.cs.jhu.edu/~hzhu/

3 Xin Jin：约翰霍普斯金大学计算机系的助理教授，曾在加州大学伯克利分校AMPLab/RISELab工作，从事计算机网络和分布式系统领域的研究。http://www.cs.jhu.edu/~xinjin/

RISELab：致力于智能、安全交互技术，初期目标就是增强Spark的安全性与实时能力。

摘要

Packet classification 是计算机网络的一个基本问题，但这个问题至今依赖于复杂的手动调整的启发式算法，脆弱且难以优化。本文提出的NeuroCuts能够解决这一问题，并在分类时间和占用内存等方面优于手工算法。

介绍

现有方法分为两种，一种基于TCAMS,一种基于决策树。

TCAMS分类时间固定，且局限多。基于决策树的算法比基于TCAMS的有更好地伸缩性，但是慢，毕竟要遍历树。依靠手工调整的启发式方法来构建树，这使得启发式算法在通用性和针对性上取得平衡。而且有可能达不到全局最优。

将学习应用到Packet classification上有两个方向。

一，用神经网络取代决策树，但这个方法不保证总是最好的，而且很费资源（烧GPU）。二，用DL学习如何建树，用于分组分类的决策树通过构造提供了完美的准确性，其目标是最小化分类时间和内存占用。

为什么选择将RL应用于Packet classification，有三个理由。

一，构建决策树是从一个节点开始并递归地切割它，这使得我们在完成构建之前，不知道这个切分的决定是否是一个好的决定——这符合RL的特性，因为它不假定给定决策对性能目标的影响是立即已知的。

二，现有的启发式算法优化算法时，只能采用与性能目标松散相关的动作，最后可能得到不是最优解，但不同于现有的启发式算法，RL算法的明确目标是直接最大化性能目标。

三，RL在其他领域的应用可能需要很多的资源，但是对于我们的问题，可以快速评估RL模型，用CPU也只用几秒钟就可以完成。这就缓解了RL算法的一个主要缺点：由于需要对大量模型进行评估以找到一个好的解决方案。

将RL应用于Packet classification有三个问题。

一，RL的输入要求是固定大小的，但我们的树会随着算法切割节点并生长的，这增加了编码难度。但是我们发现怎样切分树只跟节点本身有关系，与树无关，所以我们只用对节点进行编码即可。

二，减少奖励的稀缺性以加速学习过程。解决方法是根据树的大小深度，提供更加密集的反馈。

三，减少训练大规模规则所需的时间。解决方法是利用RLlib，一个分布式强化学习库。

背景

2.1 Packet Classification

图1 显示了三种规则。一，规则匹配所有源地址为10.0.0.1、目标地址共享前缀为10.0.0.0/16的数据包。二，将所有TCP数据包与[0，1023]范围内的源端口和目标端口匹配。三，与所有数据包匹配的默认规则。这保证任何数据包至少与一个规则匹配。

Packet classification含有规则列表。而一个数据包可能匹配多个规则，为了解决这个模糊性，每个规则都被分配了一个优先级。然后，一个包被匹配到最高优先级规则。比如，（10.0.0.0，10.0.0.1，0，0，6）符合上述三条规则，但由于优先级，只匹配第一条规则。

2.2 Decision Tree Algorithms

Packet classification类似于多维几何空间中的点位置问题。一个包被表示为这个空间中的一个点，一个规则被表示为一个超立方体，但是这很难在时间和空间复杂度上取得平衡。

我们要找到所有（包含数据包对应的）点的超立方体。举个例子，在具有n个非重叠超立方体的d维几何空间中，当d>3时，该问题具有两种情况。一，具有O（log n）时间和O（n^d）空间的下界；二，O（log^d-1 n）时间和O（n）空间的下界。但分组分类问题允许超立方体（即规则）重叠，因此很难。而且对于d=5时，无论哪种情况都不是很好。

Node cutting

建树：从包含所有规则的根开始，算法迭代地分割节点，直到每个叶包含的规则数少于预定义的数目。

对于数据包，给定一个树，从树根开始遍历到叶子节点，最后选择叶子节点有关的、具有最高优先权的规则。

如图2，Packet classification在二维空间中包含六个规则（R0到R5）。b中树的根包含所有六条规则。一，我们将整个空间沿维度x切割成四个块（沿a中竖着的虚线切），导致划分成四个子空间，如果b中树的第二行节点。二，我们沿着y维度切割，因此树的第三行每一块最多两个规则。

Rule partition

Node cutting 可能导致某个“较大”的规则在叶子节点上频繁出现，如R1

建树：根据“形状”划分，再根据划分后的区域各建一棵树。

图2中的六个规则被分为两个分区。一个分区由规则R1和R4组成，因为这两个规则在维度x中的大小都很大。另一个分区由其他四个规则组成，因为这些规则在维度x中的大小很小。图3（a）和图3（b）显示了每个分区对应的决策树。请注意，与图2（b）中的原始决策树相比，生成的树的深度更低，每个节点的规则数更少。

3 RL相关

4 NEUROCUTS DESIGN

4.1 NeuroCuts Overview

如图4b，NeuroCuts的框架和RL相似，以规则和现有决策树为环境，以DNN作为代理模型，在每一步中选择最合适的节点进行Node cutting 或 rule partition 动作。

4.2  NeuroCuts Training Algorithm

Design challenges

将RL应用于Packet classification有三个问题，下面进行详细解释：

一 如何将变长决策树状态作为神经网络策略的输入进行编码。

虽然可以将树展平，比如说，变成一维向量，但这样的向量的大小将非常大。最近的工作已经提出利用递归神经网络RNN和图嵌入技术来减少输入大小，但面对大型或动态增长的图结构，这些解决方案是脆弱的。

因此，我们采用分组分类树的底层结构来设计简单紧凑的状态表示。

二 如何处理建立决策树的逐节点过程中产生的稀疏和延迟的报酬。

设计了一个不寻常的步骤：当树完成时，只计算部署的奖励，并设置γ=0，有效地创建了一系列与contextual bandits类似的1-step descision problems.

另一种针对密集报酬问题的方法是，建立决策树的过程是树结构的，在这种“分支”公式中，γ>0，但一个动作的回报是作为一个动作产生的多个子状态的聚合计算的。例如，切割一个节点会产生多个子节点，并且报酬计算可能涉及每个子节点未来报酬的总和或最小值这取决于我们是否在优化树的大小或深度。

三 如何将解决方案扩展到大型分组分类器。

State representation

一个关键的观察结果是，树节点上的操作只依赖于节点本身，因此不必在环境状态下对整个决策树进行编码。给定一个树节点，该节点上的操作只需要做出优化该节点上的子树的最佳决策。它不需要考虑决策树中的其他树节点。

因此，树中的节点可以完全由它们在每个维度中所占的范围来定义。

Training algorithm

6 EVALUATION

参考文献&相关链接

原文：https://arxiv.org/pdf/1902.10319.pdf?context=cs.NI

代码：https://github.com/NeuroCuts/NeuroCuts