|
|
|
| A Mechanism of Identifying Heavy Hitters Based on Multi-dimensional Counting Bloom Filter |
| Zhang Zhen; Wang Bin-qiang; Chen Shu-qiao; Zhu Ke |
| National Digital Switching System Engineering & Technological R & D Center, Zhengzhou 450002, China |
|
|
|
|
Abstract In high-speed network, identifying heavy hitters precisely in time serves as great significance for both network security and network management. In order to circumvent the deficiency of the limitted computing and storage abilities in traditional traffic measurement, a novel mechanism called identifying heavy hitters based on Multi-Dimensional Counting Bloom Filter(MDCBF) is proposed. Extending the standard structure of Counting Bloom Filter(CBF) to multi-dimensional one, the mechanism can not only represent, query and count traffic flows, but also sustain real time multi-granularity measurement. Based on Apriori principle, it can realize the identification of heavy hitters through implementing renormalization of MDCBF. Experiments are conducted based on the data either randomly produced by computer or sampled from the real network trace. Results demonstrate that the proposed mechanism can achieve finer space saving without sacrificing accuracy.
|
|
Received: 15 December 2008
|
|
|
|
Corresponding Authors:
Zhang Zhen
|
|
|
|
|
|
|
2010, Vol. 32 
