System method and computer program for prioritizing filter rules

[0002] Patent Application Ser. No. 09/312,148, now U.S. Pat. No. 6,298,340 filed May 14, 1999, by Jeffries et al, entitled “System and Method and Computer Program for Filtering Using Tree Structure”, discloses a filtering method that determines if the key in an IP packet matches a rule in a database.

[0003] 1. Field of the Invention

[0004] 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.

[0005] 2. Prior Art

[0006] 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.

[0007] 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.

[0008] 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).

[0009] 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.

[0010] 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.

[0011] Still other filtering techniques are disclosed in U.S. Pat. Nos. 5,530,703; 5,761,424; 5,848,233 and 5,822,527.

[0012] 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.

[0013] 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.

[0014] In assigning priority numbers and in executing related algorithms and methods, the present invention will do the following upon presentation of new rules:

[0015] explicitly query the network administrator to enter a domination declaration for every preexisting rule which intersects a new rule;

[0016] build the intersection table and the priority number assignments as rules are entered (rules are entered in any order);

[0017] alert the network administrator if inconsistencies of two types occur; namely cyclic domination declaration and inclusion declaration;

[0018] 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.

[0019] 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.

[0020] 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:

[0021] 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;

[0022] 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;

[0023] Source Port (SP) 16 bits, or equivalently an integer with value in the interval [0, 65,535];

[0024] Destination Port (DP) 16 bits, or equivalently an integer with value in the interval [0, 65,535];

[0025] Protocol (P) 8 bits, or equivalently an integer with value in the interval [0, 255].

[0026] The above five components are called the five dimensions used in IP filtering or, collectively, the five-tuple.

[0027] 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.

[0028] 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).

[0029] 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:

[0030] (sa, SA, da, DA, sp, SP, dp, DP, p, P)

[0031] 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.

[0032] Two rules R₁, R₂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:

[0033] sa₁<=SA₂da₁<=DA₂sp₁<=SP₂dp₁<=DP₂p₁<=P₂(intersection) sa₂<=SA₁da₂<=DA₁sp₁<=SP₁dp₂<=DP₁p₂<=P₁

[0034] The present invention examines all distinct pairs from a set of N rules and finds those pairs which intersect. In a data base, all intersections are entered as a pair of rule labels {i,j } where i and j are in {0, 1, 2, . . . , N-1}, rule i intersects rule j, and i<j.

[0035] Furthermore, the present invention queries the system administrator as a new rule is To added to a rule set about intersections in which the new rule is a member. The query includes asking which of the two intersecting rules (the new rule and a preexisting rule) dominates in the event that one key is tested and fits both rules. The response of the administrator is called declaring domination.

[0036] Furthermore, the present invention includes the Priority Number Algorithm as explicitly described below. The value of a priority number is a natural number 1, 2, 3, . . . The subset of rules with highest priority are those not dominated by any other rule, and they all have priority number 1. If one rule or more rules with priority number 1 dominate one rule or more other rules, then those rules which are so dominated but not dominated by any other rules comprise a subset of rules each of which is given priority number 2. If one rule or more rules with priority number<=2 dominate one rule or more other rules, then those rules which are so dominated but not dominated by any other rules comprise a subset of rules each of which is given priority number 3. This relationship and priority number allocation is extended by an algorithm in the present invention to all rules.

[0037] Furthermore, after all domination relationships between a new rule and all preexisting rules it intersects are explicitly stated as above, the present invention calculates a priority number for each new rule as well as a priority number for all the rules already in the rule set. The present invention uses the Priority Number Algorithm (described in detail below) to accomplish this.

[0038] Furthermore, upon allocating priority numbers the present invention then enables a filter rule mechanism to determine which of two or more rules which fit a key to apply. Namely, of all rules which do apply, the one to select is the one rule with highest priority (lowest priority number). The present invention contains a proof that no two rules which intersect can possibly have the same priority number as generated by the Priority Number Algorithm. Hence the problem of which rule to apply is mathematically guaranteed to have a unique and easily decidable answer.

[0039] Two administrative errors can occur in filter rule specification; to wit:

[0040] rules that can never be logically referenced can be described and entered, wasting resources and falsely suggesting that a certain action will be taken for certain keys; and

[0041] circular domination patterns which can make deciding which rule to apply impossible.

[0042] The first error type is: if every key which fits rule i also fits rule j (a relationship called inclusion of rule i in rule j, to be defined precisely below for IP headers) and if rule j dominates rule i, then rule i will never be referenced. The second error type is: if several rules intersect with the first dominating the second, the second dominating the third, and so on, and the last dominating the first, then the rules are said to have circular domination. If a key fits all the rules in the cycle, then no rule can be selected for application to the key.

[0043] Furthermore, the present invention automatically informs the administrator if either of the above errors is made upon the introduction of a new rule.

