Identifying elephant flows in internet backbone traffic with bloom filters and LRU

Traffic measurements provide critical input for network security, traffic engineering and accounting. Restrained capabilities of computing and storage have motivated recent researches on partial flow maintenance like identifying elephant flows. Considering high false negative probability of traditional algorithms, a novel scheme called BF–LRU (Bloom filters and least recent used) is presented. Our BF–LRU scheme adopts LRU replacement to evict mice flows and Bloom filters representation to conserve heavy hitters. Based on Pareto and hypergeometric distribution, expressions of upper-bound error probability are analyzed in detail. Experiments are conducted based on real Internet traffic data. Simulation results indicate that BF–LRU can not only achieve lower error probability, but also scale up to OC-768 backbone trace without losing any space efficiency.