Algorithms For Detecting Elephant Flows Based On Packet Sampling

Detecting elephant flows is important for network security,traffic accounting and bandwidth allocation.Flow-based studies show that flows in networks have a strong heavy-tailed distribution,that is,most flows contain only a small number of packets,and a small fraction of the flows carry a larger number of packets.A noticeable attribute of elephant flows is that they contribute a large portion of the total traffic volume despi te being relatively few in the number of flows.Therefore,detection of elephant flows can not only make contribution to a better understanding of network behavior but also be of immense significance for the operation and management in the networks.In this paper,we propose four algorithms based on packet sampling.The first algorithm can detect elephant flows and accurately estimate their lengths by combining Sample and Hold with Counting Bloom Filter.The second algorithm amalgamates Sample and Hold with Counter Tree to reduce the on-line processing time while ensuring that the length of the elephant flows can be precisely measured.To improve the scalability of the algorithms,that packet sampling techniques are applied to the first two algorithms forms two new algorithms.These two new algorithms first sample the arriving packets according to a certain probability,reducing the number of memory accesses and speeding up on-line processing.We use the real network trace collected from different regions in experiments,the experimental results show that the proposed algorithms can accurately detect the elephant flows and occupy small storage space,and the time cost of handling each packet is very low.Thus,the four algorithms are suitable for high-speed networks.