Packet Classification Algorithms

In order to implement the new characteristic of Qos, VPN, MPLS, access control which the next generation information network put forward, Internet must provide the network status guarantee of the bandwidth, delay, the ratio of packet lost etc. , which means Internet must classify the packets of different requests.In this paper, we first do a systemic ,detail research on all classical packet classification algorithms and analysis the time and space request of all algorithms , then forward three questions of the packet classification. As to the multiple classification algorithms of large size rule set, we introduce a algorithms named recursive flow classification and this algorithms use the linear buffer to implement recursive map. This paper discuss the map process using the class equivalent class deeply and program to implement the three phases process. Secondly , we introduce the principle and flow of the tuple space search base on the detail explaining of tuple space. Tuple space search is a fast update algorithms which can employ to large size rule set and we provide a two fields classification algorithms named rectangle algorithms which is a optimized two fields algorithms in the search time and space after we discuss the way of mark in detail. Then as to the disadvantage of the TSS native algorithms we bring forword a new algorithms which is bit vector algorithms base on rule length and the result of program show the performance of new algorithms is better than the native one. Finally, we introduce the concept of the rule subset and the multiple fields packet classification algorithms can make use of the fast IP routing search algorithms base on the new concept. So we put forward the field-divided classification algorithms in the IPv6 circumstance and the new algorithms need seven times to access memory in the worse case.We put forward a principle of design multiple field packet classification algorithms base on the analyzing of the basic theory, algorithms structure and flow. Now the speed of link is more and more high and the size of rule set is more and more large, it is difficult to design fast multiple field classification algorithms and the design principle is combine or improve the classical algorithms base on the analyzing the distributing law of the actual rule set.