The Research Of Flow Classification Algorithm Based On Bit Vector

With the development and application of network technology, people increasingly depend on network to process information. The flow classification emerges as one of key technologies for network devices such as router and firewall in order to improve the rate of dealing with information and adapt to the development of network.This dissertation describes the current researched status of flow classification, introduces the main ideas of classical algorithms and analyzes their relative merits. The thesis studies ABV algorithm mainly, and presents an enhanced algorithm to resolve the problem of spending on space in the environment of multi-dimensional and large-scale rules database. The improved algorithm ensures the corresponding relative between rules and bitmap and reduces the complexity of the storage by intersecting storage with aggregated bitmap and BV bitmap and neglecting the seriate part of zero in BV bitmap.The dissertation designs and implements a flow classification based on the improved algorithm in the framework of Linux netfilter, and tests the performance of the improved algorithm. The results indicate that the enhanced algorithm has good efficiency of time and space compared with ABV algorithm in a multi-dimensional and large-scale rules database.