Adaptive line search algorithm for packet classification

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

研究成果: Conference contribution同行評審

摘要

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%.

原文English
主出版物標題Proceedings - 10th IEEE International Conference on Networks
主出版物子標題Towards Network Superiority, ICON 2002
頁面191-196
頁數6
DOIs
出版狀態Published - 1 十二月 2002
事件10th IEEE International Conference on Networks: Towards Network Superiority, ICON 2002 - Singapore, Singapore
持續時間: 27 八月 200230 八月 2002

出版系列

名字IEEE International Conference on Networks, ICON
ISSN(列印)1556-6463

Conference

Conference10th IEEE International Conference on Networks: Towards Network Superiority, ICON 2002
國家Singapore
城市Singapore
期間27/08/0230/08/02

指紋 深入研究「Adaptive line search algorithm for packet classification」主題。共同形成了獨特的指紋。

引用此