一种基于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的大流检测算法，通过引入“小流早期丢弃”和“大流预保护”机制来提高了检测准确性;文献［8］提出了Landmark-LRU算法，在LRU结构中设置“Landmark”来区分大流和小流的存储区域;文献［9］提出了FEFS算法，在原始LRU基础上，通过引入流尺寸因子s和自适应调节因子M，来筛选要淘汰的流记录，提高了大流提取的准确率。以上基于LRU［10］方法在处理速度、识别效率、硬件消耗方面各有优点，但是当大量小流突发到达时，由于多种原因，均会造成某些大流被错误地替换出缓存。

此外在高速网络中，流量测量还会受到计算速度和存储资源的限制。恰恰相反，现实情况中却是速度快的存储器容量小，容量大的存储器访问速度慢［11］。运用哈希技术能够缓解存储速率和存储器容量的矛盾。基于哈希计算的数据结构Bloom Filter具有空间效率高、计算复杂度低的优点，常被用于网络大流测量中，但是此结构不具有计数统计功能，因此又产生了Count Bloom Filter、Space Code Bloom Filter、Loop Bloom Filter等多种数据结构［12-14］。运用这些数据结构进行网络大流的识别，能够对符合条件的流信息进行精确维护，极大降低了对存储空间的需求，明显提高了存储速度和识别的准确度。

本文研究一种基于LRU算法和BF算法的大流识别算法:FEFS_CBF算法。将CBF结构引入到FEFS算法中，首先使用CBF过滤小流，然后将达到一定阈值的流信息放入LRU中进行筛选，并将识别出的大流隔离，可减少突发小流对大流识别造成的干扰。

2 相关算法

2．1 LRU基本原理及拓展

LRU算法通过设置一个固定大小的缓存，用来保存流记录。每新到一个数据包，LRU即检测它所属的流是否存在缓存中。若存在，则更新对应流的信息，并将此流记录提取到缓存的最顶端;若不存在，就新建一条流记录，插入到缓存的最顶端。以此类推，接收频率较小的流信息就会处在缓存的最底端，当缓存已满，且再有新流的数据包到来时，LRU将新建流信息插入缓存顶端，并将最底端的流记录替换出缓存。由于大流传输的持续时间长，到达频率高，因此有很大概率使大流信息留在 LRU缓存中。

文献［9］对原始的LRU算法进行了改进，形成FEFS算法。FEFS算法相较于LRU算法有以下优势:(1)在选取淘汰流时，并非直接淘汰处于LRU链表底部的流，而是选取一个相对较小的流进行淘汰。为了定位淘汰流的位置，FEFS算法设置了调节因子M，并为每一个流都引入一个属性——尺寸因子s。在最开始时，s的值等于流的报文的数量，即每当有属于该流的报文到达时，s就加1。当选择一个流淘汰时，检查LRU链表底部流的s值，如果s≤M，就淘汰该流;否则，依次检查链表中前一个单元，直到找到s≤M的流，将该流淘汰。对于检查过的流，重新定义流的s值为s=s－M。最终将新建的流与检查过的流一起移至LRU链表头部。(2)当LRU中的某条流记录达到一定阈值，则认为此流很可能是一个大流，那么将此流隔离到一个单链表中，当再有此流的数据包到达时，只需要更新单链表中流的状态。这样能有效地降低计算资源的消耗。FEFS算法结构如图1所示。

图1 FEFS算法结构

2．2 Bloom Filter基本原理及拓展

Bloom Filter是一种基于hash的简洁数据结构。其核心是设置一个向量Vector，通过几个hash函数，来判断元素是否属于一个集合。

在初始状态时，Bloom Filter是一个m维的位数组，每一位的值都预设为0。设集合S={s1，s2，…，sn}中共有n个元素，选取并使用k个相互独立的哈希函数，将集合中的每一个元素，映射到m维的空间中，被映射到的位置，其数值被置为1。若一个位置被多次置为1，那么此位置的值保留为1。在判断x是否属于该集合时，对x应用k次hash函数，如果所有的hi(x)(1≤i≤k)所映射的位置的值都为1，则判定x是集合中的元素;否则，就认为x不是集合中的元素。Bloom Filter结构如图2所示。

图2 Bloom Filter结构

Bloom Filter在使用时可能会将不属于该集合的元素误判为属于该集合，所以不适合“零错误”的应用场合，而且不支持计数操作，因此除了进行判断查找，无法进行数值统计。Count Bloom Filter将标准Bloom Filter中的每个1 bit单元拓展为一个计数器(counter)。在插入元素时，使用k个hash函数进行映射，对映射到每一位，将其数值加1。在删除元素的时候，对应的k个位置的数值分别减1。Count Bloom Filter通过增加存储空间的代价，给 Bloom Filter增加了删除操作。Count Bloom Filter结构如图3所示。

