Packet classification using multidimensional cutting

TLDR

HyperCuts builds on the decision‑tree approach of the prior state‑of‑the‑art HiCuts algorithm. The paper proposes a new packet‑classification algorithm named phHyperCuts. phHyperCuts replaces hyperplane nodes with k‑dimensional hypercubes and uses heuristics to select optimal hypercubes, enabling an order‑of‑magnitude performance boost. phHyperCuts consumes 2–10× less memory than HiCuts, achieves 50–500% faster worst‑case search, outperforms EGT‑PC by 1.8–7× in memory and up to fivefold in speed, and supports full pipelining for one‑packet‑per‑arrival classification with rapid updates.

Abstract

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.