Page 230 - 《软件学报》2020年第12期

3896 Journal of Software 软件学报 Vol.31, No.12, December 2020

4) 所谓聚合操作,就是将误报为 0 的非叶子节点的左右孩子全部删除,因此只需遍历一次 PC 树,时间复
−
杂度为 o(32×[|P|+|P |]);
5) 鉴于最优前缀就是叶子节点,最优前缀生成过程就是通过遍历 PC 树来输出叶子节点,它的时间复杂
−
度为 o(32×[|P|+|P |]).
−
综上所述,算法的时间复杂度为各子过程之和,也就是线性阶 o(5×32×[|P|+|P |]).
新增成员前缀优化过程包含 4 步.
1) 插入新增的成员前缀.如图 8(f)所示,被虚线方框包围的灰色节点表示新增成员,最多比较 32 次,因此
时间复杂度为 o(32);
2) 计算每个与新增成员前缀相关节点误报,相关节点数最多 32,时间复杂度为 o(32);
3) 自顶向下逐层删除与新增成员前缀相关、误报为 0 的节点,时间复杂度为 o(32);
−
4) 输出新增叶子节点,如图 8(g)所示,被虚线圆圈包围的节点表示新增最优成员前缀,同时更新 P .
综上所述,新增成员的时间复杂度为 o(4×32).
删除成员前缀优化过程包含 5 步.
1) 将树中与 f 1 相关节点的孩子都补全,使它们成为完全二叉节点.如图 8(h)所示,虚线方框内节点的孩子
都需补齐,遍历节点最多 32 个,时间复杂度也为 o(32);
2) 删除节点 f 1 .如图 8(g)所示,被虚线方框包围的灰色节点就是将要被删除节点,最多比较 32 次,因此时
间复杂度为 o(32);
3) 更新节点误报,时间复杂度为 o(32);
4) 删除所有白色节点,时间复杂度为 o(32);
−
5) 输出更新后的叶子节点,如图 8(j)所示,被虚线圆圈包围的节点表示最优成员前缀,同时更新 P 和 P .
综上所述,删除成员前缀优化的时间复杂度为 o(5×32).
−
−
−
-
图 8 中,假设新增成员前缀为 f 1 =198.3.2.0,P=f 1 ∪P,P =P −f 1 .删除成员前缀为 f 2 =198.3.9.0,P=P−f 1 ,P =P ∪f 1 .
被虚线方框包围的灰色节点表示新增成员网络前缀,被虚线方框包围的灰色节点表示删除成员网络前缀.
/20 >0 >0 >0 >0 >0
>0 >0 >0 >0 >0 >0 >0 >0 >0 >0
/21
0 >0 0 0 >0 0 0 >0 0 >0 0 >0 >0 >0 0 >0 >0 >0
/22
0 0 0 0 0 0 0 0 >0 0 0 >0 0
/23
局部更新 0 0 局部更新 0 >0 0
/24
(f) 插入新节点 (g) 局部聚合 (h) 补齐局部节点 (i) 删除旧成员前缀 (j) 生成最优前缀
Fig.8 An example of prefix updating procedure (from Fig.7)
图 8 成员前缀更新过程举例(源于图 7)

2.3.2 存储空间优化
随着联盟扩张,布鲁姆过滤器数量会越来越多.鉴于存储空间是决定布鲁姆过滤器性能重要因素,而溯源路
由器的内存空间是有限的,如何为不同的布鲁姆过滤器分配合理的存储容量,以便它们产生尽可能小的误报率,
就显得非常重要.根据定义 10 可知,布鲁姆过滤器集规模取决于插入前缀的掩码长度.因此,该集合中元素个数
最多不超过 32.不失一般性,本文以 32 种不同掩码长度的布鲁姆过滤器为例进行讨论.此外,假设溯源路由器可
用存储总量为 M,掩码长度为 i 的布鲁姆过滤器的存储容量表示为 m i ,也就是 m 1 +m 2 +…+m 32 =M.根据文献[16],
单个布鲁姆过滤器的误报率 P 计算公式如下: