基于Counting Bloom Filter的流抽样算法研究

翟金凤,, ,,

(1.东南大学 仪器科学与工程学院,南京 210096; 2.南京市计量监督检测院,南京 210049)

0 概述

网络流量测量作为一种用来掌握网络运行状况和行为特征的基本方法,已被广泛应用于安全检测、运营管理和流量工程等领域。新一代互联网的规模更大、速率更快,对系统计算和存储资源提出了更高的要求[1],且增加了传统的对流经链路所有数据包进行捕获和测量的难度。因此,需要在流量测量中引进一些必要的测量策略,用来对数据量进行缩减并保留流量数据的特征信息。抽样技术作为一种可扩展的数据缩减技术[2],已被众多大规模网络引进到实际的网络流量测量中,其能够有效保留原始流量行为的细节,提高系统的处理效率和资源利用率。因此,抽样测量已成为网络流量测量领域的重要研究方向之一。

但是,当前网络的高速发展使得网络的异构性和复杂性在不断加强,而系统处理分析能力的局限性和存储资源的缺乏,导致基本的抽样方法已难以满足实际测量的需求。为解决该问题,同时保证测量具备一定的高效性和准确性,以及系统资源具有一定的可控性,有研究者考虑在测量中引入一些其他的关键技术。目前,应用较广泛的技术主要有哈希算法、超时策略和概要数据结构[3],并由此衍生出如流抽样、抽样与哈希结合的测量以及基于Bloom Filter的抽样测量等[4]。其中,Bloom Filter凭借其简便易实现、资源利用率高以及处理速度快等优点,吸引了众多研究者的关注,如何将其与抽样技术进行高效地结合,成为近年来网络流量测量领域的热点论题[5]。……