Reduction of ternary rules with common priority and actions

Abstract

A system for reducing the size of a database includes a memory in which the database configured in a ternary matrix array structure is stored. A processor executing at least one reduction algorithm scans the database tagging superfluous entries that are subsequently deleted. The tagging and deleting are done in such a way that the logical contents of the original database is unchanged, even though the size of the database is reduced.

What is claimed is:  
     
         1 . A method comprising the acts of: 
 providing a database including ternary characters arranged in a matrix;    performing predefined operations on the database with a programmed processor; and    deleting superfluous entries from said database wherein the size of said database is reduced.    
     
     
         2 . The method of  claim 1  wherein the ternary characters include 0, 1 and * (don't care).  
     
     
         3 . The method of claims  1  or  2  wherein the predefined operations include tagging a first indicia to each entry in the database.  
     
     
         4 . The method of  claim 3  wherein the predefined operations further include determining entries in the database that are included in other entries in said database.  
     
     
         5 . The method of  claim 4  wherein the predefined operations still further include tagging a second indicia to entries identified as being inclusive.  
     
     
         6 . The method of  claim 3  wherein the first indicia includes a logical “1”.  
     
     
         7 . The method of  claim 5  wherein the second indicia includes a logical “0”.  
     
     
         8 . The method of  claim 7  wherein the superfluous entries are tagged with logical “0”.  
     
     
         9 . The method of  claim 3  wherein the predefined operations further include determining rules that can be combined with other rules so as to reduce the number of rules in said database.  
     
     
         10 . The method of  claim 4  wherein the predefined operations further include determining rules that can be combined with other rules so as to reduce the number of rules in said database.  
     
     
         11 . An apparatus comprising: 
 a memory in which a ternary data matrix is being stored;    a processor operatively coupled to access said memory and to perform predefined operations that reduce the number of entries in said ternary data matrix.    
     
     
         12 . The apparatus of  claim 11  wherein characters in the ternary data matrix include 0, 1 and * (wild card).  
     
     
         13 . The apparatus of claims  11  or  12  wherein the predefined operations include tagging each entry in the ternary data matrix with a first indicia.  
     
     
         14 . The apparatus of  claim 13  wherein the first indicia includes 1.  
     
     
         15 . The apparatus of  claim 14  wherein the predefined operations further include determining redundant entries in said ternary database.  
     
     
         16 . The apparatus of  claim 15  wherein said processor tags redundant entries with a second indicia.  
     
     
         17 . The apparatus of  claim 16  wherein the second indicia includes 0.  
     
     
         18 . The apparatus of  claim 17  wherein the processor deletes all entries tagged with 0.  
     
     
         19 . The apparatus of  claim 14  wherein the predefined operations include determining entries in the database that are identical in each bit position except one.  
     
     
         20 . The apparatus of  claim 15  wherein the predefined operations include determining entries in the database that are identical in each bit position except one.  
     
     
         21 . A program product including 
 a medium on which a computer program is recorded, said computer program including a first set of instructions that causes a computer to tag each entry in a database with a first indicia;    a second set of instructions that causes the computer to determine redundant entries in said database; and    a third set of instructions that causes said computer to tag selected ones of said redundant entries with a second indicia.    
     
     
         22 . The program product of  claim 21  wherein the first indicia includes 1.  
     
     
         23 . The program product of claims  21  or  22  wherein the second indicia includes 0.  
     
     
         24 . The program product of  claim 21  further including a fourth set of instructions that causes the computer to delete from said database the selected ones of said entries tagged with the second indicia.  
     
     
         25 . The program product of claims  24  a fifth set of instructions that causes the computer to determine all entries in the database identical in each bit position except 1.  
     
     
         26 . A method to reduce the size of a database comprising the acts of: 
 (a) providing the database in a memory said database including a listing of N rules, N >=2, with indices 0, 1, 2 . . . N and characters 0, 1 and * (wild card or don't care);    (b) tagging each rule with a valid bit having a first value;    (c) processing the N rules with a redundancy test algorithm that identifies rules included in other rules; and    (d) tagging rules identified in (c) with a value bit having a second value.    
     
     
         27 . The method of  claim 26  further including the acts of processing only rules tagged with the first indicia with a Reduction Algorithm thus to determine Rules that are identical to other rules in all bit positions except one.  
     
     
         28 . The method of  claim 27  further including the act of tagging selected ones of the rules processed with the second indicia.  
     
     
         29 . The method of  claim 28  wherein the first indicia includes a 1 and the second indicia a 0.  
     
     
         30 . The method of  claim 29  further including the act of deleting from said database entries rules marked with 0.  
     
     
         31 . The method of  claim 26  wherein act (c) further includes the act of applying to the database the redundancy step altgorithm as a program with the folloiwng steps of: 
 step 1 letting an index i initially be 0;  
 step 2 letting an index j initially be 0;  
 step 3 if rule Rj has valid bit=0, then go to step 6;  
 step 4 if j=i, then go to step 6;  
 step 5 if 
 no 0 entry in Ri corresponds to a 1 entry in Rj  
 AND no 1 entry in Ri corresponds to a 0 entry in Rj  
 AND every * entry in Ri corresponds to a * entry in Rj  
 
 then go to step 7;  
 step 6 if j<N−1, then increment j by 1 so j:=j+1 and go to step 3;  
 step 7 if i<N−1, then increment i by 1 so i:=i+1 and go to step 2;  
 step 8 END.  
 
     
     
         32 . The method of  claim 27  wherein processing rules with the Reduction Algorithm further includes the act of applying to the database a program with the steps of: 
 step 1 letting an index i initially be 0;  
 step 2 letting an index j initially be 0;  
 step 3 if rule Rj has valid bit=0, then go to step 6;  
 step 4 if j=i, then go to step 6;  
 step 5 if Ri and Rj are identical in every position except exactly one entry, then write * in that entry in Rj, reset the valid bit Ri to 0, and go to step 7;  
 step 6 if j<N−1, then increment j by 1 so j:=j+1 and go to step 3;  
 step 7 if i<N−1, then increment i by 1 so i:=i+1 and go to step 2;  
 step 8 END.  
 
     
     
         33 . The method of  claim 26  wherein the rules represent a description of policies including security policies to be enforced regarding traffic at an edge device flowing in either direction.  
     
     
         34 . The method of claims  1  or  2  wherein the predefined operations include determining entries that are redundant in said database.  
     
     
         35 . The method of claims  1  or  2  wherein the predefined operations include determining entries that can be combined in said database.  
     
     
         36 . The method of  claim 34  wherein the entries are redundant if no 0 in Ri is 1 in Rj and no 1 in Ri is 0 in Rj and every * in Ri is * in Ri, where Ri and Rj are indices.  
     
     
         37 . The method of  claim 35  wherein the entries can be combined if Ri and Ri are identical in every position except one, where Ri and Rj are indices.