Vysokorychlostní vyhledávání regulárních výrazů

Práce popisuje architekturu jednotky pro rychlé vyhledávání regulárních výrazů v moderních počítačových sítích. Navržená jednotka je schopná pracovat na propustnostech do 10Gbps, v závislosti na množství dostupné paměti. Představená implementace využívá perfektní hashování pro efektivní využití dostupné paměti. Jednotka podporuje možnost zmenšení potřebné paměti zavedením malého množství chyb. Datovou strukturu jednotky je možno umístit přímo do paměti na čipu nebo do externí paměti. V případě využití externí paměti jednotka maskuje latenci paměti paralelním zpracováním většího množství síťových toků. Přepnutí mezi toky nezanáší do vyhledávání žádné zpoždění. Experimenty s hardwarovou jednotkou ukázaly, že využití logických zdrojů čipu a frekvence jednotky nejsou závislé na množství a struktuře vyhledávaných regulárních výrazů.

The paper describes an architecture of the pattern matching unit for high speed networks. Presented architecture is able to work at 10Gbps networks . The implementation of the unit is based on the perfect hashing. A small probability of failure is inserted into the matching process to reduce memory consumption. The transition table of the automaton can be place into both onchip and off chip memory. It is possible to mask latency of the transitional memory by processing several network flows at once.