随着网络的快速发展，网络测量已成为维护网络可靠性的必要手段^[1]. 它为大量网络功能的实现提供了充足的信息，比如流量工程^[2]、容量规划^[3]和拥塞控制^[4]等. 其中，流频率测量、大象流测量和超点测量等是实现上述网络工程的基础^[5-6]. 流频率是某段测量时间内具有相同流标识的数据包总和. 大象流指其流频率与所有流的流频率和的比值超过一定阈值的流，它的出现与网络异常强相关^[7]. 超点指具有很多不同连接的主机，比如受分布式拒绝服务（distributed denial of service， DDos）攻击的服务器^[8]、受蠕虫病毒感染的主机^[9]、端口扫描^[10]等.

目前，网络测量主要面临2个挑战. 1）现有网元设备的高速转发能力要求算法内存占用小，处理速度快，一般对于64字节的包须支持10 Gb/s的链路速度^[11-12]，即吞吐量超过14.88 Mp/s. 2）网络流量的分布是偏态的，即少部分大象流占据了大部分网络流量，大部分流的频率很小. 为了统计大象流的流频率，设计的算法常采用大尺寸的计数器比如32 bit，这对于小流造成了内存浪费^[13]. 概率性数据结构草图因其较小的内存占用及可接受可估算的测量误差，成为近些年的研究热点^[14].

经典的草图有Count-Min (CM)^[15]、Conservati-ve Update(CU)^[16]和Count Sketch (CS)^[17]等. 经典草图的内存浪费大，精确度不高，且测量任务单一，不支持大象流测量和超点测量的任务. 学术界提出一些混合结构. 它们含有分别统计大象流和小流的2个部分，比如Elastic^[3]、Diamond^[18]、TowerCU^[4]、WavingSketch^[19]、C-MH和CUH等（由CM和CU添加堆后形成）. 其中Elastic记录了大象流的流标识，具备了测量大象流的能力，但是不能过滤同一个流的重复数据包，因此无法完成超点测量. Diamond、CMH及CUH等因算法复杂度高，导致插入吞吐量满足不了链路速度的要求. TowerCU没有记录大象流的流标识，无法完成大象流测量. 其他一些草图，比如spread^[12]，它们虽然能够完成超点测量任务，但是去除重复数据包的实现是通过多分辨率位图^[20]（multiresolution bitmap）完成的. 该位图对重复数据包无法计数，因此无法兼顾基本的流频率测量和大象流测量任务.

综上，现有的草图方案无法兼顾测量精度、吞吐量和多种测量任务的需求. 为此，本文提出面向超点测量的多重过滤草图，它包含前置分流过滤器和统计过滤器2级. 分流过滤器可选择性地去除重复的包，以支持流频率测量、大象流测量和超点测量等多种测量任务. 统计过滤器分为3级子结构，分别用来捕捉不同大小的流, 以适应偏态的流量分布，提升测量精度. 此外，本文提出非对称的插入查询算法AIQ并应用全局哈希，提升吞吐量.

统计过滤器是混合型草图，它包含一个大象流部分L和一个小流部分S. 如图1所示，大象流部分被分为L₁和L₂ 2个哈希表，每个哈希表都是由若干个桶构成. 其中L₁被用来记录大象流和大象流候选者，L₂仅用来记录大象流.L₂的每个桶包含流标识$ {\text{key}} $和计数器$ {v_e} $ 2个字段，计数器${v_e}$的值为流标识$ {\text{key}} $频率的估计值. L₁的每个桶包含流标识$ {\text{key}} $以及计数器${v_e}$、$ {v_c} $共3个字段，其中$ {v_c} $用于记录候选大象流的频率. 当候选者大象流的频率超过相应大象流频率的$ \lambda $倍时，会触发流替换. 此外，L₁桶中计数器的比特数$ {\delta _1} $小于L₂桶中计数器的比特数$ {\delta _2} $.

