Modern network devices need to perform deep packet in- spection at high speed for security and application-specific services. Finite Automata (FAs) are used to implement reg- ular expressions matching, but they require a large amount of memory. Many recent works have proposed improvements to address this issue. This paper presents a new representation for determinis- tic finite automata (orthogonal to previous solutions), called Delta Finite Automata (δFA), which considerably reduces states and transitions and requires a transition per char- acter only, thus allowing fast matching. Moreover, a new state encoding scheme is proposed and the comprehensive algorithm is tested for use in the packet classification area.

An Improved DFA for Fast Regular Expression Matching

GIORDANO, STEFANO;PROCISSI, GREGORIO;VITUCCI, FABIO;ANTICHI, GIANNI;
2008

Abstract

Modern network devices need to perform deep packet in- spection at high speed for security and application-specific services. Finite Automata (FAs) are used to implement reg- ular expressions matching, but they require a large amount of memory. Many recent works have proposed improvements to address this issue. This paper presents a new representation for determinis- tic finite automata (orthogonal to previous solutions), called Delta Finite Automata (δFA), which considerably reduces states and transitions and requires a transition per char- acter only, thus allowing fast matching. Moreover, a new state encoding scheme is proposed and the comprehensive algorithm is tested for use in the packet classification area.
Ficara, D; Giordano, Stefano; Procissi, Gregorio; Vitucci, Fabio; Antichi, Gianni; DI PIETRO, A.
File in questo prodotto:
File Dimensione Formato  
13/69059472278749571765082454551449255333

solo utenti autorizzati

Tipologia: Versione finale editoriale
Licenza: NON PUBBLICO - Accesso privato/ristretto
Dimensione 334.68 kB
Formato Unknown
334.68 kB Unknown   Visualizza/Apri   Richiedi una copia

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11568/201226
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 125
  • ???jsp.display-item.citation.isi??? 76
social impact