Abstract—Regular-expression is widely used in various network applications, such as a network intrusion detection system (NIDS). However, existing regular-expression process does not meet required throughput in core routers because most of NIDSs have been implemented by software. In particular, a pattern matching function, a part of regular-expression processing, requires comparatively longer processing time. Huge amounts of patterns are used for this pattern matching in NIDS. Therefore, high-throughput processing modules are strongly required in order to execute a large number of complicated regular-expression. In this paper, a simple but effective hash-based architecture of pattern filtering with special entries is discussed, and it enables to achieve a large number of patterns matching.
Index Terms—Network processor, regular-expression, pattern matching, hash
H. Yamaki, Y. Nagatomi, and H. Nishi are with the Graduate School of Science and Technology, Keio University, Yokohama, Kanagawa, 223-8522, Japan (e-mail: yamaki@west.sd.keio.ac.jp, yasu@west.sd.keio.ac.jp, west@sd.keio.ac.jp)
Cite: Hayato Yamaki, Yasutsugu Nagatomi, and Hiroaki Nishi, "Effective Hash-Based Filtering Architecture for High-throughput Regular-Expression Matching," International Journal of Information and Electronics Engineering vol. 2, no. 5, pp. 672-677, 2012.