Hierarchical associative memory-based classification system
0 Assignments
0 Petitions
Accused Products
Abstract
A system and method for efficiently searching long strings of data, such as network messages, is described. The system preferably includes an associative memory structure, having a plurality of content addressable memories (CAMs). The CAMs are hierarchically arranged such the output of at least one CAM is used as the input to a second CAM. Preferably, a top-level CAM receives only a selected portion of the data string or network message as its input. The output of the top-level CAM is then joined with some or all of the remaining portions of the data string to form a new output that is provided to the CAM at the next lower level. The top-level CAM is programmed such that its output is substantially smaller (e.g., has fewer bits) than the selected data string portion that is input to the top-level CAM. The system can thus search data strings that are on the whole far longer than the widths of the respective CAMs forming the memory structure.
121 Citations
24 Claims
-
1-17. -17. (canceled)
-
18. A method for loading a hierarchical, associative memory structure with a plurality of records, each record organized into common fields having values and/or don'"'"'t cares, so that a data string, also having a plurality of fields, may be compared with the contents of the memory structure in order to identify a matching record, the method comprising the steps of:
-
identifying the coordinate sub-fields of at least one selected field of the records, the selected field having distinct values or don'"'"'t cares;
determining the number of distinct values that each coordinate sub-field has;
for each coordinate sub-field, computing the minimum number of bits needed to individually represent each of the distinct values and don'"'"'t care, if present, for the respective coordinate sub-field;
assigning a unique coordinate value (UCV), that falls within the previously computed minimum number of bits, for each distinct value and don'"'"'t care, if present;
for each record, generating a unique coordinate value sequence (UCVS) by concatenating the UCVs assigned to the distinct values and don'"'"'t care, if present, of the respective record; and
loading the hierarchical, associative memory structure with the generated UCVSs. - View Dependent Claims (19, 20, 21)
-
-
22. An apparatus for loading a hierarchical, associative memory structure with a plurality of records, each record organized into common fields having values and/or don'"'"'t cares, so that a data string, also having a plurality of fields, may be compared with the contents of the memory structure in order to identify a matching record, the method comprising the steps of:
-
means for identifying the coordinate sub-fields of at least one selected field of the records, the selected field having distinct values or don'"'"'t cares;
means for determining the number of distinct values that each coordinate sub-field has;
for each coordinate sub-field, means for computing the minimum number of bits needed to individually represent each of the distinct values and don'"'"'t care, if present, for the respective coordinate sub-field;
means for assigning a unique coordinate value (UCV), that falls within the previously computed minimum number of bits, for each distinct value and don'"'"'t care, if present;
for each record, means for generating a unique coordinate value sequence (UCVS) by concatenating the UCVs assigned to the distinct values and don'"'"'t care, if present, of the respective record; and
means for loading the hierarchical, associative memory structure with the generated UCVSs.
-
-
23. A computer readable medium containing executable program instructions for loading a hierarchical, associative memory structure with a plurality of records, each record organized into common fields having values and/or don'"'"'t cares, so that a data string, also having a plurality of fields, may be compared with the contents of the memory structure in order to identify a matching record, the executable program instructions comprising steps for:
-
identifying the coordinate sub-fields of at least one selected field of the records, the selected field having distinct values or don'"'"'t cares;
determining the number of distinct values that each coordinate sub-field has;
for each coordinate sub-field, computing the minimum number of bits needed to individually represent each of the distinct values and don'"'"'t care, if present, for the respective coordinate sub-field;
assigning a unique coordinate value (UCV), that falls within the previously computed minimum number of bits, for each distinct value and don'"'"'t care, if present;
for each record, generating a unique coordinate value sequence (UCVS) by concatenating the UCVs assigned to the distinct values and don'"'"'t care, if present, of the respective record; and
loading the hierarchical, associative memory structure with the generated UCVSs.
-
-
24-67. -67. (canceled)
Specification