Fast packet classification using bit compression

Abstract

In order to support Internet security, virtual private networks, QoS, etc., Internet routers need to classify incoming packets quickly into flows. A packet classifier uses information contained in the packet header and a predefined rule table in the routers to classify the packets. This paper presents a novel packet classification algorithm, called the bit compression algorithm. Like the previously best known algorithm, bitmap intersection, bit compression is based on the multiple dimensional range lookup approach. Since the bit vectors of the bitmap intersection contain lots of '0' bits, the bit vectors could be compressed. We compress the bit vectors by preserving useful information but removing the redundant '0' bits of the bit vectors. Additionally, the wildcard rules also enable more extensive improvement. Comparing with the bitmap intersection algorithm, the bit compression algorithm reduces the storage complexity in the average-case from theta (dN(2)) to theta (dN(.)logN), where d denotes the number of dimensions and N represents the number of rules. By exploring the memory hierarchy, we show that bit compression algorithm requires much less memory access than bitmap intersection algorithm on Intel IXP1200 network processor. Since memory access dominates the lookup time, even though extra decompression time is required for bit compression scheme, the bit compression scheme in the average still outperforms bitmap intersection scheme on the classification performance.