Patent US6539394B1 successfully refreshed from Google Patents.
US6539394B1
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and system for performing interval-based testing of filter rules
Assignee: International Business Machines Corp
•
Filing: 2000-01-04
•
Granted: 2003-03-25
•
Expires: 2020-01-04
Abstract
Abstract A method and system for testing a plurality of filter rules in a computer system is disclosed. The plurality of filter rules uses at least one range of values in at least one dimension. Each range includes a minimum and a maximum value. The filter rules are used with a key. The method and system include reducing an amount of testing required based on the minimum and maximum value of each range to ensure that the key can match a portion of the filter rules and testing the key against the portion of the filter rules. In one aspect, the method and system include determining at least one subset of filter rules and testing the key against each subset to determine whether the key matches a filter rule of a subset. The subset of filter rules is non-intersecting in at least a second dimension and is based on the minimum value and the maximum value of each range in the second dimension. In another aspect, the method and system include providing at least one bit for each interval set of a plurality of interval sets and providing a decision tree for the filter rules based on the interval sets. The bit characterizes each interval set. The decision tree includes leaf paths having at least one node and is for isolating a portion of the plurality of filter rules on a leaf path. Each node of the decision tree utilizes a bit of the at least one bit.
Inventors
- 👤 Jean Louis Calvignac
- 👤 Clark Debs Jeffries
- 👤 Fabrice Verplanken
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-08 02:21
CPC Classifications
H; H04; H04L; H04L63/00; H04L63/02; H04L43/00; H04L43/50; H04L63/0227; H04L63/0263; H04L63/04; Y; Y10; Y10S; Y10S707/00; Y10S707/99941; Y10S707/99943
Claims Analysis
Total Claims: 37
Claim 1
Independent Claim
111 words
A method for enforcing a plurality of filter rules in a computer system comprising the steps of: (a) preprocessing rules, each of which in at least one dimension applies to a certain minimum packet header field value and a certain maximum packet header field value, to form a binary search tree; and (b) compressing packet header bits into a key, the key being the concatenation of a plurality of labels, each label denoting membership in an interval of values; and (c) testing the compressed key relative to the binary search tree to reduce the number of rules that might still possibly apply to the packet to one or a small number.
Claim 2
Independent Claim
111 words
A method for enforcing a plurality of filter rules in a computer system comprising the steps of: (a) preprocessing rules, each of which in at least one dimension applies to a certain minimum packet header field value and a certain maximum packet header field value, to form a binary search tree; and (b) compressing packet header bits into a key, the key being the concatenation of a plurality of labels, each label denoting membership in an interval of values; and (c) testing the compressed key relative to the binary search tree to reduce the number of rules that might still possibly apply to the packet to one or a small number.
Claim 3
Dependent Claim
168 words
The method of claim 1 wherein the preprocessing step (a) further includes the steps of: (a1) determining at least one subset of filter rules of the plurality of filter rules, the at least one subset of filter rules being non-intersecting in the sense that no one packet is affected by any two or more filter rules; (a2) examining minimum values of rule ranges in an at least one dimension (header field) and defining a plurality of intervals bounded by the minimum range values of the plurality of rules in the each selected dimension; (a3) examining maximum values of rule ranges in an at least one dimension (header field) and defining a plurality of intervals bounded by the maximum range values of the plurality of rules in the each selected dimension; and (a4) labeling the intervals bounded by minimum values in the plurality of dimensions by convenient binary labels as well as labeling the intervals bounded by maximum values in the plurality of dimensions by additional, convenient binary values.
Claim 4
Dependent Claim
18 words
The method of claim 2 wherein each of the at least one subset of filter rules is nonintersecting.
Claim 5
Dependent Claim
105 words
The method of claim 2 wherein the subset of determining step (a1) further includes the steps of: (a1i) determining a first subset of the at least one subset of filter rules, the first subset being a largest possible subset of the plurality of filter rules that are nonintersecting; (a1ii) iteratively proceeding to additional nonintersecting subsets of the original filter rules so long as additional such subsets remain unprocessed; (a1iii) for each such subset of nonintersecting rules, iteratively processing the rules one dimension at a time, in any order; (a1iv) repeating steps (a1ii) and (a1iii) until no dimension of any subset of nonintersecting rules remains unprocessed.
Claim 6
Dependent Claim
93 words
The method of claim 1 wherein the compressing step (b) further includes the steps of: (b1) comparing each of a plurality of field values to the corresponding dimension intervals obtained by preprocessing rules by minimum range values to obtain labels designating membership of the header values in one of said intervals; and (b2) deriving additional label bits by comparing each of a plurality of field values to the corresponding dimension intervals obtained by preprocessing rules by maximum range values to obtain labels designating membership of the header values in one of said intervals.
Claim 7
Dependent Claim
103 words
The method of claim 1 wherein the testing step (c) further includes the steps of: (c1) submitting a key obtained from the original header bits of a packet to examination in a binary tree search of rules; (c2) reaching after at least one bit test a tree leaf at which only one rule or possible a small set of rules might still possibly apply to the packet; and (c3) finally testing the full, original, raw packet header key with respect to the full, original, raw rule ranges to determine the at most one rule that determines treatment of the packet in the device.
Claim 8
Dependent Claim
217 words
The method of claim 1 wherein rule preprocessing step (a) further includes the steps of: (a2i) providing a plurality of interval sets for each of the at least one dimension, a first interval set of the plurality of interval sets being based on the at least one minimum value of the at least one rule range interval and a second interval set of the plurality of interval sets being based on the at least one maximum value of the at least one rule range interval; (a2ii) providing at least one bit for each interval set of the plurality of interval sets, the at least one bit labeling each interval set of the plurality of interval sets; (a2iii) providing a decision tree for the plurality of filter rules based on the plurality of interval sets, the decision tree including a plurality of decision paths based upon bit values of the compressed key and having at least one node corresponding to at least one bit decision, each of the at least one node of the decision tree utilizing a bit of the at least one bit of the compressed key, the decision tree for isolating the portion of the plurality of filter rules that actually might match in terms of range values the original header bits of a packet.
Claim 9
Dependent Claim
38 words
The method of claim 7 wherein each of the plurality of interval sets includes a number of intervals, and wherein the at least one bit characterizes the number of intervals for each of the plurality of interval sets.
Claim 10
Dependent Claim
171 words
The method of claim 7 wherein the decision tree providing step (a2iii) further includes the steps of: (a3i) providing a matrix including at least one row and at least one column, the at least one matrix row being constructed from a vector for each of the plurality of filter rules, the vector including at least one entry having at least one digit, each of the at least one digit capable of being a one, a zero, or a wildcard; (a3ii) selecting a column of the at least one column for a first binary decision tree node of the at lest one node, the column having a minimum number of wildcards, and then having as close as possible to equal numbers of one entries and zero entries; (a3iii) eliminating the column from the at least one column; and (a3iv) repeating steps (a3ii) and (a3iii) on subsequent submatrices corresponding to branches of the binary decision tree to provide a remaining portion of the at least one node until the decision tree is completed.
Claim 11
Dependent Claim
140 words
The method of claim 7 wherein each of the plurality of interval sets includes at least one interval and wherein testing step (b) further includes the steps of: (b1) compressing original header bits of a packet by a process that yields at least one bit designating membership in exactly one interval of minimum type or one interval of maximum type in each of the at least one dimension for each of the at least one filter rule in the subset of at least one nonintersecting filter rules; and (b2) testing the at least one bit in the processed key using the decision tree by means of testing one bit or a set of bits simultaneously to reduce the set of rules that might apply to the packet to only one possible rule or to a small set of possible rules.
Claim 12
Dependent Claim
174 words
A computer-readable medium including a program for testing a plurality of filter rules in a computer system, the plurality of filter rules using at least one range of values in at least one dimension, each of the at least one range including a minimum and a maximum value, the plurality of filter rules being used with a processed key derived by comparing original packet header values to said intervals defined by minimum values in at least on dimension and maximum values in at least one dimension, the program including instructions for: (a1) determining at least one subset of filter rules of the plurality of filter rules, the at least one subset of filter rules being nonintersecting, the at least one subset being based on the minimum value and the maximum value of each of the at least one range; (a2) testing the processed key with respect to a binary decision tree generated from processing the nonintersecting rules; and (b) testing the full packet header key against the portion of the plurality of filter rules.
Claim 13
Dependent Claim
174 words
A computer-readable medium including a program for testing a plurality of filter rules in a computer system, the plurality of filter rules using at least one range of values in at least one dimension, each of the at least one range including a minimum and a maximum value, the plurality of filter rules being used with a processed key derived by comparing original packet header values to said intervals defined by minimum values in at least on dimension and maximum values in at least one dimension, the program including instructions for: (a1) determining at least one subset of filter rules of the plurality of filter rules, the at least one subset of filter rules being nonintersecting, the at least one subset being based on the minimum value and the maximum value of each of the at least one range; (a2) testing the processed key with respect to a binary decision tree generated from processing the nonintersecting rules; and (b) testing the full packet header key against the portion of the plurality of filter rules.
Claim 14
Dependent Claim
45 words
The computer-readable medium of claim 11 wherein testing instructions (b) further includes instructions for: (b1) testing the full, original packet header values against each of a small subset of one rule or a few rules that from step (a2) might still apply to the packet.
Claim 15
Dependent Claim
24 words
The computer-readable medium of claim 11 wherein each of the at least one subset of the plurality of filter rules is a distinct subset.
Claim 16
Dependent Claim
19 words
The computer-readable medium of claim 11 wherein each of the at least one subset of filter rules is nonintersecting.
Claim 17
Dependent Claim
104 words
The computer-readable medium of claim 11 wherein the subset determining instructions (a1) further includes instructions for: (a1i) determining a first subset of the at least one subset of filter rules, the first subset being a largest possible subset of the plurality of filter rules that are nonintersecting; (a1ii) iteratively proceeding to additional nonintersecting subsets of the original filter rules so long as additional such subsets remain unprocessed; (a1iii) for each such subset of nonintersecting rules, iteratively processing the rules one dimension at a time, in any order; (a1iv) repeating steps (a1ii) and (a1iii) until no dimension of any subset of nonintersecting rules remains unprocessed.
Claim 18
Dependent Claim
310 words
A computer-readable medium including a program for testing a plurality of filter rules in a computer system, the plurality of filter rules using at least one range of values in at least one dimension, each of the at least one range including a minimum and a maximum value, the plurality of filter rules being used with a processed key derived by comparing original packet header values to said intervals defined by minimum values in at least on dimension and maximum values in at least one dimension, the program including instructions for: (a1) providing a plurality of interval sets for each of the at least one dimension, a first interval set of the plurality of interval sets being based on the at least one minimum value of the at least one rule range interval and a second interval set of the plurality of interval sets being based on the at least one maximum value of the at least one rule range interval; (a2) providing at least one bit for each interval set of the plurality of interval sets, the at least one bit labeling each interval set of the plurality of interval sets; (a3) providing a decision tree for the plurality of filter rules based on the plurality of interval sets, the decision tree including a plurality of decision paths based upon bit values of a compressed key and having at least one node corresponding to at least one bit decision, each of the at least one node of the decision tree utilizing a bit of the at least one bit of the compressed key, the decision tree for isolating the portion of the plurality of filter rules that actually might match in terms of range values the original header bits of a packet; and (b) testing the full packet header key against the portion of the plurality of filter rules.
Claim 19
Dependent Claim
310 words
A computer-readable medium including a program for testing a plurality of filter rules in a computer system, the plurality of filter rules using at least one range of values in at least one dimension, each of the at least one range including a minimum and a maximum value, the plurality of filter rules being used with a processed key derived by comparing original packet header values to said intervals defined by minimum values in at least on dimension and maximum values in at least one dimension, the program including instructions for: (a1) providing a plurality of interval sets for each of the at least one dimension, a first interval set of the plurality of interval sets being based on the at least one minimum value of the at least one rule range interval and a second interval set of the plurality of interval sets being based on the at least one maximum value of the at least one rule range interval; (a2) providing at least one bit for each interval set of the plurality of interval sets, the at least one bit labeling each interval set of the plurality of interval sets; (a3) providing a decision tree for the plurality of filter rules based on the plurality of interval sets, the decision tree including a plurality of decision paths based upon bit values of a compressed key and having at least one node corresponding to at least one bit decision, each of the at least one node of the decision tree utilizing a bit of the at least one bit of the compressed key, the decision tree for isolating the portion of the plurality of filter rules that actually might match in terms of range values the original header bits of a packet; and (b) testing the full packet header key against the portion of the plurality of filter rules.
Claim 20
Dependent Claim
35 words
The computer-readable medium of claim 16 wherein each of the plurality of interval sets includes a number of intervals, and wherein the at least one bit labels the intervals in the plurality of interval sets.
Claim 21
Dependent Claim
171 words
The computer-readable medium of claim 16 wherein the decision tree providing instructions (a3) further includes instructions for: (a3i) providing a matrix including at least one row and at least one column, the at least one matrix row being constructed from a vector for each of the plurality of filter rules, the vector including at least one entry having at least one digit, each of the at least one digit capable of being a one, a zero, or a wildcard; (a3ii) selecting a column of the at least one column for a first binary decision tree node of the at lest one node, the column having a minimum number of wildcards, and then having as close as possible to equal numbers of one entries and zero entries; (a3iii) eliminating the column from the at least one column; and (a3iv) repeating steps (a3ii) and (a3iii) on subsequent matrices corresponding to branches of the binary decision tree to provide a remaining portion of the at least one node until the decision tree is completed.
Claim 22
Dependent Claim
141 words
The computer-readable medium of claim 16 wherein each of the plurality of interval sets includes at least one interval and wherein testing instructions (b) further includes the steps of: (b1) compressing original header bits of a packet by a process that yields at least one bit designating membership in exactly one interval of minimum type or one interval of maximum type in each of the at least one dimension for each of the at least one filter rule in the subset of at least one nonintersecting filter rules; and (b2) testing the at least one bit in the processed key using the decision tree by means of testing one bit or a set of bits simultaneously to reduce the set of rules that might apply to the packet to only one possible rule or to a small set of possible rules.
Claim 23
Independent Claim
141 words
A system for testing a plurality of filter rules in a computer system, the plurality of filter rules using at least one range of values in at least one dimension, each of the at least one range including a minimum and a maximum value, the plurality of filter rules being used with a key, the system comprising: a plurality of hosts for transmitting and receiving data; means for reducing an amount of testing required by using a compressed key and a binary decision tree obtained from a processed set of filter rules based upon intervals defined by minimums and intervals defined by maximums occurring in ranges of filter rules to ensure that the original packet header can match only a portion of the plurality of filter rules and for testing the original packet header key against that portion of filter rules.
Claim 24
Independent Claim
141 words
A system for testing a plurality of filter rules in a computer system, the plurality of filter rules using at least one range of values in at least one dimension, each of the at least one range including a minimum and a maximum value, the plurality of filter rules being used with a key, the system comprising: a plurality of hosts for transmitting and receiving data; means for reducing an amount of testing required by using a compressed key and a binary decision tree obtained from a processed set of filter rules based upon intervals defined by minimums and intervals defined by maximums occurring in ranges of filter rules to ensure that the original packet header can match only a portion of the plurality of filter rules and for testing the original packet header key against that portion of filter rules.
Claim 25
Dependent Claim
52 words
The system of claim 20 wherein the reducing means further determine at least one subset of filter rules of the plurality of filter rules, the at least one subset of filter rules being nonintersecting in, the at least one subset having minimum and maximum values for each filter rule in each dimension.
Claim 26
Dependent Claim
14 words
The system of claim 21 in which the reducing means further include a switch.
Claim 27
Dependent Claim
14 words
The system of claim 21 in which the reducing means further include a gateway.
Claim 28
Dependent Claim
98 words
The system of claim 21 wherein the reducing means determine a subset by determining a first subset of the at least one subset of filter rules, the first subset being a largest possible subset of the plurality of filter rules that are nonintersecting, processing second that set by means of identifying and labeling intervals of the dimensions based upon minimum range values and then identifying and labeling intervals of the dimensions based upon maximum range values, and iterating upon completion of processing of one subset back to the remaining original filter rules until no original filter rules remain.
Claim 29
Dependent Claim
86 words
The system of claim 20 wherein reducing means further provide a plurality of interval sets for each of the at least one dimension, a first interval set having interval endpoints defined by the minimum values in the ranges of the filter rules for each of the at least one dimension of the filter rules, and a second interval set having interval endpoints defined by the maximum values in the ranges of the filter rules for each of the at least one dimension of the filter rules.
Claim 30
Dependent Claim
58 words
The system of claim 25 wherein each of the plurality of intervals in each of the at least one interval set has its intervals labeled by binary values of length that is minimal but sufficient to label distinctly the intervals in the particular type (minimum or maximum) in the particular dimension in the particular set of filter rules.
Claim 31
Dependent Claim
13 words
The system of claim 25 wherein the reducing means further include a switch.
Claim 32
Dependent Claim
13 words
The system of claim 25 wherein the reducing means further include a gateway.
Claim 33
Dependent Claim
142 words
The system of claim 25 wherein each of the plurality of interval sets includes at least one interval and wherein testing bits in a compressed key further includes the steps of compressing original header bits of a packet by a process that yields at least one bit designating membership in exactly one interval of minimum type or one interval of maximum type in each of the at least one dimension for each of the at least one filter rule in the subset of at least one nonintersecting filter rules and testing the at least one bit in the processed key using the resulting decision tree by means of testing one bit or a set of bits simultaneously to reduce the set of rules that might apply to the packet to only one possible rule or to a small set of possible rules.
Claim 34
Dependent Claim
158 words
The system of claim 20 wherein the reducing means further providing a matrix including at least one row and at least one column, the at least one matrix row being constructed from a vector for each of the plurality of filter rules, the vector including at least one entry having at least one digit, each of the at least one digit capable of being a one, a zero, or a wildcard, selecting a column of the at least one column for a first binary decision tree node of the at lest one node, the column having a minimum number of wildcards, and then having as close as possible to equal numbers of one entries and zero entries, eliminating the column from the at least one column, and repeating these steps on subsequent submatrices corresponding to branches of the binary decision tree to provide a remaining portion of the at least one node until the decision tree is completed.
Claim 35
Independent Claim
95 words
A method for enforcing a plurality of filter rules against header bits of a packet comprising the acts of: (a) compressing the header bits into a plurality of labels wherein each label denoting membership in an interval of values derived from minimum and maximum values of the rules; (b) preprocessing the rules; (c) generating a binary search tree based upon the labels and preprocessed rules wherein only a portion of the preprocess rules correspond to a label; and (d) using labels in the tree to identify header bits selected to traverse the binary search tree.
Claim 36
Independent Claim
95 words
A method for enforcing a plurality of filter rules against header bits of a packet comprising the acts of: (a) compressing the header bits into a plurality of labels wherein each label denoting membership in an interval of values derived from minimum and maximum values of the rules; (b) preprocessing the rules; (c) generating a binary search tree based upon the labels and preprocessed rules wherein only a portion of the preprocess rules correspond to a label; and (d) using labels in the tree to identify header bits selected to traverse the binary search tree.
Claim 37
Dependent Claim
31 words
The method of claim 31 further including the step of when a leaf of the tree is reached, comparing header bits with the portion of the rules stored in said leaf.
References Cited (Backward Citations)
US5574910A
Cited
US5835726A
Cited
US5951649A
Cited
US5546390A
Cited
US5790634A
Cited
US5828833A
Cited
US5898830A
Cited
US5848233A
Cited
US6298340B1
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2006-03-24 | 2006-09-23 | 2007-03-25 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2010-03-24 | 2010-09-23 | 2011-03-25 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2014-03-24 | 2014-09-23 | 2015-03-25 | $7700.00 | Window Closed / Lapsed |