Research On Persistent Flow Detection And Compression Algorithm Based On Sketch

Sketch is a kind of algorithm that uses synopsis data structure to record massive data information,which has the advantages of low memory overhead and high precision.Sketch-based measurement methods have become the prevalent research direction in the field of network traffic measurement.Persistent flow detection is a network traffic measurement task that focuses on abnormal traffic,which persists in multiple time windows and is likely to be some potential network attacks.Sketch compression is a method for processing data information,which compresses the traffic information obtained by Sketch in measurement tasks,and reduces the communication overhead of uploading information in distributed measurement system.However,existing researches have the following problems in persistent flow detection and Sketch compression: existing Sketch algorithms are not accurate in measuring persistent flow in small memory scenarios,and existing Sketch compression algorithms can not ensure compression accuracy and fast compression at the same time.Aiming at the above two problems,this thesis studies the persistent flow detection and compression algorithm based on Sketch.The main contributions are as follows:(1)Based on the analysis of existing researches and the verification experiments,this thesis finds that existing algorithm holds an "unfair" update strategy,which reduces the detection accuracy of persistent flows.Therefore,this thesis proposes a new persistent flow detection algorithm based on Sketch named Fair-Replacing,which designs a new data structure and update strategy.Fair-replacing uses bloom filter and flag bits to filter and control network data packets,and ensures every flow that arrives in current time window has a "fair" opportunity to record its flow key,so as to improve the detection accuracy.This thesis also theoretically analyzes the time and space complexity and the error bound of algorithm,and performs simulation experiments in multiple measurement scenarios.The experimental results show that,compared with the existing algorithms,the detection accuracy of Fair-Replacing is improved by21.46% on average.(2)Based on the analysis of the problems of the existing Sketch compression algorithms,this thesis proposes a Sketch compression algorithm based on the prior knowledge,named Fast-Mapping.Fast-Mapping maps the compressed data by the distribution of the bucket values of historical Sketches,and aggregates more similar bucket values to achieve the compression with low error.This thesis also theoretically analyzes the time complexity and compression error of the algorithm in compression,and performs simulation experiments in multiple compression scenarios.The experimental results show that,compared with other algorithms,Fast-Mapping reduces the compression error by 7.34 times and the compression time by 3.45 times on average.In conclusion,Fair-Replacing and Fast-Mapping proposed in this thesis have certain reference value for persistent flow detection and compression work based on Sketch.