Bachelor's Thesis

Probabilistic Packet Classification Acceleration on FPGA

Final Thesis 1.77 MB

Author of thesis: Ing. Denis Kurka

Acad. year: 2022/2023

Supervisor: Ing. Lukáš Kekely, Ph.D.

Reviewer: Ing. Jiří Matoušek, Ph.D.

Abstract:

Classifying network packets is a crucial task in networking systems, as it allows for efficient routing and filtering of data. Probabilistic filters are a classification method that uses different techniques to approximate the membership of a packet in a set of rules. This work investigates three algorithms: Bloom, cuckoo, and xor filter. The main aim is to compare the performance of these three methods when implemented as hardware components in FPGA systems. The evaluation criteria include error rate, maximal frequency, and FPGA resource usage, primarily focusing on memory. The results indicate that the xor filter outperforms the others regarding error rate, which is superior in any error rate category. The Bloom filter is the fastest option for smaller and quicker components where a higher error rate is tolerable. The cuckoo filter is the most resource-efficient when FPGA logic is the primary concern. These findings contribute to the development of optimised classification systems and provide valuable insights into the possibilities of implementing probabilistic filters in hardware architectures.

Keywords:

packet filtering, FPGA, hardware architecture, cuckoo filter, Bloom filter, xor filter

Date of defence

13.06.2023

Result of the defence

Defended (thesis was successfully defended)

znamkaAznamka

Grading

A

Process of defence

Student nejprve prezentoval výsledky, kterých dosáhl v rámci své práce. Komise se poté seznámila s hodnocením vedoucího a posudkem oponenta práce. Student následně odpověděl na otázky oponenta a na další otázky přítomných. Komise se na základě posudku oponenta, hodnocení vedoucího, přednesené prezentace a odpovědí studenta na položené otázky rozhodla práci hodnotit stupněm A.

Topics for thesis defence

  1. Jak se změní závislost pravděpodobnosti falešně pozitivního výsledku klasifikace na počtu bitů na element v případě, že bude uvažována průměrná hodnota získaná z vícenásobného simulačního běhu Cuckoo filtru?
  2. Jak by bylo třeba rozšířit současnou implementaci statistických filtrů a příslušného testovacího prostředí, aby bylo možné simulovat klasifikaci milionů paketů pomocí extrémně přesných statistických filtrů přímo v FPGA?
  3. Víte, jak funguje metoda WaldBoost pro detekci obličeje?
  4. "Bits/Element" je šířka elementu v bitech?

Language of thesis

English

Faculty

Department

Study programme

Information Technology (BIT)

Composition of Committee

doc. Ing. Ondřej Ryšavý, Ph.D. (předseda)
doc. Ing. Vladimír Drábek, CSc. (člen)
Ing. Bohuslav Křena, Ph.D. (člen)
doc. Ing. Vítězslav Beran, Ph.D. (člen)
Dr. Ing. Petr Peringer (člen)

Supervisor’s report
Ing. Lukáš Kekely, Ph.D.

Student byl při vytváření práce aktivní a věnoval práci hodně času. Díky aktivnímu přístupu se mu podařilo splnit zadání ve všech bodech, a to s vynikajícími výsledky. Navíc nad rámec zadání student neimplementoval jen jeden, ale hned tři filtrační algoritmy, kterých parametry pak vzájemně podrobně porovnal. Výsledky práce student publikoval na studentské konferenci Excel@FIT a chceme je použít i při tvorbě publikace na mezinárodní konferenci. Kromě publikačního potenciálu jsou vytvořené implementace velmi dobře prakticky uplatnitelné. Jsou součástí open-source repozitáře FPGA modulů používaného při tvorbě aplikací pro monitorování vysokorychlostních sítí. Je proto studentem plánováno jejich další rozšiřování a nasazení do sítě ve spolupráci se sdružením CESNET.


