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.
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
- 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?
- 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?
- Víte, jak funguje metoda WaldBoost pro detekci obličeje?
- "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.
Grade proposed by supervisor: A
Reviewer’s report
Ing. Jiří Matoušek, Ph.D.
Grade proposed by reviewer: A