S部分是一个$ d $行、宽度为$ w $的CU，由二维数组成. 数组中的每一个单元是一个计数器，该计数器的大小为$ {\delta _0} $比特（$ {\delta _0} \lt {\delta _1} $），用来记录小流频率. CU、L₁和L₂中计数器的最大值分别用$ {\tau _0} $、$ {\tau _1} $和$ {\tau _2} $表示，易知$ {\tau _0} \lt {\tau _1} \lt {\tau _2} $. 将每个计数器达到最大值的情况定义为溢出. 由于CU、L₁和L₂分别用来记录不同大小的流，统计过滤器中使用全局哈希$ {h_1},{h_2}, \cdots ,{h_d} $来减少哈希计算. L₁或CU的哈希计算结果$ {r_1},{r_2},\cdots ,{r_d} $会被保留后重复利用.

为了兼顾算法的插入吞吐量和查询吞吐量，提出非对称的插入查询算法AIQ. 如图1所示，插入与查询的所有可能路径分别用实线和虚线箭头标注. 假设插入流标识为$ f $的数据包，

L₁首先被访问，根据在L₁中流标识$ f $的匹配情况和相关计数器的溢出情况，决定接下来是否需要访问CU或L₂. 虽然先访问L₁，但是L₁只允许在流标识匹配成功时才能插入. 所有流实际上是先插入CU，然后逐渐变大后进入L₁，此时L₁部分才真正有流插入. 当查询流$ f $时，CU可以先被访问. 这种插入时先访问L₁而查询时先访问CU的方式得益于偏态的流分布特征，可以让少数大象流快速插入L₁，增加插入吞吐量，又可以使得CU立即返回大部分小流的查询结果，增加查询吞吐量.

在测量开始时，L部分和S部分的计数器被清空，流标识字段置为空. 所有输入的数据包首先通过哈希$ {h_1} $访问L₁. L₁只允许在流标识匹配的情况下插入，所以若$ {h_1} $索引到的桶的流标识与输入数据包的流标识$ f $不匹配，则会尝试进行第2次哈希$ {h_2} $定位第2个桶，继续判断桶中流标识是否与$ f $匹配. 若不匹配，则至多进行$ d $次哈希计算尝试匹配，记录哈希值. 根据L₁中流标识的匹配情况和计数器的溢出情况，决定访问L₂或CU. 算法1详细描述了插入过程，以流标识为$ f $的数据包为例，分6种情景解释插入.

1) L₁中流标识匹配成功，且对应的计数器${v_e}$未发生溢出. 将${v_e}$进行加1操作.

2) L₁中流标识匹配成功，但是对应的计数器${v_e}$在插入之前已经溢出，流$ f $将插入L₂. 在L₁中可能进行了$ n $（$ n \in [1:d] $）次哈希计算，流标识匹配成功，$ n $至少为1，所以$ {r_1} $必然是有效的. 利用$ {r_1} $在L₂中索引一个桶，如果其流标识与$ f $不匹配，那么遍历L₂找到与$ f $匹配的桶，将对应的$ {v_e} $加1. 若找不到流标识为$ f $的桶，则放弃在L₂中的插入，插入结束.

3) L₁中流标识匹配成功，但是对应的计数器$ {v_e} $在插入之后发生溢出. 流$ f $将插入L₂. 利用已经记录的哈希值$ {r_1} $在L₂中索引一个桶. 如果该桶不为空，那么遍历L₂找到一个空桶，将对应的$ ({\mathrm{key}},{v_e}) $赋值为$ (f,{\tau _1}) $. 若找不到空桶，则放弃在L₂插入.

4) L₁中没有与$ f $匹配的流标识，且在CU中对应的计数器在插入后未发生溢出. 流$ f $借助$ {r_1},{r_2}, \cdots ,{r_d} $插入CU中，将对应的计数器加1.

