US6298340B1 — System and method and computer program for filter…

Claim 1

Independent Claim 244 words

A method for generating a search tree including the acts of: (a) providing, in a storage, a set of N rules wherein each rule in the set of rules is being represented by the union of bit patterns passed by the rule, so each bit position is 0, 1, * (corresponding to p>0 adjacent bit positions and a rule which applies to all 2 p possible binary values in a range of values in a segment of a rule), or b (corresponding to q>1 adjacent bit positions and a rule which applies to some (>0) but not all 2 q possible binary values in a range of values in a segment of a rule); (b) identifying at least a column in said set of N rules 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; (c) partitioning said column into two new rule 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 (d) repeating such a partition procedure on submatrices until no further partition is possible.

Claim 2

Independent Claim 244 words

A method for generating a search tree including the acts of: (a) providing, in a storage, a set of N rules wherein each rule in the set of rules is being represented by the union of bit patterns passed by the rule, so each bit position is 0, 1, * (corresponding to p>0 adjacent bit positions and a rule which applies to all 2 p possible binary values in a range of values in a segment of a rule), or b (corresponding to q>1 adjacent bit positions and a rule which applies to some (>0) but not all 2 q possible binary values in a range of values in a segment of a rule); (b) identifying at least a column in said set of N rules 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; (c) partitioning said column into two new rule 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 (d) repeating such a partition procedure on submatrices until no further partition is possible.

Claim 3

Dependent Claim 14 words

The method of claim 1 wherein a metric is used to identify the column.

Claim 4

Dependent Claim 21 words

The method of claim 2 wherein the metric includes the expression M5=(a0−N/2){circumflex over ( )}2+(a1−N/2){circumflex over ( )}2+(a*+ab){circumflex over ( )}2.

Claim 5

Dependent Claim 24 words

The method of claim 1 wherein the set of rules is arranged in an N-by-m matrix with each row having m elements in it.

Claim 6

Dependent Claim 85 words

The method of claim 1 further including the acts of in the case that one or a few rules appear very frequently as terminal rules in many leaf chains, designating said rules as “secondary,” designating all other rules as “primary,” recalculating a bit choice and compare tree using primary rules only, and organizing the secondary rules in a set of rules to be tested sequentially or in lattices with pointers from certain primary rules to certain secondary rules determined by relative priorities of the rules.

Claim 7

Dependent Claim 33 words

The method of claim 5 further including the act of if a primary rule of higher priority than any secondary rule already fits a key, no secondary rules are selected for further testing.

Claim 8

Dependent Claim 55 words

The method of claim 5 further including the act of if a primary rule of higher priorities than some but not all secondary rules already fits a key, pointing the primary rule of higher priority to a lattice of only those secondary rules of higher priority with which the primary rule of higher priority intersects.

Claim 9

Dependent Claim 59 words

The method of claim 5 further including the act of if the search of primary rules reaches a leaf chain and no primary rules fit the key, the final primary rule in the leaf chain will point generally to a subset of secondary rules which are not automatically eliminated from consideration by the path taken through the primary tree.

Claim 10

Independent Claim 130 words

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.

Claim 11

Independent Claim 130 words

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.

Claim 12

Dependent Claim 72 words

The method of claim 9 wherein the single bit branches to multiple intercepting rules including R1, R2 and R3 illustrated in the following lattice: wherein R1, R2 and R3 are arranged in order of decreasing priority with partial exact compare followed by full compare if the partial exact compare is True or partial exact compare of the next rule in order if partial exact compare of a rule being considered is false.

Claim 13

Dependent Claim 33 words

The method of claim 9 further including the acts of assigning at least one specified action to the rule; and performing the action to said frame if a match occurs in step (e).

Claim 14

Independent Claim 32 words

The method of claims 9 or 11 wherein the binary search tree is generated from a set of rules configured in an N-by-m matrix with each of the rules having dimension m.

Claim 15

Independent Claim 149 words

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.

Claim 16

Independent Claim 149 words

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.

Claim 17

Dependent Claim 35 words

The method of claim 13 further including the acts of mapping the bit test and bit compare tree into a hardware enabled structure prior to searching said tree with selected bits from the provided expression.

