Previous [ 1] [ 2] [ 3] [ 4] [ 5] [ 6] [ 7] [ 8] [ 9] [ 10] [ 11] [ 12] [ 13] [ 14] [ 15] [ 16] [ 17] [ 18] [ 19] [ 20]


Journal of Information Science and Engineering, Vol. 24 No. 1, pp. 61-81 (January 2008)

Fast Packet Classification Using Bit Compression with Fast Boolean Expansion*

Chien Chen, Chia-Jen Hsu and Chi-Chia Huang

Department of Computer Science
National Chiao Tung University
Hsinchu, 300 Taiwan

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 predefined rule table in the routers. In general, packet classification on multiple fields is a difficult problem. Hence, researchers have proposed a variety of classification algorithms. This paper presents a novel packet classification algorithm, the bit compression algorithm. As with the best-known classification algorithm, bitmap intersection, bit compression 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 redundant 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 enable an extensive improvement in the storage requirement. A novel Fast Boolean Expansion 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 c(dN P log N), where d denotes the number of dimensions and N represents the number of rules. The proposed scheme cuts the cost of packet classification engine and increases classification performance by accessing less memory, which is the performance bottleneck in the packet classification engine implementation using a network processor.

Keywords: router, packet classification, bitmap intersection, bit compression, Boolean expansion, network precessor

Full Text () Retrieve PDF document (200801_05.pdf)

Received February 2, 2007; accepted July 13, 2007. Communicated by K. Robert Lai, Yu-Chee Tseng and Shu-Yuan Chen. * This work was supported by the New Generation Broadband Wireless Communication Technologies and Applications Project of Institute for Information Industry and sponsored by MOEA, R.O.C.