Front End Processing Algorithms For Backbone Traffic Analysis Based On Bloom Filters

According to the fundamental technique research task of the"New Generation Network with High Trustability"project of the National High-Tech Research and Development Program of China (863 Program), this thesis studied the design and implementation of front end processing algorithms for traffic analysis system on high-speed backbone networks. Starting from the research on Bloom filters, this thesis then proposed front end processing algorithms based on an improved Bloom filter. The design and implementation of a front end processing system for real-time backbone traffic classification was presented finally.Firstly, this thesis proposed a new Counting Bloom filter (CBF) based on in-depth analysis and thorough comparison of three existing CBF schemes with low computational complexity, that is, the Na?ve Counting Bloom Filter (NCBF), the Space-Code Bloom Filter (SCBF) and the d-left Counting Bloom Filter (dlCBF). The optimal parameter setting rules for the three CBF schemes were presented through in-depth analysis. The performance of the three CBF schemes was compared using metrics of counting error, space complexity and load adaptability. The results showed that dlCBF outperforms NCBF and SCBF in terms of both counting error and space complexity. However, the load adaptability of dlCBF is very limited. Then, a new CBF schema called Binary Shrinking d-left Counting Bloom Filter (BSdlCBF) is proposed. The experimental results show that our proposal BSdlCBF outperforms the existing three CBF schemes in terms of counting error, space complexity and load adaptability.Then, this thesis presented front end processing algorithms based on BSdlCBF. A new per-flow traffic measurement algorithm named Multi-Resolution BSdlCBF (MR-BSdlCBF) was proposed. MR-BSdlCBF has better load adaptability and lower space complexity than its same category competitor, that is, the Multi-Resolution SCBF (MRSCBF). Another advantage of MR-BSdlCBF is that it can support flow label recording. Furthermore, this thesis also proposed a Space-Efficient Fair Sampling (SEFS) algorithm based on MR-BSdlCBF. SEFS has not only lower space complexity but also better sampling performance for short flows than existing fair sampling algorithm. It is feasible for network equipments to integrate SEFS as an IP core due to its high space efficiency.Lastly, this thesis implemented a front end processing system for real-time traffic classification on high-speed backbone networks. By decomposing the system into front end and back end, this thesis proposed a new architecture for real-time backbone traffic classification system. The benefit of this system architecture is that it eliminates the coupling between front end and back end, thus a more efficient and flexible system implementation can be achieved. Based on such architecture, the hardware implementation of the front end system for real-time backbone traffic classification is presented. Meanwhile, the implementation technique of SEFS algorithm using FPGA is discussed in detail. The front end processing system has been applied in"N ew Generation Internet Content Inspecting System"successfully.