Heavy hitter identification based on adaptive sampling with mapreduce

摘要

As network bandwidth increases continually, identifying heavy hitters becomes more significant for some network applications, such as network management, network accounting and so on. MapReduce is a powerful tool for parallel and distributed processing of large-scale data. Unfortunately, the performance of MapReduce strongly depends on the even data distribution, while network traffic distribution has the heavy-tailed feature. The load imbalance, which is caused by the heavy-tailed feature, delays the finishing time of some tasks and significantly influences performance. In addition, existing methods to identify heavy hitters lack of scalability. In this paper, we propose the heavy hitter identification method based on adaptive sampling with MapReduce and it solves the problems of load imbalance. It introduces an adaptive sampling, which adjusts the sampling rate in the light of the updating counter value, to estimate the original distribution of flow size accurately by sampling a small fraction of network traffic. On the basis of the estimated distribution, we present the data partitioning strategy. Identifying heavy hitters is realized by the above data partitioning strategy during the reduce stage. It considers the impact of the network traffic change over time on the load balancing and the execution time. The experiments are conducted using real network traffic and the testing results illustrate that the proposed method can achieve better performance than the other two in terms of estimation accuracy, load balancing, scalability, data updating and the number of reducers.