Method and apparatus for implementing a search engine using an SRAM
View Patent ↗A search engine system including a memory bank coupled to a bank selection signal, mask logic for receiving constructed keys and incoming key masks and for providing masked keys, hash function blocks for receiving at least two of the masked keys and for providing at least three hash function outputs and multiplexers for receiving hash function outputs, and for providing the bank selection signal is disclosed. Also, the system can allow for local masking of the constructed keys using local mask fields. The hash function can be a Cyclic Redundancy Code (CRC) type function. The memory bank can be arranged as buckets of entries and can be implemented as a standard static random access memory (SRAM). Further, the system can be configured to operate in either a shared mode for sharing hash function outputs or a non-shared mode whereby hash function outputs can be designated for particular portions of the memory bank.
1. A search engine system, comprising:
a memory bank coupled to a bank selection signal;
a plurality of mask logic blocks, wherein each mask logic block is configured to receive a constructed key and an incoming key mask and to provide a masked key;
a plurality of hash function blocks, wherein each hash function block is configured to receive at least two of the masked keys and to provide at least three hash function outputs; and
a multiplex configured to receive a plurality of hash function outputs and to provide the bank selection signal.
2. The search engine system of claim 1 , wherein:
the memory bank includes memory that is static random access memory (SRAM) type.
3. The search engine system of claim 1 , wherein:
the memory bank is arranged as a plurality of buckets, wherein each bucket includes a plurality of entries.
4. The search engine system of claim 3 , wherein:
the bank selection signal is configured to select one of the plurality of buckets.
5. The search engine system of claim 3 , wherein:
each of the plurality of entries includes a stored key pattern field, a local mask field, and a hash function indication field.
6. The search engine system of claim 5 , further comprising:
a comparator configured to provide a match indication for each of the plurality of entries in response to a comparison between the constructed key and the stored key pattern.
7. The search engine system of claim 6 , wherein:
the comparator includes an AND-function block configured to provide a masking of the constructed key by applying the local mask field.
8. The search engine system of claim 3 , wherein:
in a first mode, each of the plurality of entries is configured to be responsive to any of the plurality of hash function outputs; and
in a second mode, each of the plurality of entries is configured to be responsive to a designated one of the plurality of hash function outputs.
9. The search engine system of claim 1 , wherein:
the constructed key includes information from a packet header.
10. The search engine system of claim 1 , wherein:
each of the plurality of mask logic blocks includes a logical-AND type function.
11. The search engine system of claim 1 , wherein:
each of the plurality of hash function blocks includes:
a first hash function generator configure to receive a first masked key and to provide a first hash function output;
a second hash function generator configured to receive a second masked key and to provide a second hash function output; and
a third hash function generator configured to receive the first masked key and the second masked key and to provide a third hash function output.
12. The search engine system of claim 11 , wherein:
the third hash function output is configured for a concatenated key type search.
13. The search engine system of claim 12 , wherein:
the concatenated key type search includes a same address selection in a first memory bank and a second memory bank.
14. The search engine system of claim 11 , wherein:
each of the first, second, and third hash function generators include a Cyclic Redundancy Code (CRC) type function.
15. The search engine system of claim 1 , wherein:
the multiplexer is configured to receive at least eight hash function outputs.
16. The search engine system of claim 15 , wherein:
the at least eight hash function outputs includes outputs from at least four different hash function blocks.
17. The search engine system of claim 16 , wherein:
the multiplexer is configured to select a different one of the outputs from the at least four different hash function blocks in response to a clock signal.
18. A method of searching a table populated with a plurality of entries, comprising the steps of:
constructing a plurality of keys;
performing a key masking on each of the plurality of keys to provide a plurality of masked keys, wherein the plurality of masked keys provide for a bit-by-bit search of the plurality of entries;
performing a hashing on each of the plurality of masked keys;
determining if a system is in a shared mode;
if the system is in the shared mode, sharing a plurality of hash functions for an entry of a memory bank;
if the system is not in the shared mode, hard configuring the hash functions for the entry of the memory bank;
selecting a bucket from the memory bank, wherein the bucket includes the plurality of entries;
applying a local mask;
performing a comparison to provide one or more match indications;
determining a precedence from among the one or more match indications; and
selecting a match from the one or more match indications based on the precedence, the match corresponding to one of the plurality of entries.
19. The method of searching the table of claim 18 , wherein:
the constructing the plurality of keys includes getting information from a packet.
20. The method of searching the table of claim 18 , wherein:
the performing the hashing includes using a Cyclic Redundancy Code (CRC) type function.
21. The method of claim 18 wherein the plurality of masked keys further provide for a field search of the plurality of entries.