HyperCuts pro filtrování Linuxových paketů

Abstract

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...