Adaptive line search algorithm for packet classification

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

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review


Packet classification has become an important component of routers supporting various services such as QoS guarantee and VPN. Packet classification can be considered as looking for the best matching filter in a filter set for several fields selected from the packet header. Various data structures and search algorithms have been proposed for such multi-field packet classification. In particular, the line search algorithm presented by M. Waldvogel (see Proc. IEEE LCN'00, 2000) was designed for two-dimensional tuple space based packet classification. The time complexity of the line search algorithm is close to that of the worst case, i.e., (W+1)⌈log(W+1)⌉, where W is the length of the fields. We present two priming criteria to improve the average performance. Empirical results for random filter sets show that the scheme incorporating these criteria reduces the average search time by nearly 90%. In order to improve the lookup time in the worst case, we propose a new search algorithm, called adaptive line search, which can find the best matching filter in k⌈log(W+1)⌉ probes, where k is a tunable parameter with 2 ≤ k ≤ W+1. Achieving better lookup time in the worst case, i.e. smaller k, requires adding filters to the original filter set. We perform a thorough experimental study of the tradeoffs between memory requirement and lookup performance for various k, and the results show that, for k = 2, our adaptive line search scheme requires about twice the memory space consumed by the line search scheme, but reduces the maximum number of hash probes by nearly 94%.

Original languageEnglish
Title of host publicationProceedings - 10th IEEE International Conference on Networks
Subtitle of host publicationTowards Network Superiority, ICON 2002
Number of pages6
StatePublished - 1 Dec 2002
Event10th IEEE International Conference on Networks: Towards Network Superiority, ICON 2002 - Singapore, Singapore
Duration: 27 Aug 200230 Aug 2002

Publication series

NameIEEE International Conference on Networks, ICON
ISSN (Print)1556-6463


Conference10th IEEE International Conference on Networks: Towards Network Superiority, ICON 2002

Fingerprint Dive into the research topics of 'Adaptive line search algorithm for packet classification'. Together they form a unique fingerprint.

Cite this