System, method and computer program for filtering multi-action rule set

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.

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.

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.