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

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

n
立的哈希函数,使用它们来计算每个成员前缀,若每个哈希值占 n bits,那么 k 个哈希值对应 2 bits 布鲁姆过滤器
的位置索引,并将这 k 个位置的值设置为 1.任给 IP 分组 p,鉴于当前网络广泛采用 CIDR 技术,覆盖 p 中目的地
址的前缀最多有 32 种.对于任一前缀,都使用 k 个哈希函数来计算它在布鲁姆过滤器所处位置,同时查验其值.
若 k 个值都为 1,那就证明 p 就是溯源分组.不过,若将传统布鲁姆过滤器直接应用于溯源分组识别,会产生如下
问题.
1) 联盟成员的灵活退出和加入,要求布鲁姆过滤器必须能够随时添加和删除成员前缀的压缩值,然而传
统结构只支持添加,不支持删除;
2) 鉴于覆盖 IP 到达分组目的地址的网络前缀类型较多,入口路由器的高负载,要求布鲁姆过滤器必须能
够并行查验所有可能的覆盖前缀,然而传统结构只支持串行查验,效率较低.
为此,本文设计一种面向网络前缀的计数布鲁姆过滤器(counting Bloom filtering toward prefixes,简称
PCBF),如定义 10 所述,它能够在随意增添和删除成员前缀的前提下快速、准确地完成溯源分组识别.
定义 10. 面向网络前缀的计数布鲁姆过滤器可被定义为五元组 PCBF=(P,E,H,S,O),具体含义如下.
• P={p 1 ,p 2 ,…,p m }为所涉及的联盟成员前缀集;
• E={e 1 ,e 2 ,…,e n }为所涉及的到达分组的目的地址集;
• H={h 1 ,h 2 ,…,h k }为所基于的散列函数集;
• S={s 1 ,s 2 ,…,s |Π(P)| }为所构建的布鲁姆过滤器集,Π表示从网络前缀到掩码长度的单向映射函数,Π(P)表
示关于 P 中元素的掩码长度集,|Π(P)|为Π(P)的基数,s i 可描述为一个长度为 x 的比特向量:
1
s = (, ,..., )ss 2 i s i x .
i
i
同一布鲁姆过滤器只接受掩码长度相同的网络前缀插入,因此|S|=|Π(P)|;
• O={o 1 ,o 2 ,…,o I }为 PCBF 上关于 P 和 E 中元素的原子操作集,主要包括插入(Insert)、删除(Delete)和查
找(Select).∀p i ∉P,“Insert p i ”执行步骤为:
1) 从 S 中搜索与掩码长度Π(p i )对应布鲁姆过滤器 s j ;
2) ∀h i ∈ H,计算前缀 P i 在 s j 中的散列地址 h 1 (P i ),h 2 (P i ),…,h k (P i );
1 ()
3) 将 s j 的上述散列位置重新置位,即 s hP i + + ,s h 2 ()P i + + ,...,s k h ()P i + + ;
j j j
1 ()
“Delete p i ”的执行步骤与“Insert p i ”几乎相同,只是在置位时,前者变成 s hP i − − .∀e i ∈E,“Find e i ”执行
j
步骤为:
1) 依据 S,构建 e i 候选前缀集 C(e i )={c i |∀s j ∈S,c i =σ(e i ,s j )},其中,σ表示利用 s j 掩码长度来截取 e i 网络
前缀的函数;
2) ∀c i ∈C(e i ),∀h i ∈H,计算 c i 的散列地址,得到 h 1 (c i ),h 2 (c i ),…,h k (c i );
1 ()
0
3) 若∃c i ,s.t. s hc i >∧ s h 2 ()c i > 0 ... s∧ ∧ k h ()c i > 0 ,那么 e i ∈ sub S,返回 True;反之,e i ∉ sub S,返回 False.
j j j
定义 11. 亚属于∈ sub :ip∈ sub S,当前仅当∃prefix∈S,s.t. ip∈S,其中,ip 表示 IP 地址.
如图 6 所示,基于布鲁姆过滤器的溯源分组识别策略的基本原理描述为:给定 PCBF=(P,E,H,S,O),其中,
P={198.3.0.0/18,198.1.1.0/24,…},E={198.3.13.28},H={H 1 ,H 2 ,…,H k },S=∅,O={Insert,Delete,Find}.
溯源路由器首先依据 P 中元素的掩码长度来构建计数布鲁姆过滤器,得到 S={s(/18),s(/21),s(/24),…}.一般
情况下,s 的每一维计数器都由 4bit 组成,初始值为 0.然后,将 P 中所有元素插入到对应布鲁姆过滤器,也就是
∀p i ∈P,执行 Insert p i .如果成员 AS j 退出联盟,那么 P=P−{p j },其中,p j 是 AS i 的网络前缀.同时,执行 Delete p i .最后,
依据 S 中布鲁姆过滤器的掩码长度裁剪 E 中元素 e i ,进而完成查找任务,也就是∀e i ∈E,Find e i .若能返回 True,就
说明到达分组是溯源分组;反之,则不是.从时间开销的角度分析,与传统布鲁姆过滤器相比,PCBF 能够完成不同
长度网络前缀的并行查找,从而将查询复杂度降到 o(k).