Research On A TCAM-SRAM Architecture For Packet Classification Range Matching Algorithms

Packet classification(PC)plays an important role in many networking services on the internet including routing,filtering,intrusion detection,billing,monitoring,and virtual private networking.Packet classification maps each packet to a stream according to the specified filtering rule,which is usually a combination of one field(e.g.,IP)or some fields(e.g.,IP,Port,Protocol)in the header part of the packet.The system first performs packet parsing and field extraction operations on data packets,then classifies data packets according to protocol types and classification fields to determine the next step such as forwarding,rejecting and discarding.The usual solutions for packet classification problems include software algorithms and hardware algorithms.A typical hardware based solution is to use Ternary Content Addressable Memories(TCAMs)which are necessary to support the gigabit line processing rate.The trimorphism of TCAM facilitates precise matching and prefix matching,but it can't directly support range matching.It needs to convert range fields into multiple matching table items to express,which is also called range expansion.The disadvantage of range expansion is that it will reduce the efficiency of TCAM space,will also cause a larger configuration load and increase its update cost,thus making the power consumption of TCAM more serious.This thesis provides a feasible solution to the problem of range expansion.The main contributions are as follows:1.Proposes a TCAM-SRAM architecture for packet classification range matching algorithms.The range matching algorithm for the suggested architecture in this thesis uses parallel lookup,finds TCAM range in TCAM,reads the corresponding SRAM range blocks at once,and sends the two results to the priority comparator module to get the best match.This method ensures that the time complexity of the matching process is O(1).2.Discusses the range matching scheme of packet classification,which combines TCAM-SRAM architecture with different coding algorithms.Mainly includes two cases:Gray code encoding algorithm SRGE and optimal encoding algorithm OPT.The corresponding range storage and search methods are described.3.Compares the range expansion of different packet classification range matching algorithms.Among them,the suggested solution which combines the TCAM-SRAM architecture with the OPT algorithm can further reduce the range expansion to 2[(Wb+l)/2]in the worst case.The simulations based on random and real-world rule sets show that the suggested method can reduce the range expansion and improve the spatial utilization of TCAM compared with the basic encoding algorithm.