Performance improvement of two-dimensional packet classification by filter rephrasing

Pi Chung Wang*, Chun Liang Lee, Chia Tai Chan, Hung Yi Chang

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

17 Scopus citations


Packet classification categorizes incoming packets into multiple forwarding classes in a router based on predefined filters. It is important in fulfilling the requirements of differentiated services. To achieve fast packet classification, a new approach, namely "filter rephrasing," is proposed to encode the original filters by exploiting the hierarchical property of the filters. Filter rephrasing could dramatically reduce the search and storage complexity incurred in packet classification. We incorporate a well-known scheme-rectangle search-with filter rephrasing to improve the lookup speed by at least a factor of 2 and decreases 70% of the storage expenses. As compared with other existing schemes, the proposed scheme exhibits a better balance between speed, storage, and computation complexity. Consequently, the scalable effect of filter rephrasing is suitable for backbone routers with a great number of filters.

Original languageEnglish
Pages (from-to)906-917
Number of pages12
JournalIEEE/ACM Transactions on Networking
Issue number4
StatePublished - 2007


  • Firewalls
  • Forwarding
  • Packet classification
  • Quality of service (QoS)


Dive into the research topics of 'Performance improvement of two-dimensional packet classification by filter rephrasing'. Together they form a unique fingerprint.

Cite this