Research On Sampling Algorithm For Traffic Measurement Based On Fairness Mechanism

With the rapid development of network quantity and the wide emergence of Internet-based new applications, it becomes increasingly difficult to control and govern the system network, while the global network becomes more and more complicated. To deal with the complex network, it is necessary to put forward effective measurement methods, which is an important basis for steady, reliable, effective operation of nowadays network and has even more important significance for developing the Next Generation Network in a scientific way.This thesis summarizes the development of traffic measurement, and 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 analyses the system framework of traffic measurement on high-speed backbone networks and studies the design and implementation of front end processing algorithms for traffic measurement. Its main work and contributions are outlined as follows:Firstly, aiming at the shortcomings of SGS (Sketch Guided Sampling), which in practice, is difficult to obtain the exact sizes of all flows on high-speed backbone networks for traffic measurement, a novel sketch called Adaptive Fair Packet Sampling (AFPS) is presented. The proposed sketch estimates the real-time flow-size according to the sampled packets, which reduces the difficulty of implementation, and adjusts the sampling probability according to the variety of the network flows in order to achieve flow wide fairness.Secondly, to avoid the memory resource waste in statistics counters, a new architecture called Counter Segment (CS) based on segment mode is proposed. The CS architecture can effectively solve the problem of resource waste caused by assigning equal counter memory for unequal flows. It divides the SRAM into several segments, and assigns the counters based on the size of flow. Two parallel hash functions are set up to map between contiguous layers. Compared with the counters assigned in uniform length, CS can economize the SRAM memory with the same accuracy.Lastly, the implement project of AFPS based on FPGA (Field Programmable Gate Array) is presented. It is discussed in detail that the implementation technique of three modules in framework of AFPS algorithm, and the resource consumption is analyzed. The test method and environment is introduced, and the results show that the design of implementation is feasible.