Research On IP Packet Classification Techniques

The techniques of IP packet classification can divide the IP Packets to different data streams according to the settled rules, which are foundation of disposing the distinct-operation IP packet of different actions, and the techniques are worthy to research for providing the Quality of Service, protecting the network security or intercepting the information of lawless user, and so on. Combined with the National 863 important Project "Military Next Generation Internet (MNGI)", this dissertation intensively researches on the IP packet classification techniques, and for fixed-position key words classification in IP head and unfixed-position key words classification in IP payload, puts forward a Five-field classification algorithm with the Mapping of Rang and Given Point and a Fast-Skip Wu-Manber (FSWM) Multi-pattern exactly string matching algorithm, then elementarily designs a hardware-realizable scheme of IP packet intercept for engineering.The main work of this dissertation is as follows:1. Based on the analysis results of the classical algorithms for Multi-field packet classification, the Five-field classification algorithm with the Mapping of Rang and Given Point (MRGP) which is an improved Recursive Flow Classification (RFC) algorithm for the large space demand, is proposed by synthesizing the current ideas of Hierarchical Space Mapping and Non-Collision Hash algorithm. The experiment results show that with an acceptable increase of lookup time, the MRGP algorithm reduces the large space demand and balances the space and time performance compared with RFC algorithm.2. Based on the analysis results of the classical algorithms for Multi-pattern matching, the Fast-Skip Wu-Manber (FSWM) Multi-pattern exactly string matching algorithm which is an improved Wu-Manber (WM) algorithm for the small scale pattern set, is proposed by synthesizing the ideas of correlative researchers and studying the key points which could accelerate the matching in WM algorithm. The experiment results show that in instance of small scale (less than 1500) pattern set the FSWM algorithm increases the lookup efficiency of SHIFT table and the matching speed compared with WM algorithm.3. Based on the analysis results of the advantages and disadvantages for the implement techniques of packet classification, a hardware-realizable scheme of IP packet intercept for engineering is elementarily proposed, which is used to accomplish the Five-field filtration for IP head and the multi-key words filtration for IP payload. On account of the "MNGI" project places the emphasis on the primary filtration for IP packet head, this dissertation validates the functionality of primary filtration in the proposed scheme. The results show that the primary classification of the scheme can capture IP packet accurately and achieve the Five-field filtration for IP head.