Research On Key Technologies Of Traffic Measurement In High Speed Backbone Network

Network traffic measurement is the important mean of learning and understanding the Internet operation behavior, collecting and analyzing the performance of network protocols, re-planning and optimizing the network structure and improving the quality of network service. The data transferred on the backbone network is high speed and large amount. Therefore, to maintain portion status of the stream is always used for measuring the traffic on the high speed backbone, which contains three steps: data sampling, storing and querying information, timeout flow management. At present, there exists threes mainly aspects: 1) The poor fairness of the existing sampling algorithm. The existing methods pay more attention to elephant flows which leads to poor accuracy of mice flows. 2) The inaccuracy of query methods. The existing query methods conflict a lot when storing information and misjudge a lot when querying information.3)The lack of combining protecting elephant flows with deleting the timeout flow entry timely makes the poor accuracy and real-time of the existing timeout flow management.For the problem above, the paper relies on major project of the National High-Tech Research and Development Program of China(863 Program)——―Common Security and Control Framework in Tri-Network Convergence‖ and researches on the key technologies of the traffic measurement towards the high speed backbone.Firstly, for the poor fairness of existing sampling algorithms, an algorithm called Adaptive Fair Sampling based on Reducing Flow Numbers is proposed. Then, consider storing, querying and managing information,the query algorithm called Two-Dimensional Space Address and Sketch query and the timeout flow management based on the distinguishable LRU are proposed.1、An algorithm called Adaptive Fair Sampling based on Reducing Flow Numbers is proposed. Based on the principle of lowing the space complexity and guaranteeing the traffic fair sampling, the algorithm samples the new packet with either reducing flow numbers or non-linear sampling to create and maintain the sample traffic set. Both theoretical analysis and experiment show that compared with ANLS, AFS-RFN can deal with the traffic measurement on a 42.7Gbps link, can be applied to the higher speed link when changing Pf and improves the fairness.2、The query algorithm called Two-Dimensional Space Address and Sketch query is proposed. Based on the principle of increasing the real-time of querying and depending on the relationship between the sum and the product of two numbers, the algorithm extends the information querying from the line space to the surface space. TDSAS disperses the computing complexity by using the two-dimensional space address together with using the two-dimensional data structure to store information. Both theoretical analysis and experiment show that compared with CMS, TDSAS reduces the computing complexity from O(d) to O( d) to, and improves the real-time by 24.4%.3、The timeout flow management based on the distinguishable LRU is proposed. Based on the principle of reducing the missing rate and guaranteeing the timeout flows to be deleted timely, the paper designed a distinguishable LRU which is consisted of a elephant protecting end(the hot end) and a timeout processing end(the cold end). Depending on l the ratio of the two ends and the threshold T which distinguishes the new packet belongs to the hot end or the cold end, a relation formula between n, l and the T is determined by n. Both theoretical analysis and experiment show that compared with traditional LRU, setting the T and l with the formula, the algorithm reduces the missing of elephant flow by an order of magnitude and can meet the need of measuring the traffic timely transferred on a 40.9Gbps link.