Invertible Bloom Filter And Its Application Of Identifying Elephant Flows

Identifying elephant flows is very useful for traffic engineering schemes, network operation and management. Many measurement studies have revealed that flow statistics exhibit strong heavy-tailed 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. Elephant flows contribute a large potion of the total traffic volume despite being relatively few in the number of flows. Knowing the information of elephant flows can master the traffic behavior accordingly. In this paper, we study and improve the invertible Bloom Filter for indentifying elephant flows.First we introduce the application condition of Bloom Filter and its variations, then put the accent on the invertible Bloom Filter. The invertible Bloom Filter is also one of these variations. It has been proposed as a method of network measurement for a few years. The invertible Bloom Filter consists of 8 hash functions which select some bits from original strings as function values. We obtain the identifier and length of elephant flows according the characteristics of hash functons and heavy-tailed feature of flow distribution. So the invertible Bloom Filter does not need to keep a flow identifier for every hash table body. In addition, it assigns every hash function an independent space, which removes the internal confliction among hashing. At last, we just apply recover algorithm to some strings whose numbers are bigger than the threshold. That can reduce calculated amount greatly.We do experiment with the traces collected from CERNET. The experiment shows that the identifiers and length of elephant flows can be obtained accurately through the algorithm.Though the research and development of the invertible Bloom Filter have yielded some results, the invertible Bloom Filter still is a new method which needs more wok to improve. The effort in this paper makes it a more effective method of elephant flows.