摘要 |
A method of classifying data packets based on general property ranges. An interval tree is constructed to represent the applicability of rules to non-overlapping ranges of a data classification property. The interval tree can be a binary tree such as a balanced binary tree or red-black tree. To determine which rules apply to a data packet, the data packet property, for example a field in a data packet header, is compared to the intervals in the tree to find a match. To balance the time and space complexity, a heuristics based method is used for classifying data packets based on general property ranges of more than one data classification property. An interval tree is constructed for a first data classification property. If the number of rules potentially applicable to the data packet based on an interval of the first tree exceeds a threshold, that interval will refer to a second interval tree representing the applicability of the rules to non-overlapping ranges of the second data classification property. If the number of potentially applicable rules does not exceed the threshold, the interval refers to an ordered list of rules that are searched through to find a match.
|