Scalable packet classification for enabling internet differentiated services

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

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

14 Scopus citations


Nowadays, IP networks are rapidly evolving toward a QoS-enabled infrastructure. The need for packet classification is increasing in accordance with emerging differentiated services. While the new differentiated services could significantly increase the number of rules, it has been demonstrated that performing packet classification on a potentially large number of rules is difficult and has poor worst-case performance. In this work, we present an enhanced tuple pruning search algorithm called "Tuple Pruning Plus" (TPP) for packet classification, which outperforms the existing schemes on the scalability. Our main idea is to simplify the lookup procedure and to avoid unnecessary tuple probing by maintaining the least-cost property of rule through precomputation and the proposed Information Marker. With extra rules added for Information Marker, only one tuple access is required in each packet classification. In our experiments, 70 MB DRAM is used to achieve 50 million packets per second (MPPS) for a 1 M-rule set, showing a performance improvement by a factor of 50. We also present a heuristic to further reduce the required storage to about 20 MB. These results demonstrate the effectiveness of the TPP scheme to achieve high speed packet classification.

Original languageEnglish
Pages (from-to)1239-1249
Number of pages11
JournalIEEE Transactions on Multimedia
Issue number6
StatePublished - Dec 2006


  • Best matching prefix
  • Multicast
  • Multidimensional range lookup
  • Packet classification


Dive into the research topics of 'Scalable packet classification for enabling internet differentiated services'. Together they form a unique fingerprint.

Cite this