Research Of Parallel Packet Classification Algorithm Based On Bitmask Rules

Along with the advancement of tri- network convergence, network becomes increasingly diversified, and various network services emerge in an endless stream. How to differentiate different network services, based on different demands of services, and to ensure the quality of services is an important research topic today. The packet classification technology provides the foundatio n for differentiated services. Because of this, the research on the technology of packet classification efficiency seems even more important.Now, most of existing packet classification algorithms are based on the range and prefix type rules, because it is convenient for these algorithms to search. However, these algorithms can't effectively meet the requirement of converging network. In contrast, the bitmask type rule has its unique advantage that can relatively handle range/prefix type simply and efficiently.According to the requirement of packet classification technology in the Common Security and Control Framework based on tri-network convergence, this thesis researches packet classification algorithm based on bit mask rules, focus on doing some improvement and optimization based on classic Grouper algorithm. The main work includes:Firstly, this thesis analyses depth the current situation and application of packet classification technology, and researches the common packet classification algorithms; then this thesis analyses the requirement of packet classification in the environment of Common Security and Control Framework, including the fine distinction between services and feature services and so on, and points out the deficiencies of the existing packet classification algorithms to lay the foundation for follow-up study.Secondly, according to the fine differentiated service s demand for higher safety and classification performance demand integration network, this thesis proposes Aggregation-Fold-Grouper(AF-Grouper) packet classification algorithm. While there are a lot of 0 bits in the bitmaps, the thesis uses the aggregation and fold technologies to improve the performance of Grouper. First, the original bitmap is operated with aggregation technology. Then, the original bitmap corresponding to the polymerization zones is operated with fold technology. So, when the need to match tables, the algorithm first looks aggregating bitmap and then look s for folding bitmap, and finally finds the necessary original bitmap. The experiment shows that AF-Grouper compared Grouper increases by 3 to 4 times in the lookup performance.Thirdly, according to the characteristics of the service is relatively less in converged network matched to a number of rules as well a s the service status update performance, this thesis proposes Link-Filter-Grouper(LF-Grouper) packet classification algorithm. LF-Grouper uses chain storage structure and filtering mechanism to improve the Grouper algorithm. First, the algorithm only stores those matching rules in the position. Secondly, combined with the particularity of actual rule sets on special port and protocol field values, the algorithm filters unnecessary rules. The experiment shows that LF-Grouper can effectively improve the search speed and reduce the pretreatment time.Last, this thesis tests above algorithms and performance test, which have a preliminary validation on Common Security and Control Framework based on the tri-network convergence.