基于抽样和两级CBF的长流识别算法

翟金凤， 孙立博， 鲁 凯， 林学勇， 秦文虎

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

0 引 言

诸多研究表明，网络流具有显著的重尾分布特征，数量较少的长流占据了网络流量的大部分[5]。因此掌握长流信息就可以对链路上经过的所有网络流有个整体的认识，便于对网络流量进行管理和监测分析，对网络流量计费、安全检测、流量调控等工程应用起着重大作用，并且对长流进行识别可以有效缩减处理和存储的数据量，提高系统处理效率和资源利用率。

目前长流识别算法主要使用抽样技术、哈希技术以及Bloom Filter技术。单独使用抽样技术需要对流信息进行维护，同时会产生较大的计算开销；而单独使用哈希技术或Bloom Filter技术则会增大哈希冲突，影响测量精度[6]。因此可以将抽样技术和哈希技术或者Bloom Filter技术相结合以实现更高效的长流识别。景泉等[7]提出了一种将分层随机抽样与哈希技术相结合的长流识别算法，能够较准确地识别出长流，但对流长度的测量存在一定误差，且哈希技术仍需对流信息进行维护，浪费存储资源。吴烨等[8]提出利用双重计数型布隆过滤器（counting bloom filter,CBF）对长流进行识别的算法，并进行了一定的理论分析，表示算法可以适应于大规模网络的流量监测，但对每个报文进行长流过滤并不能有效节约空间和时间资源。刘元珍[9]则先对报文进行随机抽样，再通过多级CBF过滤出达到阈值的长流，一定程度上可以提高长流识别的准确率，但同时也牺牲了一定的时间和存储资源。

本文提出一种基于抽样和两级CBF的长流识别算法，将长流过滤和流长计数分开处理。首先对观测时间内链路上通过的报文进行系统抽样。继而利用两级CBF对被抽样报文进行处理，第一级CBF对长流进行过滤，识别出报文数达到阈值的长流；第二级则对识别出的长流所含报文数进行统计。最后利用第二级CBF对所有未被抽样的报文进行查询，若属于已识别出的长流，则对流长继续计数。

1 抽样技术和Bloom Filter技术介绍

1.1 报文抽样技术

在网络测量中，抽样是指以某种方式从网络中提取一定数目的报文或流数据，通过样本尽可能准确描述总体数据的参数，以节约系统空间和时间资源，因而被广泛应用于高速网络流量测量领域。使用抽样进行网络流量测量时，必须考虑如何从感兴趣的数据总体中提取具有充分代表性的样本对象，以确保所提取的样本与总体特征相近[10]。

典型的报文抽样技术主要包括系统抽样、随机抽样和分层抽样3种[11]。系统抽样是在总体中按固定的间隔进行样本的选取，如图1（a）所示[12]。其主要优点是易于理解、简便易行，适用于总体容量很大的情况；缺点则是易存在同步问题，引起测量失真。随机抽样即严格按照随机原则从观察对象总体中提取一定数量的样本，如图1（b）所示。该方法操作最为简便迅速，样本间相互独立性高，但样本分配较分散，代表性恐有不足。分层抽样先根据额外信息将观察对象总体分成不同的层，然后分别在各层中以独立、随机的方式进行样本对象的提取，如图1（c）所示[13]。分层抽样样本和总体结构相似度高，代表性强，但层界的设定会增加样本选择的成本和复杂性，同时怎样选取分层特征或规则也是个难点。

图1 3种抽样方法

本文综合考虑样本对总体的代表性以及计算和时间的复杂度后，选用系统抽样作为长流识别过程中的抽样方式。

1.2 Bloom Filter技术

Bloom Filter是一种基于哈希的二进制向量数据结构[14]，其利用一个位向量简洁地表示一个包含大量元素的集合，同时实现快速查询某一元素，并检测该元素是否属于某一集合[15-16]。元素插入和查询的时间都是常数级，可以显著节约空间和时间资源，缺陷是存在一定的误判率和不支持元素删除操作。

初始化Bloom Filter时，将位向量的每一位均设置为0，选取k个相互独立的哈希函数h1,h2,···,hk[17]。插入元素时，计算元素的k个哈希值，将元素映射到位向量中相应的k个位置，设置这k个位置为1，其余位置不做改变。查询元素时，若元素的k个哈希值映射到位向量中的位置均为1，则判定该元素属于Bloom Filter所表示的集合。但由于映射过程中存在某一位被重复置1以及哈希冲突的可能性，进而会导致某个不属于集合的元素被判定为属于集合，这样的误判概率定义为“误判率”[18]。

当级配碎石拌和完毕后应及时采用大吨位自卸式卡车将其运输至施工现场，运输过程中车辆的行驶速度不宜过快，避免混合料出现较为严重的离析现象，另外，运输车的车厢上方宜覆盖一层帆布，以减小级配碎石混合料的水分散失。

标准Bloom Filter不支持元素的删除操作，CBF[19]作为Bloom Filter典型的改进结构之一，将Bloom Filter的每一位扩展为一个counter计数器，增加元素删除功能。如图2所示，插入元素时，将对应位置的k个计数器值加1；删除元素时则将对应的k个计数器值减1；查询元素时，若元素映射到对应位置的k个计数器值都不为0，则判定为属于集合。与Bloom Filter一样，CBF在判断元素是否属于集合时仍存在一定的误判率。

