1 Introduzione
Classificare in maniera efficace i pacchetti è un’esigenza sempre più presente nelle moderne reti di telecomunicazioni, rivolte ad offrire QoS (Quality of Service) e garanzie di sicurezza per un numero di servizi in continua crescita. Sebbene nel corso degli anni siano state avanzate numerose proposte in quest’area di ricerca, nessuna di esse può dirsi la soluzione definitiva per tutti gli scenari. Le tecniche attuali privilegiano, a seconda dei contesti, ridotte occupazioni di memoria o velocità di classificazione elevate.
In questo lavoro di tesi si propone l’impiego di automi a stati finiti per rappresentare l’insieme di regole del classificatore. Gli automi a
Capitolo 1
2
stati finiti sono sistemi derivati dalla teoria dei linguaggi formali, in grado di scandire ordinatamente stringhe di simboli alla ricerca di pattern specifici. Essi vengono impiegati correntemente nelle applicazioni di deep packet inspection perché garantiscono espressività molto maggiori rispetto alle tradizionali tecniche di “exact string matching”. L’algoritmo scelto per l’implementazione descrive un nuovo tipo di automa, detto δ-FA (δ Finite Automata), il quale presenta interessanti caratteristiche prestazionali. In particolare, oltre a mantenere una struttura dati molto più compatta rispetto a quella di un’automa standard, necessita di effettuare un numero di accessi in memoria assai contenuto. Tali proprietà motivano il suo impiego per la classificazione in reti ad elevate capacità trasmissive, dove la latenza delle memorie rappresenta il principale fattore di degrado delle prestazioni.
La piattaforma hardware utilizzata è la scheda NetFPGA. Si tratta di una scheda PCI composta da un chip FPGA (Field Programmable
Gate Array) interamente programmabile, da quattro porte Gigabit
Ethernet e da alcuni banchi di memoria con densità e latenze diverse (sia SRAM che DRAM). Questo dispositivo viene impiegato da studenti e ricercatori per sperimentare nuove funzionalità di rete a velocità di linea. La scheda NetFPGA è stata ideata dall’università di Stanford come parte di un progetto denominato Clean Slate, un ambizioso programma di ricerca che si propone di far nascere
Introduzione
3
soluzioni volte a superare i limiti della Internet odierna. L’FPGA viene programmata col supporto di un linguaggio di descrizione dell’hardware (Hardware Description Language, HDL), che in questo caso è il Verilog.Il progetto realizzato comprende anche un ulteriore blocco a valle del classificatore che utilizza i dati prodotti da quest’ultimo per generare trame batch. Una trama batch riunisce al suo interno informazioni relative a più pacchetti, che sono d’interesse per qualche applicazione. La struttura complessiva può diventare il componente di distribuzione primaria per architetture di monitoraggio del traffico distribuite, ovvero il nodo che effettua un primo filtraggio dei pacchetti e lo smistamento delle trame batch costruite a partire da essi verso stazioni di misura remote.
Nel secondo capitolo vengono descritte le principali caratteristiche della piattaforma NetFPGA e si danno alcuni cenni sui fondamenti del linguaggio Verilog necessario a configurarla. Nel terzo capitolo, dopo una breve introduzione alla teoria degli automi a stati finiti e dei linguaggi regolari, si analizzano diverse tipologie di automi con le relative caratteristiche implementative. Il quarto capitolo descrive l’automa scelto per la classificazione, il δ-FA, ed illustra i passaggi dell’implementazione su scheda della piattaforma di classificazione. Infine nel capitolo quinto si mostrano i risultati delle simulazioni e le valutazioni sulle prestazioni.
