Browse Prior Art Database

Filter Rule Tree with Frequent Choices Moved to Root

IP.com Disclosure Number: IPCOM000014441D
Original Publication Date: 2000-Nov-01
Included in the Prior Art Database: 2003-Jun-19
Document File: 5 page(s) / 64K

Publishing Venue

IBM

Abstract

The goal filtering is to perform tests to eliminate all but one or a few filter rules which might apply to a key. We seek to minimize both the time required to test and the complexity of the tests--competing desiderata.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 41% of the total text.

Page 1 of 5

Filter Rule Tree with Frequent Choices Moved to Root

The goal filtering is to perform tests to eliminate all but one or a few filter rules which might apply to a key. We seek to minimize both the time required to test and the complexity of the tests--competing desiderata.

In prior art, bits are chosen to be tested. The tests occur in a binary search tree. At a leaf of such a tree, a certain combination of bits in a key has been tested and all but one or all but a few filter rules have been eliminated from further consideration.

In the present disclosure, we can force certain rules to become the first tests of a tree. The selected rules for forcing might be fed to the bit choosing algorithm as a subapplication of it. The rules to force would be rules which appear in many leafs after straightforward bit choosing. For example, any rule which appears in at least 10% of the leafs might be forced to the root of the tree or to the first few nodes after the root. Especially beneficial would be rules selected for forcing which have no intersections among themselves (no one key fulfills the forced rules).

In tests with a set of real filter rules, the size of the decision tree was reduced from 67 nodes to 50 nodes by one application of forcing a frequently occurring rule to the root of the tree. We anticipate that the invention would be useful with large rule sets when storage resources for a software managed tree are limited.

The goal filtering is to perform tests to eliminate all but one or a few filter rules which might apply to a key. We seek to minimize both the time required to test and the complexity of the tests--competing desiderata.

The basic choice bit method regards rules as rows in matrix. The number of columns is the dimension of the key. Each entry in the matrix is a 0, 1, * (don't care), or b (bounded combinations of values of binaries arising from ranges of equivalent integer values such as [10000, 20000]).

Prior art teaches finding a column with many 0 entries, many 1 entries, and about equal numbers of 0 and 1 entries, if possible. After choosing such a column with at least one 0 entry and at least one 1 entry, we construct two submatrices built with the rows of the first matrix as follows. One submatrix M0 uses all the rows which are not 1 in the chosen column, and the other submatrix M1 uses all the rows which are not 0 in the chosen column.

Moving frequently tested rules to the root

Here is an example of 19 actual rules numbered 0 to 18.

1

Page 2 of 5

rule SA DA SP DP protocol

0 191.23.2.2 191.23.2.4 53 *.* 0 1 191.23.2.2 *.*.*.* 53 *.* 0 2 191.23.2.2 *.*.*.* 53 *.* 1 3 190.12.*.* 190.12.1.* 123 123 1 4 190.12.*.* *.*.*.* *.* 87 0 5 190.12.*.* *.*.*.* *.* 111 0 6 190.12.*.* *.*.*.* *.* 111 1 7 190.12.*.* *.*.*.* *.* 2049 1 8 190.12.*.* *.*.*.* *.* 2049 0 9 190.12.*.* *.*.*.* *.* 512 0 10 190.12.*.* *.*.*.* *.* 513 0 11 190.12.*.* *.*.*.* *.* 514 0 12 190.12.*.* *.*.*.* *.* 515 0 13 190.12.*.* *.*.*.* *.* 540 0 14 190.12...