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 multistage filter algorithm, while the average packet processing time is also shorter than that of the multistage filter algorithm.%随着网络带宽的不断提高,在线识别大流对于拥塞控制、异常检测等网络应用具有重要意义.提出了一种提取大流的算法FEFS(flow extracting with frequency&size),能够通过在线识别和淘汰小流,把大流信息保存在有限的高速存储空间中,从而快速提取大流.该算法利用LRU (least recently used)定位更新频率低的流,并进一步用流尺寸因子s和自适应调节因子M标记其中相对较小的流,最后用新到达的流将其替换.FEFS把LRU策略和尺寸因子s相结合,同时考虑了流的近期更新频率和累积报文数量,因此能够准确在线识别大流.LRU策略和尺寸因子都利用了流大小的重尾分布特征,因此FEFS能以很低的存储代价保存和更新大流信息.模拟实验表明,在限定存储条件下,FEFS的平均相对误差率明显低于经典的multi-stage filter算法,而平均报文处理时间也短于multi-stage filter算法.
展开▼
