Method and apparatus for allocating and using range identifiers as input values to content-addressable memories

• US 6,775,737 B1
• Filed: 10/09/2001
• Issued: 08/10/2004
• Est. Priority Date: 10/09/2001
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Eatherton, William N., Warkhede, Priyank Ramesh, Marimuthu, Peram, Maniyar, Shyamsundar N.
• Primary Examiner(s): LANE, JOHN A
• Application Number:
  US09/973,508
• Time in Patent Office: 1,036 Days
• Field of Search: 711/108, 711/158, 365/49
• US Class Current: 711/108
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 45/48 Routing tree calculation
• CPC Class Codes: H04L 69/22 Parsing or analysis of headers

Abstract

Methods and apparatus are disclosed for allocating and using range identifiers as input values to associative memories, especially binary content-addressable memories (CAMs) and ternary content-addressable memories (TCAMs). In one implementation, each of multiple non-overlapping intervals are identified with one of multiple unique identifiers. An indication of a mapping between the multiple non-overlapping intervals and the multiple unique identifiers is maintained. A particular unique identifier is determined from said multiple unique identifiers based on a value and said multiple non-overlapping intervals. A lookup operation is performed on an associative memory using the particular unique identifier to generate a result. One implementation uses a trie representation of a range tree of the intervals to derive the unique identifiers. Moreover, one implementation evaluates and selects among various possible trie representations, especially to determine identifiers such that a TCAM prefix may match multiple intervals corresponding to a desired range.

Claims

1. A method comprising:

identifying each of a plurality of non-overlapping intervals with one of a plurality of unique identifiers;

maintaining an indication of a mapping between the plurality of non-overlapping intervals and the plurality of unique identifiers;

determining a particular unique identifier from said plurality of unique identifiers based on a value and said plurality of non-overlapping intervals; and

performing a lookup operation on an associative memory using the particular unique identifier to generate a result.

2. The method of claim 1, further comprising partitioning a plurality of ranges into the plurality of non-overlapping intervals.

3. The method of claim 1, wherein said identifying each of the plurality of non-overlapping intervals with one of the plurality of unique identifiers includes:

determining at least two different sets of values for the plurality of unique identifiers; and

selecting one of said at least two different sets of values for the plurality of unique identifiers.

4. The method of claim 3, wherein said one of said at least two different sets of values for the plurality of unique identifiers is associated with a minimal cost, wherein said cost is defined as a number of ternary content-addressable entries.

5. The method of claim 1, wherein said identifying each of the plurality of non-overlapping intervals with one of the plurality of unique identifiers includes:

determining at least two different mappings between the plurality of non-overlapping intervals and the plurality of unique identifiers; and

selecting one of said at least two different mappings between the plurality of non-overlapping intervals and the plurality of unique identifiers.

6. The method of claim 1, said identifying each of the plurality of non-overlapping intervals with one of the plurality of unique identifiers includes determining a trie representation of the plurality of non-overlapping intervals.

7. The method of claim 1, wherein said identifying each of the plurality of non-overlapping intervals with one of the plurality of unique identifiers includes:

determining at least two different trie representations of the plurality of non-overlapping intervals; and

selecting one of said at least two different trie representations.

8. The method of claim 7, wherein said selecting one of said at least two different trie representations includes evaluating each of said at least two different trie representations for prefixes that would match two or more of the plurality of non-overlapping intervals.

9. The method of claim 1, further comprising programming the associative memory with an entry that matches at least two unique identifiers of said plurality of unique identifiers.

10. The method of claim 9, wherein the entry includes a prefix.

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

12. The method of claim 1, wherein the value includes a port number, an address, or a service characteristic.

13. The method of claim 12, further comprising receiving a packet including the port number, the address, or the service characteristic.

14. The method of claim 1, wherein said identifying each of the plurality of non-overlapping intervals with one of the plurality of unique identifiers includes performing a tree analysis on at least two different sets or mappings of the plurality of unique identifiers.

15. The method of claim 14, wherein said tree analysis includes analyzing a resultant set of trie representations of said at least two different sets or mappings of the plurality of unique identifiers.

16. A computer-readable medium containing computer-executable instructions for performing the method of claim 15.

17. The method of claim 1, wherein said performing a lookup operation on an associative memory using the particular unique identifier to generate a result includes performing a lookup operation in the associative memory based on a lookup word including the particular unique identifier.

18. The method of claim 17, wherein the associative memory is a ternary content-addressable memory such that each particular entry of the associative memory matches the lookup word if each bit of the lookup word is equal to each corresponding non-masked bit of said particular entry.

