| Previous | [ 1] | [ 2] | [ 3] | [ 4] | [ 5] | [ 6] | [ 7] | [ 8] | [ 9] | [ 10] | [ 11] | [ 12] | [ 13] | [ 14] | [ 15] | [ 16] | [ 17] | [ 18] | [ 19] | [ 20] |
¡@
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.
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.
