Detail publikace

High-speed Regular Expression Matching with Pipelined Automata

MATOUŠEK, D.; KOŘENEK, J.; PUŠ, V. 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. p. 93-100. ISBN: 978-1-5090-5602-6.
Název česky
Vyhledávání vzorů pomocí zřetězených automatů
Typ
článek ve sborníku konference
Jazyk
anglicky
Autoři
Matoušek Denis, Ing.
Kořenek Jan, doc. Ing., Ph.D. (UPSY)
Puš Viktor, Ing., Ph.D.
URL
Klíčová slova

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

Abstrakt

Vyhledávání vzorů je komplexní úloha rozšířená v oblasti aplikací pro monitorování síťové bezpečnosti. S rostoucí rychlostí počítačových linek je potřeba škálovat architektury tak, aby byly stále schopny pracovat na rychlosti linky. Multi-striding je známá technika pro zvýšení propustnosti architektur pro vyhledávání vzorů. Práce uvádí analýzu škálovatelnosti techniky multi-striding a ukazuje, že ta neškáluje a nelze ji použít pro propustnost 100 Gb/s a výše kvůli exponenciálnímu nárůstu využitých zdrojů na čipu FPGA. Proto jsme navrhli novou architekturu pro vysokorychlostní vyhledávání vzorů, která kombinuje techniku multi-striding a paralelní zpracování pomocí zřetězených konečných automatů (FSM). Architektura sdílí jedinou vyrovnávací paměť pro všechny paralelní FSM. Efektivní implementace vyrovnávací paměti pro pakety redukuje množství BlockRAM pamětí na 18% v porovnání s naivní paralelní implementací. Místo rozdělování vstupních dat architektura řetězí stavy konečných automatů. Takové zřetězené zpracování s lokální komunikací má přímý pozitivní vliv na frekvenci a dovoluje škálovat architekturu na stovky gigabitů.

Rok
2016
Strany
93–100
Sborník
Proceedings of the 2016 International Conference on Field Programmable Technology
ISBN
978-1-5090-5602-6
Vydavatel
IEEE Computer Society
Místo
Xi'an
DOI
10.1109/FPT.2016.7929431
UT WoS
000402988900012
EID Scopus
2-s2.0-85021394334
BibTeX 
@inproceedings{BUT133501,
  author="Denis {Matoušek} and Jan {Kořenek} and Viktor {Puš}",
  title="High-speed Regular Expression Matching with Pipelined Automata",
  booktitle="Proceedings of the 2016 International Conference on Field Programmable Technology",
  year="2016",
  pages="93--100",
  publisher="IEEE Computer Society",
  address="Xi'an",
  doi="10.1109/FPT.2016.7929431",
  isbn="978-1-5090-5602-6",
  url="http://ieeexplore.ieee.org/document/7929431/"
}
Nahoru