19. The method of claim 17, wherein the associative memory is a binary content-addressable memory such that each particular entry of the associative memory matches the lookup word if each bit of the lookup word is equal to each corresponding bit of said particular entry.

20. An apparatus comprising:

a storage mechanism configured to maintain an indication of a mapping between a plurality of non-overlapping intervals and a plurality of unique identifiers;

a range logic to determine a particular unique identifier from said plurality of unique identifiers based on a value and said plurality of non-overlapping intervals; and

an associative memory to perform a lookup operation using the particular unique identifier to generate a result.

21. The apparatus of claim 20, further comprising a programming engine for determining the mapping between the plurality of non-overlapping intervals and the plurality of unique identifiers.

22. The apparatus of claim 21, wherein the programming engine includes an associative memory programmer to program the associative memory.

23. The apparatus of claim 21, wherein the programming engine includes an analyzer for performing an analysis on at least two different sets or mappings of the plurality of unique identifiers.

24. The apparatus of claim 23, wherein the programming engine includes a selection mechanism for selecting one of said at least two different sets or mappings of the plurality of unique identifiers.

25. The apparatus of claim 23, wherein the analyzer performs a tree analysis on at least two different sets or mappings of the plurality of unique identifiers.

26. The apparatus of claim 25, wherein said tree analysis includes analyzing a resultant set of trie representations of said at least two different sets or mappings of the plurality of unique identifiers.

27. The apparatus of claim 20, wherein said to perform a lookup operation using the particular unique identifier includes to perform a lookup operation using a lookup word including the particular unique identifier.

28. An apparatus comprising:

means for identifying each of a plurality of non-overlapping intervals with one of a plurality of unique identifiers;

means for maintaining an indication of a mapping between the plurality of non-overlapping intervals and the plurality of unique identifiers;

means for determining a particular unique identifier from said plurality of unique identifiers based on a value and said plurality of non-overlapping intervals; and

means for performing a lookup operation on an associative memory using the particular unique identifier to generate a result.

29. The apparatus of claim 28, further comprising means for partitioning a plurality of ranges into the plurality of non-overlapping intervals.

30. The apparatus of claim 28, wherein said means for identifying each of the plurality of non-overlapping intervals with one of the plurality of unique identifiers includes:

means for determining at least two different sets of values for the plurality of unique identifiers; and

means for selecting one of said at least two different sets of values for the plurality of unique identifiers.

31. The apparatus of claim 28, wherein said means for identifying each of the plurality of non-overlapping intervals with one of the plurality of unique identifiers includes:

means for determining at least two different mappings between the plurality of non-overlapping intervals and the plurality of unique identifiers; and

means for selecting one of said at least two different mappings between the plurality of non-overlapping intervals and the plurality of unique identifiers.

32. The apparatus of claim 28, said means for identifying each of the plurality of non-overlapping intervals with one of the plurality of unique identifiers includes means for determining a trie representation of the plurality of non-overlapping intervals.

33. The apparatus of claim 28, wherein said means for identifying each of the plurality of non-overlapping intervals with one of the plurality of unique identifiers includes:

means for determining at least two different trie representations of the plurality of non-overlapping intervals; and

means for selecting one of said at least two different trie representations.

34. The apparatus of claim 33, wherein said means for selecting one of said at least two different trie representations includes means for evaluating each of said at least two different trie representations for prefixes that would match two or more of the plurality of non-overlapping intervals.

35. The apparatus of claim 28, further comprising means for programming the associative memory with an entry that matches at least two unique identifiers of said plurality of unique identifiers.

36. The apparatus of claim 35, wherein the entry includes a prefix.

37. The apparatus of claim 28, wherein the associative memory includes a binary or ternary content-addressable memory.

38. The apparatus of claim 28, wherein the value includes a port number, an address, or a service characteristic.

39. The apparatus of claim 38, further comprising means for receiving a packet including the port number, the address, or the service characteristic.

40. The apparatus of claim 28, wherein said means for identifying each of the plurality of non-overlapping intervals with one of the plurality of unique identifiers includes means for performing a tree analysis on at least two different sets or mappings of the plurality of unique identifiers.

41. The apparatus of claim 40, wherein said means for tree analysis includes means for analyzing a resultant set of trie representations of said at least two different sets or mappings of the plurality of unique identifiers.

42. The apparatus of claim 28, wherein said means for performing a lookup operation on an associative memory using the particular unique identifier to generate a result includes means for performing a lookup operation in the associative memory based on a lookup word including the particular unique identifier.