Fast tuple space based packet classification algorithm for two-field conflict free filters

Pau Chuan Ting*, Yung Sheng Hsu, Tsern-Huei Lee

*Corresponding author for this work

Research output: Contribution to journalConference articlepeer-review

2 Scopus citations


Packet classification is an important component of new Internet routers to support various services such as quality of service guarantee and virtual private network. Basically, packet classification can be considered as a process looking for the best matching filter in a filter set for several fields selected from packet header. Various data structures and search algorithms have been proposed for such multi-field packet classification. In particular, the nested binary tuple space search algorithm presented in [18] was designed for two-field conflict free filter sets. The time complexity of the nested binary search algorithm is (|log(W+1)|)2, where W is the length of the fields. In this paper, we investigate the impact of built-in markers and associated pre-computation mechanisms on such an algorithm. We found that, if the nested binary search algorithm employs unified markers and identical pre-computation manner for them, the search process may result in a "no match" while there exist matching filters. The incorrect decision is caused by conflicts between some markers and filters. This problem can be resolved by adding resolution filters. We present in this paper a necessary and sufficient condition to determine whether or not markers generated by a filter conflict with another filter. Besides, we further propose a novel search algorithm which can find the best matching filter in 2[log(W+1)] probes. Although more resolution filters are added, empirical results for random filter sets show that our scheme requires less memory than the nested binary search algorithm because no primary markers (and the secondary markers of primary markers) are needed.

Original languageEnglish
Article number1204193
Pages (from-to)325-331
Number of pages7
JournalIEEE International Conference on Communications
StatePublished - 11 May 2003
Event2003 International Conference on Communications (ICC 2003) - Anchorage, AK, United States
Duration: 11 May 200315 May 2003


  • Binary search
  • Marker
  • Packet classification
  • Pre-computation
  • Tuple space

Fingerprint Dive into the research topics of 'Fast tuple space based packet classification algorithm for two-field conflict free filters'. Together they form a unique fingerprint.

Cite this