王少龙， 张毅卜， 徐 敏， 陈 珍， 夏靖波

（空军工程大学 信息与导航学院， 陕西 西安 710077）

作为网络流量测量的重要组成部分，网络流测量将大量具有统一属性的数据分组聚类分析[1]，有效的节约了测量过程中所需的存储资源，更好地反应了用户的行为特征，逐渐受到重视。

传统的固定周期抽样和简单随机抽样中广泛存在对小流数据抽样不足的缺点，致使大量流分布信息丢失，不能有效获得网络流的真实分布情况，对于异常检测等应用构成了隐患[2]。 因此，有必要以更加公平的方式对网络流进行抽样。文献[3]在对所有分组归并的基础上，对每一个流进行等概率抽样，其缺点在于不能支持对网络流的在线测量。 SGS 算法[4]（Sketch Guided Sampling）将对数据分组的抽样率与其所属流的流量相结合，增加了对短流所属数据包的抽样，对各流的抽样更加公平。 但SGS 算法必须实时计算相应流的流量，对算法的精度造成影响。 文献[5]提出的算法对哈希函数的误差概率进行了计算，通过适时调整抽样概率，保证了对网络流的等概率抽样，简单实用，适合大规模部署。 但该算法在使用新位向量进行测量时会造成一定数量的网络流被重复抽样。SEFS 算法[6]运用多解析度抽样统计器实现对流的公平抽样，有效避免了测量过程中的哈希碰撞， 具有良好的空间效率，但其计算过程较为复杂，不便于大规模使用。

文中在文献[5]的基础上，提出了一种基于改进型Bloom Filter 的网络流抽样算法，有效减少了对网络流的重复抽样，具有较高的测量精度。

1 相关工作

1.1 原算法实现过程

在原算法内，Bloom Filter 用于判断数据分组所属网络流是否是第一次到达（即新流）；误差吸收模块的主要用于计算抽样过程中产生的误差概率；随机抽样模块的主要功能是以调整后的概率对Bloom Filter 认定的新流进行抽样， 算法结构如图1 所示。

图1 基于Bloom Filter 的网络流抽样算法Fig. 1 Network flow algorithm based on Bloom Filter

1.2 原算法理论分析

由文献[7]知，Bloom Filter 在对新流进行判定过程中的误差概率为：

式（1）中m 为位向量的长度，k 为哈希函数数量，n 为已经插入Bloom Filter 的网络流数量。 对于到达的数据分组使用Bloom Filter 对其进行检测， 判定其是否已经插入Bloom Filter。 由于Bloom Filter 存在检测误差，因此任意新流在此阶段被成功检测的概率为。 当Bloom Filter 检测到新流时，调整随机抽样模块的抽样概率为r/（1-p）（r 为算法对任意流总的抽样概率），则可以保证对任意新流的抽样概率都等于r（即（1-p）×r/1-p）。

为了降低Bloom Filter 的误差概率， 各个位向量n≥（m/k）×Bmax内设定装载因子上限Bmax=0.6，当流数量时，使用空位向量进行测量，刷新达到装载上限的位向量，两层位向量轮流使用，从而确保测量的连贯性。

文献[5]所提算法可以快速对到来的网络流进行识别和计算，有效吸收了Bloom Filter 产生的误差，最大限度保证了对网络流的等概率抽样。 但是该算法在第一层位向量进行初始化时，由于第二层位向量为空位向量，会将第一层位向量内已识别的部分流重新认定为新流，造成对网络流的重复抽样，浪费了有限的存储资源。

2 新算法的提出

文中在原算法的基础上，提出了一种基于新的网络流抽样算法—MBF 算法（Modified Bloom Filter），算法主要包括改进型Bloom Filter、误差吸收和随机抽样3 个模块。 MBF 算法处理流程如图2 所示。

图2 MBF 算法流程Fig. 2 MBF algorithm flow chart

为了便于实际使用， 改进型Bloom Filter 模块设置三层位向量，对不同的位向量的装载因子上限动态设置，即将位向量每一次使用时的装载因子上限在一定范围内随机设置。在使用时运用两层位向量同时对网络流展开测量，对两层位向量所得到的判定结果取交集。 将3 个位向量分别命名为、A1、A2和A3， 对应的动态装载因子上限分别表示为为B1、B2和B3。 不同的装载因子使得位向量之间的初始化时间不同，当A1位向量的装载数量达到上限时，随即进行初始化，A2和新位向量A3进行工作。 定义每个位向量都使用一次为一个测量周期，MBF 算法在一个测量周期内的实现步骤如下所示。

