Packet classification plays an important role in next generation networks. Packet classification is important to fulfill the requirements for many applications including firewalls, multimedia services, intrusion detection services, and differentiated services to name just a few. Hardware solutions such as CAM/TCAM do not scale well in space. Current software-based packet classification algorithms exhibit relatively poor performance, prompting many researchers to concentrate on novel frameworks and architectures that employ both hardware and software components. In this thesis we propose two novel algorithms, Packet Classification with Incremental Update (PCIU) and Group Based Search packet classification Algorithm (GBSA), that are scalable and demonstrate excellent results in terms of preprocessing and classification. The PCIU algorithm is an innovative and efficient packet classification algorithm with a unique incremental update capability that demonstrates powerful results and is accessible for many different tasks and clients. The algorithm was further improved and made more available for a variety of applications through its implementation in hardware. Four such implementations are detailed and discussed in this thesis. A hardware accelerator based on an ESL approach, using Handel-C, resulted in a 22x faster classification than a pure software implementation running on a state of the art Xeon processor. An ASIP implementation achieved on average a 21x quicker classification. We also propose another novel algorithm, GBSA, for packet classification that is scalable, fast and efficient. On average the algorithm consumes 0.4 MB of memory for a 10k rule set. In the worst case scenario, the classification time per packet is 2 μs, and the pre-processing speed is 3M Rule/sec, based on a CPU operating at 3.4 GHz. The proposed algorithm was evaluated and compared to state-of-the-art techniques, such as RFC, HiCut, Tuple, and PCIU, using several standard benchmarks. The obtained results indicate that GBSA outperforms these algorithms in terms of speed, memory usage and pre-processing time. The algorithm, furthermore, was improved and made more accessible for a variety of applications through implementation in hardware. Three approaches using this algorithm are detailed and discussed in this thesis. The first approach was implemented using an Application Specific Instruction Processor (ASIP), while the others were pure RTL implementations using two different ESL flows (Impulse-C and Handel-C). The GBSA ASIP implementation achieved, on average, a 18x faster running speed than a pure software implementation operating on a Xeon processor. Conversely, the hardware accelerators (based on the ESL approaches) resulted in 9x faster processing.

This diploma thesis deals with packet classification in computer networks. The problem of packet classification is described, together with requirements for classification algorithm. Then, necessary theoretical background is introduced. Contemporary approaches to the classification are described, together with the critique of the current state of the field. The main focus of the work is the new algorithm of packet classification based on problem decomposition. Unique property of the algorithm is constant time complexity in terms of external memory accesses. Algorithm implemetation is proposed, using FPGA and one external memory. Planned prototype may achieve throughput of 64 Gbit/s in the worst case.

Tato práce se zabývá klasifikací paketů v počítačových sítích. Klasifikace paketů je klíčovou úlohou mnoha síťových zařízení, především paketových filtrů - firewallů. Práce se tedy týká oblasti počítačové bezpečnosti. Práce je zaměřena na vysokorychlostní sítě s přenosovou rychlostí 100 Gb/s a více. V těchto případech nelze použít pro klasifikaci obecné procesory, které svým výkonem zdaleka nevyhovují požadavkům na rychlost. Proto se využívají specializované technické prostředky, především obvody ASIC a FPGA. Neméně důležitý je také samotný algoritmus klasifikace. Existuje mnoho algoritmů klasifikace paketů předpokládajících hardwarovou implementaci, přesto však tyto přístupy nejsou připraveny pro velmi rychlé sítě. Dizertační práce se proto zabývá návrhem nových algoritmů klasifikace paketů se zaměřením na vysokorychlostní implementaci ve specializovaném hardware. Je navržen algoritmus, který dělí problém klasifikace na jednodušší podproblémy. Prvním krokem je operace vyhledání nejdelšího shodného prefixu, používaná také při směrování paketů v IP sítích. Tato práce předpokládá využití některého existujícího přístupu, neboť již byly prezentovány algoritmy s dostatečnou rychlostí. Následujícím krokem je mapování nalezených prefixů na číslo pravidla. V této části práce přináší vylepšení využitím na míru vytvořené hashovací funkce. Díky použití hashovací funkce lze mapování provést v konstantním čase a využít při tom pouze jednu paměť s úzkým datovým rozhraním. Rychlost tohoto algoritmu lze určit analyticky a nezávisí na počtu pravidel ani na charakteru síťového provozu. S využitím dostupných součástek lze dosáhnout propustnosti 266 milionů paketů za sekundu. Následující tři algoritmy uvedené v této práci snižují paměťové nároky prvního algoritmu, aniž by ovlivňovaly rychlost. Druhý algoritmus snižuje velikost paměti o 11 % až 96 % v závislosti na sadě pravidel. Nevýhodu nízké stability odstraňuje třetí algoritmus, který v porovnání s prvním zmenšuje paměťové nároky o 31 % až 84 %. Čtvrtý algoritmus kombinuje třetí algoritmus se starším přístupem a díky využití několika technik zmenšuje paměťové nároky o 73 % až 99 %.

