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.
2. The search unit according to claim 1 wherein said DRAM storage unit comprises a multiplicity of banks and wherein said DRAM search logic unit can access one row from each bank of said DRAM storage unit generally at the same time.
3. The search unit according to claim 1 further comprising a global parents TCAM to store distributor rules each having a significant plurality of children rules.
4. A method to divide a database of TCAM (ternary content addressable memory) rules, the method comprising the steps of:
transferring to a search logic unit a rule of said database having multiple don't care values;
generating in said search logic unit two distributor rules based on said transferred rule by assigning to a bit of said transferred rule having a don't care value a 1 value in one of said two distributor rules and a 0 in the other of said two distributor rules;
associating rules of said database which match each of said two distributor rules with the distributor rule they match thereby to create subset databases; and
repeating said steps of transferring, generating, and associating on said database of TCAM rules and on said subset databases until the average number of rules in said subset databases is less than or equal to a predefined amount.
5. A method according to claim 4 further comprising placing each said two distributor rules into a TCAM and placing said subset databases in a DRAM (dynamic random access memory).
6. A method according to claim 4 further comprising placing said two distributor rules into a TCAM and placing each of said subset databases in a small TCAM.
7. The method according to claim 4 further comprising determining a set of global parents rules each having a significant plurality of children rules.
8. A method according to claim 7 further comprising placing said set of global parents rules into a global parents TCAM, separate from a TCAM for said distributor rules and separate from a storage unit for said subset databases.