Method and apparatus for possibly decreasing the number of associative memory entries by supplementing an associative memory result with discriminator bits from an original set of information

• US 6,715,029 B1
• Filed: 01/07/2002
• Issued: 03/30/2004
• Est. Priority Date: 01/07/2002
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Goren, Gil, Freund, Dov A., Trainin, Oded
• Primary Examiner(s): Sparks, Donald
• Assistant Examiner(s): CHACE, CHRISTIAN
• Application Number:
  US10/041,825
• Time in Patent Office: 813 Days
• Field of Search: 711/108, 711/202, 711/214, 711/215, 711/217, 711/220, 711/221, 365/49
• US Class Current: 711/108
• CPC Class Codes: G06F 16/90339 by using parallel associative memories or content-addressable memories
• CPC Class Codes: H04L 45/60 Router architectures
• CPC Class Codes: H04L 45/7453 using hashing

Abstract

Methods and apparatus are disclosed for possibly decreasing the number of associative memory entries by supplementing an associative memory result with discriminator bits from an original set of information. One implementation operates on a set of information, the set of information including a lookup word portion and a discriminator portion. A lookup word is derived based on the lookup word portion. A lookup operation is performed on an associative memory, such as, but not limited to a binary or ternary content-addressable memory, using the lookup word to generate an associative memory result. A memory lookup operation is performed on a memory based on the associative memory result and the discriminator portion.

Claims

1. A method performed using a set of information, the set of information including a lookup word portion and a discriminator portion and the lookup word portion includes a plurality of non-contiguous data from the set of information, the method comprising:

performing a lookup operation on an associative memory using a lookup word including the lookup word portion to generate an associative memory result; and

performing a memory lookup operation on a memory based on the associative memory result and the discriminator portion.

2. The method of claim 1, wherein said performing the memory lookup operation based on the associative memory result and the discriminator portion includes deriving a memory address including the associative memory result and the discriminator portion.

3. The method of claim 2, wherein the memory address includes the associative memory result concatenated with the discriminator portion.

4. The method of claim 1, wherein the associative memory includes a ternary content-addressable memory.

5. The method of claim 1, wherein the discriminator portion includes a small number of bits.

6. The method of claim 5, wherein the small number of bits equals two.

7. The method of claim 1, wherein the set of information includes a network address.

8. The method of claim 7, wherein the discriminator portion includes a part of the network address.

9. The method of claim 1, further comprising receiving the set of information.

10. A method comprising:

identifying a plurality of sets of potential discriminator bits;

determining an associative memory programming for each of the plurality of sets of potential discriminator bits for each one of one or more configuration files to produce a set of results;

analyzing the set of results to identify a discriminator portion and a lookup word portion of an input word;

wherein the set of results includes a number of associative memory entries generated by said determining the associative memory programing; and

wherein said analyzing the set of results includes determining which of the plurality of sets of potential discriminator bits produces a minimal number of associative memory entries.

17. The method of claim 10, comprising:

programming an associative memory with the associative memory programming corresponding to a particular set of the plurality of sets of potential discriminator bits that produces the minimal number of associative memory entries;

receiving a particular input word comprising a particular discriminator portion and a particular lookup word portion;

performing a lookup operation on an associative memory using a lookup word including the particular discriminator portion to generate an associative memory result; and

performing a memory lookup operation on a memory based on the associative memory result and the particular discriminator portion.

18. The method of claim 17, wherein the associative memory includes a ternary content-addressable memory.

19. The method of claim 17, wherein the set of information includes a network address.

20. The method of claim 19, wherein the discriminator portion includes a part of the network address.

11. An apparatus configured to operate on a set of information, the set of information including a lookup word portion and a discriminator portion and the lookup word portion includes a plurality of non-contiguous data from the set of information, the apparatus comprising:

means for deriving a lookup word based on the lookup word portion;

means for performing a lookup operation on an associative memory using the lookup word to generate an associative memory result; and

means for performing a memory lookup operation on a memory based on the associative memory result and the discriminator portion.

12. The apparatus of claim 11, wherein said means for performing the memory lookup operation based on the associative memory result and the discriminator portion includes means for deriving a memory address including the associative memory result and the discriminator portion.

13. The apparatus of claim 11, wherein the memory address includes the associative memory result concatenated with the discriminator portion.

14. The apparatus of claim 11, wherein the associative memory includes a ternary content-addressable memory.

15. The apparatus of claim 11, wherein the set of information includes a network address.

16. The apparatus of claim 15, wherein the discriminator portion includes a part of the network address.

21. A computer-readable medium containing computer-executable instructions for performing steps, said steps comprising:

identifying a plurality of sets of potential discriminator bits;

determining an associative memory programming for each of the plurality of sets of potential discriminator bits for each one of one or more configuration files to produce a set of results;

analyzing the set of results to identify a discriminator portion and a lookup word portion of an input word;

wherein the set of results includes a number of associative memory entries generated by said determining the associative memory programing; and

wherein said analyzing the set of results includes determining which of the plurality of sets of potential discriminator bits produces a minimal number of associative memory entries.

22. A method performed using a set of information, the set of information including a lookup word portion and a discriminator portion, the method comprising:

performing a lookup operation on a ternary content-addressable memory (TCAM) using a lookup word including the lookup word portion to generate a TCAM result; and

performing a memory lookup operation on a memory based on the TCAM result and the discriminator portion.

23. The method of claim 22, wherein said performing the memory lookup operation based on the associative memory result and the discriminator portion includes deriving a memory address including the associative memory result and the discriminator portion.

24. The method of claim 23, wherein the memory address includes the associative memory result concatenated with the discriminator portion.