TCAM search unit including a distributor TCAM and DRAM and a method for dividing a database of TCAM rules

摘要

A search unit including a distributor TCAM and a DRAM search unit and a method to divide a database of TCAM rules is disclosed. The method includes selecting a rule having multiple “don't care” values and selecting a bit of the rule having a “don't care” value, generating two distributor rules based on the selected rule, associating rules of the database which match each of the distributor rules with the distributor rule they match to create subset databases, and repeating the steps of selecting, generating and associating until the average number of rules in each subset database is at or below a predefined amount. A DRAM storage unit has a section for each subset database, where each section is pointed to by a different distributor rule. A DRAM search unit matches an input key to one of the rules in the section pointed to by the matched distributor rule.

主权项

1. A search unit comprising:
a distributor TCAM (ternary content addressable memory) to store distributor rules and to match an input key to one of said distributor rules; and a DRAM (dynamic random access memory) search unit comprising a DRAM storage unit and an associated DRAM search logic unit, said DRAM storage unit having a large plurality of sections, each section pointed to by a different distributor rule and storing a small plurality of rules defined by its associated distributor rule, said DRAM search logic unit to receive said input key and to receive a section identifier (ID) from said distributor TCAM responsive to the input key matching said one of said distributor rules, and to search through said small plurality of rules in the section pointed to by said section ID and to select one of the small plurality of rules best matching said input key.