초록 ▼

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

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.

대표청구항 ▼

1. A method comprising: providing a hierarchical, associative memory structure;examining a plurality of addresses of network devices and identifying coordinate sub-fields of the addresses, each address including a plurality of bit positions, each coordinate sub-field being a range of bit positions w

1. A method comprising: providing a hierarchical, associative memory structure;examining a plurality of addresses of network devices and identifying coordinate sub-fields of the addresses, each address including a plurality of bit positions, each coordinate sub-field being a range of bit positions within the addresses where the bit positions in each address hold either a distinct value for the entire range of bit positions or a don't care value for the entire range of bit positions, wherein the plurality of addresses include Internet Protocol (IP) addresses in hexadecimal format;determining the number of distinct values represented in each coordinate sub-field of the addresses;for each coordinate sub-field of the addresses, computing a minimum number of bits needed to represent the number of distinct values and a don't care value, if present;assigning a unique coordinate value (UCV), that falls within the previously computed minimum number of bits, for each distinct value and the don't care value, if present, with each UCV being shorter than the corresponding value that the UCV replaces;for each address, generating a unique coordinate value sequence (UCVS) by concatenating the UCVs assigned to the distinct values and the don't care value, if present, of the respective address; andloading the hierarchical, associative memory structure with the generated UCVSs. 2. The method of claim 1 wherein the addresses are from access control entries (ACEs) of at least one access control list (ACL). 3. An apparatus comprising: a hierarchical, associative memory structure;means for examining a plurality of addresses of network devices and identifying coordinate sub-fields of the addresses, each address including a plurality of bit positions, each coordinate sub-field being a range of bit positions within the addresses where the bit positions in each address hold either a distinct value for the entire range of bit positions or a don't care value for the entire range of bit positions, wherein the plurality of addresses include Internet Protocol (IP) addresses in hexadecimal format;means for determining the number of distinct values represented in each coordinate sub-field of the addresses;means for computing, for each coordinate sub-field of the addresses, a minimum number of bits needed to represent the number of distinct values and a don't care value, if present;means for assigning a unique coordinate value (UCV), that falls within the previously computed minimum number of bits, for each distinct value and the don't care value, if present, with each UCV being shorter than the corresponding value that the UCV replaces; andmeans for generating, for each address, a unique coordinate value sequence (UCVS) by concatenating the UCVs assigned to the distinct values and the don't care value, if present, of the respective address;wherein the hierarchical, associative memory is configured to store the generated UCVSs. 4. A non-transitory computer readable medium containing executable program instructions, the executable program instructions comprising instructions for: examining a plurality of addresses of network devices and identifying coordinate sub-fields of the addresses, each address including a plurality of bit positions, each coordinate sub-field being a range of bit positions within the addresses where the bit positions in each address hold either a distinct value for the entire range of bit positions or a don't care value for the entire range of bit positions, wherein the plurality of addresses include Internet Protocol (IP) addresses in hexadecimal format;determining the number of distinct values represented in each coordinate sub-field of the addresses;for each coordinate sub-field of the addresses, computing a minimum number of bits needed to represent the number of distinct values and a don't care value, if present;assigning a unique coordinate value (UCV), that falls within the previously computed minimum number of bits, for each distinct value and the don't care value, if present, with each UCV being shorter than the corresponding value that the UCV replaces;for each address, generating a unique coordinate value sequence (UCVS) by concatenating the UCVs assigned to the distinct values and the don't care value, if present, of the respective address; andloading a hierarchical, associative memory structure with the generated UCVSs. 5. The method of claim 1, wherein the UCVSs are ordered from smallest to largest. 6. The method of claim 1, wherein the hierarchical, associative memory structure includes a ternary content addressable memory (TCAM). 7. The method of claim 6, wherein the TCAM includes one or more rows, and the method further comprises the step of: indicating whether the UCVS associated with one of the one or more rows is a source or a destination address. 8. The method of claim 1, wherein the step of loading further comprises the step of: loading a first random access memory (RAM) with the generated UCVSs. 9. The method of claim 1, wherein the addresses include Internet Protocol (IP) addresses. 10. The apparatus of claim 3, wherein the addresses are from access control entries (ACEs) of at least one access control list (ACL). 11. The apparatus of claim 10, further comprising: means for ordering the UCVSs from smallest to largest. 12. The apparatus of claim 3, wherein the hierarchical, associative memory structure includes a top-level ternary content addressable memory (TCAM). 13. The apparatus of claim 12, wherein the TCAM includes one or more rows, and the apparatus further comprises: means for indicating whether the UCVS associated with one of the one or more rows is a source or a destination address. 14. The apparatus of claim 3, wherein the means for loading comprises: means for loading a first random access memory (RAM) with a generated UCVS. 15. A system comprising: an associative memory structure;an active control list (ACL) translation engine configured to identify a coordinate sub-field of addresses of network devices, the identified coordinate sub-field to have bit positions within the addresses that hold either a distinct value for an entire range of bit positions that constitute the coordinate sub-field or a don't care s value for the entire range of positions that constitute the coordinate sub-field, wherein the addresses include Internet Protocol (IP) addresses in hexadecimal format;the ACL translation engine further configured to compute a minimum number of bits needed to represent the distinct values and a don't care value, if present, and to assign a unique coordinate value (UCV), that falls within the minimum number of bits, for each distinct value and the don't care value, if present, with each UCV being shorter than the corresponding value that the UCV replaces; andthe associative memory structure configured to store the distinct values and the don't care value, if present, and a random access memory (RAM) configured to cooperate with the associative memory structure and to store the UCVs in unique coordinate value sequences (UCVSs). 16. The system of claim 15, wherein the addresses are from access control entries (ACEs) of at least one ACL. 17. The system of claim 16, wherein the ACL is configured to order the UCVSs from smallest to largest. 18. The system of claim 15, wherein the coordinate sub-field corresponds to at least a portion of IP addresses-field. 19. The system of claim 15, wherein the associative memory structure includes a top-level ternary content addressable memory (TCAM). 20. The system of claim 19, wherein a first random access memory (RAM) is configured to load with a generated UCVS. 21. The system of claim 19, wherein the TCAM includes one or more rows, and the system further comprising: an additional bit to indicate whether the UCVS associated with one of the one or more rows is a source or a destination address. 22. A method comprising: identifying a coordinate sub-field of a plurality of addresses of network devices, each identified coordinate sub-field to have bit positions within the addresses that hold either a distinct value for an entire range of bit positions that constitute the coordinate sub-field or a don't care value for the entire range of positions that constitute the coordinate sub-field, wherein the addresses include Internet Protocol (IP) addresses in hexadecimal format;computing, by an intermediate network device, a minimum number of bits needed to individually represent the distinct values and the don't care value, if present;assigning, by the intermediate network device, a unique coordinate value (UCV), that falls within the previously computed minimum number of bits, for each distinct value and the don't care value, if present, with each UCV being shorter than the corresponding value that the UCV replaces;storing the distinct values and the don't care value, if present, in an associative memory structure of the intermediate network device; andstoring each of the UCVs in a memory of the intermediate network device configured to cooperate with the associative memory structure. 23. The method of claim 1 wherein the distinct value is a zero or a one.