Research On High Speed Flow Measurement Techniques

Flow-based passive measurement is one of the most important measurement tech-niques in high-speed networks.High speed flow measurement should meet three require-ments:high speed,high accuracy and low cost.The existing flow measurement techniques used in industry leverage flow sampling,and only process the sampled packets,which could meet the needs of high speed and low cost.However,because this method uses a single fixed sample rate,it will produce a large measurement error,especially for mice flows.Given this reason,another different approach named adaptive non-linear sampling method has been proposed by the academia,which adopts different sampling rates on the fly for flows with different sizes adaptively.The up-to-date work,DISCO,which used adaptive non-linear sampling method can support higher precision measurement for both mice and elephant flows and can achieve wire-speed flow measurement up to 40Gbps.But in practical applications,it is difficult for DISCO to further increase the measurement throughput of network flows,such as to 100Gbps and even more.This is because every packet arrival will trigger memory accesses to off-chip SRAM,where flow counters are stored.Analytically,the DISCO implementation mechanism determines the bottleneck of its throughput lies in the access speed of off-chip memory.In order to break the technical obstacles to the DISCO implementation,this dissertation deeply studies the implementa-tion architecture and processing mechanism of adaptive non-linear sampling method,and makes the following contributions:1.A cache accelerated adaptive non-linear sampling architectrue named CASE is proposed.Faced with the problem of per-packet processing mode,a dedicated high speed on-chip cache is employed to decouple the packet counting process from the counter update process.Thanks to the heavy-tailed distribution of real network traffic,most of the packets can be counted in on-chip cache with low costs and no compression.In this dissertation,it has been proved in theory that CASE with cache assistance can achieve higher mea-surement accuracy than the existing algorithms.Experimental results show that the mean relative error of CASE is 10~4smaller than the best existing algorithm(DISCO).Mean-while,CASE can achieve up to 301.5Gbps throughput with 1.125MB on-chip memory under the assumption that the average packet length is 250 bytes.2.An adaptive non-linear sampling architecture with mice flow filter,named CASE+,is proposed.The data-mining results on real network traffic show that the interactions between on-chip and off-chip operations caused mainly by mice flows with low traffic footprint constitute the bottleneck of measurement throughput.In order to reduce the number of interactions between on-chip updating and off-chip memory accessing,CASE+architecture,in which a mice flow separator is applied at the front end of the on-chip cache,is proposed.CASE+can filter out mice flow packets which will be counted seperately by large capacity DRAM in burst-write mode.Theoretical analysis and experimental reults show that CASE+works effectively in filtering out mice flow packets,and can achieve a throughput of 390.7Gbps while maintaining the same high measurement accuracy as CASE.3.A refined counter update algorithm is designed to reduce the computational load of adaptive non-linear sampling method.Although CASE and CASE+architecture can greatly reduce the number of counter updates,it is necessary to lower the computational complexity of the counter update algorithm to further improve measurement through-put.This dissertation proposes a refined update algorithm,which takes a space-for-time strategy.The refined algorithm converts high-precision floating-point operations into table-lookup searchings,and further reduces the computational complexity by controlling the calculation precision of intermediate variables and amending corresponding process-ing procedures.Experimental results based on an FPGA prototype show that the refined algorithm can greatly reduce the calculation amount while guaranteeing measurement precision.