Layered Cutting Scheme for Packet Classification
Packet classification is an important topic for high-speed routers nowadays. There are many packet classification algorithms based on decision tree like Hicuts, Hypercuts and Hypersplit. Because Hicuts and Hypercuts divides the rule sets by cutting the address space into equal-sized subspaces, their cutting efficiency is not good. Although Hypersplit proposed a good end-point-based cutting scheme, the resulting tree depth is still very high. In this paper, the authors propose a multi-dimensional cutting algorithm to significantly reduce the decision tree depth and a multi-layered scheme to dramatically reduce the usage of memory.