Design and Implementation of a Parameter Filter Based on Virtual Bounding Rectangles

摘要

In this paper, the authors propose a high-speed implementation of a parameter filter, using a multidimensional space search algorithm with the introduction of virtual bounding rectangles. The authors have proposed and implemented a KUPF architecture for the problem of packet classification reflecting the complex policies of a router. Because parameter filters generally have filters for multiple parameters, the conventional methods for increasing speed are not applicable to KUPF. R-tree and R{sup}*-tree, which construct a search tree using minimum bounding rectangles and accelerate the search, are known search methods for multidimensional spaces. Meanwhile, this proposal represents filter rules in multidimensional space with the introduction of virtual bounding rectangles, while normalizing differences in the properties of each parameter and applying an R{sup}*-tree. KUPF-VR, in which this proposal is implemented, had an improved search speed compared to conventional KUPF and was clearly superior in the case of a large number of filter rules, compared to methods specialized for IP packet processing.