Multi-stage tcam search

Abstract

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.

What is claimed is: 
     
         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.   
     
     
         2 . The TCAM search unit according to  claim 1  and wherein said DRAM search logic unit is implemented within said DRAM unit. 
     
     
         3 . The TCAM search unit according to  claim 2  wherein said DRAM storage unit comprises a multiplicity of banks and wherein said DRAM search logic unit comprises means to access one row from each bank of said DRAM storage unit generally at the same time. 
     
     
         4 . The TCAM search unit according to  claim 1  and also comprising a global parents TCAM to store distributor rules each having a significant plurality of children rules. 
     
     
         6 . A method implementable in software to divide a database of TCAM rules, the method comprising:
 selecting a rule of said database having multiple don't care values and selecting a bit of said rule having a don't care value;   generating two distributor rules based on said selected rule, where said selected bit has a 1 value in one of said distributor rules and a 0 in the other of said distributor rules;   associating rules of said database which match each of said distributor rules with the distributor rule they match thereby to create associated databases; and   repeating said steps of selecting, generating and associating on said database and said associated databases until the average number of rules in each of said associated databases is less than or equal to a predefined amount.   
     
     
         7 . A method according to  claim 6  and also comprising placing said distributor rules into a TCAM and placing said associated databases in a DRAM. 
     
     
         8 . A method according to  claim 6  and also comprising placing said distributor rules into a TCAM and placing each of said associated databases in a small TCAM. 
     
     
         9 . The method according to  claim 6  and also comprising determining a set of global parents rules each having a significant plurality of children rules. 
     
     
         10 . A method according to  claim 9  and also 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 associated rules.