Searching small entities in a wide CAM
View Patent ↗A plurality of entities are stored in a single addressable location in a Content Addressable Memory (CAM). A column in a CAM entry is selected for storing an entity based on the property of the entity to distribute the entities among the columns to maximize memory utilization. A match for a search key stored in one of the plurality of columns can be found in a single search operation.
1. A method of searching a Content Addressable Memory for entities which are smaller than Content Addressable Memory entries comprising:
storing entities in respective columns of the Content Addressable Memory;
selecting a column to be searched based on a property of an entity search key wherein the column is selected based on a result of a hash function performed on less than all bits in the entity search key; and
applying the entity search key to the selected column to search for a match.
2. The method of claim 1 wherein the hash function evenly distributes entities across the plurality of columns in the Content Addressable Memory.
3. The method of claim 2 wherein the hash function performs a parity test on the portion of the entity search key.
4. The method of claim 2 wherein the hash function performs a CRC test on the portion of the entity search key.
5. The method of claim 1 wherein the Content Addressable Memory has 4 columns for storing IP addresses, the hash function performed on 16 most significant bits of the entity search key.
6. The method of claim 5 wherein the hash function computes parity of even bits and parity of odd bits in the 16 most significant bits of the entity search key.
7. A method of searching a Content Addressable Memory for entities which are smaller than Content Addressable Memory entries comprising:
storing entities in respective columns of the Content Addressable Memory;
selecting a column to be searched based on a property of an entity search key; and
applying the entity search key to the selected column to search for a match by shifting the entity search key to bit locations in a Content Addressable Memory search key corresponding to the selected column and performing a masked search masking nonselected columns.
8. An apparatus for searching a Content Addressable Memory for entities which are smaller than Content Addressable Memory entries comprising:
categorization function logic which selects a column of the Content Addressable Memory to be searched based on a result of a hash function performed on less than all of bits in the entity search key, the Content Addressable Memory storing entities in respective columns; and
bit shift logic which applies the entity search key to the selected column to search for a match.
9. The apparatus of claim 8 wherein the hash function evenly distributes entities across the plurality of columns in the Content Addressable Memory.
10. The apparatus of claim 9 wherein the hash function performs a parity test on the portion of the entity search key.
11. The apparatus of claim 9 wherein the hash function performs a CRC test on the portion of the entity search key.
12. The apparatus of claim 8 wherein the Content Addressable Memory has 4 columns, each columns storing an IP addresses, the hash function performed on 16 most significant bits of the column.
13. The apparatus of claim 12 wherein the hash function computes parity of even bits and parity of odd bits in the 16 most significant bits of the entity search key.
14. An apparatus for searching a Content Addressable Memory for entities which are smaller than Content Addressable Memory entries comprising:
categorization function logic which selects a column of the Content Addressable Memory to be searched based on a property of an entity search key, the Content Addressable Memory storing entities in respective columns; and
bit shift logic which applies the entity search key to the selected column to search for a match by shifting the entity search key to bit locations in a Content Addressable Memory search key corresponding to the selected column and performing a masked search masking nonselected columns.