Packet classification using multidimensional cutting

By Sumeet Singh, Florin Baboescu, George Varghese, Jia Wang. Conference on Applications, Technologies, Architectures, and Protocols for Computer Communication, 2003

606 citations recorded by the source corpus.

This paper introduces a classification algorithm called phHyperCuts. Like the previously best known algorithm, HiCuts, HyperCuts is based on a decision tree structure. Unlike HiCuts, however, in which each node in the decision tree represents a hyperplane, each node in the HyperCuts decision tree represents a k--dimensional hypercube. Using this extra degree of freedom and a new set of heuristics to find optimal hypercubes for a given amount of storage, HyperCuts can provide an order of magnitude improvement over existing classification algorithms. HyperCuts uses 2 to 10 times less memory than HiCuts optimized for memory, while the worst case search time of HyperCuts is 50--500% better than that of HiCuts optimized for speed. Compared with another recent scheme, EGT-PC, HyperCuts uses 1.8--7 times less memory space while the worst case search time is up to 5 times smaller. More importantly, unlike EGT-PC, HyperCuts can be fully pipelined to provide one classification result every packet arrival time, and also allows fast updates.

Subfields: Artificial Intelligence, Computer Networks and Communications, Hardware and Architecture

View Paper: https://www.semanticscholar.org/paper/3e36a25cd349d3291ca5d7ef54785e55edf1c5dd

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

1. Jonathan S. Turner
2. Anand Rangarajan
3. Karthik Lakshminarayanan
4. Srinivasan Venkatachary
5. Carsten Lund
6. David E. Taylor
7. David Walker
8. Jennifer Rexford

In Computer Networks and Communications

1. Jennifer Rexford
2. Jonathan S. Turner
3. David Walker
4. Nanxi Kang
5. Zhenming Liu
6. Karthik Lakshminarayanan
7. Anand Rangarajan
8. Srinivasan Venkatachary

In Hardware and Architecture

1. Jonathan S. Turner
2. Anand Rangarajan
3. Karthik Lakshminarayanan
4. Srinivasan Venkatachary
5. Jennifer Rexford
6. Nanxi Kang
7. David Walker
8. Zhenming Liu

Citations in the corpus

• ClassBench: A Packet Classification Benchmark (2005, methodology): “Student groups used the tools to evaluate the performance of various packet classification algorithms [7], [21], [25], [26] implemented on an Intel IXP network processor [24].”
• Survey and taxonomy of packet classification techniques (2005, methodology): “Some of the most promising algorithmic research embraces the practice of leveraging the statistical structure of filter sets to improve average performance [1, 5, 12, 2, 13].”
• The Design and Implementation of Open vSwitch (2015, neutral): “Many classification algorithms only work with static sets of flows, or have expensive incremental update procedures, making them unsuitable for dynamic OpenFlow flow tables [7, 8, 33, 38, 40].”
• TCAM Razor: A Systematic Approach Towards Minimizing Packet Classifiers in TCAMs (2007, neutral): “, [6], [7], [10], [12], [15], [21], [22], [24], [28], [29]).”
• Optimizing the "one big switch" abstraction in software-defined networks (2013, methodology): “We remark here that existing packet-classification algorithms [22, 23] could be viewed as a special case of Palette’s partitioning al-gorithm.”
• Packet classification in large ISPs: design and evaluation of decision tree classifiers (2005, methodology): “An effective heuristic to control memory size in standard decision trees is to halt node splitting when the node has fewer than some set number of rules [21].”
• Algorithms for advanced packet classification with ternary CAMs (2005, background): “Our algorithms do not require any modi.cations to existing TCAMs and are hence relatively easy to deploy.”