Methods and apparatus for distributing entries among lookup units and selectively enabling less than all of the lookup units when performing a lookup operation

• US 7,441,074 B1
• Filed: 08/10/2002
• Issued: 10/21/2008
• Est. Priority Date: 08/10/2002
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Sharma, Samar, Panigrahy, Rina
• Primary Examiner(s): ELMORE, STEPHEN C
• Application Number:
  US10/215,697
• Time in Patent Office: 2,264 Days
• Field of Search: 711/3, 711/108, 711/154, 365/49, 365/226, 365/227, 365/49.1
• 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/7453 using hashing

Abstract

Methods and apparatus are disclosed for distributing entries among lookup units and selectively enabling less than all of the lookup units when performing a lookup operation. Each of the lookup units is assigned a subset of the possible values of the entries and is programmed with the corresponding entries. In performing a lookup operation on a lookup word, only the lookup units possibly containing a matching entry are enabled which saves power and dissipates less heat. A lookup operation is then performed in the enabled lookup units to generate the lookup result. A lookup unit may correspond to an associative memory device, an associative memory bank, sets of entries within one or more associative memory devices or banks, a lookup control and a memory device, and/or any other lookup mechanism. In one implementation, the partitioning of elements is based on a Patricia tree representation of the possible entries.

Claims

1. An apparatus for use in generating lookup results, the apparatus comprising:

a plurality of lookup units for generating a lookup result based on a lookup value, each of the plurality of lookup units including a different one of a plurality of subsets of a plurality of entries;

an enable signal generator, coupled to each of the plurality of lookup units, for selectively enabling less than all of the plurality of lookup units based on the lookup value; and

control logic for partitioning the plurality of entries into the plurality of subsets of the plurality of entries, and for programming each of the plurality of lookup units with said different one of the plurality of subsets of the plurality of entries;

wherein said control logic is configured to perform said partitioning based on a Patricia tree representation of the plurality of entries.

2. The apparatus of claim 1, wherein each of the plurality of lookup units includes an associative memory unit.

3. The apparatus of claim 2, wherein the associative memory unit is an associative memory device.

4. The apparatus of claim 2, wherein the associative memory unit is an associative memory bank.

5. The apparatus of claim 4, wherein a single associative memory device includes each of the plurality of lookup units.

6. The apparatus of claim 2, wherein each of the plurality of lookup units corresponds to one or more entries within an associative memory device.

7. The apparatus of claim 1, wherein each of the plurality of lookup units includes a lookup control and a memory device.

8. The apparatus of claim 1, wherein a particular entry of the plurality of entries is included in only one of the plurality of lookup units.

9. The apparatus of claim 1, wherein a particular entry of the plurality of entries is included in at most two of the plurality of lookup units.

10. The apparatus of claim 1, wherein each of the plurality of subsets of the plurality of entries contains approximately the same number of entries.

11. The apparatus of claim 1, wherein said control logic is configured to add entries to one or more of the plurality of subsets.

12. The apparatus of claim 11, wherein said control logic is configured to repartition the plurality of entries into a different plurality of subsets based on an occupancy level of one of the plurality of subsets of the plurality of entries.

13. The apparatus of claim 1, wherein a first lookup unit of the plurality of lookup units includes a first subset of the plurality of entries and a second lookup unit of the plurality of lookup units includes a second subset of the plurality of entries;

and

wherein a particular entry residing on a boundary between the first and the second subsets of the plurality of subsets of the plurality of entries is included in both the first and second lookup units.

14. The apparatus of claim 1, wherein said control logic is configured to repartition the plurality of entries into a different plurality of subsets based on an occupancy level of one of the plurality of subsets of the plurality of entries.

15. The apparatus of claim 14, wherein said repartitioning the plurality of entries includes adjusting a boundary between a first and a second subsets of the plurality of entries.

16. The apparatus of claim 15, wherein the first subset is left of the second subset Patricia tree representation, and wherein said adjusting the boundary includes determining a prefix left of the second subset and setting the boundary to the prefix supplemented with ones.

17. The apparatus of claim 15, wherein the first subset is left of the second subset Patricia tree representation, and wherein said adjusting the boundary includes determining a prefix right of the first subset and setting the boundary to the prefix supplemented with zeros.

18. The apparatus of claim 1, wherein said control logic communicates an enable representation of said partitioning to the enable signal generator.

19. A method for use in determining lookup results, the method comprising:

programming each of a plurality of lookup units with a different set of entry values;

selectively enabling less than all of the plurality of lookup units;

performing a lookup operation using a lookup word on said selectively enabled lookup units; and

identifying a lookup value

wherein said selectively enabling is performed based on a first subset of the lookup value; and

wherein the lookup word includes a second subset of the lookup value.

20. The method of claim 19, wherein each of the plurality of lookup units includes an associative memory unit.

21. The method of claim 20, wherein the associative memory unit is an associative memory device.

22. The method of claim 20, wherein the associative memory unit is an associative memory bank.

23. The method of claim 22, wherein a single associative memory device includes each of the plurality of lookup units.

