Patent US6473763B1 successfully refreshed from Google Patents.
US6473763B1
Expired / Lapsed
US
⏱️ 0.0 years remaining
System, method and computer program for filtering multi-action rule set
Assignee: International Business Machines Corp
•
Filing: 2000-03-31
•
Granted: 2002-10-29
•
Expires: 2020-03-31
Abstract
Abstract A method and system for testing a plurality of filter rules in a computer system is disclosed. The plurality of filter rules is used with a key. Each of the plurality of filter rules is capable of being described using a plurality of bits corresponding to a portion of the key. The plurality of bits can include at least one binary value, at least one wildcard, and at least one boundary symbol. The at least one binary value can be a zero or a one. The method and system include selecting a portion of the plurality of filter rules that the key can match by testing part of the key against a portion of the plurality of bits and explicitly testing the key against the portion of the plurality of filter rules. A first bit of the portion of the plurality of bits has a first maximum number of the at least one binary symbol for the plurality of filter rules. Each subsequent bit of the portion plurality of bits has a second maximum number of the at least one binary symbol for a plurality of remaining bits and is selected based on testing of a prior bit. Preferably, the portion of the plurality of bits is tested using a decision tree which includes nodes corresponding to a second portion of the plurality of bits.
Inventors
- 👤 Everett Arthur Corl, Jr.
- 👤 Clark Debs Jeffries
- 👤 Colin Beaton Verrilli
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-06 16:25
CPC Classifications
H; H04; H04L; H04L63/00; H04L63/02; H04L63/0227; H04L63/0263; G; G06; G06F; G06F11/00; G06F16/00; G06F16/90; G06F16/903; G06F16/90335; G06F16/90344; H04L43/00; H04L43/50; H04L63/0236; H04L63/14; H04L63/1433; Y; Y10; Y10S; Y10S707/00; Y10S707/99941; Y10S707/99942; Y10S707/99943
Claims Analysis
Total Claims: 51
Claim 1
Independent Claim
216 words
A method for testing a plurality of filter rules in a computer system, the plurality of filter rules being used with a key, each of the plurality of filter rules capable of being described using a plurality of bits, the plurality of bits capable of including at least one binary value, at least one wildcard, and at least one boundary symbol, the at least one binary value of a filter rule of the plurality of filter rules capable of being a zero or a one, the plurality of bits corresponding to a portion of the key, the method comprising the steps of: (a) selecting a portion of the plurality of filter rules that the key can match by testing the key against a portion of the plurality of bits, a first bit of the portion of the plurality of bits having a first maximum number of the at least one binary symbol for the plurality of filter rules, each subsequent bit of the portion plurality of bits having a second maximum number of the at least one binary symbol for a plurality of remaining bits and being selected based on testing of a prior bit of the portion of the plurality of bits; and (b) testing the portion of the plurality of rules against the key.
Claim 2
Independent Claim
216 words
A method for testing a plurality of filter rules in a computer system, the plurality of filter rules being used with a key, each of the plurality of filter rules capable of being described using a plurality of bits, the plurality of bits capable of including at least one binary value, at least one wildcard, and at least one boundary symbol, the at least one binary value of a filter rule of the plurality of filter rules capable of being a zero or a one, the plurality of bits corresponding to a portion of the key, the method comprising the steps of: (a) selecting a portion of the plurality of filter rules that the key can match by testing the key against a portion of the plurality of bits, a first bit of the portion of the plurality of bits having a first maximum number of the at least one binary symbol for the plurality of filter rules, each subsequent bit of the portion plurality of bits having a second maximum number of the at least one binary symbol for a plurality of remaining bits and being selected based on testing of a prior bit of the portion of the plurality of bits; and (b) testing the portion of the plurality of rules against the key.
Claim 3
Dependent Claim
168 words
The method of claim 1 wherein the selecting step (a) further includes the step of: (a1) selecting the portion of the plurality of filter rules that the key can match using a decision tree and the portion of the plurality of bits, the decision tree including a plurality of nodes and a plurality of leaves, the portion of the plurality of filter rules being on at least one leaf of the plurality of leaves, a first node of the plurality of nodes corresponding to the first bit of the plurality of bits for each of the plurality of filter rules, the first bit having a first maximum number of the at least one binary symbol for the plurality of filter rules, each subsequent node of the plurality of nodes corresponding to a bit of a second plurality of remaining bits for each of the plurality of filter rules, the bit having a second maximum number of the at least one binary symbol for the plurality of remaining bits.
Claim 4
Dependent Claim
248 words
The method of claim 2 wherein the method further includes the step of: (c) providing the decision tree, the decision tree providing step including the steps of: (c1) providing a first matrix having a plurality of rows and a plurality of columns, each of the plurality of rows corresponding to a filter rule of the plurality of filter rules, each of the plurality of columns corresponding to a bit of the plurality of bits for the plurality of filter rules; (c2) providing a first node of the plurality of nodes using the first bit of the plurality of bits, the first bit corresponding to a column of the first matrix that has the first maximum number of the at least one binary symbols for the plurality of filter rules; (c3) providing a second matrix based on the first matrix, the second matrix including a wildcard for an entry in the column if the entry is a zero and excluding a row of the first matrix if the entry in the column for the row is a one; (c4) providing a third matrix based on the first matrix, the third matrix including a wildcard for an entry in the column if the entry is a one and excluding a row of the first matrix if the entry in the column for the row is a zero; (c5) repeating steps (c2) through (c4) for each of the second matrix and the third matrix until the plurality of nodes is provided.
Claim 5
Dependent Claim
35 words
The method of claim 3 wherein the first matrix providing step further includes the step of: (c1i) ranking the plurality of filter rules based on a priority of each of the plurality of filter rules.
Claim 6
Dependent Claim
35 words
The method of claim 3 wherein the first matrix providing step further includes the step of: (c1i) ranking the plurality of filter rules based on a type of each of the plurality of filter rules.
Claim 7
Dependent Claim
46 words
The method of claim 3 wherein the first matrix providing step further includes the step of: (c1i) ranking the plurality of filter rules based on a type of each of the plurality of filter rules and a priority of each of the plurality of filter rules.
Claim 8
Dependent Claim
79 words
The method of claim 3 wherein the first, second and third matrix are capable of having a pair of duplicate rows having a same type, a first row of the pair of duplicate rows having a higher priority, a second row of the pair of duplicate rows having a lower priority, neither row of the pair of duplicate rows having a boundary symbol, the first matrix, second matrix and third matrix further being provided by removing the second row.
Claim 9
Dependent Claim
37 words
The method of claim 1 wherein the key further includes a plurality of fields and wherein the plurality of bits for each of the plurality of filter rules corresponds to a field of the plurality of fields.
Claim 10
Dependent Claim
62 words
The method of claim 8 wherein the plurality of filter rules are further described by a second plurality of bits corresponding to remaining fields of the plurality of fields, and wherein the method further includes the steps of: (c) repeating steps (a) and (b) for the remaining fields of the plurality of fields using a portion of the second plurality of bits.
Claim 11
Dependent Claim
52 words
The method of claim 3 wherein the decision tree includes at least one pointer from at least one particular node of the plurality of nodes to at least a starting node of at least one subtree, thereby allowing the at least one subtree to be utilized for more than a single node.
Claim 12
Dependent Claim
18 words
The method of claim 1 wherein the plurality of filter rules can be of a plurality of types.
Claim 13
Independent Claim
341 words
A method for providing a decision tree for testing a plurality of filter rules in a computer system, the decision tree including a plurality of nodes and a plurality of leaves, the plurality of filter rules being used with a key, each of the plurality of filter rules capable of being described using a plurality of bits, the plurality of bits capable of including at least one binary value, at least one wildcard, and at least one boundary symbol, the at least one binary value of a filter rule of the plurality of filter rules capable of being a zero or a one, the plurality of bits corresponding to a portion of the key, the method comprising the steps of: (a) providing a first matrix having a plurality of rows and a plurality of columns, each of the plurality of rows corresponding to a filter rule of the plurality of filter rules, each of the plurality of columns corresponding to a bit of the plurality of bits for the plurality of filter rules; (b) providing a first node of the plurality of nodes using a first bit of the plurality of bits, the first bit corresponding to a column of the first matrix that has a first maximum number of the at least one binary symbols for the plurality of filter rules; (c) providing a second matrix based on the first matrix, the second matrix including a wildcard for an entry in the column if the entry is a zero and excluding a row of the first matrix if the entry in the column for the row is a one; (d) providing a third matrix based on the first matrix, the third matrix including a wildcard for an entry in the column if the entry is a one and excluding a row of the first matrix if the entry in the column for the row is a zero; (e) repeating steps (b) through (d) for each of the second matrix and the third matrix until the plurality of nodes is provided.
Claim 14
Independent Claim
341 words
A method for providing a decision tree for testing a plurality of filter rules in a computer system, the decision tree including a plurality of nodes and a plurality of leaves, the plurality of filter rules being used with a key, each of the plurality of filter rules capable of being described using a plurality of bits, the plurality of bits capable of including at least one binary value, at least one wildcard, and at least one boundary symbol, the at least one binary value of a filter rule of the plurality of filter rules capable of being a zero or a one, the plurality of bits corresponding to a portion of the key, the method comprising the steps of: (a) providing a first matrix having a plurality of rows and a plurality of columns, each of the plurality of rows corresponding to a filter rule of the plurality of filter rules, each of the plurality of columns corresponding to a bit of the plurality of bits for the plurality of filter rules; (b) providing a first node of the plurality of nodes using a first bit of the plurality of bits, the first bit corresponding to a column of the first matrix that has a first maximum number of the at least one binary symbols for the plurality of filter rules; (c) providing a second matrix based on the first matrix, the second matrix including a wildcard for an entry in the column if the entry is a zero and excluding a row of the first matrix if the entry in the column for the row is a one; (d) providing a third matrix based on the first matrix, the third matrix including a wildcard for an entry in the column if the entry is a one and excluding a row of the first matrix if the entry in the column for the row is a zero; (e) repeating steps (b) through (d) for each of the second matrix and the third matrix until the plurality of nodes is provided.
Claim 15
Dependent Claim
35 words
The method of claim 12 wherein the first matrix providing step further includes the step of: (a1) ranking the plurality of filter rules based on a priority of each of the plurality of filter rules.
Claim 16
Dependent Claim
35 words
The method of claim 12 wherein the first matrix providing step further includes the step of: (a2) ranking the plurality of filter rules based on a type of each of the plurality of filter rules.
Claim 17
Dependent Claim
46 words
The method of claim 12 wherein the first matrix providing step further includes the step of: (a3) ranking the plurality of filter rules based on a type of each of the plurality of filter rules and a priority of each of the plurality of filter rules.
Claim 18
Dependent Claim
79 words
The method of claim 12 wherein the first, second and third matrix are capable of having a pair of duplicate rows having a same type, a first row of the pair of duplicate rows having a higher priority, a second row of the pair of duplicate rows having a lower priority, neither row of the pair of duplicate rows having a boundary symbol, the first matrix, second matrix and third matrix further being provided by removing the second row.
Claim 19
Dependent Claim
37 words
The method of claim 13 wherein the key further includes a plurality of fields and wherein the plurality of bits for each of the plurality of filter rules corresponds to a field of the plurality of fields.
Claim 20
Dependent Claim
74 words
The method of claim 17 wherein the plurality of filter rules are further described by a second plurality of bits corresponding to remaining fields of the plurality of fields, and wherein the method further includes the steps of: (f) repeating steps (a) through (e) for the remaining fields of the plurality of fields using a portion of the second plurality of bits, thereby providing a plurality of decision trees for the plurality of fields.
Claim 21
Dependent Claim
67 words
The method of claim 12 further comprising the step of: (f) replacing at least one particular subtree with at least one pointer from at least one particular node of the at least one particular subtree to at least a starting node of at least one other subtree, thereby allowing the at least one other subtree to be utilized in place of the at least one particular subtree.
Claim 22
Dependent Claim
219 words
A computer-readable medium including a program for testing a plurality of filter rules in a computer system, the plurality of filter rules being used with a key, each of the plurality of filter rules capable of being described using a plurality of bits, the plurality of bits capable of including at least one binary value, at least one wildcard, and at least one boundary symbol, the at least one binary value of a filter rule of the plurality of filter rules capable of being a zero or a one, the plurality of bits corresponding to a portion of the key, the program including instructions for: (a) selecting a portion of the plurality of filter rules that the key can match by testing the key against a portion of the plurality of bits, a first bit of the portion of the plurality of bits having a first maximum number of the at least one binary symbol for the plurality of filter rules, each subsequent bit of the portion plurality of bits having a second maximum number of the at least one binary symbol for a plurality of remaining bits and being selected based on testing of a prior bit of the portion of the plurality of bits; and (b) testing the portion of the plurality of rules against the key.
Claim 23
Dependent Claim
219 words
A computer-readable medium including a program for testing a plurality of filter rules in a computer system, the plurality of filter rules being used with a key, each of the plurality of filter rules capable of being described using a plurality of bits, the plurality of bits capable of including at least one binary value, at least one wildcard, and at least one boundary symbol, the at least one binary value of a filter rule of the plurality of filter rules capable of being a zero or a one, the plurality of bits corresponding to a portion of the key, the program including instructions for: (a) selecting a portion of the plurality of filter rules that the key can match by testing the key against a portion of the plurality of bits, a first bit of the portion of the plurality of bits having a first maximum number of the at least one binary symbol for the plurality of filter rules, each subsequent bit of the portion plurality of bits having a second maximum number of the at least one binary symbol for a plurality of remaining bits and being selected based on testing of a prior bit of the portion of the plurality of bits; and (b) testing the portion of the plurality of rules against the key.
Claim 24
Dependent Claim
168 words
The computer-readable medium of claim 20 wherein the selecting instructions (a) further includes instructions for: (a1) selecting the portion of the plurality of filter rules that the key can match using a decision tree and the portion of the plurality of bits, the decision tree including a plurality of nodes and a plurality of leaves, the portion of the plurality of filter rules being on at least one leaf of the plurality of leaves, a first node of the plurality of nodes corresponding to the first bit of the plurality of bits for each of the plurality of filter rules, the first bit having a first maximum number of the at least one binary symbol for the plurality of filter rules, each subsequent node of the plurality of nodes corresponding to a bit of a second plurality of remaining bits for each of the plurality of filter rules, the bit having a second maximum number of the at least one binary symbol for the plurality of remaining bits.
Claim 25
Dependent Claim
247 words
The computer-readable medium of claim 21 wherein the program further includes instructions for: (c) providing the decision tree, the decision tree providing instruction including instructions for: (c1) providing a first matrix having a plurality of rows and a plurality of columns, each of the plurality of rows corresponding to a filter rule of the plurality of filter rules, each of the plurality of columns corresponding to a bit of the plurality of bits for the plurality of filter rules; (c2) providing a first node of the plurality of nodes using the first bit of the plurality of bits, the first bit corresponding to a column of the first matrix that has the first maximum number of the at least one binary symbols for the plurality of filter rules; (c3) providing a second matrix based on the first matrix, the second matrix including a wildcard for an entry in the column if the entry is a zero and excluding a row of the first matrix if the entry in the column for the row is a one; (c4) providing a third matrix based on the first matrix, the third matrix including a wildcard for an entry in the column if the entry is a one and excluding a row of the first matrix if the entry in the column for the row is a zero; (c5) repeating instructions (c2) through (c4) for each of the second matrix and the third matrix until the plurality of nodes are provided.
Claim 26
Dependent Claim
35 words
The computer-readable medium of claim 22 wherein the first matrix providing step further includes instructions for: (c1i) ranking the plurality of filter rules based on a priority of each of the plurality of filter rules.
Claim 27
Dependent Claim
35 words
The computer-readable medium of claim 22 wherein the first matrix providing step further includes instructions for: (c1i) ranking the plurality of filter rules based on a type of each of the plurality of filter rules.
Claim 28
Dependent Claim
46 words
The computer-readable medium of claim 22 wherein the first matrix providing step further includes instructions for: (c1i) ranking the plurality of filter rules based on a type of each of the plurality of filter rules and a priority of each of the plurality of filter rules.
Claim 29
Dependent Claim
53 words
The computer-readable medium of claim 22 wherein the decision tree includes at least one pointer from at least one particular node of the plurality of nodes to at least a starting node of at least one subtree, thereby allowing the at least one subtree to be utilized for more than a single node.
Claim 30
Dependent Claim
344 words
A computer-readable medium containing a program for providing a decision tree for testing a plurality of filter rules in a computer system, the decision tree including a plurality of nodes and a plurality of leaves, the plurality of filter rules being used with a key, each of the plurality of filter rules capable of being described using a plurality of bits, the plurality of bits capable of including at least one binary value, at least one wildcard, and at least one boundary symbol, the at least one binary value of a filter rule of the plurality of filter rules capable of being a zero or a one, the plurality of bits corresponding to a portion of the key, the program including instructions for: (a) providing a first matrix having a plurality of rows and a plurality of columns, each of the plurality of rows corresponding to a filter rule of the plurality of filter rules, each of the plurality of columns corresponding to a bit of the plurality of bits for the plurality of filter rules; (b) providing a first node of the plurality of nodes using a first bit of the plurality of bits, the first bit corresponding to a column of the first matrix that has a first maximum number of the at least one binary symbols for the plurality of filter rules; (c) providing a second matrix based on the first matrix, the second matrix including a wildcard for an entry in the column if the entry is a zero and excluding a row of the first matrix if the entry in the column for the row is a one; (d) providing a third matrix based on the first matrix, the third matrix including a wildcard for an entry in the column if the entry is a one and excluding a row of the first matrix if the entry in the column for the row is a zero; (e) repeating steps (b) through (d) for each of the second matrix and the third matrix until the plurality of nodes is provided.
Claim 31
Dependent Claim
344 words
A computer-readable medium containing a program for providing a decision tree for testing a plurality of filter rules in a computer system, the decision tree including a plurality of nodes and a plurality of leaves, the plurality of filter rules being used with a key, each of the plurality of filter rules capable of being described using a plurality of bits, the plurality of bits capable of including at least one binary value, at least one wildcard, and at least one boundary symbol, the at least one binary value of a filter rule of the plurality of filter rules capable of being a zero or a one, the plurality of bits corresponding to a portion of the key, the program including instructions for: (a) providing a first matrix having a plurality of rows and a plurality of columns, each of the plurality of rows corresponding to a filter rule of the plurality of filter rules, each of the plurality of columns corresponding to a bit of the plurality of bits for the plurality of filter rules; (b) providing a first node of the plurality of nodes using a first bit of the plurality of bits, the first bit corresponding to a column of the first matrix that has a first maximum number of the at least one binary symbols for the plurality of filter rules; (c) providing a second matrix based on the first matrix, the second matrix including a wildcard for an entry in the column if the entry is a zero and excluding a row of the first matrix if the entry in the column for the row is a one; (d) providing a third matrix based on the first matrix, the third matrix including a wildcard for an entry in the column if the entry is a one and excluding a row of the first matrix if the entry in the column for the row is a zero; (e) repeating steps (b) through (d) for each of the second matrix and the third matrix until the plurality of nodes is provided.
Claim 32
Independent Claim
237 words
A system for testing a plurality of filter rules in a computer system, A method for testing a plurality of filter rules in a computer system, the plurality of filter rules being used with a key, each of the plurality of filter rules capable of being described using a plurality of bits, the plurality of bits capable of including at least one binary value, at least one wildcard, and at least one boundary symbol, the at least one binary value of a filter rule of the plurality of filter rules capable of being a zero or a one, the plurality of bits corresponding to a portion of the key, the system comprising: a plurality of hosts for transmitting and receiving data; a switch for selecting a portion of the plurality of filter rules that the key can match by testing the key against a portion of the plurality of bits, a first bit of the portion of the plurality of bits having a first maximum number of the at least one binary symbol for the plurality of filter rules, each subsequent bit of the portion plurality of bits having a second maximum number of the at least one binary symbol for a plurality of remaining bits and being selected based on testing of a prior bit of the portion of the plurality of bits and for testing the portion of the plurality of rules against the key.
Claim 33
Independent Claim
237 words
A system for testing a plurality of filter rules in a computer system, A method for testing a plurality of filter rules in a computer system, the plurality of filter rules being used with a key, each of the plurality of filter rules capable of being described using a plurality of bits, the plurality of bits capable of including at least one binary value, at least one wildcard, and at least one boundary symbol, the at least one binary value of a filter rule of the plurality of filter rules capable of being a zero or a one, the plurality of bits corresponding to a portion of the key, the system comprising: a plurality of hosts for transmitting and receiving data; a switch for selecting a portion of the plurality of filter rules that the key can match by testing the key against a portion of the plurality of bits, a first bit of the portion of the plurality of bits having a first maximum number of the at least one binary symbol for the plurality of filter rules, each subsequent bit of the portion plurality of bits having a second maximum number of the at least one binary symbol for a plurality of remaining bits and being selected based on testing of a prior bit of the portion of the plurality of bits and for testing the portion of the plurality of rules against the key.
Claim 34
Dependent Claim
138 words
The system of claim 28 wherein the switch includes: a decision tree, the decision tree including a plurality of nodes and a plurality of leaves, the portion of the plurality of filter rules being on at least one leaf of the plurality of leaves, a first node of the plurality of nodes corresponding to the first bit of the plurality of bits for each of the plurality of filter rules, the first bit having a first maximum number of the at least one binary symbol for the plurality of filter rules, each subsequent node of the plurality of nodes corresponding to a bit of a second plurality of remaining bits for each of the plurality of filter rules, the bit having a second maximum number of the at least one binary symbol for the plurality of remaining bits.
Claim 35
Dependent Claim
257 words
The system of claim 29 further comprising: a control point for providing the decision tree, the decision tree being provided by providing a first matrix having a plurality of rows and a plurality of columns, each of the plurality of rows corresponding to a filter rule of the plurality of filter rules, each of the plurality of columns corresponding to a bit of the plurality of bits for the plurality of filter rules, providing a first node of the plurality of nodes using the first bit of the plurality of bits, the first bit corresponding to a column of the first matrix that has the first maximum number of the at least one binary symbols for the plurality of filter rules, providing a second matrix based on the first matrix, the second matrix including a wildcard for an entry in the column if the entry is a zero and excluding a row of the first matrix if the entry in the column for the row is a one, providing a third matrix based on the first matrix, the third matrix including a wildcard for an entry in the column if the entry is a one zero and excluding a row of the first matrix if the entry in the column for the row is a zero and repeating the steps of selecting the columns, providing a node, providing the second matrix and providing the third matrix for the second and third matrices until the portion of the plurality of rules can be isolated on the decision tree.
Claim 36
Dependent Claim
30 words
The system of claim 30 wherein the first matrix is provided by ranking the plurality of filter rules based on a priority of each of the plurality of filter rules.
Claim 37
Dependent Claim
30 words
The system of claim 30 wherein the first matrix is provided by ranking the plurality of filter rules based on a type of each of the plurality of filter rules.
Claim 38
Dependent Claim
41 words
The system of claim 30 wherein the first matrix is provided by ranking the plurality of filter rules based on a type of each of the plurality of filter rules and a priority of each of the plurality of filter rules.
Claim 39
Dependent Claim
79 words
The system of claim 30 wherein the first, second and third matrix are capable of having a pair of duplicate rows having a same type, a first row of the pair of duplicate rows having a higher priority, a second row of the pair of duplicate rows having a lower priority, neither row of the pair of duplicate rows having a boundary symbol, the first matrix, second matrix and third matrix further being provided by removing the second row.
Claim 40
Dependent Claim
37 words
The system of claim 28 wherein the key further includes a plurality of fields and wherein the plurality of bits for each of the plurality of filter rules corresponds to a field of the plurality of fields.
Claim 41
Dependent Claim
75 words
The system of claim 35 wherein the plurality of filter rules are further described by a second plurality of bits corresponding to remaining fields of the plurality of fields, and wherein the switch repeats the selection of the portion of the plurality of filter rules and the testing of the portion of the plurality of filter rules for the remaining fields of the plurality of fields using a portion of the second plurality of bits.
Claim 42
Dependent Claim
52 words
The system of claim 30 wherein the decision tree includes at least one pointer from at least one particular node of the plurality of nodes to at least a starting node of at least one subtree, thereby allowing the at least one subtree to be utilized for more than a single node.
Claim 43
Dependent Claim
18 words
The system of claim 29 wherein the plurality of filter rules can be of a plurality of types.
Claim 44
Independent Claim
382 words
A system for testing a plurality of filter rules in a computer system, the plurality of filter rules being used with a key, each of the plurality of filter rules capable of being described using a plurality of bits, the plurality of bits capable of including at least one binary value, at least one wildcard, and at least one boundary symbol, the at least one binary value of a filter rule of the plurality of filter rules capable of being a zero or a one, the plurality of bits corresponding to a portion of the key, the system comprising: a plurality of hosts for transmitting and receiving data; a control point for providing a decision tree; and logic coupled with the plurality of hosts and the control point for testing the plurality of filter rules, the logic including the decision tree having a plurality of nodes and a plurality of leaves, the decision tree being provided by providing a first matrix having a plurality of rows and a plurality of columns, each of the plurality of rows corresponding to a filter rule of the plurality of filter rules, each of the plurality of columns corresponding to a bit of the plurality of bits for the plurality of filter rules, providing a first node of the plurality of nodes using a first bit of the plurality of bits, the first bit corresponding to a column of the first matrix that has a first maximum number of the at least one binary symbols for the plurality of filter rules, providing a second matrix based on the first matrix, the second matrix including a wildcard for an entry in the column if the entry is a zero and excluding a row of the first matrix if the entry in the column for the row is a one, providing a third matrix based on the first matrix, the third matrix including a wildcard for an entry in the column if the entry is a one zero and excluding a row of the first matrix if the entry in the column for the row is a zero and repeating the column selecting, second matrix providing and third matrix providing steps for the second and third matrix to provide a plurality of remaining nodes for the decision tree.
Claim 45
Independent Claim
382 words
A system for testing a plurality of filter rules in a computer system, the plurality of filter rules being used with a key, each of the plurality of filter rules capable of being described using a plurality of bits, the plurality of bits capable of including at least one binary value, at least one wildcard, and at least one boundary symbol, the at least one binary value of a filter rule of the plurality of filter rules capable of being a zero or a one, the plurality of bits corresponding to a portion of the key, the system comprising: a plurality of hosts for transmitting and receiving data; a control point for providing a decision tree; and logic coupled with the plurality of hosts and the control point for testing the plurality of filter rules, the logic including the decision tree having a plurality of nodes and a plurality of leaves, the decision tree being provided by providing a first matrix having a plurality of rows and a plurality of columns, each of the plurality of rows corresponding to a filter rule of the plurality of filter rules, each of the plurality of columns corresponding to a bit of the plurality of bits for the plurality of filter rules, providing a first node of the plurality of nodes using a first bit of the plurality of bits, the first bit corresponding to a column of the first matrix that has a first maximum number of the at least one binary symbols for the plurality of filter rules, providing a second matrix based on the first matrix, the second matrix including a wildcard for an entry in the column if the entry is a zero and excluding a row of the first matrix if the entry in the column for the row is a one, providing a third matrix based on the first matrix, the third matrix including a wildcard for an entry in the column if the entry is a one zero and excluding a row of the first matrix if the entry in the column for the row is a zero and repeating the column selecting, second matrix providing and third matrix providing steps for the second and third matrix to provide a plurality of remaining nodes for the decision tree.
Claim 46
Dependent Claim
30 words
The system of claim 39 wherein the first matrix is provided by ranking the plurality of filter rules based on a priority of each of the plurality of filter rules.
Claim 47
Dependent Claim
30 words
The system of claim 39 wherein the first matrix is provided by ranking the plurality of filter rules based on a type of each of the plurality of filter rules.
Claim 48
Dependent Claim
41 words
The system of claim 39 wherein the first matrix is provided by ranking the plurality of filter rules based on a type of each of the plurality of filter rules and a priority of each of the plurality of filter rules.
Claim 49
Dependent Claim
37 words
The system of claim 39 wherein the key further includes a plurality of fields and wherein the plurality of bits for each of the plurality of filter rules corresponds to a field of the plurality of fields.
Claim 50
Dependent Claim
79 words
The system of claim 39 wherein the first, second and third matrix are capable of having a pair of duplicate rows having a same type, a first row of the pair of duplicate rows having a higher priority, a second row of the pair of duplicate rows having a lower priority, neither row of the pair of duplicate rows having a boundary symbol, the first matrix, second matrix and third matrix further being provided by removing the second row.
Claim 51
Dependent Claim
69 words
The system of claim 39 wherein the decision tree is further formed by replacing at least one particular subtree with at least one pointer from at least one particular node of the at least one particular subtree to at least a starting node of at least one other subtree, thereby allowing the at least one other subtree to be utilized in place of the at least one particular subtree.
References Cited (Backward Citations)
US4677550A
Cited
US5546571A
Cited
US5574910A
Cited
US5551027A
Cited
US5742806A
Cited
US5951649A
Cited
US5664172A
Cited
US5546390A
Cited
US6298340B1
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2005-10-28 | 2006-04-29 | 2006-10-29 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2009-10-28 | 2010-04-29 | 2010-10-29 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2013-10-28 | 2014-04-29 | 2014-10-29 | $7700.00 | Window Closed / Lapsed |