System and method and computer program for filtering using tree structure

A method for filtering comprising the acts of:

• (a) providing a binary search tree comprising of single bit test nodes, certain inequality tests for the purpose of discriminating among two or more rules with bounded ranges, and rules listed in order of priority at terminal nodes (leaf chain nodes) of the bit test nodes and compare nodes;
• (b) receiving a frame including a key section;
• (c) selecting bits from the key section of said frame and testing against single bit test nodes and compare nodes on said binary search tree;
• (d) repeating step (c) until the single bit branches to at least one rule or a few remaining rules in a leaf chain;
• and
• (e) testing the key section of the frame against the at least one single remaining rule.

A method for determining if an item is a member of a universe of items comprising the acts of:

• (a) storing, in a memory, a set of expressions representative of the universe of items;
• (b) using a software or hardware program to access the set of expressions and generating therefrom a binary search tree structure having single bit test nodes;
• (c) providing an expression representative of the item;
• (d) testing selected single bits from the expression representing the item against single bits of the search tree;
• (e) repeating act (d) until at least a leaf consisting of one rule or a few remaining rules of the tree is encountered on said search tree;
• and
• (f) comparing each bit in the provided expression with like bits in the at least one encountered rule expression wherein a match indicates the provided expression as being a member of the universe of Items.

A method of managing traffic flows within a communications network comprising the acts of:

• (a) using selected bits extracted from expressions representing a universe of items to generate a binary tree structure having single bit nodes and at least one expression branching from selected ones of the single bit nodes,
• (b) generating a hardware tree structure from the software tree of act (a);
• (c) receiving an item;
• (d) correlating selected bit from the item with single bit nodes of the software managed tree;
• (e) repeating act (d) until a node branches to at least one expression;
• and
• (f) comparing each element in the item with like elements in the at least one expression.

A classification system comprising:

• a memory;
• a database of items stored in said memory;
• a Central Processing Unit (CPU);
• a computer program to be executed on said CPU, said computer program causing said CPU to access the memory, parsing the database and generating therefrom a search tree wherein the root of said search tree relates to a selected bit in the database, nodes on the search tree relate to selected bits or comparisons of bits, and branches relate to 0 or 1.

A communications system comprising:

• at least one communications network;
• a control point provided in a general purpose or dedicated computing device;
• and
• a switch/router coupling the control point and the communications network, said control point including a memory storing a database of rules and microprocessor programmed to parse the database and generate a search tree based upon bits selected from the database and said switch/router using the search tree to filter frames received from the communications network.

A program product comprising:

• a medium on which a computer program is recorded;
• said computer program including:
• a first program code module implemented on said medium, said program code parsing a data base of rules and identifying therein at least one column with a0=the number of 0 entries, a1=the number of 1 entries, a*=the number of * entries and ab=the number of b entries, having most entries 0 or 1 and having about equal numbers of 0 and 1 entries;
• a second program code module, operatively interacting with the first program code module, implemented on said media, said second program code partitioning said column into at least two new rules submatrices wherein the first one of the two new rule submatrices includes all rows from the original set of rules with 0, *, or b in the selected column and the second one of said two new rule submatrices includes all rows from the original set of rules with 1, *, or b in the selected column;
• and
• a third program code module, operatively interacting with the first and second program modules, implemented on said media, said third program code module repeating the partitioning procedure on submatrices until no submatric is left with a column containing both 0 and 1 in it.