图3 Count Bloom Filter结构

3 基于FEFS与CBF的大流识别算法

3．1 大流定义

大流的定义方法和衡量标准有很多［15］。本文将四元组(源IP、目的IP、源端口、目的端口)相同的数据包归并为一个流。流的大小即为所含数据包的数量。大流的阈值为一个固定比值。

3．2 算法结构

FEFS-CBF算法使用三级处理机制:(1)CBF部分由m维的计数器数组和k个相互独立的hash函数组成，每个计数器大小为x位，每个计数器最大存储数值为(2x－1)。CBF用来筛选有可能成为大流的流，避免小流进入LRU。(2)LRU部分为一个固定长度的双向链表，在本文算法中，LRU长度一般定为1/大流阈值。每一个节点由3个部分组成:流信息(以四元组作为流信息标示符)，流所含的包数counter和尺寸因子s。LRU用来找出大流，淘汰小流。(3)大流存储(Elephant Flows Storing，EFS)部分为一个单链表，其节点结构与LRU链表相同，用来存储已识别出的大流(下文中的“LRU”均指本文算法中的LRU双链表存储结构，并非LRU算法)。

在一定时间段T内，检测的数据包总数为N，大流阈值为r(r为一个百分比)，含包数超过r×N的流为一个大流，那么，在监控周期内，最多有1/r个大流。所以，定义 LRU部分长度为 1/r。在文献［9-11］中也表明，这样定义能使算法存储空间复杂度与错误率接近最佳水平。另外，定义过滤阈值g=(r/2)×N，作为过滤掉小流的阈值。FEFS-CBF算法结构如图4所示。

图4 FEFS-CBF算法结构

3．3 算法流程

本文算法的基本流程为:在每一个监控周期内，初始化EFS单链表，LRU双链表以及CBF结构。当一个数据包到达时，首先在EFS链表中从上往下进行常数次查找，若能找到对应流的记录，说明此流已经被确定为大流，就更新流信息，使对应counter加1。若在EFS单链表中找不到，就将此数据包信息与LRU中的流信息进行比较，若找到相应流的记录，则将对应的counter和s加1，若counter值已经超过设定的大流阈值r×N，就将此流记录从LRU中摘除，插入到EFS链表头部;若没有达到大流阈值，将此流记录移至LRU头部。若在LRU链表中找不到对应流记录，就通过k个相互独立的hash函数映射到CBF空间中，对应的每个位置的值都加1。若此时对应的每个位置的值都不小于过滤阈值g，则将此流信息插入LRU链表头部，流数量counter和尺寸因子s设定为过滤阈值g，并将CBF中对应位置的值减去g。

在将CBF中的流信息插入LRU结构过程中，若LRU结构已满，就需要淘汰一条流信息。设定了调节因子M［9］，在选择流进行淘汰时，从LRU底部开始，检测流记录的s值，若s≤M，就淘汰该流;否则，就将该流的s值修改为s=s－(M－g)，然后检查链表中的上一个流，直到找到一个满足s≤M的流L，将LRU链表的尾节点指向L的上一条流记录，然后把L从链表中删除，并将前面检查过的流记录和从CBF中插入的流记录一起移至LRU链表头部。本文算法的实现过程如下:

算法1Search

算法2InsertLRU

Guolv表示过滤阈值;S表示尺寸因子;M表示衡量因子;Length表示LRU长度

参数:LRU双链表;pkt．info

4 理论结果分析

4．1 误报率

误报率(False Positive Ratio，FPR)是指将非大流识别为大流的概率。在本文算法中，FPR主要是由CBF部分产生的。在CBF中，设计数器数组长度为m，每个计数器位数为x。在一个监控周期内，检测的数据包总数为N，所有的数据包属于n个流。当有元素插入CBF中时，经过k个hash函数映射到计数器数组中，对应位置的值加1。每次映射，某位被映射到的概率为1/m。当所有元素映射完成后，总共执行了n×k次映射，此时，计数器数组中的任意一位仍为0的概率为:

在CBF中，出现“错报”(属于某个流的数据包没有到来，但其对应的位置却被其他到来的数据包映射到，该流计数器错误地加1)的概率为:

