Research On Network Traffic Measurement Algorithm Based On Sketch

With the increase in network flexibility,scalability and programmability,and the continuous increase in network size and link bandwidth,network behavior has become more and more complex and diversified,all of which have raised higher requirements for network management and security protection.As a hot research topic in the network field,network traffic measurement is a prerequisite for intelligent and reliable network management,and it also plays an important role in network performance diagnosis,anomaly detection,service quality assurance and security protection.As the needs of fine traffic management and intelligent scheduling,how to use limited memory and computing resources to meet the requirements of strict accuracy,packet processing rate and multi-tasks measurement in huge network traffic scenarios is a great challenge.It is also the direction of efforts of researchers around the world.This article first introduces the concept of sequence value into data packets.Sequence value is the assigned value according to the order of occurrence of data packets,and sequence value interval,which is the difference value of two sequence values,can be used to measure the occurrence density of data stream.Then through statistical research on data streams we find a significant difference in sequence value interval between elephant flows and mouse flows,thus generalizes a new method on this basis.Seq Sketch,a network traffic measurement algorithm based on Sketch structure,is proposed.It adopts the idea of separating elephant flows and mouse flows.Based on the general application of data flow frequency to distinguish flows,the feature of sequence value interval is added to select the elephant flows.The entire algorithm structure is composed of two parts: a hash table and a Sketch structure.The former is mainly used to record the elephant flow s,the latter is responsible for recording the mouse flows,and the size of the Sketch can be selected according to the accuracy requirements of the measurement.When the data packet arrives,it is first inserted into the hash table.If it is unsuccessful,the replacement condition is determined to determine whether the data stream corresponding to the position of the hash table should be eliminated;then the Sketch operation is performed.The principle of the replacement condition is to use the sequence value interval and the hash table frequency value to determine whet her the data stored in the hash table is an elephant flow.If it is not,it will be inserted into the Sketch,which can reduce unnecessary operations.The separation between elephant flows and mouse flows not only saves the memory,and improve the accuracy of the results.Through the analysis of network traffic,the feasibility of sequence value in participating in traffic measurement is verified.Then,based on the Seq Sketch algorithm,a comparative experiment is designed on the Windows platform,and the same type of algorithm under the premise of memory consistency,the results show that the Seq Sketch algorithm leads the three measurement tasks of elephant flow detection,entropy estimation and flow distribution estimation.It shows good performance in terms of memory consumption and accuracy.Finally,the application prospect of the algorithm and its implementation on the hardware system are analyzed.