Research Of Flow Classification Algorithm On Memory Optimization

With rapid development of the Internet, network applications and service species become more complex and users’ demand for data processing capabilities of firewalls, routers or other network node device increase highly. As the key technology of network devices, flow classification could effectively improve the performance of network devices and provide full range of technical support for the applications and services.This dissertation describes flow classification’s background, research status and application technology. The classical flow classification algorithm-RFC algorithm is analyzed and compared. In the preprocessing stage, RFC algorithm generates three tables (Equivalence lass table, Preprocessing table, Cross multiplication table) which take up a lot of memory space. The size of the tables associate with the scale of ruleset. An improved algorithm-Optimize_RFC is put forward with RFC algorithm’ problem of excessive memory consumption in large-scale ruleset. Optimize_RFC algorithm compresses Equivalence lass table, Preprocessing table and Cross multiplication table with chunk XOR which compresses the source/destination IP address or ports to 8 bit. Optimize_RFC algorithm reduces the memory consumption in the preprocessing stage. Packet header information is Extracted and executed by chunk XOR when the packet coming. Optimize_RFC algorithm gets the Index of each stage through the equivalence class tables and finds the best match rule according to the value of Index and CBM. Optimize_RFC algorithm could effectively overcome the problem of RFC algorithm on memory consumption in large-scale ruleset, while maintaining a high speed of classification.This dissertation also analyzes the implementation mechanism of Linux firewall. UTM gateway’ flow classification module is designed and implemented based on Optimize_RFC algorithm in framework of netfilter and improved firewall performance.The performance of RFC algorithm, the literature [42] algorithm and Optimize_RFC algorithm are analyzed and compared through building network test platform in the end. The experimental results show that Optimize_RFC algorithm had better space performance, in large-scale ruleset application environment.