Algorithms For Detecting Elephant Flows In Sliding Windows

An elephant flow is a flow whose length is larger than a predefined threshold.Network traffic has a strong heavy-tailed distribution,that is,most of the flows contain only a small number of packets,while a small number of flows contain most of the packets,and a small part of the flows are elephant flows from the network.The detection of elephant flows is important for network security,traffic accounting,and network managment.In this paper,we propose two algorithms for detecting elephant flows in sliding windows.The first algorithm ACBF(Aging Counting Bloom Filter)consists of online part and offline part.The online part of the ACBF algorithm mainly implements two operations,including reducing the count of expired packets and counting the newest packets.The offline part estimates the length of flow within sliding windows and outputs the elephant flows.Because the ACBF algorithm cannot record the arrival order of all packets in slding window and the first expired packet cannot be accurately deleted.So the second algorithm S-ACBF(Segment Aging Bloom Filter)is an improvement on ACBF and segments the sliding windows.The segmented sliding windows ensure that the packets between the sub-windows are relatively ordered.The S-ACBF algorithm also consists of online part and offline part.The online part of the S-ACBF algorithm mainly implements two operations,including reducing the count of expired packets in the tail counter and counting the newly arrival packets in the head counter.The offline part estimates the length of flow within sliding windows and outputs elephant flows.In this paper,we use real network traces collected from different regions in experiments.The experimental results show that in a short period of time(the number of read packets is less than the size of sliding window)the false positive rate and false negative rate of ACBF algorithm are relatively low.Furthermore,the false positive rate and false negative rate of S-ACBF algorithm not only are very low,but also do not increase with time.Therefore,the S-ACBF algorithm can continuously and accurately detect elephant flows in sliding windows.