Packet classification is an important part of many networking devices, such as routers and firewalls. Software-defined networking (SDN) heavily relies on online packet classification which must efficiently process two different streams: incoming packets to classify and rules to update. This rules out many offline packet classification algorithms that do not support fast updates. We propose a novel online classification algorithm, TupleMerge (TM), derived from tuple space search (TSS), the packet classifier used by Open vSwitch (OVS). TM improves upon TSS by combining hash tables which contain rules with similar characteristics. This greatly reduces classification time preserving similar performance in updates. We validate the effectiveness of TM using both simulation and deployment in a full-fledged software router, specifically within the vector packet processor (VPP). In our simulation results, which focus solely on the efficiency of the classification algorithm, we demonstrate that TM outperforms all other state of the art methods, including TSS, PartitionSort (PS), and SAX-PAC. For example, TM is 34% faster at classifying packets and 30% faster at updating rules than PS. We then experimentally evaluate TM deployed within the VPP framework comparing TM against linear search and TSS, and also against TSS within the OVS framework. This validation of deployed implementations is important as SDN frameworks have several optimizations such as caches that may minimize the influence of a classification algorithm. Our experimental results clearly validate the effectiveness of TM. VPP TM classifies packets nearly two orders of magnitude faster than VPP TSS and at least one order of magnitude faster than OVS TSS.

Many networking devices, such as firewalls and routing tables, rely upon packet classifiers to define their behavior for various kinds of network traffic. Since these devices have real-time constraints, it is important for packet classification to be as fast as possible. We present a new method, ByteCuts, which includes two major improvements over existing tree-based packet classifiers. First, it introduces a new cutting method that is more efficient than existing methods. Second, ByteCuts intelligently partitions the rule list into multiple trees in a way that supports the cutting method and reduces rule replication. We compare ByteCuts to several existing methods such as HyperCuts, HyperSplit, and SmartSplit. We find that ByteCuts outperforms SmartSplit, the previous fastest classifier, in every metric; specifically, ByteCuts is able to classify packets 58% faster, can be constructed in seconds rather than minutes, and uses orders of magnitude less memory.

Packet classification is an important part of many networking devices, such as routers and firewalls. Software-defined networks require online packet classification where classifiers receive a mixed stream of packets to classify and rules to update and both operations must be completed as efficiently as possible without knowledge of future operations. This rules out many classifiers, such as HyperCuts, HyperSplit, and their derivatives, which do not support fast updates. We build upon Tuple Space Search, the packet classifier used by Open vSwitch, to create TupleMerge. TupleMerge improves upon Tuple Space Search by combining hash tables which contain rules with similar characteristics. This greatly reduces classification time by producing fewer tables. We compared TupleMerge to PartitionSort, the current state-of-the-art online packet classifier, on rulelists generated by ClassBench. TupleMerge outperforms PartitionSort at both classifying packets and rule update. Specifically, on average, it is 34.2% faster at classifying packets and 30% faster at updating rules than PS.

OpenFlow packet classification needs to satisfy two requirements: high speed and fast updates. Although packet classification is a well-studied problem, no existing solution satisfies both requirements. Decision tree methods, such as HyperCuts, EffiCuts, and SmartSplit can achieve high-speed packet classification but not fast updates. The Tuple Space Search (TSS) algorithm used in Open vSwitch achieves fast updates but not high-speed packet classification. In this paper, we propose a hybrid approach, PartitionSort, that combines the benefits of both TSS and decision trees achieving both high-speed packet classification and fast updates. A key to PartitionSort is a novel notion of ruleset sortability that provides two key benefits. First, it results in far fewer partitions than TSS. Second, it allows the use of Multi-dimensional Interval Trees to achieve logarithmic classification and update time for each sortable ruleset partition. Our extensive experimental results show that PartitionSort is an order of magnitude faster than TSS in classifying packets while achieving comparable update time. PartitionSort is a few orders of magnitude faster in construction time than SmartSplit, a state-of-the-art decision tree classifier, while maintaining competitive classification time. Finally, PartitionSort is scalable to an arbitrary number of fields.

Access control lists (ACLs) are the core of many networking and security devices. As new threats and vulnerabilities emerge, ACLs on routers and firewalls are getting larger. Therefore, compressing ACLs is an important problem. In this paper, we propose a new approach, called Diplomat, to ACL compression. The key idea is to transform higher dimensional target patterns into lower dimensional patterns by dividing the original pattern into a series of hyperplanes and then resolving differences between two adjacent hyperplanes by adding rules that specify the differences. This approach is fundamentally different from prior ACL compression algorithms and is shown to be very effective. We implemented Diplomat and conducted side-by-side comparison with the prior Firewall Compressor, TCAM Razor, and ACL Compressor algorithms on real life classifiers. Our experimental results show that Diplomat outperforms all of them on most of our real-life classifiers, often by a considerable margin, particularly as classifier size and complexity increases. In particular, on our largest ACLs, Diplomat has an average improvement ratio of 34.9% over Firewall Compressor on range-ACLs, of 14.1% over TCAM Razor on prefix-ACLs, and 8.9% over ACL Compressor on mixed-ACLs.

Access Control Lists (ACLs) are the core of many networking and security devices. As new threats and vulnerabilities emerge, ACLs on routers and firewalls are getting larger. Therefore, compressing ACLs is an important problem. In this paper, we propose a new approach, called Diplomat, to ACL compression. The key idea is to transform higher dimensional target patterns into lower dimensional patterns by dividing the original pattern into a series of hyperplanes and then resolving differences between two adjacent hyperplanes by adding rules that specify the differences. This approach is fundamentally different from prior ACL compression algorithms and is shown to be very effective. We implemented Diplomat and conducted side-by-side comparison with the prior Firewall Compressor algorithm on real life classifiers. The experimental results show that Diplomat outperforms Firewall Compressor most of the time, often by a considerable margin. In particular, on our largest ACLs, Diplomat has an average improvement ratio over Firewall Compressor of 30.6%.