Abstract

In this paper, we are going to decompose the operation of multimatch packet classification from the complicated multidimensional search to several single-dimensional searches, and present an asynchronous pipeline architecture based on a signature tree structure to combine the intermediate results returned from single-dimensional searches. By spreading edges of the signature tree across multiple hash tables at different stages, the pipeline can achieve a high throughput via the interstate parallel access to hash tables. Two edge-grouping algorithms are designed to evenly divide the edges associated with each stage into multiple work-conserving hash tables. The proposed pipeline architecture outperforms Hyper Cuts and B2PC schemes in classification speed by at least one order of magnitude, while having a similar storage requirement. Particularly, with different types of classifiers of 4K rules, the proposed pipeline architecture is able to achieve a throughput between 26.8 and 93.1 GB/s using perfect hash tables. Multiple string match is an important problem in many application areas of computer for instance there is an increasing demand for fast analysis and data retrieval although there are various kinds of comparison tools that provide aligning and approximate matching most of them are based on exact matching in order to speed up the process. Multiple string match is an important problem in many application areas of computer for instance there is an increasing demand for fast analysis and data retrieval although there are various kinds of comparison tools that provide aligning and approximate matching most of them are based on exact matching in order to speed up the process. Another important usage of multiple string matching algorithms appears in NIDS [network intrusion detection systems]. Snort is a light weight open source NIDS which can filter packets based on predefined rules. Another important usage of multiple string matching algorithms appears in NIDS [network intrusion detection systems]. Snort is a light weight open source NIDS which can filter packets based on predefined rules.

Authors and Affiliations