5) L₁中没有与$ f $匹配的流标识,且CU中对应的计数器插入之前已经发生溢出. 该数据包以CU的方式更新L₁中$ d $个桶中的计数器$ {v_c} $. 将$ d $个桶中${v_e}$和$ {v_c} $的最小值分别记作$ {X_{\min }} $和$ {Y_{\min }} $，对应的桶索引分别记作$ l $和$ m $. 如果$ {Y_{\min }} > \lambda {X_{\min }} $，那么触发流替换，将$ (f,{Y_{\min }}) $插入桶$ l $中. 桶$ l $之前的流$ ({f_m},{X_{\min }}) $额外进行$ d $次哈希计算，将对应桶的计数器$ {v_c} $赋值为$ {X_{\min }} $.

6) L₁中没有匹配的流标识，且CU中对应的计数器在插入之后发生溢出. 流$ f $将插入L₁对应的$ d $个桶中. 若这$ d $个桶中存在空桶，则将该空桶的流标识字段$ {\text{key}} $置为$ f $，${v_e}$置为1，否则以CU的方式更新$ d $个桶的计数器$ {v_c} $，如算法1的38~41行.

给定流标识$ f $，查找对应频率的过程，如算法2所示.

进行$ d $次哈希计算查询CU中$ d $个计数器的值，记录哈希值. 如果$ d $个计数器的最小值$ {v_0} $小于$ {\tau _0} $，那么直接返回$ {v_0} $. 否则，利用记录的哈希值查询L₁. 若L₁中存在流标识为$ f $的桶，且查询值对应的$ {v_1} $小于$ {\tau _1} $，则返回$ {v_1}+{\tau _0} - 1 $. 若$ {v_1} $等于$ {\tau _1} $，则继续查询L₂. 当查询L₂时，利用$ {r_1} $索引一个桶，若该桶的流标识与$ f $相同，则直接返回该桶计数器$ {v_e} $与$ {\tau _0} - 1 $的和. 否则，遍历L₂，若存在与$ f $相同的流标识，则返回该桶计数器$ {v_e} $与$ {\tau _0} - 1 $的和. 若L₂中不存在流标识$ f $，则返回$ {\tau _1}+{\tau _0} - 1 $作为查询结果，如算法2的第24行. 若在L₁中不存在与$ f $相匹配的流标识，则返回$ d $个桶的$ {v_c} $的最小值与$ {\tau _0} - 1 $的和.

假设CU的计数器大小$ {\delta _0} $为1比特，将CU的假阳性定义为

CU在插入一个流之后任一行的任一计数器$ {c_{}} $被置为1的概率是$ {w^{ - 1}} $，不被置为1的概率为$ 1 - {w^{ - 1}} $. 在插入N个不同的流之后，$ {c_{}} $不为1的概率是$ {(1 - {w^{ - 1}})^N} $，为1的概率为$ 1 - {(1 - {w^{ - 1}})^N} $. 结合式(1)可知，在给定$ w $和$ d $的前提下，CU在插入N个不同流之后的假阳性概率$ {P_c}(N) $如下：

L₁所有桶的$ {v_c} $字段因采取CU的更新方式，等价于最小增量光谱布隆过滤器(minimal increment spectral bloom filter, MI-SBF)^[21]. 该数据结构可以视为以计数器代替单个比特的布隆过滤器. 采用与CU类似的分析方法，可以得到MI-SBF在插入$ N $个不同流后的假阳性概率$ {P_m}(N) $为

式中：$ {w_m} $为MI-SBF中计数器的数量；$ N、d $的含义与CU相同，均表示插入流的数量及相互独立的哈希函数的数量.

根据分层计数草图理论(layered counting sketch, LCS)^[22]可知, CU和MI-SBF的理论数据结构是分层计数草图. 具体来说，当流标识为$ f $的流在CU或MI-SBF中的流频率估计误差上界为$ k $时，它们对应层数为$ k $的分层计数草图. CU的估计误差与假阳性概率有如下关系：

