Research On Pattern Matching Algorithm In 40Gbps Application Awareness System

The enhancement of throughput in backbone network poses a great challenge to real-time service identification and management system. How to accurately identify and manage the services carried on the Internet packet by packet at line-speed has become a serious problem in construction of the new generation of high credible network.Combined with the state 863 project"Service Management and Control System in High Credible Network", after analyzing current researches on pattern matching algorithm, this dissertation mainly researches the matching algorithm based on TCAM which is a high-speed parallel matching chip, and improves the matching and identification mechanism, then designs a feasible high-speed service identification scheme.Main work and contributions of this dissertation are outlined as follows:Several current pattern matching algorithms have been analyzed in detail. The dissertation compares these classic pattern matching algorithms from time complexity, space complexity and difficulty of engineering implementation, then evaluates the excellence and disadvantage.To solve the problem of poor throughput and deficient storage in the case of long-pattern matching, a high-speed pattern matching algorithm based on keywords hash compression named HASH-TCAM is proposed. To increase the throughput and improve the utilization efficiency of storage space, HASH-TCAM combines the hash scheme with TCAM scheme in the hardware implementations of the pattern matching, and compresses the pattern string by hash process. Theoretic analysis and experimental results demonstrate that the throughput can reach up to 57.6Gbps at a cost of 8.9 ? 10?8 collision rate while the fixed keyword query length being 36Bytes and the number of pattern sets is 5000, thus it can meet the requirements of pattern matching under 40Gbps line-speed.Since a large number of non-sensitive keywords may lead to the increase of false positives for service identification, a pattern matching algorithm based on Bloom-Filer engine filtration named BF-TCAM is presented. BF-TCAM adopts hardware-oriented Bloom Filter to filter out non-mode keywords with a low omission factor, and it also improves the accuracy of pattern recognition. The results show that, compared with the traditional TCAM matching algorithm, HBF-TCAM improves the throughput and storage space utilization, and effectively reduce the false positive rate caused by the system.A high-speed service identification scheme based on 40Gbps backbone network is designed. This dissertation describes 40Gbps POS interface board and the modules within FPGA in detail, and particularly illuminates the hardware implementation process of the proposed algorithms above in service identification system. Testing results show that the system can efficiently provide feasible service identification guarantee for next generation of high credible network at 40Gbps line-speed.