CONTROLLING A SEARCHABLE RANGE WITHIN A NETWORK SEARCH ENGINE

• US 20070028039A1
• Filed: 07/27/2006
• Published: 02/01/2007
• Est. Priority Date: 07/27/2005
• Status: Active Grant

• Current Assignee: Avago Technologies International Sales Pte Limited (Broadcom, Inc.)
• Original Assignee: Netlogic Microsystems Incorporated (Broadcom, Inc.)
• Inventors: Gupta, Pankaj, Venkalachary, Srinivasa
• Granted Patent: US 7,581,059 B2
• Time in Patent Office: Days
• US Class Current: 711/108
• 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

Abstract

Controlling a searchable range within a network search engine. A CAM array is provided within the network search engine to store data values in entries having respective addresses and to compare the data values with a search key. First address and a second addresses that define a range of the addresses are received at an interface of the network search engine, and range-control circuitry is provided within the network search engine to generate a hit signal having either a first state or a second state according to whether any of the entries having addresses within the range of addresses match the search key.

Claims

1. A content addressable memory (CAM) device comprising:

a CAM array to store data values in entries having respective addresses and to compare the data values with a search key;

an interface to receive a first address and a second address that define a range of the addresses; and

range-control circuitry to generate a hit signal having either a first state or a second state according to whether any of the entries having addresses within the range of addresses match the search key.

2. The CAM device of claim 1 wherein the interface to receive a first address and a second address comprises a first address input and a second address input to enable the first and second addresses to be received concurrently.

3. The CAM device of claim 1 wherein the interface to receive a first address and a second address comprises a time-multiplexed input to receive the first and second addresses sequentially.

4. The CAM device of claim 1 wherein the second address is greater in numerical value than the first address.

5. The CAM device of claim 4 wherein the second address is lower in numerical value than a last address of the CAM array.

6. The CAM device of claim 4 wherein the CAM array comprises a plurality of match signals each corresponding to a row of CAM cells, each match signal having either a first state or a second state according to whether contents within the respective row matches the search key.

7. The CAM device of claim 6 wherein the range-control circuitry comprises:

a decoder circuit coupled to receive the first address and the plurality of match signals, and to output a plurality of enable signals each having either a first state or a second state according to the state of each corresponding match signal and whether their respective addresses are greater than or equal to the first address; and

an encoder circuit coupled to receive the plurality of enable signals and to output a match address and an intermediate result signal.

8. The CAM device of claim 7 further comprising an end-compare circuit, wherein the end-compare circuitry comprises:

a comparator coupled to receive the second address and the match address, and to output a comparator result signal having either the first state or the second state according to whether the match address is greater than or equal to the second address; and

a logic gate coupled to receive the comparator result signal and the intermediate result signal, and to output the hit signal.

9. The CAM device of claim 6 wherein the range-control circuitry comprises:

a decoder circuit coupled to receive the first address, the second address, and the plurality of match signals, and to output a plurality of enable signals each having either a first state or a second state according to the state of each of corresponding match signal and whether the numerical values of their respective addresses are greater than or equal to that of the first address and less than or equal to that of the second address; and

an encoder circuit coupled to receive the plurality of enable signals and to output a match address and the hit signal.

10. A method of operation within a content addressable memory (CAM) device, the method comprising:

receiving a first address and a second address that define a range of entries having respective addresses within a CAM array of the CAM device;

comparing data within the range of entries with a search key; and

generating a hit/miss signal having either a first state or a second state according to whether any of the entries within the range of entries match the search key.

11. The method of claim 10 wherein receiving a first address and a second address comprises receiving the first address and second address concurrently via respective signal paths.

12. The method of claim 10 wherein receiving a first address and a second address comprises receiving the first and second address sequentially via a shared signal path.

13. The method of claim 10 wherein the second address is lower in numerical value than a last address of the CAM array.

14. The method of claim 13 wherein the range of entries excludes all memory addresses having numerical value lower than the first address and greater than the second address.

15. A method of controlling a content addressable memory (CAM) device, the method comprising:

outputting first and second address values to the CAM device; and

instructing the CAM device to determine whether values within a range of addresses bounded by the first and second address values match a search value.

16. The method of claim 15 wherein instructing the CAM device to determine whether values within a range of addresses bounded by the first and second address values match a search value comprises outputting first and second address values to the CAM device in association with a search instruction.

17. The method of claim 15 wherein instructing the CAM device to determine whether values within a range of addresses bounded by the first and second address values match a search value comprises outputting a selector value to the CAM device in association with a search instruction, the selector value specifying a start address and end address stored within the CAM device.

18. A method of controlling a content addressable memory (CAM) device, the method comprising:

outputting to the CAM device a plurality of pairs of address values that define respective address ranges within the CAM device;

outputting to the CAM device one or more instructions to store the plurality of pairs of address values within selectable storage elements of the CAM device.

19. The method of claim 18 further comprising:

outputting a search instruction to the CAM device to initiate a search operation; and

outputting a selector value to the CAM device, the selector value specifying one of the selectable storage elements to provide the pair of address values stored to be applied in the search operation.

20. A content addressable memory (CAM) device comprising:

a CAM array;

means for receiving a first address and a second address that define a range of entries having respective addresses within the CAM array;

means for comparing data within the range of entries with a search key; and

means for generating a hit/miss signal having either a first state or a second state according to whether any of the entries within the range of entries match the search key.

21. Computer-readable media having information embodied therein that includes a description of an integrated circuit device, the information including descriptions of:

a CAM array to store data values in entries having respective addresses and to compare the data values with a search key;

an interface to receive a first address and a second address that define a range of the addresses; and

range-control circuitry to generate a hit signal having either a first state or a second state according to whether any of the entries having addresses within the range of addresses match the search key.