式中：$ {f_{\mathrm{a}}} $、$ {f_{\mathrm{r}}} $分别为流标识$ f $对应流频率的估计值与真实值，$ {D_k} $为插入的所有流中频率超过$ k $的流的数量. 结合式(2)、(4)可以得出，

令$ k = \left\lceil {{\varepsilon _0}{N_{\mathrm{t}}}} \right\rceil $（其中$ {\varepsilon _0} $为CU的误差率，$ {N_{\mathrm{t}}} $为插入的数据包总数），可以得到CU的流频率估计误差为

令$ k = \left\lceil {{\varepsilon _1}{N_{\mathrm{t}}}} \right\rceil $（其中$ {\varepsilon _1} $为MI-SBF的误差率），可以得到MI-SBF的流频率估计误差为

基于(6)、(7)，根据流最终记录在统计过滤器上的3个子结构的位置，可以分3种情况来讨论估计误差上界.

1) 记录在CU中的流. 此时，流频率估计误差为CU的误差，由式(6)可得

式中：$ {N_{\mathrm{s}}} $为在测量结束时插入到CU中的数据包数量.

2) 记录在L₁中的流. 此时，流$ f $被记录在了CU和L₁ 2个子结构. 将$ f $在CU部分的估计值和真实值分别记为$ f_{\mathrm{a}}^0 $和$ f_{\mathrm{r}}^0 $. 根据式(6)可得，$ f_{\mathrm{a}}^0 $的估计误差为

式中：$ {N_{\text{c}}} $为流$ f $从CU中溢出时，CU中插入的数据包数量，显然$ {N_{\text{c}}} \lt {N_{\text{s}}} $. L₁部分的记录考虑最坏情况，即全部记录在$ {v_c} $字段，此时L₁的估计误差与MI-SBF相同，将$ f $在L₁部分的估计值和测量值分别记为$ f_{\text{a}}^{\text{1}} $和$ f_{\text{r}}^1 $，由式(7)可得$ f_{\mathrm{a}}^1 $的估计误差：

式中：$ {N_{\mathrm{l}}} $为插入到L₁的所有$ {v_c} $字段的数据包数量. 根据对流$ f $分别在CU和L₁中真实值和估计值的定义，可得

由于CU部分的记录和L₁部分的记录是相互独立的，结合式(9)~(11)可得

3) 记录在L₂部分的流. 根据实验，选取的百万流的数据集中，记录在L₂中的流不超过100个，且L₂会以遍历的方式来寻找合适位置插入，几乎不会发生流丢失的问题，因此认为L₂部分的记录不会产生误差. 最终记录在L₂部分的误差与式(12)相同.

如图2所示，左半边是分流过滤器，它的核心模块为布隆过滤器，主要用于根据所测量的任务，选出指定字段传递给统计过滤器进行计数. 布隆过滤器部分采用哈希函数，并均分为4份哈希值，产生4次哈希映射.

假设数据包$ e $经过分流过滤器，若所测的任务是流频率测量或大象流测量，则跳过布隆过滤器，由字段选择模块确定流标识$ f $传入后级. 对于超点测量，需要经过布隆过滤器去重，由字段选择模块确定源IP或目的IP后输入后级.

为了评价多重过滤草图在流频率测量和大象流测量中的性能，选取一段真实网络流量Web page^[23]. 该数据集中包含100万个流（以五元组作为流标识来定义流）、3800万个包，以测试所提算法在极限场景下的表现. 根据齐普夫定理，人工生成了偏度为0~1.0、步进为0.1的偏态分布数据集. 该组数据集的每个子集含有25万个流、400万个包.

对于超点探测任务，选取2018年真实网络场景的CAIDA流量^[24]，将其均分为若干份1 min的子集进行测量. CAIDA数据集含有84.55万个流.

实验平台是具有十二核 3.2 GHz i5-10505 处理器和 16 GB RAM 的服务器，运行Ubuntu20.0-4，所有方案均使用C++实现.

