一种基于FEFS与CBF的网络大流识别算法

刘晓陆，刘 渊，王春龙

(江南大学数字媒体学院，江苏无锡214122)

1 概述

在高速网络链路中，快速、准确地测量网络流量是网络安全、带宽控制及计费的重要基础，网络大流识别作为流量测量问题的一个分支，应用十分广泛。通过关注大流的详细信息，能使人们迅速定位导致事故发生的对象，从而有效地应对网络攻击、合理调配网络资源。

但在当今时代，随着计算机网络向高速化、大规模化、复杂化方向发展［1］，高速网络链路中数据规模巨大、报文到达速率极高，导致完整地存储每个数据包的信息难度很大。基于实际硬件水平和优化成本的考量，面向数据包级的传统全数据采集的网络流量测量手段已不再适用［2］。

网络流的分布呈现出显著的重尾分布特征，例如在一个监控周期里，大流的数量只占总流数的0．02%，但是却包涵了传输流量的近60%［3］。这种现象通常被称为“大象和老鼠效应”。因此，文献［4］首先引入“抓大放小”的策略，在周期采样和多级hash表的基础上分别提出了SH(Sample and Hold)算法和MF(Multistage Filter)算法，SH算法实现简单，但是涉及到抽样，误差较高;MF算法对大流识别的准确性较高，但是可能将小流误报为大流。

LRU(Least Recently Used)最早是一种内存管理算法，文献［5］将它引入到网络大流的检测中。此后，衍生出多种基于LRU的升级算法，文献［6］提出了LLR算法，将LRU淘汰机制和LEAST淘汰机制相结合，将被LRU淘汰的但满足一定阈值的流重新放入LEAST中进行二次筛选，弥补了两者的不足;文献［7］提出一种新的基于LRU的大流检测算……