Packet Classification Using Multi-Iteration RFC

Abstract—Packet Classification is an enabling technique for the future Internet by classifying incoming packets into forwarding classes to fulfill different service requirements. It is necessary for IP routers to provide network security and differentiated services. Recursive Flow Classification (RFC) is a notable high-speed scheme for packet classification. However, it may incur high memory consumption in generating the pre-computed cross-product tables. In this paper, we propose a new scheme to reduce the memory consumption by partitioning a rule database into several subsets. The rules of each subset are stored in an independent RFC data structure to significantly alleviate overall memory consumption. We also present several refinements for these RFC data structures to significantly improve the search speed. The experimental results show that our scheme dramatically improves the storage performance of RFC. Keywords-packet classification; packet forwarding; firewalls; QoS I