Result Details

NFA Split Architecture for Fast Regular Expression Matching

KOŘENEK, J.; KOŠAŘ, V. NFA Split Architecture for Fast Regular Expression Matching. Proceedings of the 6th ACM/IEEE Symposium on Architectures for Networking and Communications Systems. La Jolla: Association for Computing Machinery, 2010. s. 1-2. ISBN: 978-1-4503-0379-8.
Type
conference paper
Language
Czech
Authors
Abstract

Článek se zabývá rychlým hledáním regulárních výrazů v oblasti bezpečnosti počítačových sítí. Je navržena nová NFA Split architektura, která výrazným způsobem redukuje množství potřebných hardwarových zdrojů na čipu. Pro všechny analyzované množiny regulárních výrazů byl redukován počet flip-flop registrů v průměru na 37,6 procent a počet look-up tabulek na 63.9 procent.

English abstract

Many hardware architectures have been designed to accelerate
regular expression matching in network security devices, but most of them can achieve high throughput only for strings or small sets of regular expressions. We propose new NFA Split architecture which reduces the amount of consumed FPGA resources in order to match larger set of regular expressions. New algorithm is introduced to find non-collision sets of states and determine part of nondeterministic automaton which can be mapped to the memory based architecture. For all analysed sets of regular expressions, the algorithm was able to find non-collision sets with 67.8 % of states in average and reduces the amount of consumed flip-flops to 37.6 % and look-up tables to 63.9 % in average.

Keywords

Hledání regulárních výrazů, Automat, FPGA

English keywords

Regular expressions matching, Automaton, FPGA

Published
2010
Pages
1–2
Proceedings
Proceedings of the 6th ACM/IEEE Symposium on Architectures for Networking and Communications Systems
Conference
ACM/IEEE Symposium on Architectures for Networking and Communications Systems 2010
ISBN
978-1-4503-0379-8
Publisher
Association for Computing Machinery
Place
La Jolla
BibTeX
@inproceedings{BUT35050,
  author="Jan {Kořenek} and Vlastimil {Košař}",
  title="NFA Split Architecture for Fast Regular Expression Matching",
  booktitle="Proceedings of the 6th ACM/IEEE Symposium on Architectures for Networking and Communications Systems",
  year="2010",
  pages="1--2",
  publisher="Association for Computing Machinery",
  address="La Jolla",
  isbn="978-1-4503-0379-8"
}
Projects
Optická síť národního výzkumu a její nové aplikace, MŠMT, Výzkumná centra (2000-2004), MSM6383917201, start: 2004-01-01, end: 2010-12-31, completed
Secured, reliable and adaptive computer systems, BUT, Vnitřní projekty VUT, FIT-S-10-1, start: 2010-03-01, end: 2010-12-31, completed
Security-Oriented Research in Information Technology, MŠMT, Institucionální prostředky SR ČR (např. VZ, VC), MSM0021630528, start: 2007-01-01, end: 2013-12-31, running
Research groups
Departments
Back to top