Research And Application Of An Efficient Packet Classification Algorithm Based On Multi-level Search

With the rapid development of network technology, more and more networkservices are in need of fast and accurate classification of data packets. Packetclassification has become a performance bottleneck of high-speed router, and how toclassify packets quickly and efficiently under good time and space condition is adifficult problem to solve currently. On the basis of a numerous studies on differenttypes of packet algorithms, this paper introduces a new designed packet algorithmwith the combination of the flow locality principles in the network and bloom filter,expanding its application in order to present a good performance. The main innovationpoints are embodied in the following two aspects.Firstly, a packet classification algorithm based on the flow locality principles andmulti-level lookup (PCFM) is proposed focusing on the problem of packetclassification algorithms in the high-speed network. PCFM takes the advantages of theflow locality principles and bloom filter, then3-level search algorithm is proposedaccording to the hit ratio of flow in multi-level structure as well as analysis of the kvalue of hash function. The first level stores flow arriving within10seconds, whilethe second for that arriving between10seconds to60seconds and the third level forthe rest. Experiment results show that this algorithm could not only support dynamicupdate of rule base when compared with traditional packet classification algorithms,but also increase time performance by about30%in equal memory consumption.Secondly, the application of network flow detection can be carried out with theimproved PCFM. Selecting two relatively typical flows (HTTP flow and PPlive flow),we make an analysis of the package lengths and time property features of the twoflows. It is found that HTTP flow has features of bigger packet length, slower updatespeed and steadier performance while PPlive flow is featured with smaller packerlength, quicker update speed and the higher capacity. According to the variantcharacteristics, we put flows with varied quantities in three-levels of PCFM algorithm.Regarding HTTP flow, the principle of storage was depositing flow within100seconds in the first-level cache and then flow within100-150seconds in the secondlevel, and lastly the rest flow in the third level. As for PPlive flow, the principle ofstorage was depositing flow within20seconds in the first-level cache and then flowwithin20-80seconds in the second level, and lastly the rest flow in the third level. With the above settings in experiments, it is found that the improved PCFM algorithmis endowed with much higher accuracy in large flow detecting application, andimproves space performance by35%when compared with traditional large flowdetecting algorithm.