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

翟金凤,, ,,

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

0 概述

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

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

文献[6]较早将哈希函数引进抽样测量中。文献[7]使用Time-Out Bloom Filter来缓解对长流的抽样偏差,以提高对短流的抽样概率。该方法与随机抽样相比,能够在相同的抽样率下记录并识别出更多的短流,但是因为未考虑具体的流信息,所以其存在局限性。文献[8]提出一种基于Dynamic Count Filter的公平抽样算法,可以高效地获取全面的流信息,但Dynamic Count Filter存在误判率,导致算法会出现一定的测量误差。文献[9]基于改进型Bloom Filter数据结构,提出一种简单实用的流抽样算法,其通过调整抽样频率来实现对网络流的等概率抽样。其中,改进型Bloom Filter设置3层位向量,通过对2层位向量的判定结果取交集来实现对新流的识别,但该算法在3层位向量中交替使用时,会将某些已识别的流再次判断为新流,导致某些网络流的重复抽样。

针对上述方法存在的不足,本文将基于报文的流抽样技术和Bloom Filter相结合,提出一种基于Counting Bloom Filter的流抽样算法,用以实现对网络流的等概率抽样,然后通过实验验证该算法的性能。

1 流量抽样测量技术

1.1 基于报文的流抽样

报文抽样不考虑报文之间的相关性,其相对平等地对组成网络流量的报文进行抽样。常用的报文抽样方法主要有3种:系统抽样,随机抽样,分层抽样。然而,组成网络流量的报文并非独立的,它们是为实现特定的行为应用而产生的,彼此间有着一定的相关性,流则是反映这种相关性的一种途径。基于报文的抽样忽略了报文之间的相关性,不能体现更高层面的信息,从而无法实现掌控和提升网络性能的目的[10]。为解决该问题,衍生出基于报文的流抽样测量,其先对报文实施抽样,再对具有相同特征的报文进行流归并操作。这样可以将属于特定流的分组综合起来进行分析,从而缩减需要处理的数据量。此外,将部分重要特征信息保留下来,具有一定程度的可扩展性,更适合于当前的高速网络环境。

基于报文流抽样的普遍实现策略是在测量设备中,为抽中的流维护一块存储空间,先按某种频率对报文实施随机抽取,再按报文的特征信息将其归并为不同的流,并以流的形式存储在开辟的缓存中,最终构成抽中的流集合。对于在链路上传输的每一条报文,都将其与抽中的流集合中的属性信息作比对,如果其与某条流的属性相匹配(如具有相同的源IP地址、目的IP地址、源端口、目的端口和协议类型),则该报文被抽中,更新与该报文具有相同属性的相关流信息;如果其与集合中任何流的属性都不匹配,则该报文被丢弃。对网络流进行测量和分析,有助于了解网络的流量行为细节,且能在很大程度上释放系统存储资源。

1.2 Bloom Filter技术

1.2.1 标准Bloom Filter

Bloom Filter是概要数据结构中最具代表性的结构之一,是由Howard Bloom于1970年提出的二进制向量数据结构[11],其在高速网络流量测量中发挥着巨大作用。Bloom Filter使用长为m的位向量V表示含有n个元素的集合S={s1,s2,…,sn}。初始化时Bloom Filter为空,位向量全部设为0,同时定义k个相互独立的具有分布均匀特性的哈希函数h1,h2,…,hk[12],且其值域均为[1,m]。计算每个元素si∈S的哈希值h1(si),h2(si),…,hk(si)。将位向量V中对应于哈希映射的k个位置设为1。标准Bloom Filter原理如图1所示。

图1 标准Bloom Filter原理

与其他数据结构相比,Bloom Filter可以充分利用有限的存储资源,有效提高数据查询和处理的速率,且可以表示全集。但是,由Bloom Filter原理可以看出,在哈希映射过程中其可能会将位向量中的某一位重复置1,这会导致在判断一个元素是否属于某个集合时,存在一定的概率将不属于这个集合的元素误判为属于这个集合,本文定义这样的误差概率为误判率[13]。下面对误判率的大小进行分析估计。

