Abstract
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^*^β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^*^β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. Β© 2007 Wiley Periodicals, Inc. Syst Comp Jpn, 38(13): 92β103, 2007; Published online in Wiley InterScience (www.interscience.wiley.com). DOI 10.1002/scj.20287