DTRadar: Accelerating Search Process of Decision Trees in Packet Classification

Packet classification is an essential part of computer networks. Existing algorithms propose a partition process to address the memory explosion problem of the decision tree algorithm caused by the huge number of rules with multiple fields. However, the search process requires traversing multiple trees generated by the partition, which reduces the search efficiency. The existing algorithms take simple approaches to optimize the search process, which is low efficiency or high hardware overhead. In this paper, we propose DTRadar, a framework for expediting the decision tree packet lookup process. Its key idea is building an abstract One-Big-Tree(OBT) for multiple decision trees by establishing the middle data structure. DTRadar considers each decision tree as a splittable tree and organizes these subtrees by intermediate data structures. Extensive experiments show that DTRadar benefits existing decision tree-based solutions in classification time by 61.60%, and the memory footprint only increased by 4.21% on average.

I. Introduction

Packet classification is a critical part of modern networks. Each packet matches a pre-defined rule and is performed with corresponding actions. Packet classification serves as the basis for implementing network functions, such as route forwarding, quality of service and security authentication, etc. The decision tree algorithm has high throughput that shows promise in packet classification. Several tree-building heuristics [1]–[3] have been proposed to cutting rules and deliver multi-field rule matching. But since the classifier has many overlapping rules, large rule replications are generated when cutting small rules.