2016 · 33 citations · 25 references
ComputingComputer EngineeringComputer ScienceComputer NetworksData StructuresInterconnection NetworksData PartitioningDecision TreesNetwork Performance AnalysisFlow-based AnalysisHigh-speed Packet ClassificationInterval TreesPacket ClassificationPartitioningPartitioning StrategiesSearch Space ReductionTraffic Classification
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.
25
Nick McKeown, Tom Anderson, Hari Balakrishnan et al. · ACM SIGCOMM Computer Communication Review · 2008 · 8.4K citations
The design and implementation of open vSwitch
Ben Pfaff, Justin Pettit, Teemu Koponen et al. · Networked Systems Design and Implementation · 2015 · 673 citations
Packet classification using multidimensional cutting
Sumeet Singh, Florin Baboescu, George Varghese et al. · 2003 · 536 citations · Full text
Packet classification using tuple space search
V. Srinivasan, Subhash Suri, George Varghese · 1999 · 489 citations