Research On High Speed Packet Lookup Rule Matching Algorithm

With the increasement of network traffic and line speed, the datapath processing in the switching and routing devices faces great challenges. To get the wire speed forwarding for 100Gbps interface for the minumal ethernet packet, the processing time must be less than 6.72ns. L2-L7 rule matching is the key processing in packet processing for packet forwarding,QoS scheduling and traffic controlling. This thesis focus on the research of L3 Longest Prefix matching(LPM), L3-L4 Packet Classification(PC) and L7 Deep Packet Inspection(DPI). The researches are on TCAM(Ternary Content Addressable Memory) hardware. Some rule mathcig algorithms have been proposed, analysized and simulated.IP address lookup need to do two dimensions matching to find the longest matching prefix.Traditional schemes implement IP address lookup using linear or binary search on prefix lengths or prefix values at the cost of slow lookup speed,complex pre-computation or high power consumption. A novel binary search algorithm based on prefix covered levels called BSPCL is proposed in this paper.At each level we use TCAMs to determine whether there is a match.TCAM entries need not be sorted because prefixes at each level are disjoint. Pre-computation is no longer needed and incremental updates are supported. IP address lookup can be done in O(log2max_level+1) TCAM clock cycle at the worst case where max_level is the maximal number of overlapping prefixes.The current max_level is 7 for IPv4 and 2 for IPv6.We can reduce the power consumption about 50%.Complexity comparision and performance evaluation shows the proposed sheme has better performance over other schemes.A parallel IP address look scheme called LEAF-TCAM was proposed. The routing table is partitioned into subtable according to the leaf nodes which result in simple and even table partition. A greedy algorithm was proposed to distributed the subtables to the K TCAM chips which could aassure load balance among the chips.With the proposed LEAF-TCAM scheme we can get K-1 speedup of IP address lookup and incremental updates are also supported. Simulation with backbone routing table shows with 0.1*(K-1) redundant factor, over 90% routing prefixes need not be sorted and the power dissipation is only 12% of single chip scheme.The current IP address cache or IP prefix cache technologies have limitations.We analysized the overlapping relationships among prefixes in the global routing tables and proposed a threshold-based routing cache method which combined IP address cache and prefix cache technologies without the need of prefix expansion.The threshold value K is selected according to the prefix overlapping features of global routing tables which overcame the shortcomings of address caching and prefix caching technologies.Comparision and simulation showed our scheme had better performance over other schemes in cache size,cache hit ratio,fairness among prefixes and incremental prefix updates.For a global routing table with more than 250K entries and cache size of 10K, above 97% prefix nodes could be 1:1 cached by prefix cache and the other prefix nodes could be cached by address cache with threshold K=4.Computation showed that it could fulfil the wire speed forwording requirement of 100Gbps ethernet with small cache sizeHish speed packet classification using TCAM faces the problem of range expansion problem where ranges must be broken into several entries when matching range field. The expansion factors of PE(Prefix Expansion) and SRGE (Short Range Gray Encoding) are 2(w-1) and 2(w-2) repectively in the worst case where w is the field width of the range. The range expansion of TCAM will lower down the efficiency of TCAM space and increase the power dissipation. A new TCAM range matching method called C-TCAM(Compressed TCAM) was proposed in this paper. Firstly C-TCAM could compress two expanded TCAM entries into one and get the expansion factor of w-1 and w-2 respectively in the worst case. Secondly, we disigned a new TCAM matching algorithm to lower down the power dissipation by avoiding matching of unnessary TCAM entries. Thirdly, C-TCAM could scale to more than two levels under the performance restriction and resulted in more space efficiency and less power dissipation. Analysis and simulation showed that C-TCAM gets advantages over other schemes in TCAM space efficiency and power dissipation.Hish speed Deep Packet Inspection using TCAM faces the problem of high power dissipation. A 2-phase DPI method BF-TCAM was proposed. The first phase used parallel bloom filters to exclude the normal packets not including attack signatures. The second phase used TCAM to inspect suspicious packets including real attack packets and false positive packets of the first phase. The bloom filters' false negative probability is zero and false positive probability is very low. Since most of the network data do not include attack signatures, our method can get high speed DPI with low power dissipation.The above proposed algorithms and schemes have been implemented and available on prototypes of IPv4/IPv6 internetworking gateway and ethernet switch designed for CNGI and MII Electronic Grant projects. These projects had been checked and accepted, and the IPv6 ehternet switch has been licensed by China Ministry of Information Industry.