Department of Computer Systems

Conference paper

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:
Publication language:english
Original title:High-speed Regular Expression Matching with Pipelined Automata
Title (cs):Vyhledávání vzorů pomocí zřetězených automatů
Proceedings:Proceedings of the 2016 International Conference on Field Programmable Technology
Conference:The 2016 International Conference on Field-Programmable Technology
Place:Xi'an, CN
Publisher:IEEE Computer Society
FPGA, NFA, multi-striding, pattern matching, regular expressions, finite automata, pipelined automata, high-speed networks, 100Gbps, 40Gbps, 10Gbps, 100G Ethernet, 40G Ethernet, 10G Ethernet
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.
   author = {Denis Matou{\v{s}}ek and Jan Ko{\v{r}}enek and Viktor
   title = {High-speed Regular Expression Matching with Pipelined
   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},
   language = {english},
   url = {}

Your IPv4 address:
Switch to IPv6 connection

DNSSEC [dnssec]