MBF 算法

1） 分组p′到达，解析其流关键字f；

2） 各位向量分别生成装载因子上限B1、B2。

3） 通过哈希函数将f 分别映射到A1，A2位向量；

4） If（A1判定为新流）

5） n1=n1+1

6） else 处理下一个分组

7） End；

8） if（A2判定为新流）

9） n2=n2=1

10） else 处理下一个分组

11） End；

12） If（两层位向量均判定为新流）；

13） 流数量n=n+1

14） 计算Bloom Filter 误差PTBF；

15） 调整随机抽样概率为r/（-pTBF）。

16） End；

17） If（ni（1=1，2）≥（m/k）×Bi（1=1，2）），刷新相 应位向 量，生成 装载因子上限B3使用位向量A3进行测量

18） End；

3 理论分析

3.1 动态装载因子上限的设置

由（1）式知：

即p=eln（1-e-kn/m）k=ekln（1-e）

令p′=k ln（1-e-kn/m），当p′取最小值时，p 也为最小值，设p″=e-kn/m，则

易知，当p″=1/2 时，式（3）取最小值，Bloom Filter 误差最小，此时位向量中0 和1 数量各占50%。在无哈希冲突的情况下，装载因子上限Bi=kn/m=0.5 是最理想的状态，但是由于哈希碰撞，当元素数量n=0.5m/k 时，装载因子小于0.5。 因此，从节约存储空间的角度考虑，可以将适当增大。 文献[5]将装载因子上限设置为0.6，本文中将动态装载因子上限设置在0.5-0.8 区间内。

3.2 算法准确性

假设pi、pj分别为使用中的两层位向量对分组进行判定时产生的误差（其计算可借助式（1）完成），MBF 算法在决定是否抽取相应分组时需要对两层位向量的判定结果进行取交集操作，因此，MBF 算法产生的误差为：

即

由于0＜pi＜1，因此pj－pipj＞0，所以式（4）和式（5）均大于0，不会有小于0 的情况出现。

不同的装载因子上限使得位向量在不同时间初始化，当系统使用A1、A2位向量测量时， 在一个测量周期内，A2位向量达到装载上限初始化时，A1位向量内会有m×B2/k 个流记录（B1＞B2），此时A1位向量尚未使用的比特位数为mB1－mB2，这些空间需要存储m×（B1－B2）/k 个流后再进行初始化。 在A2位向量初始化后，使用A1和A3位向量进行测量时，部分A2位向量内已经认定的网络流的后续分组到来时不会被再次认定为新流，有效的减少了由于单个位向量进行初始化造成的对已识别网络流的重复认定。

此外，由于位向量在每一次使用时其装载因子上限随机设置，可以有效避免由于两层位同时初始化造成的网络流重复认定，使得算法可以更加精确的对网络流进行测量。

3.3 算法复杂度分析

1）时间复杂度分析

MBF 算法实现过程中，时间开销主要包括哈希运算和存储器访问两部分。 文献[5]对CRC32、Bob 和H3哈希函数进行对比，确定H3哈希函数综合性能较为优异，时间效率能够达到纳秒级，故在此选用H3哈希函数完成对元素的哈希运算。假设改进型Bloom Filter 中拥有个哈希函数， 则新流识别模块处理一个数据分组需要进行次哈希运算， 时间复杂度为；对于每个位向量来说， 改进型Bloom Filter 最多需要对存储器进行2 次访问，相应的时间开销为2O（k）。 当前高规格的存储器的访问速率已经达到1－2ns/次，而在OC－192 链路中，相邻分组之间的间隔为32ns。 因此在新流识别阶段，通过选择适当的高速随机访问存储器和适当的哈希函数数量，可以使得算法应用于当前的高速网络环境。

2）空间复杂度分析

MBF 算法在借助两层位向量对到来的数据分组进行判定，因此，当有个网络流需要进行测量时，在无哈希碰撞的情况下，所花费的空间开销为2k×n；对于原算法而言，面对同样数量的网络流，相应的空间开销为。因此，相比于原算法，MBF 算法的空间复杂度有所提高， 但与对每条流的信息逐个维护的传统方法相比，MBF 算法大幅度降低了测量过程中的空间开销。

