AI Case Study

UC Berkeley researchers improve network packet classification by 18% using reinforcement learning

Researchers from UC Berkeley and Johns Hopkins University apply reinforcement learning with deep neural networks to network packet classification in a system called NeuroCuts. This avoids having to hand-code rules for classification which can make the system brittle, and improves benchmark performance over other systems by 18% in the median,.

Industry

Technology

Software And It Services

Project Overview

The researchers posit that their "approach has the potential to address the limitations of the existing hand-tuned heuristics. In particular, our approach learns to optimize packet classification for a given set of rules and objective, can easily incorporate pre-engineered heuristics to leverage their domain knowledge, and does so with little human involvement.

[The] solution uses deep reinforcement learning (RL) to
build efficient decision trees. There are three characteristics
that makes RL a particularly good fit for packet classification.
First, the natural solution to build a decision tree is to start
with one node and recursively split (cut) it. Unfortunately,
this kind of approach does not have a greedy solution. When
making a decision to cut a node, we do not know whether
that decision was a good one (i.e., whether it leads to an
efficient tree) before we finish building the actual tree. RL
naturally captures this characteristic as it does not assume
that the impact of a given decision on the performance objective is known immediately. Second, unlike existing heuristics
which take actions that are only loosely related to the performance objective, the explicit goal of an RL algorithm is to
directly maximize the performance objective. Third, unlike
other RL domains such as as robotics, for our problem it is
possible to evaluate an RL model quickly (i.e., a few seconds
of CPU time). This alleviates one of the main drawbacks of
RL algorithms: the non-trivial learning time due to the need
to evaluate a large number of models to find a good solution.
By being able to evaluate each model quickly (and, as we will
see, in parallel) we significantly reduce the learning time.

To this end, we design NeuroCuts, a deep RL solution for
packet classification that learns to build efficient decision
trees."

Reported Results

The researchers found that "NeuroCuts signi cantly improves over all baselines in classi cation time while also generating significantly more compact trees."

Technology

"We introduce the design for NeuroCuts, a new Deep RL
formulation of the packet classification problem. Given a rule set and an objective function (i.e., classification time, memory footprint, or a combination of both), NeuroCuts learns to build a decision tree that minimizes the objective.

...NeuroCuts as an RL system: the environment consists of the set of rules and the current decision tree, while the agent uses a model (implemented by a DNN) that aims to select the best cut or partition action to incrementally build the tree. A cut action divides a node along a chosen dimension (i.e., one of SrcIP, DstIP, SrcPort, DstPort, and Protocol) into a number of sub-ranges (i.e., 2, 4, 8, 16, or 32 ranges), and creates that many child nodes in the tree. A partition action on the other hand divides the rules of a node into disjoint subsets (e.g., based on the coverage fraction of a dimension), and creates a new child node for each subset. The available actions for the current node are advertised by the environment at each step, the agent chooses among them to generate the tree, and over time the agent learns to optimize its decisions to maximize the reward from the environment."

Function

Information Technology

Network Operations

Background

"Packet classification is one of the fundamental problems in
computer networking. The goal of packet classification is to
match a given packet to a rule from a set of rules, and to do
so while optimizing the classification time and/or memory
footprint. Packet classification is a key building block for
many network functionalities, including firewalls, access
control, traffic engineering, and network measurements.

Existing solutions for packet classification can be divided
into two broad categories. Solutions in the first category are
hardware-based... The solutions in the second category are software based."

Benefits

Data

The research used "the standard benchmark, ClassBench, to generate packet classifiers with different characteristics and sizes."