Research On Deep Packet Inspection Algorithm In High-speed IP Network

With the continual development of transferring speed and application typies on Internet, traffic management system demands a better matching algorithm for rule capacity and searching speed. Traditional deep packet inspection algorithms which achieve online matching at the cost of high memory consumption, can't meet the demand of large-scale pattern matching and traffic management in high-speed networks. Combined with the"High Creditability Network Traffic Management and Control System"project of the National High-Tech Research and Development Program of China, this dissertation analyses and summarizes the current researches on deep packet inspection. It also studies the matching method and implementation of string and regular expression in high-speed networks for resolving memory explosion caused by incremental rules. Its main work and contributions are outlined as follows:1. A large-capacity string matching algorithm using set-segment coding(LSMA-SC) is proposed. Combined the idea of state transferring in finite state machine with the powerful comparing ability of TCAM, LSMA-SC establishes a multi-character deterministic finite automaton which can accelerate the searching process. It encodes state value by set-segment and combines the redundant translations for improving the rule capacity. Experimental results show that LSMA-SC supports high-speed searching in a large-scale string database.2. Based on the deep analysis of matching quality in deterministic finite automaton, a metacharacter-based regular expression matching algorithm(MRMA) is presented. Rules are converted into divisional deterministic finite automaton for removing the multivocal meaning of regular expression and avoiding the explosion of entry scale. Experimental results show that MRMA can achieve high-speed matching for large-scale regular expressions rules by reducing the memory consumption.3. A detecting engine based on deep packet inspection that supports the string matching and regular expression matching is designed. This engine adopts a segregative framework which implements system management with control-panel and traffic matching with data-panel for improving the expansibility and trans-plantablity of system. It achieves line-speed processing with extended algorithm and pipelining design, and gets a high capability of rule-management by constructing the mapped table of TCAM entries and the structure of state value. Experimental results validate the proposed scheme.