Algorithm For Identifying Large Flows Through Reversible Hash Counting

With the popularity of smart phones and the continuous development of the Internet,the traffic in the network is exploding,which brings many problems to network management.The research shows that the network traffic is heavy-tailed,that is,a small number of flows contain most packets,while most flows contain only a few packets.Large flow refers to the flow with a number of packets exceeding the threshold,which contains a large number of packets and has a greater impact on the network.Therefore,counting large flow information is of great significance to network operation,load balancing and service quality.In high-speed network,due to the limited computer hardware resources,it is difficult to identify large flows with both memory overhead and accuracy,which brings new challenges to identify large flows.Based on analyzing the advantages and disadvantages of existing algorithms for Identifying large Flows,this thesis proposes an Algorithm for Identifying Large Flows through Reversible Hash Counting(RHC).RHC uses three sets of one-dimensional arrays,each associated with a hash function.RHC does not store any flow identification(flow ID)directly,but instead uses the first set of hash functions to take successive bits of flow ID as hash values,each of which corresponds to the address of a counter,thus effectively reducing space consumption.Although RHC does not store flow ID directly,it is possible to reconstruct flow ID based on cyclic overlap of hash values.The second set of hash functions and the counter in the array can be used to filter out the fictitious flow ID substring during the reconstruction process,reducing the computation.Finally,a third set of hash functions and the counter in the array are used to filter the fictitious flow ID and estimate the length of the flow.RHC can be applied to high-speed links because it avoids storing flow ID and finding flow ID.RHC reaches the optimal processing speed,processing each packet only needs to access the memory twice.In order to evaluate the performance of RHC,this thesis firstly analyzes the algorithm theoretically.Then the Trace collected in three real networks is used for experiments and compared with other algorithms.The experimental results show that RHC can accurately identify large flows with less space and has a high throughput.