Fast Packet Classification Using Bit Compression. Global Telecommunications Conference

To support applications such as Internet security, virtual private networks, and Quality of Service (QoS), Internet routers need to quickly classify incoming packets into flows. Packet classification uses information contained in the packet header and a prede-fined rule table in the routers. In general, packet classification on multiple fields is a dif-ficult problem. Hence, researchers have proposed a variety of classification algorithms. This paper presents a novel packet classification algorithm, the bit compression algo-rithm. As with the best-known classification algorithm, bitmap intersection, bit compres-sion is based on the multiple dimensional range lookup approach. Since bit vectors of the bitmap intersection contain many “0 ” bits, the bit vectors could be compressed. We compress the bit vectors by preserving only useful information and removing the redun-dant bits of the bit vectors. An additional index table would be created to keep track of the rule number associated with the remaining bits. Additionally, the wildcard rules en-able an extensive improvement in the storage requirement. A novel Fast Boolean Expan-sion enables our scheme to obtain better classification speed even under a large number of wildcard rules. Compared to the bitmap intersection algorithm, the bit compression algorithm reduces the storage complexity in the average case from O(dN2) (for bitmap intersection) to θ(dN · log N), where d denotes the number of dimensions and N repre-sents the number of rules. The proposed scheme cuts the cost of packet classification en-gine and increases classification performance by accessing less memory, which is the performance bottleneck in the packet classification engine implementation using a net-work processor