Method and apparatus for matching a string with multiple lookups using a single associative memory

• US 6,871,262 B1
• Filed: 02/14/2002
• Issued: 03/22/2005
• Est. Priority Date: 02/14/2002
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Oren, Eyal, Belz, David E.
• Primary Examiner(s): Sparks, Donald
• Assistant Examiner(s): Peugh, Brian R.
• Application Number:
  US10/077,243
• Time in Patent Office: 1,132 Days
• Field of Search: 711/108, 711/128, 711/154, 365/49, 365/50, 370/392, 370/409, 370/374, 370/395.7
• US Class Current: 711/108
• CPC Class Codes: G06F 16/90344 by using string matching techniques
• CPC Class Codes: H04L 45/7453 using hashing
• CPC Class Codes: H04L 69/22 Parsing or analysis of headers
• CPC Class Codes: H04L 9/40 Network security protocols

Abstract

Methods and apparatus are disclosed for matching a string with multiple lookups using a single associative memory, such as, but not limited to binary and ternary content-addressable memories (CAMs). In one implementation, an information string is partitioned into multiple segments. A first lookup operation is performed on the associative memory using the first segment to produce a first associative memory result, which is used as input to a memory lookup operation to produce a first result. The first result can be programmed to have any desired value or length. This first result along with a second segment of the information string is then used as input to the same associative memory to produce a second associative memory result, which is typically used as input to a memory lookup operation to produce a second result. This process can be repeated for an arbitrary or predetermined number of times.

Claims

1. A method comprising:

performing a first associative memory lookup based on a first lookup word as input to a particular associative memory device to produce a first associative memory result;

performing a first memory lookup based on the first associative memory result to produce a first memory result;

deriving a second lookup word based on the first memory result; and

performing a second associative memory lookup based on the second lookup word as input to the particular associative memory device to produce a second associative memory result.

2. The method of claim 1, wherein the particular associative memory device includes a binary or ternary content-addressable memory.

3. The method of claim 1, wherein the second lookup word includes the first memory result.

4. The method of claim 1, further comprising deriving the first lookup word based on a first set of information extracted from a packet.

5. The method of claim 4, wherein said first set of information includes an address, a port, or a service type.

6. The method of claim 4, wherein the second lookup word is further based on a second set of information extracted from the packet.

7. The method of claim 6, wherein said second set of information includes an address, a port, or a service type.

8. A method performed based on a set of information, the method comprising:

repeating for a predetermined number of times steps (a)-(c)

(a) deriving a lookup word;

(b) performing a lookup on a particular associative memory device based on the lookup word to produce an associative memory result; and

(c) performing a memory lookup based on the associative memory result to produce a memory result;

wherein said deriving the lookup word includes initially referencing the set of information, and subsequently includes referencing the set of information and the memory result.

9. The method of claim 8, wherein the lookup word derived subsequently includes the memory result.

10. The method of claim 8, further comprising receiving the set of information.

11. The method of claim 10, wherein the set of information is received in a packet.

15. The method of claim 8, wherein the particular associative memory device includes a binary or ternary content-addressable memory.

12. The method of 8, wherein the set of information includes a plurality of portions, and said deriving the lookup word is performed each time using a different portion of the plurality of portions.

13. The method of claim 12, wherein the plurality of portions are non-overlapping within the set of information.

14. The method of claim 12, wherein the number of the plurality of portions is the predetermined number.

16. An apparatus comprising:

an associative memory device to receive a lookup word and to produce an associative memory result; and

a memory coupled to the associative memory device to receive the associative memory result and to produce a memory result;

wherein the lookup word includes the memory result.

17. The apparatus of claim 16, further comprising a component, coupled to the associative memory device and the memory, to receive the memory result and to generate the lookup word.

18. The apparatus of claim 17, wherein the component includes a packet processing device.

19. An apparatus comprising:

means for performing a first associative memory lookup based on a first lookup word as input to a particular associative memory device to produce a first associative memory result;

means for performing a first memory lookup based on the first associative memory result to produce a first memory result;

means for deriving a second lookup word based on the first memory result; and

means for performing a second associative memory lookup based on the second lookup word as input to the particular associative memory device to produce a second associative memory result.

20. The apparatus of claim 19, wherein the particular associative memory device includes a binary or ternary content-addressable memory.

21. The apparatus of claim 19, wherein the second lookup word includes the first memory result.

22. An apparatus comprising:

means for deriving a lookup word;

means for performing a lookup on a particular associative memory device based on the lookup word to produce an associative memory result; and

means for performing a memory lookup based on the associative memory result to produce a memory result;

wherein said means for deriving the lookup word includes means referencing a set of information and the memory result.

23. The apparatus of claim 22, wherein the lookup word includes the memory result.

24. The apparatus of claim 22, further comprising means for receiving the set of information.

25. An apparatus comprising:

means for receiving a lookup word and for producing an associative memory result; and

means, coupled to said means for receiving a lookup word and for producing an associative memory result, for receiving the associative memory result and for producing a memory result;

wherein the lookup word includes the memory result.

26. The apparatus of claim 25, further comprising means for generating the lookup word, coupled to said means for receiving a lookup word and for producing an associative memory result and said means for receiving the associative memory result and for producing a memory result.

27. A method comprising:

performing a first associative memory lookup based on a first lookup word as input to a particular associative memory device to produce a first associative memory result;

deriving a second lookup word based on the first associative memory result; and

performing a second associative memory lookup based on the second lookup word as input to the particular associative memory device to produce a second associative memory result.

28. The method of claim 27, wherein the particular associative memory device includes a binary or ternary content-addressable memory.

29. The method of claim 27, wherein the second lookup word includes the first memory result.

30. The method of claim 27, further comprising deriving the first lookup word based on a first set of information extracted from a packet.