Práce byla náročná rozsahem i řešenou problematikou, dosahuje výborných výsledků a je prakticky i publikačně uplatnitelná. Proto navrhuji hodnocení A (výborně) a navrhuji práci na cenu děkana.

Evaluation criteria Verbal classification
Informace k zadání

Cílem práce bylo nastudovat problematiku a seznámit se s několika algoritmy pro ne-exaktní klasifikaci paketů na základě políček z jejich hlaviček. V praktické části pak navázat vlastní implementací jedné zvolené nebo nově navržené metody pro hradlové pole FPGA a vyhodnocením jejich parametrů. Student toto zadání splnil s výrazným rozšířením. Místo výběru jen jedné metody se rozhodl implementovat všechny tři nastudované a porovnat jejich parametry navzájem mezi sebou. Navíc pak sám identifikoval vzájemné podobnosti mezi třemi tvořenými moduly na úrovni nejen samotného HDL popisu, ale také jejich softwarové konfigurace nebo funkční verifikace. Při implementaci si tak vhodnou abstrakcí vyčlenil společné části, které elegantně znovupoužil a ušetřil si zbytečnou re-implementaci. Ušetřený čas pak student raději věnoval dalšímu rozšíření práce z pohledu identifikace a přidání vlastních nastavení do implementovaných algoritmů, kterými je možné dále ovládat výsledné parametry filtrace. Práce byla náročná rozsahem i řešenou tématikou a výrazně svou šíří převyšuje standard běžné bakalářské práce. O kvalitě výsledného řešení svědčí nejen efektivní a precizně otestovaná implementace, ale i kvalitně zpracovaná technická zpráva, které je celá napsána v anglickém jazyku.

Práce s literaturou

Student čerpal z velkého množství literatury jak doporučené, tak z literatury získané vlastní aktivitou.

Aktivita během řešení, konzultace, komunikace

Student byl během řešení bakalářské práce iniciativní. Pravidelně konzultoval navrhovaná řešení se svým vedoucím i s dalšími kolegy ze sdružení CESNET. Na konzultace byl vždy připraven a dané problematice vždy rozuměl.

Aktivita při dokončování

Práce byla dokončena v termínu. Obsah i výsledky byly před odevzdáním v dostatečném předstihu konzultovány.

Publikační činnost, ocenění

Student úspěšně prezentoval výsledky své práce na studentské soutěži Excel@FIT. Tyto výsledky mají také další publikační potenciál a je plánováno podání posteru na vybrané odborné mezinárodní konferenci zaměřené na technologii FPGA. Implementace modulů vytvořené v práci jsou součástí open-source repozitáře OFM spravovaného sdružením CESNET. V spolupráci studenta se sdružením je plánován také další rozvoj a praktické využití vytvořených modulů v aplikacích pro filtrování reálného provozu na vysokokapacitních linkách páteřních sítí.

Points proposed by supervisor: 95
Display more

Grade proposed by supervisor: A

Reviewer’s report
Ing. Jiří Matoušek, Ph.D.

Ačkoliv bylo zadání hodnocené bakalářské práce mírně obtížnější, student jej ve všech bodech splnil a navíc vypracoval i části, které jdou nad rámec původního zadání. Realizační výstupy i technická zpráva jsou vypracovány v nadstandardní kvalitě, přičemž text technické zprávy je psán v angličtině. Navrhuji proto hodnocení stupněm výborně / A.

Evaluation criteria Verbal classification Points
Náročnost zadání

Evaluation level: obtížnější zadání

Zadání hodnocené bakalářské práce považuji za obtížnější především pro požadavek na implementaci zvolené metody pro statistickou klasifikaci síťových paketů v FPGA, ačkoliv běžně jsou v literatuře popisovány pouze softwarové implementace těchto metod.

Rozsah splnění požadavků zadání

Evaluation level: zadání splněno a práce obsahuje podstatná rozšíření

