Method for fast multi-dimensional packet classification

Abstract

A simple and fast algorithm for multi-dimensional packet classification by solving the best matching filter problem. The substantial part of the algorithm includes the search of filters being concurrently stabbed by the packet using a KD-tree data structure. Another aspect of the present invention includes the classification of the packet according to its destination address using a second data-structure which preferably consists of a one dimensional segment tree. In a preferred embodiment of the present invention, the packet is first classified according to its protocol type, then the packet is classified according to its destination address using a one dimensional segment tree data structure, and finally, a 6 dimension KD-tree is used to find the filters being stabbed by the remaining 3 parameters of the packet. Among the filters, which comply with the packet, the filter which applies to the packet is the filter with the highest pre-determined priority. Theoretical analysis predicts and experimental results verify that in practice, the proposed data-structure can handle a lot of “difficult” filters quickly and efficiently.

Dependencies are inferred from the claim text.