HyperCuts pro filtrování Linuxových paketů
HyperCuts pro filtrování Linuxových paketů
bachelor thesis (DEFENDED)
View/ Open
Permanent link
http://hdl.handle.net/20.500.11956/6983Identifiers
Study Information System: 44412
Collections
- Kvalifikační práce [10925]
Author
Advisor
Referee
Peterka, Jiří
Faculty / Institute
Faculty of Mathematics and Physics
Discipline
Programming
Department
Department of Applied Mathematics
Date of defense
18. 9. 2006
Publisher
Univerzita Karlova, Matematicko-fyzikální fakultaLanguage
English
Grade
Excellent
Filtrování paketů pomocí multidimensionálního štěpení je jedním z nových přístupů k této problematice klasifikace paketů. Základem je vytváření stromu, který obsahuje zadaná pravidla pro filtraci. Matchování paketu je v tomto případě podstatně rychlejší než lineární procházení všech pravidel. Metoda HyperCuts je jednou z nejnovějších metod založených na multidimensionálním štěpení. Implementace této metody na první pohled ukáala její použitelnost. Závěrečné rozhodnutí o využití programu HyperCuts v praxi je věak možné učinit pouze na základě výsledků testování v reálném provozu. Ve srovnání s programem PTree, který je založen na metodě zvané TBF, byl HyperCuts úspěšnější. Srovníní bylo prováděno spíše z pohledu přístupu k problému, než z implementačního pohledu nebo na základě úspěšnosti se stejnými daty. Tam, kde bylo odkazováno na implementaci PTree, bylo odkázáno i na naši implementaci HyperCuts. Srovnávána byla jak časová tak prostorová složitost. V teoretické části je zdůvodněno použití formátu "range match" (neboli intervalového formátu). Také je zde definován pojem "cut" (neboli řez), který je velice výhodný pro počítání složitosti jak časové tak prostorové. Jedním z úkolů práce bylo implementovat metodu HyperCuts, a proto je její součístí práce také uživatelský a programátorský manuál.
Filtering of packets by multidimensional cutting is one of the new approaches to the solution of the packet classiffication problem. It is based on creating a tree that contains the set rules of filtering. In this case a packets matching is considerably faster than linear traversing of all rules. The HyperCuts methods are one of the latest methods that use multidimensional cutting. At first sight the implementation of the HyperCuts method demonstrated its utility. However, the final decision about the usage of the HyperCuts program in practice can be made only on the basis of the results of testing in it is necessary to can be using in a practice it have to be tested in practical operation. In comparison with the PTree program, which is based on the TBF method, the HyperCuts program, was more successful. The comparison was based on resolving the problem rather than on implementation aspect or success with the same data. In case, where we use PTree source code for confrontation, we compare it with source code of HyperCuts from our implementation. We compare time and memory complexity. In the theoretic part there is explain why the "range match" was used. There is definition of term "cut" which is very advantageous for time and memory complexity. One of the goals of the work was HyperCuts method...