Faculty of Information Technology, BUT

Publication Details

Regular Expression Matching with Pipelined Delayed Input DFAs for High-speed Networks

MATOUŠEK Denis, KUBIŠ Juraj, MATOUŠEK Jiří and KOŘENEK Jan. Regular Expression Matching with Pipelined Delayed Input DFAs for High-speed Networks. In: Proceedings of the 2018 Symposium on Architectures for Networking and Communications Systems. Ithaca, NY: Association for Computing Machinery, 2018, pp. 104-110. ISBN 978-1-4503-5902-3.
Czech title
Vyhledávání vzorů popsaných regulárními výrazy za použití zřetězených automatů se zpožděným vstupem pro vysokorychlostní sítě
Type
conference paper
Language
english
Authors
Matoušek Denis, Ing. (DCSY FIT BUT)
Kubiš Juraj, Bc. (FIT BUT)
Matoušek Jiří, Ing., Ph.D. (DCSY FIT BUT)
Kořenek Jan, doc. Ing., Ph.D. (DCSY FIT BUT)
Keywords
Regular expression matching, 100 Gbps, 400 Gbps, Delayed Input DFA, Pipelined automata
Abstract
Regular expression matching (RE matching) is a widely used operation in network security monitoring applications. With the speed of network links increasing to 100 Gbps and 400 Gbps, it is necessary to speed up packet processing and provide RE matching at such high speeds. Although many RE matching algorithms and architectures have been designed, none of them supports 100 Gbps throughput together with fast updates of an RE set. Therefore, this paper focuses on the design of a new hardware architecture that addresses both these requirements. The proposed architecture uses multiple highly memory-efficient Delayed Input DFAs (D2FAs), which are organized to a processing pipeline. As all D2FAs in the pipeline have only local communication, the proposed architecture is able to operate at high frequency even for a large number of parallel engines, which allows scaling throughput to hundreds of gigabits per second. The paper also analyses how to scale the number of engines and the capacity of buffers to achieve desired throughput. Using the parameters obtained while matching two sets of REs (represented by D2FAs) in a real network traffic, the architecture can be tuned for wire-speed throughput of 400 Gbps.
Published
2018
Pages
104-110
Proceedings
Proceedings of the 2018 Symposium on Architectures for Networking and Communications Systems
Conference
14th ACM/IEEE Symposium on Architectures for Networking and Communications Systems (ANCS '18), Ithaca, NY, US
ISBN
978-1-4503-5902-3
Publisher
Association for Computing Machinery
Place
Ithaca, NY, US
DOI
BibTeX
@INPROCEEDINGS{FITPUB11711,
   author = "Denis Matou\v{s}ek and Juraj Kubi\v{s} and Ji\v{r}\'{i} Matou\v{s}ek and Jan Ko\v{r}enek",
   title = "Regular Expression Matching with Pipelined Delayed Input DFAs for High-speed Networks",
   pages = "104--110",
   booktitle = "Proceedings of the 2018 Symposium on Architectures for Networking and Communications Systems",
   year = 2018,
   location = "Ithaca, NY, US",
   publisher = "Association for Computing Machinery",
   ISBN = "978-1-4503-5902-3",
   doi = "10.1145/3230718.3230730",
   language = "english",
   url = "https://www.fit.vut.cz/research/publication/11711"
}
Back to top