Research And Application Of Flow Classification Algorithm Based On Marked Bitmap

With the rapid growth of network traffic and the development of new network services, the stronger ability of data processing of network devices such as firewall and security gateway is required. Flow classification is able to support a full range of network services and improve the performance of network devices, which is one of the most important technologies for high-speed network.This dissertation introduces the current researches and the background of flow classification as well as the related technology of firewall and UTM gateway, and describes the classical flow classification algorithms, such as Grid-of-tries algorithm, RFC algorithm, TSS algorithm, BV algorithm and ABV algorithm. Then the time complexity and space complexity of these algorithms are analyzed and compared.ABV algorithm is an improvement of BV algorithm. It transforms BV bitmap into aggregated bitmap by aggregated factor to reduce classification time. ABV algorithm spends on large space in the environment of multi-dimensional and large-scale rules database, because it stores both of aggregated bitmap and BV bitmap. To resolve the problem, an improved algorithm named MBV is presented. MBV algorithm transforms the aggregated bitmap in ABV algorithm into marked bitmap, which replaces large of sequential zero in BV bitmap with limited bits to reduce the space of the storage and improve the efficiency of classification.The data structures of the framework of Linux netfilter is analyzed, and the implementation principle and operational mechanism of the five hook points is studied. On this basis, the module of flow classification in the UTM gateway which is based on MBV algorithm is designed. Then the performance of MBV algorithm is tested. The results indicate that MBV algorithm has better space efficiency than ABV algorithm in a multi-dimensional and large-scale rules database.