Optimal Tuple Reduction for Fast Two-Dimension Packet Classification

Packet classification categorizes packets into flows based on some predefined filters. Nowadays the packet classification techniques play an impor-tant role for many new Internet services. Rect-angle search is a well-known packet classification scheme which is based on multiple hash accesses for different filter length. It shows good scalabil-ity with respect to the number of filters; however, the lookup performance is not fast enough. For example, through experiments, each packet classi-fication takes about 40 hash accesses in a 100,000-filter database and each hash access may take more than one memory access. Obviously, this is not capable to provide gigabits throughput. In this paper, we propose an efficient Tuple Reduction Algorithm to improve the rectangle search. The Tuple Reduction Algorithm is based on the filter duplication. In spite of the increased number of filters, the pre-computation information is dramatically reduced, the perfor-mance has increased two times while only about one quarter storage is required. The experimental results indicate that the proposed scheme can fulfill OC-48 throughput.