为简化分析模型,假设各哈希函数是完全随机的,且kn

则误判率为:

1.2.2 Counting Bloom Filter

标准Bloom Filter仅支持对元素的插入和查询操作,当对静态集合进行表示时,其能够呈现出较好的工作性能,但是当要表示的集合经常变动时,因为它不支持删除操作,所以会产生一定的误差。

由于Bloom Filter存在误判率,以及不能用来表示动态集合,因此诸多研究人员对Bloom Filter提出了新的改进。目前,Bloom Filter的经典改进结构主要有:Counting Bloom Filter,Compressed Bloom Filter,Spectral Bloom Filter和Dynamic Count Filter等。其中,文献[14]提出的Counting Bloom Filter是最具代表性的改进结构之一。

Counting Bloom Filter解决了标准Bloom Filter无法删除元素的问题。对于标准Bloom Filter,当要从集合中删除元素时,它不能简单地将位向量中的对应位置设为0,而Counting Bloom Filter则将标准Bloom Filter位向量的每一位扩展为一个小的Counter(计数器),并赋初值为0。Counting Bloom Filter将元素插入操作扩展为给对应的k个Counter值分别加1;元素查找操作扩展为检验对应的k个Counter值是否为非零;元素删除操作扩展为将对应的k个Counter值分别减1。Counting Bloom Filter原理如图2所示。

图2 Counting Bloom Filter原理

此外,有研究表明,若为Counting Bloom Filter中的每个计数器分配4 bit,则当计数器值达到16时,Filter会溢出,该概率为:

F≤m×1.37×10-15

(3)

其中,m为Counter向量的大小,即向量空间的大小。此时的溢出率已经微乎其微,可以满足大部分应用程序的需求。在实际应用中,使用Counting Bloom Filter时也可以从实际需求的角度为Counter分配合适的位数。

2 基于Counting Bloom Filter的流抽样算法

2.1 算法描述

如图3所示,基于Counting Bloom Filter的流抽样算法由Counting Bloom Filter模块、误差吸收模块和随机抽样模块组成。Counting Bloom Filter模块用于判定到来的数据分组所属网络流是否为新流;由于Counting Bloom Filter同样存在误判率,误差吸收模块就用来记录当前到达的流数量,同时根据抽样过程中产生的误判率调整抽样频率;随机抽样模块则以调整后的抽样频率对经Counting Bloom Filter认定的新流进行抽样,从而实现对网络流的等概率随机抽样,该模块可以有效反映网络流的真实分布情况,具有较高的测量精度。

图3 基于Counting Bloom Filter的流抽样算法结构

基于Counting Bloom Filter的流抽样算法设计流程如图4所示。

图4 基于Counting Bloom Filter的流抽样算法设计流程

算法具体实现步骤为:

步骤1对Counting Bloom Filter结构的参数、哈希函数个数和向量空间大小进行合理配置,为Counting Bloom Filter结构中的每个Counter分配4 bit。

步骤2当一个分组到达时,先解析其流标识,然后计算其流标识的k个哈希函数值,若Counting Bloom Filter结构中对应的k个Counter值均大于或等于1,则判定为没有新流到达;否则,判定为有新流到达。

步骤4如果判定为没有新流到达,则继续处理下一分组,重复步骤2并继续循环。

2.2 哈希函数个数和向量空间大小选择

在使用Counting Bloom Filter进行流抽样测量时,有一个较重要的问题,就是如何根据网络情况确定合适的哈希函数个数和向量空间大小,这对算法的测量效果有很大影响。使用较少的哈希函数时,会造成较大的误判率;使用较多的哈希函数时,则会引起计算复杂度的上升以及向量空间消耗的增大。而向量空间选择过大会浪费较多的存储资源,向量空间过小则会导致误判率的增加[10]。

图5 误判率随哈希函数个数的变化关系

