Packet classification using diagonal-based tuple space search

Fu Yuan Lee*, Shiuhpyng Shieh

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

4 Scopus citations


Multidimensional packet classification has attracted considerable research interests in the past few years due to the increasing demand on policy based packet forwarding and security services. These network services typically involve determining the action to take on packets according to a set of rules. As the number of rules increases, time for determining the best matched rule for an incoming IP packet will increase and subsequently incur long processing delay. To address this issue, in this paper we propose a two-dimensional packet classification algorithm which focuses on reducing time for classification while keeping reasonable memory requirement in practice. Our approach extends the tuple space framework and then allows performing binary search on the tuple space. To our knowledge, the proposed scheme is the first binary search scheme on two-dimensional tuples. With the proposed scheme, given a filter set with n two-dimensional filters, it requires only O(log(w)) hash operations to determine the best matched filter, where w is the maximum prefix length of filters. The proposed scheme achieves fast packet classification, and according to our experimental results, it does not require huge memory space. This makes it useful for network applications that require high speed packet classification.

Original languageEnglish
Pages (from-to)1406-1423
Number of pages18
JournalComputer Networks
Issue number9
StatePublished - 20 Jun 2006


  • Computer networks
  • High speed network
  • Layer 4 switching
  • Network security

Fingerprint Dive into the research topics of 'Packet classification using diagonal-based tuple space search'. Together they form a unique fingerprint.

Cite this