Show simple item record

2020-08-31Dissertation DOI: 10.18452/21780
System-Specialized and Hybrid Approaches to Network Packet Classification
dc.contributor.authorHager, Sven
dc.date.accessioned2020-08-31T13:25:59Z
dc.date.available2020-08-31T13:25:59Z
dc.date.issued2020-08-31none
dc.identifier.urihttp://edoc.hu-berlin.de/18452/22542
dc.description.abstractPaketklassifikation 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.ger
dc.description.abstractPacket 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.eng
dc.language.isoengnone
dc.publisherHumboldt-Universität zu Berlin
dc.rights(CC BY 4.0) Attribution 4.0 Internationalger
dc.rights.urihttps://creativecommons.org/licenses/by/4.0/
dc.subjectPaketklassifikationger
dc.subjectRegelsatztransformationger
dc.subjectHybride Klassifikationger
dc.subjectMaßgeschneiderte Matchingschaltkreiseger
dc.subjectPacket classificationeng
dc.subjectRule set transformationeng
dc.subjectHybrid classificationeng
dc.subjectTailormade matching circuitseng
dc.subject.ddc000 Informatik, Informationswissenschaft, allgemeine Werkenone
dc.titleSystem-Specialized and Hybrid Approaches to Network Packet Classificationnone
dc.typedoctoralThesis
dc.identifier.urnurn:nbn:de:kobv:11-110-18452/22542-4
dc.identifier.doihttp://dx.doi.org/10.18452/21780
dc.date.accepted2020-08-19
dc.contributor.refereeScheuermann, Björn
dc.contributor.refereeAschenbruck, Nils
dc.contributor.refereeWehrle, Klaus
dc.subject.rvkST 190
local.edoc.pages254none
local.edoc.type-nameDissertation
local.edoc.institutionMathematisch-Naturwissenschaftliche Fakultätnone

Show simple item record