TY - GEN

T1 - Fast packet classification using bit compression

AU - Hsu, Chia Ren

AU - Chen, Chien

AU - Lin, Chun Yuan

PY - 2005/12/1

Y1 - 2005/12/1

N2 - 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 θ (dN2) to θ (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.

AB - 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 θ (dN2) to θ (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.

UR - http://www.scopus.com/inward/record.url?scp=33846629538&partnerID=8YFLogxK

U2 - 10.1109/GLOCOM.2005.1577738

DO - 10.1109/GLOCOM.2005.1577738

M3 - Conference contribution

AN - SCOPUS:33846629538

SN - 0780394143

SN - 9780780394148

T3 - GLOBECOM - IEEE Global Telecommunications Conference

SP - 739

EP - 743

BT - GLOBECOM'05

Y2 - 28 November 2005 through 2 December 2005

ER -