Paketklassifikation ist eine Kernfunktionalität vieler Netzwerksysteme, wie zum Beispiel Firewalls und SDN-Switches. Für viele dieser Systeme ist Durchsatz von höchster Bedeutung. Weitere wichtige Eigenschaften sind dynamische Aktualisierbarkeit und hohe Regelsatz-Ausdrucksfähigkeit. Die Kombination dieser Eigenschaften macht Paketklassifikation zu einem schwierigen Problem. Diese Arbeit befasst sich mit dem Design von Klassifikationssystemen und -algorithmen, welche mindestens zwei dieser Eigenschaften vereinen. Es werden hybride Systeme sowie Systemspezialisierung verwendet, um effiziente Ansätze zum Paketklassifikationsproblem in drei Bereichen zu erarbeiten: Klassifikationsalgorithmen, Regelsatztransformation und hardwarebasierte Architekturen. Die Beiträge im Bereich der Klassifikationsalgorithmen sind Jit Vector Search (JVS) und das SFL-System. JVS verbessert existierende Techniken durch spezialisierte Suchdatenstrukturen und durch Nutzung von SIMD-Fähigkeiten der CPU, was in fast optimaler Klassifikationsperformanz bei kaum erhöhten Vorberechnungszeiten resultiert. Das hybride SFL-System hingegen kombiniert einen Klassifikationsalgorithmus mit einem Änderungspuffer, um sowohl hohe Klassifikations- als auch Aktualisierungsperformanz zu ermöglichen. Bezüglich Regelsatztransformationen wird die RuleBender-Technik vorgestellt, welche Suchbäume in Regelsätze für Firewalls mit Sprungsemantik kodiert. Somit kann der Durchsatz dieser Systeme unter Beibehaltung komplexer Regelsatzsemantik um eine Größenordnung gesteigert werden. Schließlich wird der MPFC-Ansatz vorgestellt, welcher einen Regelsatz in einen auf einem FPGA implementierbaren Matching-Schaltkreis übersetzt. Die generierten Schaltkreise sind hochoptimiert und kleiner als generische Matching-Schaltkreise. Um dynamische Regelsatzänderungen zu ermöglichen, wird der hybride Consul-Ansatz konzipiert, welcher MPFC-Matcher mit generischen Matching-Schaltkreisen kombiniert. / Packet classification is a core functionality of a wide variety of network systems, such as firewalls and SDN switches. For many of these systems, throughput is of paramount importance. Further important system traits are dynamic updateability and high expressiveness in terms of rule set semantics. The combination of several of these properties turns packet classification into a hard problem. This work focuses on the design of classification systems and algorithms that combine at least two of the abovementioned characteristics. To this end, the concepts of hybrid systems and system specialization are employed to obtain efficient approaches to the packet classification problem in three domains: classification algorithms, rule set transformation, and hardware-centric architectures. The contributions in the domain of classification algorithms are Jit Vector Search (JVS) and the SFL system. JVS improves upon existing techniques through specialized search data structures and by exploiting SIMD capabilities of the underlying CPU, which results in near-optimal classification performance at only slightly increased preprocessing times. In contrast, the SFL system is a hybrid approach that combines a classification algorithm with an update buffer to allow for high classification as well as update performance. With respect to rule set transformation, the RuleBender technique is proposed, which encodes search tree structures into rule sets of firewalls with jump semantics. That way, the throughput of these systems can be improved by an order of magnitude, while maintaining complex matching semantics. Finally, the MPFC approach is proposed, which translates a given rule set into a matching circuit that can be implemented on an FPGA. The generated circuits are highly optimized and significantly smaller than those of generic matchers. To allow for dynamic rule set updates, the hybrid Consul approach is devised, which combines MPFC circuits with a generic matcher.

Die Menge an in Computernetzwerken verarbeiteten Daten steigt stetig, was Netzwerkgeräte wie Switches, Bridges, Router und Firewalls vor Herausfordungen stellt. Die Performance der verbreiteten, CPU/softwarebasierten Ansätze für die Implementierung dieser Aufgaben ist durch den inhärenten Overhead in der sequentiellen Datenverarbeitung limitiert, weshalb solche Funktionalitäten vermehrt auf dedizierten Hardwarebausteinen realisiert werden. Diese bieten eine schnelle, parallele Verarbeitung mit niedriger Latenz, sind allerdings aufwendiger in der Entwicklung und weniger flexibel. Nicht jede Anwendung kann zudem für parallele Verarbeitung optimiert werden. Diese Arbeit befasst sich mit hybriden Ansätzen, um eine bessere Ausnutzung der jeweiligen Stärken von Soft- und Hardwaresystemen zu ermöglichen, mit Schwerpunkt auf der Paketklassifikation. Es wird eine Firewall realisiert, die sowohl Flexibilität und Analysetiefe einer Software-Firewall als auch Durchsatz und Latenz einer Hardware-Firewall erreicht. Der Ansatz wird auf einem Standard-Rechnersystem, welches für die Hardware-Klassifikation mit einem rekonfigurierbaren Logikbaustein (FPGA) ergänzt wird, evaluiert. Eine wesentliche Herausforderung einer hybriden Firewall ist die Identifikation von Abhängigkeiten im Regelsatz. Es werden Ansätze vorgestellt, welche den redundanten Klassifikationsaufwand auf ein Minimum reduzieren, wie etwa die Wiederverwendung von Teilergebnissen der hybriden Klassifikatoren oder eine exakte Abhängigkeitsanalyse mittels Header Space Analysis. Für weitere Problemstellungen im Bereich der hardwarebasierten Paketklassifikation, wie dynamisch konfigurierbare Filterungsschaltkreise und schnelle, sichere Hashfunktionen für Lookups, werden Machbarkeit und Optimierungen evaluiert. Der hybride Ansatz wird im Weiteren auf ein System mit einer SDN-Komponente statt einer FPGA-Erweiterung übertragen. Auch hiermit können signifikante Performancegewinne erreicht werden. / Network devices like switches, bridges, routers, and firewalls are subject to a continuous development to keep up with ever-rising requirements. As the overhead of software network processing already became the performance-limiting factor for a variety of applications, also former software functions are shifted towards dedicated network processing hardware. Although such application-specific circuits allow fast, parallel, and low latency processing, they require expensive and time-consuming development with minimal possibilities for adaptions. Security can also be a major concern, as these circuits are virtually a black box for the user. Moreover, the highly parallel processing capabilities of specialized hardware are not necessarily an advantage for all kinds of tasks in network processing, where sometimes a classical CPU is better suited. This work introduces and evaluates concepts for building hybrid hardware-software-systems that exploit the advantages of both hardware and software approaches in order to achieve performant, flexible, and versatile network processing and packet classification systems. The approaches are evaluated on standard software systems, extended by a programmable hardware circuit (FPGA) to provide full control and flexibility. One key achievement of this work is the identification and mitigation of challenges inherent when a hybrid combination of multiple packet classification circuits with different characteristics is used. We introduce approaches to reduce redundant classification effort to a minimum, like re-usage of intermediate classification results and determination of dependencies by header space analysis. In addition, for some further challenges in hardware based packet classification like filtering circuits with dynamic updates and fast hash functions for lookups, we describe feasibility and optimizations. At last, the hybrid approach is evaluated using a standard SDN switch instead of the FPGA accelerator to prove portability.