High-speed packet classification for differentiated services in next-generation networks

Pi Chung Wang*, Chia Tai Chan, Shuo Cheng Hu, Chun Liang Lee, Wei Chun Tseng

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

23 Scopus citations


In next-generation networks, packet classification is important in fulfilling the requirements of multimedia services, including VoIP and VoD. Using pre-defined filters, the incoming packets can be categorized that determines to which forwarding class a packet belongs. Packet classification is essentially a problem of multidimensional range matching. The tuple space search is a well-known solution based on multiple hash accesses for various filter length combinations. The tuple-based algorithm, a rectangle search, is highly scalable with respect to the number of filters; however, it suffers from the memory-explosion problem. Besides, the lookup performance of the rectangle search is not sufficiently fast to accomplish high-speed packet classification. This work proposes an improved scheme to reduce the required storage and realize OC-192 wire-speed forwarding. The scheme consists of two parts. The "Tuple Reduction Algorithm" drastically reduces the number of tuples by duplicating filters. Dynamic programming is used to optimize the tuple reduction and two heuristic approaches are introduced to simplify the optimization process. Furthermore, the "Look-ahead Caching" scheme is presented to improve the lookup performance. The basic idea is to prevent unnecessary tuple probing by filtering out the "un-matched" situation of the incoming packet. The experimental results show that combining the tuple reduction algorithm with look-ahead caching increases the lookup speed by a factor of six while requiring only around one third of the storage. Additionally, an extension of multiple fields to more general filters is addressed.

Original languageEnglish
Pages (from-to)925-934
Number of pages10
JournalIEEE Transactions on Multimedia
Issue number6
StatePublished - Dec 2004


  • High-speed network
  • Internet
  • IP address lookup
  • Packet classification


Dive into the research topics of 'High-speed packet classification for differentiated services in next-generation networks'. Together they form a unique fingerprint.

Cite this