Claim 18

Independent Claim 113 words

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.

Claim 19

Independent Claim 113 words

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.

Claim 20

Dependent Claim 82 words

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.

Claim 21

Dependent Claim 82 words

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.

Claim 22

Dependent Claim 74 words

The classification of claim 16 further including: a circuit arrangement for parsing the key (selected portions) of an unknown item for bits similar to bits identified at nodes of said tree and, if found, searching the tree in a predetermined order until at least one item in the database is identified, wherein a full comparison on all the identifying data in the item is made to determine the action to apply to the item.

Claim 23

Dependent Claim 28 words

The classification system of claim 17 wherein the predetermined order is dictated by values extracted from the key at bit positions common to said key and said tree.

Claim 24

Dependent Claim 32 words

The binary tree classification system of claim 17 wherein the predetermined order includes left of the node if the value is 0 and right of the node if the value is 1.

Claim 25

Dependent Claim 21 words

The classification system of claim 16 wherein items in the database include Rules having a key section and an action section.

Claim 26

Dependent Claim 26 words

The classification system of claim 16 wherein the items in the database are identified by symbols including 0, 1, * (don't care), or b (bounded range).

Claim 27

Dependent Claim 49 words

The classification system of claim 20 wherein the union of keys satisfying each rule in the database is configured as a row in a Rectangular Matrix, with the Rectangular Matrix having N rows (the number of rules) and m columns (the total dimension of the keys to be tested).

Claim 28

Dependent Claim 36 words

The classification system of claim 20 wherein the key section includes a Source Address (SA), Destination Address (DA), Source Port (SP), and Destination Port (DP), and Protocol (P), or any other such fixed, standardized identification format.

Claim 29

Dependent Claim 77 words

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.

Claim 30

Dependent Claim 77 words

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.

Claim 31

Dependent Claim 14 words

The communications system of claim 24 wherein the communications network may include the Internet.

Claim 32

Dependent Claim 31 words

The communications system of claim 25 further may include at least one workstation coupled directly or indirectly to the switch/router; and may include at least one server coupled to said switch/router.

Claim 33

Dependent Claim 118 words

An interconnecting device comprising: a housing; a switch fabric mounted within said housing; a plurality of network ports coupled to said switch fabric, wherein at least one of the network ports includes a packet classification system that includes a software managed tree generated from selected bits of a database of Rules, a controller including logic which parses an unknown Rule for bits similar to bits identified at nodes of the tree and, if found, searching the tree in a predetermined way until at least one Rule of the database of Rules is encountered wherein the at least one Rule is compared with the unknown Key to determine the action to apply to the packet represented by the Key.

Claim 34

Dependent Claim 118 words

An interconnecting device comprising: a housing; a switch fabric mounted within said housing; a plurality of network ports coupled to said switch fabric, wherein at least one of the network ports includes a packet classification system that includes a software managed tree generated from selected bits of a database of Rules, a controller including logic which parses an unknown Rule for bits similar to bits identified at nodes of the tree and, if found, searching the tree in a predetermined way until at least one Rule of the database of Rules is encountered wherein the at least one Rule is compared with the unknown Key to determine the action to apply to the packet represented by the Key.

Claim 35

Dependent Claim 17 words

The interconnecting device of claim 27 further including a Central Processing System coupled to said switch fabric.

Claim 36

Dependent Claim 212 words

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.

Claim 37

Dependent Claim 212 words

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.

Annuity Stage	Window Opens	Payment Deadline	Surcharge Period Until	Estimated Fee	Status
3.5 Years (Year 4)	2004-10-01	2005-04-02	2005-10-02	$2000.00	Window Closed / Lapsed
7.5 Years (Year 8)	2008-10-01	2009-04-02	2009-10-02	$3760.00	Window Closed / Lapsed
11.5 Years (Year 12)	2012-10-01	2013-04-02	2013-10-02	$7700.00	Window Closed / Lapsed

System and method and computer program for filtering using tree structure

Abstract

Inventors

Bibliographic Details

Claims Analysis

References Cited (Backward Citations)

USPTO Annuity & Maintenance Windows

Assigned Categories & Tags

Assign Category Tag