[0044] The foregoing and other features and advantages of the invention will be more fully described in the accompanying drawings.

[0045] FIG. 1 shows a Communication System embodying the teachings of the present invention.

[0046] FIG. 2 shows a format for an IP Rule.

[0047] FIG. 3 shows an IP frame format.

[0048] FIG. 4 shows a flowchart of the Frame Classification System according to the teachings of the present invention.

[0049] FIG. 5 shows an acyclic directed graph and corresponding priority numbers for six rules with domination declarations as specified below.

[0050] FIG. 6 shows a flowchart for the Priority Number Algorithm.

[0051] FIG. 7 shows a workstation including a control unit.

[0052] The invention to be described hereinafter can be used in any environment in which one wishes to organize, study, or test for logical correctness of a set of rules with possible intersections (in which one key fits two or more rules) or possible inclusions (in which every key that fits some first rule necessarily fits some second rule). It works well in a communications system in which there is frame classification or frame filtering. As a consequence, it will be described in that environment. However, this should not be construed as a limitation upon the scope of the invention since one skilled in the art could use the teachings in other environments in which one wishes to classify items. If the invention is used in such an environment, it is intended that the claims set forth below will be applicable.

[0053] FIG. 1 shows a block diagram of a communications network in which the present invention is implemented. The communications network includes a Switch/Router 10 connected through a simple multiplex device (Multiplexer) 11 to Workstations 1 through N (a LAN), a Control Point 12, Internet 14 or some other form of Wide Area Network (WAN) 16, Server 18, and another Local Area Network (LAN) 20. A LAN can be ethernet, token-ring or any other local area network which might include many additional workstations. Those skilled in the art will understand that a great variety of combinations of such elements is possible in permutations of FIG. 1. In particular, some elements could be duplicated and others deleted. The Multiplexer 11 is a conventional off-the-shelf device that selects one of the plurality of attached workstations and allows it to communicate with the switch/router. The use of multiplexers to provide such services are so well known that further description is not warranted.

[0054] Still referring to FIG. 1, the Control Point 12 provides the interface between the switch/router and the network administrator. In one embodiment of the present invention, the control point includes a computer comprising a keyboard, control unit, display, etc. (FIG. 7).

[0055] More particular, the computer includes a system bus to which a central processing unit (CPU), a memory, RAM, ROM, I/O devices, display device, etc., are coupled. The I/O devices, including a keyboard, scanner, pointing devices (mouse), etc., are coupled through appropriate interfaces to the system bus. The display device includes a cathode ray tube which is connected through an appropriate graphic controller to the system bus. The graphic controller, in response to information provided by a driver in the CPU, displays information to the administrator. As will be discussed hereinafter, the displayed information may include prompts or queries from the CPU. The displayed information may also include the non-cyclic directed graph (discussed hereinafter), etc. The CPU is provided with a conventional multi-tasking operating system, software drivers and application programs that configure the computer to operate according to the teachings of the present invention.

[0056] FIG. 2 shows an IP header Rule Database Format. It consists of Segments 48 which have upper and lower bounds for each of SA, DA, SP, DP, Protocol (P) and an Action portion in segment 50. The Action portion lists the action to be taken if a key (described hereinafter) fits the rules.

[0057] FIG. 3 shows an IP Frame Format. The Frame Format includes a section termed “Key”, an Information section, and an Ending Delimiter (ED) section. The Key section of the frame includes an SA field, DA field, SP field, DP field and Protocol (P) field. The key section of the IP frame is correlated with rules in the Rule Database to determine if the key matches one of the rules in the database. If it does, the Action set forth in the matching rule is taken relative to the frame. If the key matches multiple rules, the present invention causes the action associated with the highest priority rule to be taken.

[0058] FIG. 4 shows a Frame Classification System including the teachings of the present invention. The process labeled OFFLINE CALCULATIONS is practiced in the Control Point (FIG. 1) with the computer (FIG. 7). Likewise, HIGH SPEED PROCESSING is done, in real time, in the Switch/Router 10 (FIG. 1).

[0059] Still referring to FIG. 4, Block 36 is the entry point into the process. From Block 36, the process descends into Block 38 where a Rule set is input by a User 40. Turning to FIG. 7 for the moment, the user uses the keyboard or other input devices to input the rules into the memory of the computer. Referring again to FIG. 4, an Algorithm 42 (described hereinafter), executing on the CPU, operates on the Rule Set to assign Priority Numbers in Block 44 which are transmitted to the select Highest Priority Rule in Block 54. The Packet Key (Block 48) inputs into the Test Structure Block 46. The Packet Key could be a portion of a frame which is received from an input such as the Internet, a Wide Area Network, LAN, etc. Alternatively, the packet key could be a portion of the frame, information derived from the frame and its origin and/or destination ports. Still other characteristics of the frame could be used to generate the packet key; such key would still fall within the teachings of the present invention.

