Adaptive line search algorithm for packet classification

Abstract

Packet classification has become an important component of routers to support various services such as quality of service guarantee and virtual 2 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 Line Search algorithm presented in [9] was designed for two-dimensional tuple space based packet classification. Since every column has to be examined, the time complexity of the Line Search algorithm is close to that in the worst case, i.e., (W+1)[log(W+1)], where W denotes the length of the fields. In this paper, we present two pruning criteria to improve the average performance. Empirical results for random filter sets show that the Line Search scheme incorporating these two pruning criteria reduces the average search time by nearly 90%. Besides, in order to improve the lookup time in the worst case, we further 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 more filters to the original filter set. We perform a thorough experimental study of 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 two times of memory space consumed by the Line Search scheme, but reduces significantly the maximum number of hash probes by nearly 94%.