Algorithm For Detecting Elephant Flows Through Two-stage Sketch

Elephant flow detection is great significant for load balancing,traffic engineering and intrusion detection,etc.Network traffic exhibits long-tailed distribution,that is,most flows contain a small number of packets,while a small fraction of flows contain a large number of packets.Detecting elephant flows from network traffic can better understand network behavior,which is helpful for network management.In order to match the data transmission efficiency in the high-speed network,it is necessary to perform elephant flow detection in the SRAM with fast read and write speed.Sketch is a probabilistic data structure that can use small memory to store and query the frequency of any item in a given multinomial set,and can be well used for elephant flow detection.But existing sketches usually use many counters of the same size to keep track of the number of packets in the flow,so these counters must be large enough to accommodate the largest flow.Since most of the flows in the network are non-elephant flows,and only a few are elephant flows,many counters record small values,which will cause some space waste.In this thesis,we propose a algorithm for detecting elephant flows through Two-Stage Sketch(TSS).The structure of TSS consists of two parts: one is the light part and the other is the heavy part.The core idea of the TSS algorithm is to dynamically store elephant flows and non-elephant flows,so that non-elephant flows are allocated in the light part,while elephant flows are stored together by the light part and the heavy part,thereby optimizing memory efficiency.In order to evaluate the performance of the TSS algorithm in elephant flow detection,we first conduct a theoretical analysis on the error range of the algorithm to estimate the size of elephant flows,and then conduct extensive experiments using three real traces collected from different network environments,and compare with the three other algorithms.The theoretical analysis and experimental results show that TSS has better performance in elephant flow detection.