Networking and distributed computing system have provided computational resources for machine learning (ML) application for a long time. Network system itself also can benefit from ML technologies. For example high performance packet classification is a key component to support scalable network applications like firewalls, intrusion detection, and differentiated services. With ever increasing demand in the line rate for core networks, a great challenge is to use hand-tuned heuristic approaches to design a scalable and high performance packet classification solution. By exploiting the sparsity present in a ruleset, in this thesis an algorithm is proposed to use few effective bits (EBs) to extract a large number of candidate rules with just a few number of memory access. These effective bits are learned with deep reinforcement learning and they are used to create a bitmap to filter out the majority of rules which do not need to be fully matched to improve the online system performance. Utilizing reinforcement learning allows the proposed solution to be learning based rather than heuristic based algorithms. So proposed learning-based selection method is independent of the ruleset, which can be applied to different rulesets without relying on the heuristics. Proposed multibit tries classification engine outperforms lookup time both in worst and average case by 55% and reduce memory footprint, compared to traditional decision tree without EBs. Furthermore, many field packet classification are required for openFlow supported switches. With the proliferation of fields in the packet header, a traditional 5-field classification technique isn’t applicable for an efficient classification engine for those openFlow supported switches. Although the algorithmic insights obtained from 5-field classification techniques could still be applied for many field classification engine. To decompose given fields of a ruleset, different grouping metrics like standard deviation of individual fields and a novel metric called Diversity Index (DI) is considered for such many field scenarios. A detailed discussion and evaluation of how to decompose rule fields/dimension into subgroup, how a decision tree construction can be considered as reinforcement learning problem, and how to encode state and action space, reward calculation to effectively build trees for each subgroup with a global optimization objective is introduced in this work. Finally, to identify benign or malicious heterogeneous type of traffic present in a modern home network, a deep neural network based approach is introduced. A split architecture of such traffic classifier, in application of home network intrusion detection system consists of multiple machine learning (ML) models. These models trained on two separate dataset for heterogeneous traffic types. An analysis of run-time implementation performance of the proposed IDS models is also discussed.

A substantial increase in the number of internet users and the traffic volume bring new challenges for network router design. The current routers need to support higher link data rates and large number of line cards to accommodate the growth of the internet traffic, which necessitate an increase in physical space, power and memory use. Packet forwarding, which is one of the major tasks of a router, has been a performance bottleneck in internet infrastructure. In general, most of the packet forwarding algorithms are implemented in software. However, hardware based solutions has also been popular in recent years because of their high throughput performance. Besides throughput, memory efficiency, incremental/dynamic updates and power consumption are the basic performance challenges for packet forwarding architectures. Hardware-based packet forwarding engines for network routers can be categorized into two groups that are ternary content addressable memory (TCAM) based and dynamic/static random access memory (DRAM/SRAM) based solutions. TCAM-based architectures are simple and hence popular solutions for today&rsquo / s routers. However, they are expensive, power-hungry, and oer little adaptability to new addressing and routing protocols. On the other hand, SRAM has higher density, lower power consumption, and higher speed. The common data structure used in SRAM-based solutions for performing longest prefix matching (LPM) is some type of a tree. In these solutions, multiple memory accesses are required to find the longest matched prefix. Therefore, parallel and pipelining techniques are used to improve the throughput. This thesis studies TCAM and SRAM based parallel and pipelined architectures for high performance packet forwarding. We proposed to use a memory efficient disjoint prefix set algorithm on TCAM based parallel IP packet forwarding engine to improve its performance. As a fundamental contribution of this thesis, we designed an SRAM based parallel, intersecting and variable length multi-pipeline array structure (SAFIL) for trie-based internet protocol (IP) lookup. We also proposed a novel dual port SRAM based high throughput IP lookup engine (SAFILD) which is built upon SAFIL. As an alternative to traditional binary trie, we proposed a memory efficient data structure called compact clustered trie (CCT) for IP lookup. Furthermore, we developed a novel combined length-infix pipelined search (CLIPS) architecture for high performance IPv4/v6 lookup on FPGA. Finally, we designed a memory efficient clustered hierarchical search structure (CHSS) for packet classification. A linear pipelined SRAM-based architecture for CHSS which is implemented on FPGA is also proposed.