为了方便部署实现，MFS中计数器大小设置为2的整数次幂. 经过实验测试，将MFS的$ {\delta _0} $、$ {\delta _1} $和$ {\delta _2} $分别设置为8、16和32比特，能够最佳区分大象流和小流. $ \lambda $的设置需要综合考量流频率测量准确性、大象流测量准确性和插入吞吐量3个性能指标. 如图3所示，e为平均相对误差，T_u为插入吞吐量. 随着$ \lambda $从1增大至16，流频率测量的平均相对误差没有明显变化，插入吞吐量从$ \lambda $为1.2开始在22 Mp/s上下波动. 大象流测量的平均相对误差在$ \lambda $从1增长至2时无明显变化，从$ \lambda $为4开始，大象流的平均相对误差接近线性上升. 综上所述，为了取得最佳的准确度和吞吐量，$ \lambda $设置为1.2.

此外，在流频率测量和大象流测量任务下，MFS的全局哈希函数的数量设置为3，L₁内存为115 kB，L₂内存为1 kB，使用与对比方案相同的BOBHash. 在超点测量中，MFS使用与对比方案相同的MurmurHash，统计过滤器的L₁设置为8 kB，L₂设置为1 kB，CU设置为12 kB，以使用位与代替取余，求解哈希值对应的索引. 大象流的门限为0.02%，超点的门限为0.1%，其他对比方案的参数设置与原文保持一致.

评价指标如下. 1) 平均相对误差：全部流频率的真实值与测量值之差的绝对值与真实值的比值取平均. 2) 精准度：召回的大象流中真实大象流的占比. 3) 召回率：所有真实大象流中被召回的大象流的占比. 4)调和平均数：2×精准度×召回率/（精准度+召回率）.5) 吞吐量(Mp/s, million packets per second)：每秒处理的百万包数.

在Web page数据集下流频率的测量结果如图4 (a)所示，详细信息如表1所示. 图中，M为存储消耗. MFS的平均相对误差类似于TowerCU，在所有内存条件下优于其他方案. 与CM、CU、CS、Diamond和Elastic相比，当内存为400 kB时，MFS的平均相对误差分别减小了7.71、5.26、10.5、2.86和4.56倍. MFS的统计过滤器利用CU、L₁和L₂ 3级子结构，逐级过滤分离大象流和小流，减少了彼此的干扰，提升了准确性. 此外，3个子结构分别使用不同尺寸的计数器对不同大小的流进行统计，有效减少了因使用统一尺寸的大计数器比如32 bit的计数器带来的内存浪费，提升了草图的内存利用率，进而提升了准确性.

除了真实网络流量数据集，使用合成的不同偏度s的数据集下不同方案的误差变化如图4 (b)和表2所示. 在几乎所有的偏度下，MFS的平均相对误差都小于其他方案. 当偏度为零时，即完全均匀的数据集，与 CM、C-U、CS、Diamond、Elastic 和TowerCU相比，MFS的平均相对误差分别减小了14.99、7.68、5.44、47.29、3.73 和 1.95倍. 当偏度从0到1变化时，MFS的误差没有出现明显的波动并几乎持续低于其他方案，证明了所提方案能够适应多种不同特征的网络流量场景.

此外，因为Web数据集的1百万个流明显多于偏度数据集中的25万个流. 根据式(8)、(12)可知，流的数目越多，取得相同误差上界的概率越小；反之，在相同概率的保证下，流数目越多，误差上界越大. Web数据集下流频率的平均相对误差更大.

使用Web page探测大象流的实验结果如图5所示. 图中，P为精准度，R为召回率，F₁为调和平均数. 从精准度来看，随着内存的变化，MFS和Elastic均接近100%，高于CMH、WavingSketch和MVS-ketch^[25]. 即使在200 kB内存下，MFS召回的流全部是大象流，没有出现假阳性. 从召回率来看，MFS、CMH和MVSketch均为100%，优于Elastic和WavingSketch. Elastic召回率较低的原因是采用了非确定性的大象流替换策略，有一定概率将大象流误判为小流. MFS采用阈值的确定性替换，保证被替换掉的流是更小的流，提升了召回率. 从综合评价指标的调和平均数来看，MFS接近100%，即无丢失，无误报地召回了每一个大象流，明显优于其他对比方案.

