Přístupnostní navigace
E-application
Search Search Close
Bachelor's Thesis
Author of thesis: Ing. Denis Kurka
Acad. year: 2022/2023
Supervisor: Ing. Lukáš Kekely, Ph.D.
Reviewer: Ing. Jiří Matoušek, Ph.D.
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.
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)
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
Language of thesis
English
Faculty
Fakulta informačních technologií
Department
Department of Computer Systems
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 reportIng. 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.
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.
Student čerpal z velkého množství literatury jak doporučené, tak z literatury získané vlastní aktivitou.
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.
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.
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í.
Grade proposed by supervisor: A
Reviewer’s reportIng. 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 level: more difficult assignment
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.
Evaluation level: assignment fulfilled, and the work contains significant extensions
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.
Evaluation level: is within the usual extent
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í.
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.
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.
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.
Realizační výstup je vytvořen v odpovídající kvalitě a je přiměřeně dokumentován.
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.
Grade proposed by reviewer: A
Responsibility: Mgr. et Mgr. Hana Odstrčilová