由式(1)～式(4)可以看出，算法的误报率随着k的增大而减小，但是随着k的增大，也就是哈希函数个数的增加，不仅会增加计算量，也要相应的增加CBF计数器的个数，从而增大了存储成本，因此在实践过程中，应根据现实硬件水平做出权衡。

4．2 漏报率

漏报率(False Negative Ratio，FNR)是指真实的大流没有被识别出来的概率。在本文算法中，FNR主要产生在LRU部分中。虽然经过CBF部分的过滤，使数据包数超过一定阈值的流才会放到LRU结构，但由于大量小流突发到来，还是可能将大流错误淘汰。例如:当LRU满载时，在一定时间t内，大流F到来的数据包数小于(M－g)(M为衡量因子，g为过滤阈值)，从LRU底部开始向上检查，选择要淘汰的流，检查过的流记录的尺寸因子s值均大于衡量因子M，直到检查到大流F，算法会将F淘汰。由此可见，在过滤阈值g一定的前提下，衡量因子M值越大，造成漏报的情况越高，但M值越小，会使算法检测距离越长，降低了算法处理速度。因此，M值的选取，要在处理速度和准确率方面进行权衡。

4．3 时间复杂度

本文用处理每一个数据包的计算复杂度来表示算法的时间复杂度。当一个数据包到达时，先要在EFS部分进行查询，若能找到相应记录，就只更新流信息，此时为最好的情况下，计算复杂度为O(1)。若找不到，移至LRU部分进行查找，若能找到相应流记录，需要更新流信息并将该流移至LRU头部，查找和移动的操作为常数次，此时计算复杂度为O(1)。若在LRU部分中找不到，则要将数据包插入到CBF中，插入CBF的复杂度为O(k)。若在CBF中达到过滤阈值，应将CBF中的相应计数器记录进行减法操作，计算复杂度为O(k)，并将该流信息提取到LRU中，此时为算法最坏的情况下，处理一个数据包的计算复杂度为O(1)+O(k)。因此，在监控周期开始时，本文算法处理一个数据包的计算复杂度为O(1)+O(k)，但根据大象老鼠效应，绝大多数数据包都能在EFS和LRU结构中找到相应记录，这时的计算复杂度趋近最好情况下的复杂度O(1)。

4．4 空间复杂度

空间复杂度用占用内存的大小来衡量。在10 Gb/s高速骨干链路下，取单位时间1 s，超过总数据包数0．01%的流为大流，平均每个流含10个数据分组，平均每个分组大小1 000 Byte。根据上文分析，EFS部分和LRU部分至多各需要10 000个存储空间。每个空间最大需要192 Byte，其中包括每个流的流信息96 Byte，流包计数count、尺寸因子s和指针各32 Byte。因此，EFS和LRU所需内存最大均为1．92 MB。在CBF中，平均要存储990 000个小流。选取7个hash函数，计数器长度为8位，则CBF所需最大存储约为105 MB。目前的硬件水平完全能满足本文算法实验的要求。

5 实验结果分析

在实验室有限的硬件环境中，使用2组数据集进行实际流量数据仿真，测试本文算法性能。实验中所使用的2个数据集分别为:MIT林肯实验室入侵检测数据集中较大的一个文件——1999 outside．tcpdump(大小约为 314 MB)，以下简称 Outside;CAIDA网公开的2008年的OC-192主干链路数据集 equinix-chicago．dirB．20080717-130000．pacap(大小约为161 MB)，以下简称Equinix。有关数据集的详细介绍如表1所示。

表1 实验数据集信息

为了检验算法在不同流分布条件下，大流识别的准确率，在本文选取的2个仿真数据集中，Outside数据集的网络流重尾分布特征较为明显，而Equinix的流分布较为平均，Outside的大流比率远大于Equinix。举例说明，当取大流阈值为 0．05%时，Outside中的大流数为204，而Equinix中的大流数仅为7。

本文使用2组数据集，并设置3种大流阈值，将本文算法FEFS-CBF与FEFS、原始CBF进行测试，分别比较它们的误报率(FPR)和漏报率(FNR)，并统计综合错误率(FNR+FPR)。FEFS与本文算法中的LRU双链表结构长度均被设为1/大流阈值。原始CBF算法中的CBF计数器位数设定则较大，从而能在实验条件允许的情况下取得较低误报率。本文将FEFS-CBF的过滤阈值设为大流阈值的一半，隔离阈值设为大流阈值，尺寸因子设为(过滤阈值+10)。实验结果如表2所示。

从实验数据集流分布来看，在Equinix中的大流占有很小比率，突发小流更多，这对大流识别产生的干扰也就更大。但是从实验结果来看，突发小流越多，越能体现出FEFS-CBF的优势。

