Research And Improvement On Recursive Flow Packet Classification Algorithm

With the development of Internet and the extraordinary growth of various application and network flows, the network equipments need to provide broader band access and more efficient packet classification ability. Packet classification is the key technology for the network equipment in NGN, and the classification speed has a direct impact on the performance of network technology and the demand for memory, CPU and other resources. Besides, for more IP addresses and higher quality of service, IPv4-based network is tending to be upgraded to IPv6-based network gradually and this brings more pressures and new challenges to packet classification. Therefore, the study on fast packet classification algorithm has important practical significance and theory value.Through the systemic research of all the classical packet classification algorithms and detailed comparison on time and space comsumption between them, RFC(Recursive Flow Classification) algorithm is primarily studied for its perfect performance on classification speed. To reduce the memory redundancy and extend the limits of application while keeping on a high classification speed, RFC algorithm has been improved in two aspects as follows:(1) RFC algorithm has a good performance in classification speed but the excessive memory consumpution incurred by the expansion of filter sets costs large storage. To solve this problem, Merge_RFC, a memory optimized RFC, is proposed in this paper, designing a method of mergeing bit strings to compress the cross-productiing tables and reduce the memory redundancy of RFC. The simulation results show the outstanding performance of Merge_RFC that it can reduce the memory consumpution up to 80% when achieving the same classification speed as RFC.(2) Along with the unceasing expansion of network scale, the new generation of network protocol IPv6 instead of IPv4 becomes the next generation Internet standard and packet classification tecnology applied to IPv6-network is becoming the hot spot of this field. After evaluating the application values of RFC algrorithm under IPv6 environment, RFCv6, a modified RFC algrorithm applied to IPv6-network, is proposed in this paper designing a method of picking up character rules to excessive memory consumpution incurred by the increase of address size from 32bits to 128 bits. The simulation results show that RFCv6 strikes a right balance between memory demand and classification speed.