Packet Classification Using Dynamically Generated Decision Trees

Abstract

Binary search on levels (BSOL) is a decision-tree algorithm for packet classification with superior speed performance. However, the most decision-tree-based algorithms, like BSOL, may suffer from a memory explosion problem caused by filter replications. In this work, we improve the storage performance of BSOL by employing a scheme, replication control. Our scheme dynamically generates multiple decision trees to eliminate filter replications in BSOL. The experimental results show that the new scheme achieves better performance than the existing decision-tree-based algorithms.