基于以上实验结果不难看出:虽然FEFS的误报率趋近于0，但是漏报率较大。本文算法虽然略有误报，但由于能提前过滤掉小流，漏报率要显著低于FEFS，算法的综合性能优于FEFS。原始CBF的漏报率比FEFS低，但是误报率却很大，综合性能远低于FEFS-CBF。

从所需空间上来看，在CBF算法中，由于每位计数器都要设定较大，因此需要很大内存空间。在以上3种对比算法中，CBF占用存储空间最大，FEFS-CBF所需的空间虽然大于FEFS，但在当前实验环境中也能完全满足。

综合来看，FEFS-CBF的错误率(包括误报率和漏报率)要明显优于以上2种对比算法。

表2 FEFS，CBF，FEFS-CBF算法实验结果

6 结束语

在高速网络链路流量测量中，完整地存储每个数据包信息十分困难，流量测量也从传统的数据包级测量发展到数据流级别的测量。大流识别作为流量测量的重要分支，应用十分广泛。针对高速网络测量中大量小流影响大流准确识别的问题，本文提出了FEFS-CBF算法。使用CBF过滤小流，将流包数达到过滤阈值的流信息放入LRU中，当LRU满载时，运用FEFS机制来选取淘汰流信息。本文算法结合了FEFS算法和CBF算法的优势，对比实验结果表明，误报率、漏报率均相对较低。但由于CBF与LRU会产生误报和漏报的局限性，因此下一步的研究目标是选择更为简洁、准确的过滤结构，并对淘汰流进行重复筛选，进一步减少误报率和漏报率。

［1］ Yang L，Micahilidis G．Sampled Based Estimation of Network Traffic Flow Characteristics［C］//Proceedings of the 26th IEEE International Conference on Computer Communications．Washington D．C．，USA:IEEE Press，2007:1775-1783．

［2］ 夏靖波，任高明．大流识别方法综述［J］．控制与决策，2013，28(6):801-807．

［3］ Mori T，Uchida M，Kawahara R．Identifying Elephant Flows Through Periodically Sampled Packets［C］//Proceedings of ACM IMC’04．New York，USA:ACM Press，2004:115-120．

［4］ Estan C，Varghese G．New Directions in Traffic Measurement and Accountinga:Focusing on the Elephants，Ignoring the Mice［J］．ACM Transactions on Computer System，2003，21(3):270-313．

［5］ Kim S I，Reddy N A L．Identifying Long-term High-bandwidth Flows at a Router［C］//Proceedings of the 8th International Conference on High Performance Computing．Hyderabad，India:［s．n．］，2001:361-371．

［6］ 王风宇，云晓春，王晓峰，等．高速网络监控中大流对象的提取［J］．软件学报，2007，18(12):3060-3070．

［7］ 王洪波，裴育杰，林 宇，等．基于LRU的大流检测算法［J］．电子与信息学报，2007，29(10):2487-2492．

［8］ Che L C，Qiu B．Landmark LRU:An Efficient Scheme for the Detection of Elephant Flows at Internet Routers［J］．IEEE Communication Letters，2006，10(7):567-569．

［9］ 王风宇，郭山清，李亮雄，等．一种高效率的大流提取方法［J］．计算机研究与发展，2013，50(4):731-740．

［10］ 张娟娟，高仲合，马兆丰．基于滑动窗口的LRU大流检测算法［J］．通信技术，2012，45(10):52-54．

［11］ 张 震，汪斌强，张风雨，等．基于LRU-BF策略的网络流量测量算法［J］．通信学报，2013，34(1):111-120．

［12］ 谢冬青，周再红，骆嘉伟．基于LRU和SCBF的大象流提取及其在DDoS防御中的应用［J］．计算机研究与发展，2011，48(1):1517-1523．

［13］ Kummar A，Xu J，Wang J，et al．Space-code Bloom Filter for Efficient Per-flow Traffic Measurement［C］//Procee-dings of IEEE INFOCOM’04．Washington D．C．，USA:IEEE Press，2004:1762-1773．

［14］ Sun Y，Zhang Z B，Guo L，et al．An Effective Algorithm forCounting Active Active Flows Based on Loop Filter［C］//Proceedings of International Conference on Networking，Architecture and Storage．Chongqing，China:［s．n．］，2008:104-109．

［15］ 李 臻，杨雅辉，张广兴，等．大业务流识别方法研究综述［J］．计算机应用研究，2011，28(1):6-9．