MULTI-STAGE TCAM SEARCH

摘要

A method to divide a database of TCAM rules includes selecting a rule of the database 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, where the selected bit has a 1 value in one of the distributor rules and a 0 in the other of the distributor rules, associating rules of the database which match each of the distributor rules with the distributor rule they match thereby to create associated databases, and repeating the steps of selecting, generating and associating on the database and the associated databases until the average number of rules in each associated database is at or below a predefined amount. A search unit includes a distributor TCAM and a DRAM search unit having a DRAM storage unit and an associated DRAM search logic unit. The DRAM storage unit has a section for each associated database, where each section is pointed to by a different distributor rule. The DRAM search unit matches the 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 having multiple bits with don't care values, said TCAM to match an input key to one of said distributor rules; and a DRAM (dynamic random access memory) search unit having 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 search unit to match said input key to one of said rules in the section pointed to by said one of said distributor rules.