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.
| Identifer | oai:union.ndltd.org:HUMBOLT/oai:edoc.hu-berlin.de:18452/22542 |
| Date | 31 August 2020 |
| Creators | Hager, Sven |
| Contributors | Scheuermann, Björn, Aschenbruck, Nils, Wehrle, Klaus |
| Publisher | Humboldt-Universität zu Berlin |
| Source Sets | Humboldt University of Berlin |
| Language | English |
| Detected Language | English |
| Type | doctoralThesis, doc-type:doctoralThesis |
| Format | application/pdf |
| Rights | (CC BY 4.0) Attribution 4.0 International, https://creativecommons.org/licenses/by/4.0/ |
Page generated in 0.0025 seconds