Packet Classification Consuming Small Amount of Memory

Abstract — In order to provide more value added services, the Internet needs to classify packets into flows for different treatment. This function becomes a bottleneck in the router. High performance packet classification algorithms are therefore highly demanded. This paper describes a new algorithm for packet classification using the concept of independent sets. The algorithm has very small memory requirements. The search speed is neither sensitive to the size of the rule table nor to the percentage of wildcards in the fields. It also scales well from two dimensional classifiers to high dimensional ones. In particular, the algorithm is inherently parallel. Hardware tailored to this algorithm can achieve very fast search speed. The update algorithm proposed is also very fast in general