Multibit Tries Packet Classification with Deep Reinforcement Learning
High performance packet classification is a key component to support scalable
network applications like firewalls, intrusion detection, and differentiated
services. With ever increasing in the line-rate in core networks, it becomes a
great challenge to design a scalable and high performance packet classification
solution using hand-tuned heuristics approaches. In this paper, we present a
scalable learning-based packet classification engine and its performance
evaluation. By exploiting the sparsity of ruleset, our algorithm uses a few
effective bits (EBs) to extract a large number of candidate rules with just a
few of memory access. These effective bits are learned with deep reinforcement
learning and they are used to create a bitmap to filter out the majority of
rules which do not need to be full-matched to improve the online system
performance. Moreover, our EBs learning-based selection method is independent
of the ruleset, which can be applied to varying rulesets. Our multibit tries
classification engine outperforms lookup time both in worst and average case by
55% and reduce memory footprint, compared to traditional decision tree without
EBs.