4 仿真实验与结果分析

4.1 仿 真

仿真所使用的流量数据来自互联网数据分析合作组织（CAIDA）在互联网上采集所得到，详情如表1 所示。 仿真工具为MATLAB R2010a；处理器为Pentium（R）E5200，2.50 GHz；1G 内存；操作系统为Windows XP Professional。

表1 流量数据信息Tab. 1 Information of traffic data

由于硬件性能有限， 实验选取两组流量数据的前1×105个数据分组作为实验对象，3 个位向量的长度均设置为50 000 bits，使用五元组[8]作为网络流的流关键字，将原抽样算法和MBF 算法的抽样率均设置为r=0.5。为保证公平起见，原算法中位向量的长度也设置为50 000 bits， 哈希函数仍选择使用H3哈希函数，数量与原抽样算法相同，即设置k=3。

图3 和图4 为分 别使用trace－1 流量数据和trace－2 流量数据时，原算法、MBF 算法和流量数据真实值（抽样后）的基本情况。

图3 流数量比较图（trace－1）Fig. 3 Comparison of flow number（trace－1）

图4 流数量比较图（trace－2）Fig. 4 Comparison of flow number（trace－2）

可以看出，原有的基于Bloom Filter 的网络流抽样算法，由于在每个位向量达到装载上限后均使用新的位向量对数据分组进行判定， 因此会出现检测到的流数量陡增的情况。在同等条件下， 新提出的MBF 算法运用两层位向量同时对数据分组进行判定，并且对每层位向量的装载因子上限动态设置， 很好地避免了由于位向量初始化造成的流数量激增，所得到的流数量更加趋近与真实值，具有较高的测量精度。

与Bloom Filter 相似， 改进后的Bloom Filter 依然存在误差，在一定阶段会有部分流数据不被识别，因此在部分阶段会出现MBF 算法仿真结果小于实际数量的情况， 该误差产生的影响会在随后的随机抽样模块被“吸收”掉，对最终的实验结果影响有限。

4.2 误差分析

图5 误差比较图（trace-1）Fig. 5 Comparison of error（trace-1）

图6 误差比较图（trace-2）Fig. 6 Comparison of error（trace-2）

能够发现， 新提出的MBF 算法有效的减少了对网络流的重复认定，减小了测量误差，结果更加准确。

5 结束语

本文提出了一种基于改进型Bloom Filter 的网络流等概率抽样算法。 改进型Bloom Filter 中运用两层位向量对到来的数据分组分别进行判定，将每层位向量的装载因子上限动态设置，通过误差吸收和随机抽样模块最终实现对网络流的等概率抽样。 实验证明新算法可以有效减少对网络流的重复抽样，所得结果更加趋近于网络流真实值，测量精度较高，能够适应当前的高速网络环境。 三层位向量的设置，进一步拓展了算法的使用空间。

[1] 钱宇. 高速网络流测量模型研究[D]. 郑州:解放军信息工程大学，2008.

[2] 杨家海，吴建平，安常青. 互联网络测量理论与应用[M]. 北京:人民邮电出版社，2009.

[3] HOHN Nicolas，VEITCH Darryl. Inverting sampled traffic[J].IEEE/ACM Transactions on Net-working.2006，14（1）:68-80.

[4] KUMAR Abhishek，XU Jun. Sketch guided sampling-using on-line estimates of flow size for adaptive data collection[C].Proc. of IEEE Infocom 2006， Washington，2006.

[5] 王洪波，程时端，林宇. 高速网络超连接主机检测中的流抽样算法研究[J]. 电子学报，2008，36（4）:809-818.

[6] 张进，邬江兴，钮晓娜. 空间高效的数据包公平抽样算法[J].软件学报，2010，21（10）:26422655.

[7] 孙昱，夏靖波，赵小欢，等. 基于LEAST和CBF两级结构的大流检测算法[J]. 华中科技大学学报.2014，42（4）:40-44.

[8] 张震，汪斌强，张风雨，等. 基于LRU-BF策略的网络流量测量算法[J]. 通信学报.2013，34（1）:111-120.