2 长流识别算法

设观测时间内链路上通过的报文总数为N，若将占据报文总数m%以上的流定义为长流，则阈值设置为T=N·m%，长流即为观测时间内所含报文数超过阈值T的流。长流的定义是可调的，通过改变m的值进而满足各种测量应用需求。

图2 CBF原理图

由网络流显著的重尾特性可见，如果对链路上通过的总报文按某种抽样频率进行抽样，那么长流中包含的大量报文被抽中的可能性要比短流中的少量报文大的多，因此可以先对总报文实施抽样，再利用抽样后的报文进行长流识别。这样既能大大缩减处理的数据量，有效节省时间资源，又能保证长流识别的准确性。如图3所示，基于抽样和两级CBF的长流识别算法的实现过程为：

图3 算法流程示意图

2）设定长流识别的阈值T1，同时合理配置两级CBF的结构参数。由于报文的抽样频率为p=1/n，根据简单线性关系，使用抽样报文进行长流识别的阈值应设置为T1=T/n。两级CBF选用相同的k个冲突小的哈希函数h(1),h(2),···,h(k)；第一级CBF结构中counter数组的长度m1设置为大于抽样报文总数N/n的2的幂次方，每个counter分配的位数b1需满足条件2b1>T1，且需适当地多分配几位以避免计数器溢出；第二级CBF结构中counter数组的长度m2设置为大于报文总数N的2的幂次方，每个counter分配的位数b2需满足条件也需适当地多分配几位以避免计数器溢出。

3）对于每个被抽样的报文，先通过k个哈希函数将其映射到第二级CBF的相应位置。若相应位置的k个计数器值均不为0，则判定该报文属于已识别出的长流，将其插入第二级CBF中，即将这k个计数器值分别加1。

4）若相应位置的k个计数器值中有任意一个为0，则判定该报文不属于已识别出的长流，再通过k个哈希函数将其映射到第一级CBF中，求取相应位置的k个计数器的最小值；若这k个计数器的最小值等于阈值T1，则判定其所属流为长流，记录下该报文的流标识，将这k个计数器值分别减去阈值T1，并将其映射到第二级CBF中，设置相应位置的k个计数器值为T1+1。

5）若这k个计数器的最小值不等于阈值T1，则判定其所属流不为长流，将其插入第一级CBF中，即将这k个计数器值分别加1。

6）重复步骤3）～5）完成对所有被抽样报文的处理后，通过第二级CBF对所有未被抽样的报文进行查询。若报文映射到第二级CBF的相应位置的k个计数器值均不为0，则判定该报文属于已识别出的长流，将其插入第二级CBF中，即将相应位置的k个计数器值分别加1，否则不做任何处理。

由上述算法的具体实现过程可以看出，对所有报文处理完后，步骤4）中记录的流标识即为该算法识别出的长流的流标识；将记录的流标识映射到第二级CBF中，相应位置的计数器的最小值即为该算法测量出的长流的流长度。

3 实验分析

实验选取互联网数据分析合作组织（CAIDA）公开提供的2016年3月17日在Chicago采集的实际Trace数据进行仿真分析。实验平台为Visual Studio 2013，原始Trace中共有1 759 536 911个报文，本文截取前5 000 000个报文数据进行实验分析，阈值设置为21 000，报文数超过阈值的真实长流共有3个，具体长流信息如表1所示。实验中的流是指具有相同的源和目的IP地址的报文集合，具体的流标识的定义可以根据网络实际应用需求决定。

表1 真实长流信息

分别以1/10、1/50、1/100的抽样频率对总报文进行系统抽样，两级CBF的哈希函数均选用SHA1算法。分别取哈希函数个数为1，2，3进行长流识别，当哈希函数个数大于1时，对报文信息进行复制作为新的SHA1输入以生成新的哈希值。当抽样频率设为1/100，哈希函数个数设为1时，算法仿真结果如表2所示，可以看出由本算法识别出的长流信息与真实的长流信息完全相同。

表2 算法识别出的长流及流长度

使用不同的抽样频率和哈希函数个数进行仿真实验后发现：

2）当系统抽样的抽样频率分别取1/10、1/50、1/100时，该算法均可以零误差地识别出各长流及其流长度。由此可以看出，长流识别中利用系统抽样可以提取出具有充分代表性的报文样本，且操作简单，时间复杂度低。同时，抽样频率越小，算法用时越短，识别速度越快，因此在报文总数较大时，可以适当降低抽样频率以提高算法的处理速度。

4 结束语

本文提出一种基于抽样和两级CBF的长流识别算法，对3种典型的报文抽样技术进行性能比较分析后，选取系统抽样对总报文进行抽样；继而利用两级CBF对被抽样报文分别进行长流过滤和流长计数处理，最后再利用第二级CBF对所有未被抽样的报文进行查询，统计出长流所含的总报文数。通过仿真实验验证本文算法能在有效节约空间和时间资源的基础上，既实现对长流的准确识别，又实现对原始流长度的零误差的高精度测量。同时，算法还具有可扩展性，一定误差范围内可以选用相对简单的哈希算法，或者使用硬件实现，以进一步提高算法的处理效率，满足当前高速网络发展对网络流量监测的需求。