Sketch Data Structure Design And Optimization For Network Measurement

Network measurement provides the necessary information for diverse network management.With the advent of the digital and intelligent era,the explosive growth of network applications and user scale has brought great challenges to the operation and management of network infrastructure.Network measurement is the basic method to master the dynamic change of network infrastructure,and the efficient and available network measurement method often needs to acknowledge the statistics of a large number of equipment and network flow in the network,including the operation status of network equipment,the statistics of a single stream,and the aggregate information of multiple network streams.Typical statistics include: the throughput of the switch,the degree of congestion of the switch queue,the transmission delay of packet,the number of stream elements(stream cardinality),the size of the data stream(the number of packets),the proportion of data in the total network stream,and so on.These statistics depict the performance of the network system and provide the necessary decision-making basis for network operation and network security business.Sketch is the general term for an efficient compressed data structure that uses hashing strategies to store as much raw data statistics as possible at a much less spatial cost than the original data.In the network traffic of the Sketch,only constant time overhead is required.Because of Sketch’s superior performance,Sketch-based network measurement methods and systems have been widely studied and paid attention to by academia and industry.Based on the problem of Sketch based network measurement,the main work of the paper includes:(1)Surveying the existing Sketch based network measurement systematically.With the development of Sketch,Sketch-based network measurement technology has become the mainstream method in the field of passive network measurement.This paper focuses on Sketch’s data processing process,and systematically summarizes the existing work from the aspects of hash policy,counter,overall structure,combination,compression technology and information extraction.(2)Proposing Counting Cuckoo Filter based methods for multiset synchronization.For the data synchronization problem among measuring nodes,this paper designs the differential synchronization strategy between the nodes through the improved Cuckoo Filter structure(Counting Cuckoo Filter),and through the query or decoding of the exchanged data sketch,the differential synchronization strategy is realized between the nodes,which greatly reduces the transmission bandwidth overhead in the synchronization process.(3)Proposing a differentiated Sketch strategy for Double-Stack networks.In the existing dual-stack network where IPv4/IPv6 coexists,there are huge differences in the data characteristics of different types of network packets.Indistinguishable summary of the raw network data will cause a large error in the measurement results,DSketch is designed to solve the problem of interference between heterogeneous traffic and improve the measurement accuracy.(4)Proposing Stable Cuckoo Filter for data streams.The design of Cuckoo Filter,due to the lack of data update strategy,resulting in a onetime data structure,the data structure needs to be reset regularly zeroing,this mode is very unfriendly to the data stream.This paper designs the update strategy of Cuckoo Filter,including the insertion of the new data and the deletion of the stale data.The stable Cuckoo Filter has stable performance and a relatively high accuracy.