Neural packet classification
Neural packet classification
复制标题
DOI：
10.1145/3341302.3342221
复制
发表时间：
2019-02
期刊：
影响因子：
--
通讯作者：
Eric Liang;Hang Zhu;Xin Jin;I. Stoica
中科院分区：
文献类型：
--
作者：
Eric Liang;Hang Zhu;Xin Jin;I. Stoica
数据包分类是计算机网络中的一个基本问题。这个问题暴露了计算和状态复杂度之间的艰难权衡，这使得它特别具有挑战性。为了驾驭这种权衡，现有的解决方案依赖于复杂的手动调整的算法，这是脆弱的，难以优化。在本文中，我们提出了一种深度强化学习（RL）方法来解决数据包分类问题。有几个特征使这个问题非常适合深度RL。首先，许多现有的解决方案通过分裂树中的节点来迭代地构建决策树。其次，这些行动的影响（例如，分裂节点）只能在构建整个树时进行评估。这两个特征自然被RL采取具有稀疏和延迟奖励的行动的能力所捕获。第三，生成数据轨迹和评估决策树在计算上是高效的，这缓解了Deep RL算法众所周知的高样本复杂性问题。我们的解决方案NeuroCuts使用简洁的表示来编码状态和动作空间，并有效地探索候选决策树以优化全局目标。它生成针对特定规则集和给定性能指标（如分类时间、内存占用或两者的组合）进行优化的紧凑决策树。在Class-Bench上的评估表明，NeuroCuts在分类时间上比现有的手工算法的中值高出18%，并将分类时间和内存占用减少了3倍。
Packet classification is a fundamental problem in computer networking. This problem exposes a hard tradeoff between the computation and state complexity, which makes it particularly challenging. To navigate this tradeoff, existing solutions rely on complex hand-tuned heuristics, which are brittle and hard to optimize. In this paper, we propose a deep reinforcement learning (RL) approach to solve the packet classification problem. There are several characteristics that make this problem a good fit for Deep RL. First, many existing solutions iteratively build a decision tree by splitting nodes in the tree. Second, the effects of these actions (e.g., splitting nodes) can only be evaluated once the entire tree is built. These two characteristics are naturally captured by the ability of RL to take actions that have sparse and delayed rewards. Third, it is computationally efficient to generate data traces and evaluate decision trees, which alleviate the notoriously high sample complexity problem of Deep RL algorithms. Our solution, NeuroCuts, uses succinct representations to encode state and action space, and efficiently explore candidate decision trees to optimize for a global objective. It produces compact decision trees optimized for a specific set of rules and a given performance metric, such as classification time, memory footprint, or a combination of the two. Evaluation on Class-Bench shows that NeuroCuts outperforms existing hand-crafted algorithms in classification time by 18% at the median, and reduces both classification time and memory footprint by up to 3X.