A Method of Extracting Heavy-Hitter Flows Efficiently

Along with the continuous improvement of network bandwidth, identifying heavy-hitter flows on-line is more significant for some network application, such as congestion controlling, anomaly detecting and so on. A novel algorithm FEFS (flow extracting by frequency & size) is proposed to extract heavy-hitter flows online. Through online identification and elimination of small flows, the information of heavy-hitter flows is stored and updated in the limited high-speed memory, so heavy-hitter flows can be extracted rapidly and accurately. FEFS locates the flows with low update frequency using LRU (least recently used) mechanism, and furthermore it labels the relatively small flows in storage space with a flow size factor s and an adaptive modulating factor M. Taking into account both the recent update frequency and the cumulative number of packets, FEFS can identify heavy-hitter flows precisely online. Both LRU policy and size factors have taken advantage of the heavy-tail distribution characteristics of flow size, and therefore heavy-hitter flows can be handled with very low computing and storage costs. The simulation results show that in the limited storage conditions, average relative error rate of FEFS is significantly lower than that of the classic multi-stage filter algorithm, while the average packet processing time is also shorter than that of the multi-stage filter algorithm.