This master thesis focuses on filtering and forwarding packets in high speed networks. Firstly the DPDK framework is introduced, which is used for fast packet processing. This project also introduces a design of application for high-speed packet filtering and design of tools for making it easier to work with that application. Subsequently, the implementation of this design is introduced and testing with comparison of results with a standard firewall

Pokrok při zdokonalování klasifikačních algoritmů je zpomalován nedostatkem dat potřebných pro testování. Reálná data je obtížné získat z důvodu bezpečnosti a ochrany citlivých informací. Existují však generátory syntetických sad pravidel, jako například ClassBench-ng. K vyhodnocení správného fungování, propustnosti, spotřeby energie a dalších vlastností klasifikačních algoritmů je zapotřebí také vhodný síťový provoz. Tématem této práce je tvorba takového generátoru síťového provozu, který by umožnil testování těchto vlastností v kombinaci s IPv4, IPv6 a OpenFlow1.0 pravidly vygenerovanými ClassBench-ng. Práce se zabývá různými způsoby, jak toho dosáhnout, které vedly k vytvoření několika verzí generátoru. Vlastnosti jednotlivých verzí byly zkoumány řadou experimentů. Implementace byla provedena pomocí jazyku Python. Nejvýznamnějším výsledkem je generátor, který využívá principů několika zkoumaných přístupů k dosažení co nejlepších vlastností. Dalším přínosem je nástroj, který bylo nutné vytvořit pro analýzu užitých sad klasifikačních pravidel a vyhodnocení vlastností vygenerovaného síťového provozu.

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.

This thesis particularly deals with design and implementation of FPGA unit, which performs hardware acclerated header field extraction of network packets. By utilizing NetCOPE platform it is proposed flexible and effective high-peformance solution for high-speed networks. A theoretical part presents a classical protocol model and an analysis of the Internet traffic. Main part of the thesis is further focused on key issues in hardware packet preprocessing, such as packet classification and deep packet inspection. The author of this thesis also discusses possible technology platforms, which can be utilized to acceleration of network applications.

Power grids have rapidly evolved into Smart grids and are heavily dependent on Supervisory Control and Data Acquisition (SCADA) systems for monitoring and control. However, this evolution increases the susceptibility of the remote (VMs, VPNs) and physical interfaces (sensors, PMUs LAN, WAN, sub-stations power lines, and smart meters) to sophisticated cyberattacks. The continuous supply of power is critical to power generation plants, power grids, industrial grids, and nuclear grids; the halt to global power could have a devastating effect on the economy's critical infrastructures and human life. Machine Learning and Deep Learning-based cyberattack detection modeling have yielded promising results when combined as a Hybrid with an Intrusion Detection System (IDS) or Host Intrusion Detection Systems (HIDs). This thesis proposes two cyberattack detection techniques; one that leverages Machine Learning algorithms and the other that leverages Artificial Neural networks algorithms to classify and detect the cyberattack data held in a foundational dataset crucial to network intrusion detection modeling. This thesis aimed to analyze and evaluate the performance of a Hybrid Machine Learning (ML) and a Hybrid Deep Learning (DL) during ingress packet filtering, class classification, and anomaly detection on a Smart grid network.