Algorithm Based On Multi Layer Hashed CBF For Elephant Flows Identification

Identifying elephant flows is very important in developing effective and efficient traffic engineering schemes. As many measurement-based studies have revealed, flow statistics exhibit strong heavy-tail behaviors in various networks. This characteristic is often referred to as the elephant and mice phenomenon; i.e., most flows (mice flows) only have a small number of packets, while a very few flows (elephant flows) have a large number of packets. A noticeable attribute of elephant flows is that they contribute a large portion of the total traffic volume despite being relatively few in the number of flows.In addition, obtaining the statistics of these flows is also very useful for network operation and management,and the impact of elephant flows on network performance is also significant. On the other hand,with the rapid growth of link speed in recent years, it makes identifying elephant flows become a research hot-spot in network measurement. However, it also makes identifying elephant flows become much more difficult.It is a challenge for backbone router to accept the resource overhead when maintaining the information of flow ID in the memory.In this paper,we improve a counting method of multilayer hashed Counting Bloom Filter(ML-HCBF) in order to reduce the space overhead and propose a novel algorithm to identify elephant flows by improced ML-HCBF.We count packets with multilayer structure, in which the first layer can filter out most mice flows, and elephant folws can be beared by the high level. To control the consumption of resources in measurement,we ues some hash functions carrying the part of information of flow ID. We obtain the information of elephant flow using the overlapping of hash bit strings and heavy-tailed feature of flow distribution.In the process of merging, to improve the accuracy of algorithm we use a filtering approach that can filter out some elephant flows which is mistaken identified. We do some experiments under Linux using real network traffic traces.The experiment results show that the proposed algorithm can identified elephant flows accurately and its false negative rate (FNR) is zero.On the other hand,the algorithm also requires less memory usage.Furthermore,we can set different layers according to different applications,so this algorithm has a good flexibility and scalability.