Hierarchical associative memory-based classification system

• US 9,111,013 B2
• Filed: 12/08/2005
• Issued: 08/18/2015
• Est. Priority Date: 07/10/2000
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Cheriton, David R.
• Primary Examiner(s): Alam, Hosain
• Assistant Examiner(s): HARPER, ELIYAH STONE
• Application Number:
  US11/297,551
• Publication Number:
  US 20060155875A1
• Time in Patent Office: 3,540 Days
• Field of Search: 707/104.1, 707/100, 707/10, 707/2, 707/758
• US Class Current: 1/1
• CPC Class Codes: G06F 16/90339 by using parallel associative memories or content-addressable memories
• CPC Class Codes: G06F 16/955 using information identifiers, e.g. uniform resource locators [URL]
• CPC Class Codes: H04L 69/22 Parsing or analysis of headers

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.

Claims

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; and

loading 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).

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.

23. The method of claim 1 wherein the distinct value is a zero or a one.

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; and

means 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.

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.

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; and

loading a hierarchical, associative memory structure with the generated UCVSs.

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; and

the 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; and

storing each of the UCVs in a memory of the intermediate network device configured to cooperate with the associative memory structure.