24. The method of claim 20, wherein each of the plurality of lookup units corresponds to one or more entries within an associative memory device.

25. The method of claim 20, comprising providing the lookup word to each of the plurality of lookup units.

26. The method of claim 20, comprising providing the lookup word to said selectively enabled associative memory devices.

27. The method of claim 19, wherein each of the plurality of lookup units includes a lookup control and a memory device.

28. The method of claim 19, wherein said selectively enabling is performed based on the lookup word.

29. The method of claim 19, wherein each of the plurality of lookup units is programmed with approximately the same number of values from the set of entry values.

30. A method for use in generating lookup results, the method comprising:

partitioning a space of possible values into a plurality of subsets of the space;

programming each of a plurality of lookup units with a corresponding one of the plurality of subsets of the space;

identifying a lookup value;

selectively enabling less than all of the plurality of lookup units based on the lookup value; and

providing a lookup word, based on the lookup value, to at least said selectively enabled lookup units;

wherein said partitioning the space includes deriving a Patricia tree representation of the space of possible values.

31. The method of claim 30, wherein each of the plurality of lookup units includes an associative memory unit.

32. The method of claim 31, wherein the associative memory unit is an associative memory device.

33. The method of claim 31, wherein the associative memory unit is an associative memory bank.

34. The method of claim 33, wherein a single associative memory device includes each of the plurality of lookup units.

35. The method of claim 31, wherein each of the plurality of lookup units corresponds to one or more entries within an associative memory device.

36. The method of claim 31, comprising providing the lookup word to each of the plurality of lookup units.

37. The method of claim 31, comprising providing the lookup word to said selectively enabled associative memory devices.

38. The method of claim 30, wherein each of the plurality of lookup units includes a lookup control and a memory device.

39. The method of claim 30, comprising programming an enable signal generator based on ranges of the plurality of subsets of the space.

40. The method of claim 30, comprising programming a plurality of enable signal generators based on ranges of the plurality of subsets of the space.

41. The method of claim 40, wherein each of the plurality of enable signal generators corresponds to a different one of the plurality of lookup units.

42. The method of claim 30, comprising repartitioning the space of possible values into the plurality of subsets of the space including modifying a boundary between a first and a second subsets of the space.

43. The method of claim 42, wherein the first subset is left of the second subset Patricia tree representation, and wherein said adjusting the boundary includes determining a prefix left of the second subset and setting the boundary to the prefix supplemented with ones.

44. The method of claim 42, wherein the first subset is left of the second subset Patricia tree representation, and wherein said adjusting the boundary includes determining a prefix right of the first subset and setting the boundary to the prefix supplemented with zeros.

45. An apparatus for use in generating lookup results, the apparatus comprising:

means for partitioning a space of possible values into a plurality of subsets of the space;

means for programming each of a plurality of means for performing a lookup operation with entries corresponding to one of the plurality of subsets of the space;

means for selectively enabling less than all of the plurality of said means for performing a lookup operation based on a lookup value; and

means for performing a lookup operation in said selectively enabled means for performing a lookup operation based on the lookup value;

wherein said means for partitioning the space includes means for deriving a Patricia tree representation of the space of possible values.

46. The apparatus of claim 45, comprising means for repartitioning the space of possible values into the plurality of subsets of the space includes means for modifying a boundary between a first and a second subsets of the space.

47. An apparatus for use in generating lookup results, the apparatus comprising:

a plurality of lookup units for generating a lookup result based on a lookup value, each of the plurality of lookup units including a different one of a plurality of subsets of a plurality of entries;

an enable signal generator, coupled to each of the plurality of lookup units, for selectively enabling less than all of the plurality of lookup units based on the lookup value; and

control logic for partitioning the plurality of entries into the plurality of subsets of the plurality of entries, and for programming each of the plurality of lookup units with said different one of the plurality of subsets of the plurality of entries;

wherein said control logic is configured to add entries to one or more of the plurality of subsets, and to repartition the plurality of entries into a different plurality of subsets based on an occupancy level of one of the plurality of subsets of the plurality of entries.

48. A method for use in generating lookup results, the method comprising:

partitioning a space of possible values into a plurality of subsets of the space;

programming each of a plurality of lookup units with a corresponding one of the plurality of subsets of the space;

programming an enable signal generator based on ranges of the plurality of subsets of the space;

identifying a lookup value;

selectively enabling less than all of the plurality of lookup units based on the lookup value; and

providing a lookup word, based on the lookup value, to at least said selectively enabled lookup units.

49. A method for use in generating lookup results, the method comprising:

partitioning a space of possible values into a plurality of subsets of the space;

programming each of a plurality of lookup units with a corresponding one of the plurality of subsets of the space;

programming a plurality of enable signal generators based on ranges of the plurality of subsets of the space;

identifying a lookup value;

selectively enabling less than all of the plurality of lookup units based on the lookup value; and

providing a lookup word, based on the lookup value, to at least said selectively enabled lookup units.

50. The method of claim 49, wherein each of the plurality of enable signal generator corresponds to a different one of the plurality of lookup units.