Packet classification with multiple decision trees

Packet classification, which performs multidimensional point location upon fields in packet headers, categorizes incoming packets into multiple forwarding classes based on predefined filters. It fulfills the requirements of network applications by treating their incoming packets with consistent actions defined in the filters. In this work, we propose a new scheme to enhance the scalability of packet classification by using multiple decision trees, where each filter is stored in one of the decision trees. With the optimized filter assignment, our scheme can significantly improve the storage efficiency of decision trees while reducing the search latency. We evaluate the performance of our scheme with twelve different types of filter databases whose sizes vary from 16K to 100K. The experimental results demonstrate the feasibility and scalability of the scheme. Also, we show that our scheme takes less time and space as compared to the prominent existing schemes.