除了精准召回大象流外，MFS可以实现较高的流频率测量精度. 如图5(d)和表3所示, 与Elastic、CMH、WavingSketch和MVSketch相比，MFS大象流的平均相对误差分别平均减小了29.24、4.50、65.48和13.23倍. MFS能够取得很小的测量误差，一方面是因为MFS提前过滤掉了小流，避免了小流对大象流测量的干扰；另一方面，在L₁部分确定性地利用阈值替换滚动更新大象流，保证大象流能够占据Key字段,且Key字段的流是精确计数.

CAIDA的超点测量结果如图6所示. 从精准度来看，MFS、WavingSketch和CUH在不同内存限制下均为1, 即召回的流全部为真实的超点，优于CMH和Spread. 从召回率来看，MFS和CMH类似，当内存大于700 kB时，召回了全部的超点，优于其他方案. MFS召回率会随着内存的提升而提升，这是因为分流过滤器部分内存增大后能够更加精准地去重，减小假阳性，提升了召回率. 从调和平均数来看，MFS在所有内存下优于CMH、CUH、Spread和WavingSketch，达到综合最优. 此外，从超点的不同连接数测量的平均相对误差来看，如图6(d)和表4所示. 当内存为500 kB时，与Spread、CMH、 CUH和WavingSketch相比，MFS的超点测量平均相对误差分别降低了2.95、1.28、1.25和1.11倍.

随着内存的变大，MFS的测量误差逐渐减小并始终低于其他方案. MFS误差的降低，得益于内存变大后分流过滤器精度的提升，进而提升了统计过滤器的精度.

统计过滤器的插入吞吐量如图7所示，在Web page数据集上的吞吐量超过了14.88 Mp/s. MFS在高精度下能够实现较高的插入吞吐量，得益于非对称的插入，利用流的偏态分布特征在L₁中快速插入大量数据包. 从统计过滤器的查询吞吐量来看，如图8所示，MFS的查询吞吐量T_q超过14.88 Mp/s. Elastic、 Diamond和CS在2个数据集上的吞吐量均少于14.88 Mp/s. 得益于MFS的非对称查询，大量的查询结果可以从CU快速返回，因此MFS取得了高的查询吞吐量. 综合来看，仅MFS和经典方案CM、CU及CS同时取得了较高的插入和查询吞吐量.

超点测量任务中的插入吞吐量如图9所示. 插入吞吐量超过14.88 Mp/s的方案为MFS、Spread和WavingSketch. MFS高的超点插入吞吐量来源于分流过滤器的一次哈希多次映射以及统计过滤器的非对称插入查询算法.

本文提出新型的多重过滤草图MFS，借助前置分流过滤器有选择地去除重复数据包，满足了流频率测量、大象流测量与超点测量任务的需要. MFS的统计过滤器部分进一步被划分为3级，以契合偏态分布的流量特征，从而提高了方案的内存利用率，减小了大象流和小流之间的相互干扰，提升了测量精度. 在统计过滤器部分，设计非对称的插入查询算法，利用流分布特征来提高算法的插入和查询吞吐量.

实验结果表明，本文算法不仅兼顾了流频率测量和大象流测量，而且能够完成超点测量任务. 从测量误差来看，所提的MFS在每一项测量任务上的误差均低于其他方案，且算法在不同任务下的吞吐量均高于14.88 Mp/s，即满足10 Gb/s的链路速度要求. 此外，FPGA部署能够明显提升算法的吞吐量，但是为了避免算法中出现的回路，提升硬件的执行效率，还须对算法进一步调整. 笔者将其作为下一步的研究工作.