Research On Storage And Power Efficiency Packet Classification Algorithm Based On TCAM

Ternary Content-Addressable Memory (TCAM) has become the de facto industrial standardin high-throughput packet classification and IP route lookup field. However, the two majordrawbacks of TCAM, range rule expansion and high power consumption, proposing newchallenges to its futher deployment in high speed network. A single range rule has to beconverted to multiple TCAM entries, which makes the storage usage unefficiency; high powerconsumption generates a lot of energy,which makes great difficult in system designning andlayout.Combined with the “Uniform Security Control and Management Network for ThreeNetworks Convergence” project of the National863Program, this dissertation comprehensivelyanalyzes and summarizes the current researches on typical packet classification algorithms basedon TCAM.From the perspective of how to efficiently represent range rules and reduce powerconsumption, it makes some improvment and designs a packet classification engine.The maincontributions are outlined as follows:1、Aiming at TCAM could not well-suited for representing rules that contain range fieldsleading to low storage efficiency, this paper proposes an efficient range rule matching algorithmbased on domain transformation(DTRM).It propose an improved range encoding methodSmart-DIRPE, which fully make use of the extra bits in TCAM entries to encode and construct anew range domain.Based on the releationships among rules,a domain transformation approach isdesigned to transform the original domain of each field to the new domain of Smart-DIRPE,making the classifiers be represented by smaller number of TCAM entries. The experimentationshows that, DTRM not only reduce range expansion to1.21below, achieves more than82%storage efficiency，but also gains better update performance.2、Aiming at TCAM s high power consumption due to its parallel search mechanism againstall the entries, this paper proposes a power reduction algorithm based on Tri-state-based Partitionapproach (TSP-PR). Based on the observation that TCAM allows three matching states,0,1or*(wildcard), it proposes a classifier partition approach without rules duplication. It employsdynamic heuristic schemes at bit level to select identification bits, which can represent theinherent characteristics of the classifiers, partitionning the classifier into many subsets and storedin the corresponding TCAM blocks. The experimentation shows that, by taking advantage of theinherent characteristics of the classifiers, TSP-PR makes a highly effective partition to classifiers,achieves a great power reduction over70%with a little penalty of storage overhead.3、A realizable TCAM-based packet classification engine is designed based on the abovealgorithms and the platform of three Networks Convergence.It makes an overview of the schemeand introduce the function of each module, a detailed description of the implemention of theproposed algorithms is depicted. Testing results show that, the scheme can achieve lower power consumption, and keeps a relatively high storage efficiency meanwhile,at last analyze thedisparity between the theoretical and practical power reduction and explains the reason behind it.