Adaptive line search algorithm for packet classification

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