Packet classification has become one of the most important application techniques in network security since the last decade. The technique involves a traffic descriptor or user-defined criteria to categorize packets to a specific forwarding class which will be accessible for future security handling. To achieve fast packet classification, we propose a new scheme, Hierarchical Cross-Producting. This approach simplifies the classification procedure and decreases the distinct combinations of fields by hierarchically decomposing the multi-dimensional space based on the concept of telescopic search. Analogous to the use of telescopes with different powers**, a multiple-step process is used to search for targets. In our scheme, the multi-dimensional space is endowed with a hierarchical property which self-divides into several smaller subspaces, whereas the procedure of packet classification is translated into recursive searching for matching subspaces. The required storage of our scheme could be significantly reduced since the distinct field specifications of subspaces is manageable. The performance are evaluated based on both real and synthetic filter databases. The experimental results demonstrate the effectiveness and scalability of the proposed scheme.

In the last decade, the technique of packet classification has been widely deployed in various network devices, including routers, firewalls and network intrusion detection systems. In this work, we improve the performance of packet classification by using multiple hash tables. The existing hash-based algorithms have superior scalability with respect to the required space; however, their search performance may not be comparable to other algorithms. To improve the search performance, we propose a tuple reordering algorithm to minimize the number of accessed hash tables with the aid of bitmaps. We also use pre-computation to ensure the accuracy of our search procedure. Performance evaluation based on both real and synthetic filter databases shows that our scheme is effective and scalable and the pre-computation cost is moderate.

Packet classification categorizes incoming packets into multiple forwarding classes based on pre-defined filters. This categorization makes information accessible for quality of service or security handling in the network. In this paper, we propose a scheme which combines the Aggregate Bit Vector algorithm and the Pruned Tuple Space Search algorithm to improve the performance of packet classification in terms of speed and storage. We also present the procedures of incremental update. Our scheme is evaluated with filter databases of varying sizes and characteristics. The experimental results demonstrate that our scheme is feasible and scalable.