Student nad rámec zadání implementoval nejen jednu, ale všechny tři nastudované metody pro statistickou klasifikaci síťových paketů. Zároveň svou implementaci vhodně rozdělil na části specifické pro jednotlivé metody a části společné pro všechny metody. Výstupem bakalářské práce je tedy komplexní systém umožňující ověřovat parametry implementací jednotlivých metod v FPGA a také verifikovat jejich správnou funkci oproti modelu v software.

Rozsah technické zprávy

Evaluation level: je v obvyklém rozmezí

Rozsah technické zprávy se pohybuje okolo spodní hranice obvyklého rozmezí. Technická zpráva však obsahuje všechny požadované části a žádné podstatné informace v ní ani nechybí, ani nepřebývají.

Prezentační úroveň technické zprávy

Technická zpráva je vhodně rozčleněna do přiměřeně dlouhých kapitol, které na sebe plynule navazují. Z pohledu čtenáře je technická zpráva velmi dobře čitelná a snadno pochopitelná, čemuž napomáhá i řada kvalitně zpracovaných obrázků. Jedinou drobnou výtku mám ke způsobu prezentace konstrukčního algoritmu xor filtru (podkapitola 3.3), respektive jeho modifikované varianty (podkapitola 5.4), kde bych doporučil doplnění textového popisu pseudokódem algoritmu. Zároveň bych doporučil namísto opakování rovnic (např. rovnice 4.1 a 4.2, které jsou stejné jako rovnice 3.4 a 3.5) uvést odkaz na jejich původní výskyt, aby bylo jasné, že se nejedná o nové rovnice.

92
Formální úprava technické zprávy

Ačkoliv je technická zpráva psaná v anglickém jazyce, lze jí po jazykové stránce jen máloco vytknout (drobné překlepy a chyby ve členech či předložkách se vyskytují opravdu výjimečně). Výjimku tvoří jen zvláštní věty na začátku některých odstavců (např. odstavec 3 na straně 9), které by dávaly větší smysl při spojení s bezprostředně navazujícími větami.

Z typografického hlediska nemám technikcé zprávě co vytknout.

95
Práce s literaturou

Student pracoval s relevantními literárními zdroji, které v rámci technické zprávy vhodným způsobem citoval. S výjimkou zdroje [9] jsou všechny bibliografické citace v souladu s citačními zvyklostmi.

93
Realizační výstup

Realizační výstup je vytvořen v odpovídající kvalitě a je přiměřeně dokumentován.

85
Využitelnost výsledků

Výstupem hodnocené bakalářské práce jsou předeším FPGA implementace tří statistických metod pro klasifikaci paketů, prostředí pro funkční verifikaci těchto implementací, systém pro experimentování s vytvořenými implementacemi umožňující měření jejich parametrů a v neposlední řadě také výsledky provedených měření.

Vytvořené implementace statistických klasifikačních metod mají dle mého názoru značný potenciál na praktické využití sdružením CESNET při realizaci systémů pro zpracování dat ve vysokorychlostních počítačových sítích. Na tento potenciál ukazuje i skutečnost, že vývoj probíhal v rámci repozitáře pro open-source FPGA moduly, který je sdružením CESNET spravován.

Výsledky provedených měření pak mají značný publikační potenciál, jelikož představují vlastnosti FPGA implementací statistických metod pro klasifikaci paketů, které jsou v dosutpné literatuře typicky představovány jen ve formě softwarového modelu.

Topics for thesis defence:
  1. Jak se změní závislost pravděpodobnosti falešně pozitivního výsledku klasifikace na počtu bitů na element v případě, že bude uvažována průměrná hodnota získaná z vícenásobného simulačního běhu Cuckoo filtru?
  2. Jak by bylo třeba rozšířit současnou implementaci statistických filtrů a příslušného testovacího prostředí, aby bylo možné simulovat klasifikaci milionů paketů pomocí extrémně přesných statistických filtrů přímo v FPGA?
Points proposed by reviewer: 95
Display more

Grade proposed by reviewer: A