Research On Fast Packet Classification Algorithm

Since the emergence of Internet, it has supported the function of each domestic field directly, and played more and more important role in the development of national economy. Currently Internet gets the gigabit or higher transfer speed in the communication networks. However, the traditional router, shouldering the communication task, which offers a Best-of-Service and forwards packets undistinguishedly, can't meet the requirement of customized services. And in order to provide differentiated services for various users, routers should classify packets it receives before forwarding. Therefore, packet classification has become the foundation of differentiated services such as firewall packet filtering, policy-based routing, virtual private network, traffic billing and so on. However, at the same time, it has turned out to be a bottleneck of high-speed router, and brings forward the problem of efficient classification with an acceptable time and space complexity.In this thesis, we propose a priority-based quad-tree (PQT) algorithm for packet classification, based on recursive space decomposition and the priority of rules. In constructing a quad-tree generated based on recursive space decomposition, the priority of rules is primarily considered in the proposed algorithm. In the simulation, the proposed algorithm achieves good performance in the required memory size and reasonable performance in the classification speed.In this paper, we exploit distinctive flow characteristics of attacks when they communicate on a network, and propose a semi-supervised classification method that can accommodate both known and unknown attacks. In training our classifier, we employ SFS (sequential forward selection) to get the best feature subset. Meanwhile, we propose weighted sampling techniques to obtain training flows. Our performance evaluation using KDD CUP1999 data shows that high flow and byte classification accuracy can be achieved.