[0060] In FIG. 4, Block 54 requires examination of all rules which a key fits. This set must be tested by comparing the priority numbers of the selected rules until the rule with the highest priority (lowest priority number) is found. Since the key in question fits all the rules of the set, the rules in the set intersect. Therefore, no two rules in the set have the same priority number (Theorum). Therefore the selection is well defined and unique.

[0061] The Test Structure 46, including a database of rules, tests selected data from the Packet Key, and at the end, does a full scale compare between a rule in the Rule Set and the Key to determine if the packet matches the rule in the Rule Set. If the key matches a single rule in the database of rules (Rule Set), the process descends into block 56 whereat one of the actions associated with the matching rule is performed.

[0062] Still referring to FIG. 4, if the key matches several rules, the process rules that fit the key (Block 52) are sent to Select Highest Priority Rule Block 54 wherein priority numbers provided by block 44 are used to select the rule that fits with highest priority (lowest priority number). When the selection is made, the Packet is then subjected to the action of the rule, one of the Apply Action 56 functions labeled 1 through n.

[0063] Still referring to FIG. 4, the Test Structure could be the filtering system set forth in the above related patent application. In the alternative, any filtering system that is able to correlate an item with a database of related items and indicate a match between the item and one or more of the items in the data, can be used.

[0064] The value of a priority number is a natural number 1, 2, 3, . . . The subset of rules with highest priority are those not dominated by any other rule, and they all have priority number 1. If one rule or more rules with priority number 1 dominate one rule or more other rules, then those rules which are so dominated but not dominated by any other rules comprise a subset of rules each of which is given priority number 2. In the event that one rule or more rules with priority number<=2 dominate one rule or more other rules, those rules which are so dominated but not dominated by any other rules comprise a subset of rules each of which is given priority number 3. This relationship and priority number allocation is extended to all rules.

[0065] In the context of the above description of IP header components, two rules R₁, R₂are defined to intersect if the following 10 statements are all true.

[0066] Rule R₁intersects Rule R₂:

[0067] sa₁<=SA₂da₁<=DA₂sp₁<=SP₂dp₁<=DP₂p₁<=P₂(intersection)

[0068] sa₂<=SA₁da₂<=DA₁sp₂<=SP₁dp₂<=DP₁p₂<=P₁

[0069] Also in the context of the above description of IP header components, rule R₁is said to be included in rule R₂if the following 10 statements are all true.

[0070] Rule R₁is included in Rule R₂:

[0071] SA₁<=SA₂DA₁<=DA₂SP₁<=SP₂DP₁<=DP₂P₁<=P₂(inclusion)

[0072] sa₂<=sa₁da₂<=da₁sp₂<=sp₁dP₂<=dP₁P₂<=P₂<=p₁

[0073] Although the present invention uses IP conventions for the purpose of illustration, those skilled in the art will recognize that the definitions of intersection and inclusion given here could readily be adapted to any other fixed format packet labeling system. Also, other filter schemes might still have the concepts of intersection and inclusion, rendering them suitable for application of the present invention.

[0074] The present invention examines a new rule and all preexisting rules and finds those pairs which intersect. In a data base, all intersecting rules are first entered as a pair of rule labels (i, j) where i and j are in {0, 1, 2, . . . , N-1}, rule i intersects rule j, and i <j. As more rules are added, the pairs of intersections are added to the database so that the database records all pairs of rules which intersect. A second database (to be labeled J below) consists of all the intersecting rule pairs except they are in order of domination. That is, a pair (i, j) of rule indices is in the second database if rules i and j intersect and rule j dominates rule i (note the order).

[0075] It will be convenient to couch the above definition of priority numbers in terms of graph theory. A graph consists of vertices and directed edges. In the present invention, each rule is identified with a vertex. Furthermore, each pair of intersecting rules is identified with an edge. If rule i and rule j intersect and if rule j dominates rule i, then the pair (i, j) is included in the database of edges. Note the order of rule label entries: the second dominates the first. In terms of graphs, the symbol (i, j) is equivalent to a directed edge from vertex i to vertex j.

[0076] In terms of graph nomenclature, a rule is said to have priority number 1 (highest priority) if all edges (possibly none) attached to the corresponding vertex are directed to it. The priority number of any other rule is one plus the number of edges in the longest directed path from it to any rule with priority number 1.

[0077] Technically the rule set with domination declarations can be thought of as construction of a directed graph. The vertices of the graph are filter rules. An edge connects two vertices if and only if the vertices correspond to intersecting filter rules. Whenever two range filter rules intersect, one must be specified as having higher priority than the other. We direct an arrowhead on each such edge pointing from the rule with lower priority to the rule with higher priority. Provided cyclic patterns of rule domination are not allowed, this must yield an acyclic directed graph.

