Optimization of Crossproduct-Based Classification Algorithms

Tato diplomová práce se zabývá problematikou klasifikace paketů v počítačových sítích. Přibližuje problém klasifikace spolu s požadavky kladenými na klasifikační algoritmy. Popsány jsou různé přístupy ke klasifikaci paketů a jsou přiblíženy konkrétní příklady moderních algoritmů implementovatelných obvodově spolu s jejich vlastnostmi. Pozornost je věnována algoritmům kartézského součinu, jejichž výhodou je vysoká rychlost, ale mají problém s velkými paměťovými nároky. Představeny jsou metody optimalizace těchto algoritmů založené na prohledávání stavového prostoru a to redukcí původní sady filtrovacích pravidel jejich výběrem do asociativní paměti. Práce také ilustruje využití asociativní paměti jako flexibilní možnost ke klasifikaci a možnost implementace takovéto paměti přímo na čipu.This thesis deals with the packet classification problem in computer networks. It introduces packet classification along with the demands on classification algorithms. Different approaches to packet classification and several concrete examples of modern classification algorithms with their properties are described. The aim is on algorithms which can be implemented in hardware. Crossproduct-based algorithms are described in more detail whose biggest advantage is classification speed, but their disadvantage consists in great memory requirements. Several optimization methods based on state space search are presented. These optimization methods are based on reduction of original ruleset by selecting a small number of rules to associative memory. Lastly, utilization of associative memory as a flexible part of classification is illustrated together with the potential hardware implementation of such memory directly on a chip.