Reducing content addressable memory (CAM) power consumption counters

• US 7,984,235 B2
• Filed: 01/29/2010
• Issued: 07/19/2011
• Est. Priority Date: 09/05/2007
• Status: Expired due to Fees

• Current Assignee: Juniper Networks Incorporated
• Original Assignee: Juniper Networks Incorporated
• Inventors: Narayan, Harsha, Pendersen, Soren B., Huang, Kenneth, Pathak, Ruturaj
• Primary Examiner(s): LANE, JOHN A
• Application Number:
  US12/697,063
• Publication Number:
  US 20100131703A1
• Time in Patent Office: 536 Days
• Field of Search: 711/108, 711/156, 711/165, 711/170, 709/223, 709/225
• US Class Current: 711/108
• CPC Class Codes: G06F 12/0811 with multilevel cache hierarchies
• CPC Class Codes: G11C 15/00 Digital stores in which information comprising one or more characteristic parts is written into the store and in which information is read-out by searching for one or more of these characteristic parts, i.e. associative or content-addressed stores
• CPC Class Codes: Y02D 10/00 Energy efficient computing, e.g. low power processors, power management or thermal management

Abstract

A method may include counting the number of times each of a plurality of entries in a content addressable memory (CAM) matches one or more searches; grouping entries in the CAM into a first subset and a second subset based on the number of times each of the plurality of entries in the CAM matches one or more searches; and searching the first subset for a matching entry and, if no matching entry is found, searching the second subset for the matching entry.

Claims

1. A device comprising:

a memory that stores data including;

a plurality of data entries, and

a plurality of count values, where each of the plurality of count values indicates a number of times that a corresponding one of the plurality of data entries has been previously accessed; and

a processor to;

sort the plurality of data entries based on the plurality of count values;

receive a search request, and

identify one, of the plurality of data entries that correspond to the search request, where the processor, when identifying the one of the plurality of data entries, is further to;

search a first group, of the plurality of data entries, for data corresponding to the search request, where the first group includes a particular number of the sorted plurality of data entries that were previously accessed more often, relative to a second group, and

if the data corresponding to the search request is not located in the first group, search the second group for the data, where the second group includes ones, of the plurality of data entries, that are not included in the first group.

2. The device of claim 1, where the memory includes a content addressable memory (CAM).

3. The device of claim 2, where the processor is further to increment a count value, of the plurality of count values, associated with the identified one of the plurality of data entries.

4. The device of claim 3, where the processor is further to re-sort the plurality of data entries after incrementing the count value.

5. The device of claim 1, where, when sorting the pluralities of data entries, the processor is to:

sort the plurality of data entries based on a time-dependent function of the count values.

6. The device of claim 1, where each of the plurality of data entries corresponds to a network address.

7. The device of claim 6, where the processor is further to determine, according to a network address in the identified one of the data entries, to either forward or drop a data unit from which the search request is extracted.

8. The device of claim 7, where, when sorting the pluralities of data entries, the processor is to

sort the plurality of data entries based on at least one of:

a protocol associated with the data unit, or

a user configuration setting associated with the data unit.

9. A method comprising:

grouping, by a device, network addresses stored in a memory into a plurality of groups based on count values that each indicate a number of times that a corresponding one of the network addresses has been previously accessed;

searching, by the device, a first group, of the plurality of groups for a particular network address, where the first group includes a particular number of the network addresses that includes higher count values, relative to remaining ones of the network addresses in other ones of the plurality of groups, where the particular number corresponds to a number of the network addresses that can be searched concurrently; and

if the particular network address is not found in the first group, searching a next one of the plurality of groups for the particular network address.

10. The method of claim 9, further comprising:

receiving, by the device, a data unit; and

extracting, by the device, the particular network address from the received data unit.

11. The method of claim 10, where grouping the network addresses is further based on at least one of:

a protocol associated with the data unit, or

a user configuration setting associated with the data unit.

12. The method of claim 10, further comprising:

determining whether to forward the data unit or drop the data unit based on searching the first group or searching the next one of the plurality of groups for the particular network address.

13. The method of claim 9, where the memory is a content addressable memory (CAM).

14. The method of claim 9, further including:

incrementing one of the count values that corresponds to the particular network address.

15. The method of claim 9, where grouping the network addresses is further based on a time-dependent function of the count values.

16. A memory device to store instructions executable by a processor in a network device, the instructions comprising:

one or more instructions to sort a plurality of stored data entries based on a plurality of count values, where each of the plurality of count values indicates a number of times that the processor has previously accessed a corresponding one of the plurality of stored data entries;

one or more instructions to extract, from a data unit, a search criteria;

one or more instructions to search, in response to extracting the search criteria, a first group, of the plurality of stored data entries, for data corresponding to the search criteria, where the first group includes a particular number of the plurality of stored data entries that are associated with higher ones of the plurality of count values, relative to a second group of the plurality of stored data entries; and

one or more instructions to search, if the data corresponding to the search criteria is not in the first group, the second group for the data, where the second group includes remaining ones, of the plurality of stored data entries, that are not included in the first group.

17. The memory device of claim 16, where the instructions further include:

one or more instructions to increment a count value, of the plurality of count values, associated with the one, of the plurality of stored data entries, that includes the data corresponding to the search criteria.

18. The memory device of claim 16, where the one or more instructions to sort the plurality of stored data entries includes one or more instructions to sort the plurality of stored data entries based on a time-dependent function of the count values.

19. The memory device of claim 16, where the instructions further include:

one or more instructions to determine, according to the data corresponding to the search criteria, to either forward or drop the data unit.

20. The memory device of claim 16, where the one or more instructions to sort the plurality of stored data entries includes one or more instructions to sort the plurality of stored data entries further based on at least one of:

a protocol associated with the data unit, or

a user configuration setting associated with the data unit.