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

鲁宁 等:联盟模式下高效单包溯源方法研究 3895

• 同时,将操作结果加入 P,形成新的成员前缀集 P′;
• 然后,在 P′中展开新一轮聚合误报率计算,直到新的成员前缀集中没有误报率为 0 的聚合.
上述算法虽然简单有效但是不支持增量计算,考虑到 P 中元素会随着联盟成员的加入或退出而随时调整,
若总是无法利用已有计算结果而重新开始一轮计算,那么整个过程会产生非常大的计算开销.为此,借鉴文献
[15]提出的最长公共前缀树,本文提出一种新的数据结构——前缀压缩(prefix compression,简称 PC)树,以此为
基础,提出可增量的成员前缀优化算法.
成员前缀优化过程应包含 5 步.
−
1) 构建 PC 树,其中,叶子节点由 P 和 P 元素组成,非叶子节点则由它们孩子的公共前缀组成.如图 7(a)
−
所示,黑色节点表示 P 中成员前缀,白色节点表示 P 中非成员前缀,星形节点表示中间聚合前缀.与已
有的 LCP 树不同,PC 树的叶子节点按层次分类,只有同层次节点才可能发生聚合;
2) 计算每个节点 x 误报情况ρ(x),具体公式如下:
⎧ > 0, x = Leaf , x∈ P
ρ ( ) x = ⎪ 0, x = ⎨ Leaf , x∈ P − (7)
⎪
⎩ ρ L ρ ∧ R , 其他
如图 7(b)所示,黑色节点的误报ρ 1 为 0,白色节点的误报ρ 2 >0.星形节点的误报ρ 3 =ρ L ∧ρ R ,其中,ρ L 表示其
左孩子误报,ρ R 表示其右孩子误报.当ρ L =0 且ρ R >0 时,得ρ 3 >0;当ρ L >0 且ρ R =0 时,得ρ 3 >0;当ρ L >0 且ρ R >0
时,得ρ 3 >0;当ρ L =0 且ρ R =0 时,得ρ 3 =0;当ρ L =∅,得ρ 3 =ρ R ;当ρ R =∅,得ρ 3 =ρ L ;
3) 剪去 PC 树中所有白色无用节点.如图 7(c)所示:黑色叶子因参与前缀优化,故留下;而白色叶子因节点
误报情况已经获得,故删除;
4) 执行前缀聚合,生成最优树.如图 7(d)所示,由底向上逐层删除所有父亲误报为 0 的叶子节点;
5) 生成最优的成员前缀.如图 7(e)所示:只需依据广度优先来遍历 PC 树中所有叶子节点,就能获得最优
的成员前缀,即被虚线圈包围的节点.

198.3.0.0/20
/20 >0 >0 >0
0 1 >0 >0 >0 >0 >0 >0
/21
0 1 0 1 >0 >0 0 >0 >0 >0 0 >0 >0 0
/22
0 1 0 1 0 1 0 >0 >0 0 >0 0 0 0 0 0 0 0
/23
0 1 0 0
/24
(a) 构建PCB 树 (b) 计算误报 (c) 剪去白叶子 (d) 完成聚合 (e) 生成最优前缀
Fig.7 An example of prefix optimization procedure (from Fig.1 and Fig3)
图 7 成员前缀优化过程举例(源于图 1 和图 3)
−
图 7 中,假设 P={198.3.0.0/23,198.3.6.0/23,198.3.10.0/23,198.3.8.0/24,198.3.9.0/24},P ={198.3.2.0/23,198.3.4.
0/23,198.3.12.0/22}.黑色节点表示成员网络前缀,白色节点表示非成员网络前缀,星形节点表示聚合前缀,被虚
线圈包围的节点表示优选出的成员网络前缀.
上述过程的时间复杂度分析如下.
−
1) 构建 PC 树需要执行|P|+|P |次前缀插入操作,每次插入最多比较 32 次,因此,它的时间复杂度上界为
−
o(32×[|P|+|P |]);
2) 若采用分治策略来计算节点误报,通过构建递归树,已知每个节点需要计算一次,那么整体时间复杂
−
度上界为 o(32×[|P|+|P |]);
−
3) 只有通过遍历一次 PC 树才能剪去所有白叶子节点,它的时间复杂度上界为 o(32×[|P|+|P |]);