TERNARY CONTENT ADDRESSABLE MEMORY UTILIZING COMMON MASKS AND HASH LOOKUPS

摘要

A ternary content-addressable memory (TCAM) that is implemented based on other types of memory (e.g., SRAM) in conjunction with processing, including hashing functions. Such a H-TCAM may be used, for example, in implementation of routing equipment. A method of storing routing information on a network device, the routing information comprising a plurality of entries, each entry has a key value and a mask value, commences by identifying a plurality of groups, each group comprising a subset number of entries having a different common mask. The groups are identified by determining a subset number of entries that have a common mask value, meaning at least a portion of the mask value that is the same for all entries of the subset number of entries.

主权项

1. A computer-implemented method comprising:
identifying among a plurality of keys wherein each key is associated with a mask value, a first subset of the plurality of keys having a common mask value; entering the first subset of the plurality of keys having a first common mask value into a first table stored in a random access memory (RAM), wherein the first table is associated with the first common mask value; and entering the remaining plurality of keys that do not have a common mask value into a ternary content addressable memory (TCAM) including each key and its associated mask value.