Efficient multidimensional packet classification with fast updates

Research output: Contribution to journalArticlepeer-review

15 Citations (Scopus)


Packet classification has continued to be an important research topic for high-speed routers in recent years. In this paper, we propose a new packet classification scheme based on the binary range and prefix searches. The basic data structure of the proposed packet classification scheme for multidimensional rule tables is a hierarchical list of sorted ranges and prefixes that allows the binary search to be performed on the list at each level to find the best matched rule. We also propose a set of heuristics to further improve the performance of the proposed algorithm. We test our schemes by using rule tables of various sizes generated by ClassBench and compare them with the existing schemes, EGT, EGT-PC, and HyperCuts. The performance results show that in a test using a 2D segmentation table, the proposed scheme not only performs better than the EGT, EGT-PC, and HyperCuts in classification speed and memory usage but also achieves faster table update operations that are not supported in the existing schemes.

Original languageEnglish
Pages (from-to)463-479
Number of pages17
JournalIEEE Transactions on Computers
Issue number4
Publication statusPublished - 2009

All Science Journal Classification (ASJC) codes

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture
  • Computational Theory and Mathematics


Dive into the research topics of 'Efficient multidimensional packet classification with fast updates'. Together they form a unique fingerprint.

Cite this