2)k=8、16、32的3条误判率变化曲线较接近,即当哈希函数达到一定数量后,继续增加k值对误判率的影响极其微小。因此,要根据实际情况对误判率与计算复杂度[16]进行权衡,从而选取恰当的k、m值。

图6 误判率随的变化关系

3 实验结果与分析

3.1 实验数据

本次实验使用的流量数据来自互联网数据分析合作组织CAIDA公开提供的真实被动测量数据Traces。Trace 1为2011年2月17日在芝加哥采集得到的数据,Trace 2为2012年6月21日在圣约瑟采集得到的数据,数据详情如表1所示。实验平台为Visual Studio 2013和MATLAB R2014b。由于硬件性能限制,本文选取2组Traces数据的前104个数据分组进行仿真分析。

表1 Trace 1和Trace 2流量数据信息

3.2 算法性能分析

使用报文头中的源IP地址和目的IP地址作为网络流的流标识,为Counting Bloom Filter结构中的每个Counter分配4 bit,向量的长度即Counter向量的大小设为实际流总数的20倍,先后使用3个、10个哈希函数进行仿真比较。

图7、图8分别为使用Trace 1和Trace 2数据时,基于Counting Bloom Filter的流抽样算法使用3个、10个哈希函数的测量值与流量数据真实值的对比结果。

图7 Trace 1流数量测量结果比较

图8 Trace 2流数量测量结果比较

由图7、图8可以看出,本文网络流等概率抽样算法得到的流数量与真实值较接近,算法测量精度较高。误判率的存在会导致部分新流数据不被识别,从而使得Counting Bloom Filter模块识别出的新流数量小于实际流数量,引起测量误差。但是,本文算法中的随机抽样模块将会以实时调整抽样频率的形式吸收该误差,从而降低误判率对最终测量结果的影响。

由图7、图8还可以看出,算法中哈希函数个数设为10时的测量精度要高于哈希函数个数设为3的情况,这与第2.2节得出的Counting Bloom Filter的误判率在一定范围内会随哈希函数个数的增加而减小的结论相一致。由于哈希函数个数大于10时误判率变化放缓,且哈希函数达到一定数量后,反而会使计算复杂度和误判率增大,因此本文算法在实际应用中应尽量选择约10个哈希函数。

定义测量误差为e=|n′-n|/n,其中,n′为通过算法测量出的网络流数量值,n为网络流数量的真实值。选取每1 000个数据分组作为记录点。图9、图10分别为本文算法对Trace 1和Trace 2流量数据进行仿真时的测量误差。

图9 Trace 1测量误差

图10 Trace 2测量误差

由图9、图10可以看出,哈希函数个数设为10时,本文算法能够有效提高对网络新流的识别率,其测量误差明显低于哈希函数个数设为3时的情况,测量结果较准确。因此,哈希函数个数要尽可能地设为10左右。由图9、图10还可以看出,随着数据分组数量的增加,算法结果的测量误差都呈现先上升后趋于平稳的趋势。算法结果控制在一定的误差范围内,可以满足一定精度下的网络流等概率抽样,并有效获得网络流的真实分布情况,最终节省系统的处理和存储资源,因此,该算法适用于当前的高速网络环境。

4 结束语

本文对基于报文的流抽样技术与Bloom Filter技术进行探究,将Counting Bloom Filter结构和流抽样技术相结合,并充分利用两者的优势,提出一种网络流等概率抽样算法。该算法为Counting Bloom Filter结构中的每个Counter分配4 bit,通过4 bit的Counter向量识别是否有新流出现,并借助后续的随机抽样模块以实时调整抽样频率的形式吸收由Counting Bloom Filter的误判率引起的测量误差,最终实现对网络流的等概率抽样。仿真结果表明,本文算法测量结果趋近于网络流真实值,可以有效获得网络流的真实分布情况,测量精度较高,且具有可扩展性,能够适应当前的高速网络环境。下一步将考虑改进Counting Bloom Filter,以使其计数器的位数能够动态适配高速网络环境。