Research On UA-Sketch And Sliding Window Algorithm For Heavy Flow Detection

Heavy flow detection is an important task for network measurement.In large-scale network,accurate detection of heavy flows is challenging due to limited memory and low link capacity.Sketch is a probability-based data structure that can accurately store flow information using smaller memory resources.Compared with traditional network measurement algorithms,Sketchbased algorithm(Sketch algorithm for short)achieves accurate per-packet measurement under limited resource overhead.It is mainly divided into two parts: insertion and query.In high-speed network,the existing Sketch algorithm has the problem of low detection accuracy and processing speed when detecting heavy flows with limited memory.Thus,we propose UA-Sketch(Uninterrupted Arrival Sketch)algorithm and Moving-Sketch algorithm that supports sliding window for detecting heavy flows.The contributions of our work are as follows:(1)The existing Sketch algorithms use the flow size to decide the flow replacement strategy.In the network that the number of small flows is more than that of heavy flows,heavy flows are frequently replaced incorrectly when the recorded flow size is still very small,and the flow size of heavy flows is underestimated,resulting in low accuracy of heavy flow detection.Through a series of simulation experiments,we found that the Uninterrupted Arrival packet count(UA count for short)provides a favorable basis for Sketch algorithm to detect heavy flows.So,we propose UA-Sketch,an algorithm for detecting heavy flows based on UA count.The algorithm improves the accuracy of heavy flow detection while ensuring the speed of packet detection.UA-Sketch is tested in trajectory driven simulation and OVS(Open v Switch).The experimental results show that UA-Sketch has higher accuracy than MV-Sketch and Elastic Sketch in low memory,and improves 3.5 times on average in F1 Score.(2)When the existing Sketch algorithms refer to the sliding window model to detect the recent heavy flows,there is a problem that the expired data cannot be deleted in time,which leads to low accuracy of heavy flow detection.So,we propose Moving-Sketch,an algorithm for detecting heavy flows in sliding window.Moving-Sketch uses flow keys and periods as hash keys and decides flows replacement operation with probability,which can effectively improve the accuracy of detecting heavy flows in sliding window.We not only analyzes the space complexity,time complexity and heavy flow detection error of MovingSketch,but also shows that ARE(Average Relative Error)of Moving-Sketch is reduced by 93.3% on average compared with Sliding Sketch based on trackdriven simulation.The research works of our work are valuable for algorithm research and practical application in the field of network measurement.