Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
1999-05-14
2001-10-02
Choules, Jack (Department: 2177)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000, C707S793000, C707S793000, C707S793000
Reexamination Certificate
active
06298340
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to traffic management in a communications network and, in particular, to filtering of traffic in said network.
2. Prior Art
The use of filter systems to manage the flow of traffic in a communications network is well known in the prior art. In a conventional filtering system, selected characteristics of an unknown item are subjected to rules which are known to classify items. If the unknown item fits the criteria of a rule, then the action associated with that rule is taken. Rules may have priority so that an item which passes several rules is actually subjected to a unique action, namely that of the highest priority rule it fits. In some systems rules may be of several types, in which case the rule to apply would be the rule of each type which fits and has highest priority.
One straightforward or brute force way of filtering an item is to subject the item to all rules sequentially, in order of priority. Compared to the method disclosed herein, the sequential method is simple but slow. This brute force approach is acceptable only if the number of rules is small or speed is not essential. In a communications system where the universe could have tens or hundreds of rules and time is very critical, this brute force approach is not acceptable.
Another brute force way of filtering an item is to subject the item to all rules in parallel, then accumulate the results and find the rule with highest priority passed by the item. Compared to the method disclosed herein, the parallel method is simple and fast, but also expensive and inefficient. A specialized chip capable of performing parallel compares would be required to carry out the comparisons. Such a chip might not perform any other function. Consequently, the cost cannot be leveraged to a multifunction chip.
The prior art has improved the brute force methods by utilizing tree structures in the filtering process. U.S. Pat. No. 5,463,777 describes a tree structure in which the key segments of multiple bits (such as 32 bit segments) from the header of a frame are compared with chosen values at tree nodes. Results of the searches on segments are ANDed to produce a final result.
U.S. Pat. No. 5,574,910 also makes use of fixed length keys (such as 32 bits) and, in the case of a plurality of segments, ANDs results to reach a final decision.
U.S. Pat. No. 5,546,390 also teaches the advantages of choosing certain bits in building a search tree called a radix tree-type decision process. This method examines two or more bits at each tree branch. In fact, U.S. Pat. No. 5,546,390 distinguishes itself from its prior art in part by selecting two or more bits for each node in its decision tree nodes. Unfortunately, as mentioned therein, allowing 4, 8, or more branches at each node can result in wasted space for unused links. Those skilled in the art will recognize that it is not always feasible to find such combinations of bits in real rule sets.
U.S. Pat. No. 5,813,001 describes another search technique in which groups of bits from a search object are matched against groups of bits from entries in a knowledge base system. It is believed that this approach requires complex circuities or long processing time in order to perform the required group processing.
U.S. Pat. No. 5,136,580 uses a Programmable Logic Array (PLA) and a Content Addressable Memory (CAM) to recognize if a Destination Address (Recipient) and Source Address (Sender) are on the same LAN. If so, the frame is filtered and not forwarded to another LAN. Hence this system provides a limited filtering function.
U.S. Pat. Nos. 5,541,911 and 5,790,554 refer to filters in a general way, but appear not to disclose any specific structures or mechanism for filtering.
Even though the prior art patents may work satisfactorily for their intended purposes, none of the patents gives a mechanism for selection of bits to use at tree nodes.
SUMMARY OF THE INVENTION
In view of the foregoing, the present invention provides an improved method and apparatus for filtering.
The present invention presents five metrics for selection of bits. Actual filter rules sometimes apply to bounded ranges of data identifiers with integer boundaries which are not powers of 2. For example, in IP terminology, a filter rule might apply to port numbers 1 to 53. In this case the bits representing the port number in a key which fits the rule are certain combinations, namely combinations 000001 through 110101, not all 2{circumflex over ( )}6 possible combinations of six binary bits. By testing inequalities with simple compare operations, the present invention allows such irregular ranges in rules, as will be explained below. Furthermore, the present invention uses metrics to solve the non-intuitive and important problem of finding the optimal bit.
As used in this document, metric means a quantitative measure of the optimal bit to choose. For large rules sets with many “don't care” entries and many bounded range entries in its rules, this choice can be non-intuitive and yet critical to algorithm performance.
Furthermore, those practiced in the art will recognize that filter rule tables often contain rules which cannot be differentiated by examination of one bit position or a combination of a few bit positions. For example, a rule set might contain a first rule which applies to a specific source address and any destination address, and a second rule which applies to any source address and a specific destination address. The rules might be otherwise identical. Such combinations appear when an administrator wishes to filter all traffic of a type in the same way but differentiated with respect to two directions, to and from a subnetwork. The present invention treats such cases by means of a lattice of tests (as opposed to a tree) described herein.
An algorithm termed “Choice Bit Algorithm” uses a certain metric to build a binary search tree based upon bits selected from items termed “rules” in a set or universe of rules. All our examples are couched in terms of Internet Protocol (IP) headers, but a fixed format header of any type could be used instead.
In IP, each Rule pertains to certain Keys which might be built with the following subsections: Source Address (SA), Destination Address (DA), Source Port (SP), Destination Port (DP), and Protocol (P). These data are respectively 32, 32, 16, 16, and 8 bits long and so a Key to be tested consists of 104 bits. The Choice Bit Algorithm finds certain of the 104 bits which are especially useful. Testing the few bits in effect eliminates all but one or all but a few rules from possible application. For some rules, testing inequalities by means of simple compare operations are also appropriate. The bit tests and compares are logically organized in a binary tree. The tree is mapped into a hardware enabled structure that tests bits at high speeds. Such testing results in just one rule or a small number of rules (called a leaf chain) which the Key might fit. In the former case, the Key is then tested in full by the rule. In the latter case, the Key is then tested in a lattice of tests using compares and full rule tests.
Each rule in the rule set is associated with an action which is taken if the rule is the highest priority rule which fits the key. Rules can intersect (one key fits two or more rules). In that case, rules can be given priority numbers 1, 2, 3, . . . , so that any two intersecting rules have different priorities (an administrator must declare which rule dominates if a key fits two or more). Thus if more than one rule remains to be tested after the bit tests and compares, the rules are tested in order of priority. A lower priority number designates a rule with higher priority.
If no fit is found at all, some default provision may be specified.
The method works, that is, produces an efficient, nearly balanced search tree, for the following underlying reasons. It can be shown using probability theory that the probability of observing exactly 1000 heads in 2000 tosses of a fair coin is about 1 div
Calvignac Jean Louis
Corl, Jr. Everett Arthur
Gallo Anthony Matteo
Heddes Marco C.
Jeffries Clark Debs
Choules Jack
Cockburn Joscelyn G.
International Business Machines - Corporation
Lewis Cheryl
LandOfFree
System and method and computer program for filtering using... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System and method and computer program for filtering using..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method and computer program for filtering using... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2600787