Packet Classification Using FPGA Technology

Tato diplomová práce se zabývá klasifikací paketů v počítačových sítích. Je popsán problém klasifikace paketů a jsou definovány požadavky, které musí splňovat klasifikační algoritmus. Dále je zavedena potřebná teorie a popsány současné přístupy ke klasifikaci paketů, spolu s kritikou současného stavu v této oblasti. Těžištěm práce je nový algoritmus klasifikace paketů založený na dekompozici problému. Unikátní vlastností algoritmu je konstantní časová složitost vzhledem k počtu přístupů do externí paměti. Je navržena implementace algoritmu v FPGA s využitím jedné externí paměti. Plánovaný prototyp může dosáhnout propustnosti 64 Gbit/s v nejhorším případě.This diploma thesis deals with packet classification in computer networks. The problem of packet classification is described, together with requirements for classification algorithm. Then, necessary theoretical background is introduced. Contemporary approaches to the classification are described, together with the critique of the current state of the field. The main focus of the work is the new algorithm of packet classification based on problem decomposition. Unique property of the algorithm is constant time complexity in terms of external memory accesses. Algorithm implemetation is proposed, using FPGA and one external memory. Planned prototype may achieve throughput of 64 Gbit/s in the worst case.