Fast packet classification using bit compression

Chia Ren Hsu*, Chien Chen, Chun Yuan Lin

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

4 Scopus citations


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.

Original languageEnglish
Title of host publicationGLOBECOM'05
Subtitle of host publicationIEEE Global Telecommunications Conference, 2005
Number of pages5
StatePublished - 1 Dec 2005
EventGLOBECOM'05: IEEE Global Telecommunications Conference, 2005 - St. Louis. MO, United States
Duration: 28 Nov 20052 Dec 2005

Publication series

NameGLOBECOM - IEEE Global Telecommunications Conference


ConferenceGLOBECOM'05: IEEE Global Telecommunications Conference, 2005
CountryUnited States
CitySt. Louis. MO

Fingerprint Dive into the research topics of 'Fast packet classification using bit compression'. Together they form a unique fingerprint.

Cite this