Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
2000-03-31
2002-11-19
Mizrahi, Diane D. (Department: 2175)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000, C707S793000
Reexamination Certificate
active
06484171
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. Specifically, it describes a method for assignment of priority numbers to rules. Priority numbers are essential both in organizing rule searches and in detecting administrative errors.
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. The filter systems include filter rules that are used to test information in a packet.
In some prior art, ways of testing the filter rules are listed sequentially and information from the packet is presented to the first rule in the list. If the packet information passes the requirements of the rule, the action of the rule is applied to the packet. Otherwise, the packet information is then tested against the next rule, and so on. The sequential method of testing rules is straightforward and simple, but slow.
Another prior art method uses decision trees or parallel calculations to test information in the packet against the rules. For example, U.S. Pat. No. 5,546,390 describes a tree structure in which two or more bits from the header of a packet are tested at each node of the tree. Prior art described in that patent discloses techniques consisting of testing individual bits or contiguous blocks of bits (for example, 32 contiguous bits constituting a destination address).
U.S. Pat. No. 5,574,910 also teaches filtering by use of a binary tree search method in which tree nodes use masks and ranges to make decisions.
U.S. Pat. No. 5,761,424 teaches in general terms the use of programmable criteria to accomplish high-speed filtering through bit tests and compares.
Still other filtering techniques are disclosed in U.S. Pat. Nos. 5,530,703; 5,761,424; 5,848,233 and 5,822,527.
It would not be uncommon to find that information, termed the “key”, in the packet could fit several rules within a database of rules. This condition is termed “Rules Intersection” (described hereinafter). Whenever this condition occurs, the system would break down unless a mechanism and method are provided to address this condition. To the best of our knowledge, the prior art does not include the systematic resolution of this problem as disclosed herein. That is, there is a need to provide a mechanism and method that addresses the condition of a packet matching multiple rules. It is this problem the present invention addresses. In addition, the present invention addresses two types of administrative errors, termed “cyclic domination” and “inclusion of one rule in another,” resulting in some rules not being referenced. Suffice it to say at this point that both types of errors can cause failure in a filtering system unless they are detected and appropriate corrective actions are taken. The prior art neither addresses nor recognizes these errors in the manner of the present invention, so far as we know.
SUMMARY OF THE INVENTION
The present invention addresses the problems by assigning priority numbers to rules. The priority numbers are assigned in an efficient and clear manner so that any two rules that intersect (some keys fit both rules) have necessarily different priority numbers. Rules with the same priority numbers do not intersect.
In assigning priority numbers and in executing related algorithms and methods, the present invention will do the following upon presentation of new rules:
explicitly query the network administrator to enter a domination declaration for every preexisting rule which intersects a new rule;
build the intersection table and the priority number assignments as rules are entered (rules are entered in any order);
alert the network administrator if inconsistencies of two types occur; namely cyclic domination declaration and inclusion declaration;
The present invention prompts the administrator to declare domination relationships only between pairs of rules which intersect. Again, two rules intersect if some key fits both rules.
In a preferred embodiment of the present invention, information is communicated to the administrator by means of computer generated graphics or text or both. The graphical presentation is in the form of a directed non-cycle graph. Specifically, a vertex in the rule set graph (discussed in detail below) corresponds to a rule. Edges connecting rules are drawn precisely if two rules intersect (one key fits both rules). Such an edge is endowed with a pointer designating domination of one rule by another when the administrator declares that domination. The pointer is directed from the lower priority rule to the higher priority rule. Finally, when a new rule has been added and all dominations declared, the present invention tests the rules for consistency. Then the present invention either informs the user of errors and awaits corrections, or notifies the user that the rules are consistent and computes and displays new priority numbers for the rules.
Filter rules are generally expressed in terms of inequalities to be satisfied by the components of a key. An important example concerns IP headers in which the following information is used to make filter decisions:
Source Address (SA) 32 bits often organized into four bytes of eight bits each with a dot (.) designating separation, or equivalently four integers with values in the interval [0, 255] presented with a dot (.) designating separation such as 17.3.1.18, or equivalently one integer with value in the interval [0, 4,294,967,295] such as 285,409,554;
Destination Address (DA) 32 bits often organized into four bytes of eight bits each with a dot (.) designating separation, or equivalently four integers with values in the interval [0, 255] presented with a dot (.) designating separation such as 17.3.1.18, or equivalently one integer with value in the interval [0, 4,294,967,295] such as 285,409,554;
Source Port (SP) 16 bits, or equivalently an integer with value in the interval [0, 65,535];
Destination Port (DP) 16 bits, or equivalently an integer with value in the interval [0, 65,535];
Protocol (P) 8 bits, or equivalently an integer with value in the interval [0, 255].
The above five components are called the five dimensions used in IP filtering or, collectively, the five-tuple.
Every IP filter rule which uses the above data types can be stated as a combination of ten integers, namely, the ten integers being the upper integer and lower integer limits of a rule in the five dimensions.
Thus the above rule specifications can pertain to the important but special case of IP (Internet Protocol) headers. The present invention not only applies to that case but also every other system of filtering on a protocol with fixed format headers. Indeed, the present invention in describing the organizing of filter rules applies to any filtering system, including those filtering on packet data and on variable length keys. The two basic concepts are intersection (two rules intersect if one key fits both) and inclusion (one rule is included in a second if every key that fits the first also fits the second).
Continuing with the example of filtering in IP, any rule can be written as a 10-tuple of integers, the aforementioned upper and lower limits of values of components of keys which fit the rule, in the following form:
(sa, SA, da, DA, sp, SP, dp, DP, p, P)
Here, sa is the lower limit of Source Address, SA is the upper limit of Source Address, da is the lower limit of Destination Address, and so on.
Two rules R
1
, R
2
are defined to intersect if one key fits both. In terms of IP headers, intersection is equivalent to the following 10 statements being all true:
sa
1
<=SA
2
da
1
<=DA
2
sp
1
<=SP
2
dp
1
<=DP
2
p
1
<=P
2
(intersection) sa
2
<=SA
1
da
2
<=DA
1
sp
1
<=SP
1
dp
2
<=DP
1
p
2
<=P
1
The present invention examines all distinct pairs from a set of N rules and fin
Corl, Jr. Everett Arthur
Gallo Anthony Matteo
Jeffries Clark Debs
Verrilli Colin Beaton
Cockburn Joscelyn G.
Mizrahi Diane D.
Mofiz Apu M
LandOfFree
System method and computer program for prioritizing filter... 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 method and computer program for prioritizing filter..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System method and computer program for prioritizing filter... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2946827