Publication Details

High-speed Regular Expression Matching with Pipelined Automata

MATOUŠEK Denis, KOŘENEK Jan and PUŠ Viktor. High-speed Regular Expression Matching with Pipelined Automata. In: Proceedings of the 2016 International Conference on Field Programmable Technology. Xi'an: IEEE Computer Society, 2016, pp. 93-100. ISBN 978-1-5090-5602-6. Available from: http://ieeexplore.ieee.org/document/7929431/
Czech title
Vyhledávání vzorů pomocí zřetězených automatů
Type
conference paper
Language
english
Authors
Matoušek Denis, Ing. (DCSY FIT BUT)
Kořenek Jan, doc. Ing., Ph.D. (DCSY FIT BUT)
Puš Viktor, Ing. (DCSY FIT BUT)
URL
Keywords

FPGA, NFA, multi-striding, pattern matching, regular expressions, finite automata, pipelined automata, high-speed networks, 100Gbps, 40Gbps, 10Gbps, 100G Ethernet, 40G Ethernet, 10G Ethernet

Abstract

Pattern matching is a complex task which is widely used in network security monitoring applications. With the growing speed of network links, pattern matching architectures have to be improved in order to retain wire-speed processing. Multi-striding is a well-known technique on how to increase throughput of pattern matching architectures. In the paper we provide an analysis of scalability of multi-striding and show that it does not scale well and cannot be used for 100Gbps throughput because utilization of FPGA resources grows exponentially. Therefore, we have designed a new hardware architecture for high-speed pattern matching that combines the multi-striding technique and parallel processing using pipelined finite state machines (FSMs). The architecture shares a single packet buffer for all parallel FSMs. Efficient implementation of the packet buffer reduces the number of BlockRAMs to 18% when compared to simple parallel implementation. Instead of multiplexing input data, the architecture pipelines the states of FSMs. Such pipelined processing with only local communication has a direct positive impact on frequency and throughput and allows us to scale the architecture to hundreds of Gbps.

Published
2016
Pages
93-100
Proceedings
Proceedings of the 2016 International Conference on Field Programmable Technology
Conference
The 2016 International Conference on Field-Programmable Technology, Xi'an, CN
ISBN
978-1-5090-5602-6
Publisher
IEEE Computer Society
Place
Xi'an, CN
DOI
UT WoS
000402988900012
EID Scopus
BibTeX
@INPROCEEDINGS{FITPUB11288,
   author = "Denis Matou\v{s}ek and Jan Ko\v{r}enek and Viktor Pu\v{s}",
   title = "High-speed Regular Expression Matching with Pipelined Automata",
   pages = "93--100",
   booktitle = "Proceedings of the 2016 International Conference on Field Programmable Technology",
   year = 2016,
   location = "Xi'an, CN",
   publisher = "IEEE Computer Society",
   ISBN = "978-1-5090-5602-6",
   doi = "10.1109/FPT.2016.7929431",
   language = "english",
   url = "https://www.fit.vut.cz/research/publication/11288"
}
Back to top