[0078] If n is a natural number and some rule has priority number n, then we call the set of all of the rules with priority number n a priority number class.

[0079] To illustrate the above concepts of applying graph notions to rule priorities, suppose six rules {R₀, R₁, . . . , R₅} are related as follows:

[0080] R₀dominates R₃

[0081] R₀dominates R₄

[0082] R₁dominates R₄

[0083] R₁dominates R₅

[0084] R₂dominates R₅

[0085] R₄dominates R₃

[0086] R₅dominates R₄

[0087] The corresponding acyclic directed graph is shown in FIG. 5. Examination of paths in the graphs leads to the following assignment of priority numbers.

[0088] R₀1

[0089] R₁1

[0090] R₂1

[0091] R₃4

[0092] R₄3

[0093] R₅2

[0094] Thus there are four priority number classes.

[0095] A companion program could be written to test for pure inclusion (any packet that satisfies one rule must also satisfy a rule that includes it). Once priority numbers are computed, a network administrator could then examine all inclusions and verify that if one rule is included in a second, then the first has a higher priority (lower priority number) than the second. If, in our example, Rule 4 (priority number 3) were included in Rule 5 (priority number 2), then Rule 4 would never be referenced (since 3>2).

[0096] Note again that in the present invention, a correct rule set has the property that no set of rules is cyclic, that is, that the associated directed graph is acyclic. The importance of this assumption is emphasized by the following theorem.

[0097] Theorem: No two rules with the same priority number intersect.

[0098] Proof:. Suppose rules 1 and 2 intersect, both have priority number p+1, and rule 1 dominates rule 2. If p=0, then all edges involving the rules are directed to the rules. But there is an edge directed from rule 2 to rule 1, a contradiction for rule 2. Assume p>0. Then the longest path from rule 1 to some rule 3 with priority number 1 is of length p. The same path can be used along with the edge from 2 to 1 to make a path of length p+1 from rule 2 to rule 3. Thus the priority number of rule 2 is at least p+2 contradicting the stated priority number p of rule 2. QED Table 1 (below) lists the pseudo-code for an algorithm, the Priority Number Algorithm, that determines the priority numbers of filter rules when rules and domination declarations are presented as vertices and edges in an acyclic directed graph.

[0099] Method: The graph is represented as a set of N vertices {i}, each corresponding to a rule, and a set J (possibly except 2) of some ordered pairs of vertex labels {(i, j) } with (i, j) signifying: rules i and j intersect and j dominates i. Since the graph is assumed to be acyclic, not both (i, j) and (j, i) can be edges. Also associated with each vertex is a nonnegative integer k. At the beginning of the program, all k:=0. At the end of the program, the priority number of a rule (vertex) is its k value, a natural number 1, 2, 3, . . .

[0100] FIG. 6 shows a flowchart for the Priority Number algorithm. The algorithm starts at 60. Sets of labels are defined in 62. The set of indices I occurring as first indices in the current set J of confirmation pairs is defined in 68. Then I and J are tested as empty or nonempty in 70. A cycle is found if we branch to 72. Else, I is tested again. The algorithm can end if we branch to 76. Else increment the priority number value x in 79. Then assign that value x to same rules in 80. Then delete such newly labeled rules from J in 82. Then go to 68.

[0101] As stated earlier, the pseudo-code (Table 1), when applied to the above six intersecting rules, yield the graph and priority numbers as shown in FIG. 5.

[0102] In summary, the present invention includes the following steps:

[0103] 1. The present invention tests the new rule and each preexisting rule for intersection. If an intersection is found, the administrator is asked to declare domination.

[0104] 2. After all dominations are declared, the Priority Number Algorithm set forth above, is run.

[0105] 3. If the Priority Number Algorithm ends by finding a cyclic domination pattern, then the program writes the same and the administrator is allowed to reverse one or more domination declarations or erase one or more rules. Then the rule set is resubmitted to the Priority Number Algorithm.

[0106] 4. Else, all rules have priority numbers.

[0107] 5. The present invention then tests the new rule and all preexisting rules for inclusion. If an inclusion is found, the priority numbers of the new rule and the preexisting rule are compared. If any pair is found in which the priority number of the included rule is higher than that of the other rule, then the present invention writes that there is an inclusion error (a rule has been entered which will never be referenced). Else, the present invention writes that the rule set with the new rule does not have an inclusion error.

[0108] 6. In the preferred embodiment, all the results from the above five functions are displayed or made available for display as computer generated images accompanied by computer generated text.

[0109] In view of the foregoing, the present invention provides an improved method and apparatus that improved the filtering process.

[0110] While the invention has been described in terms of preferred embodiments, those skilled in the art will recognize that the invention can be practiced with modification within the spirit and scope of the appended claims.