One Sketch to Rule Them All: Rethinking Network Flow Monitoring with UnivMon阅读笔记

$D(m, n)$D(m,n)是一个长度为$m$m, 包含$n$n个不同元素的信息流 (stream). 假设这些元素分别为$[1, 2, \cdots, n]$[1,2,⋯,n], $f_i$fi​是元素在信息流中$i$i的频数. 假设$g()$g()是任意一个函数, 则我们将$\sum_{i=1}^ng(f_i)$∑i=1n​g(fi​)称为频数向量的$g-sum$g−sum.

如果$g()$g()是单调函数并且$g(f_i)\le O(f_i^2)$g(fi​)≤O(fi2​), 则用于估计$G-sum$G−sum的具有多重对数型空间复杂度的信息流算法(streaming algorithm)是存在的.

$Stream-PolyLog$Stream−PolyLog是所有存在对应的多重对数型空间复杂度的信息流算法的$G-sum$G−sum的集合.

对于元素$i \in [1, 2, \cdots, n]$i∈[1,2,⋯,n], 如果$g(f_i) > \gamma\sum_jg(f_j)$g(fi​)>γ∑j​g(fj​), 其中$0 < \gamma < 1$0<γ<1, 则我们称$i$i为一个g-重型元素 (g-heavy element 或 g-heavy hitter). $G-core$G−core是所有g-重型元素的集合.

已有文献证明, 对于元素$[1, 2, \cdots, n]$[1,2,⋯,n], 它的频率向量是$[f_1, f_2, \cdots, f_n]$[f1​,f2​,⋯,fn​], 如果某个元素是频率向量的L2范数的重型元素, 则它也是这个频率向量的g-重型元素.

UnivMon包括两部分, 即在线测量部件和离线估计部件. 在线测量部件的工作流程如算法1所示. 其工作流程可具体描述如下.信息流$D(m, n) = \{a_1, a_2, \cdots, a_m\}$D(m,n)={a1​,a2​,⋯,am​}中共有$n$n个不同的元素. 令$d=log_2 n$d=log2​n. 我们建立$d+1$d+1个梗概. 我们将这些梗概分别记为$S_0, S_1, \cdots, S_d$S0​,S1​,⋯,Sd​. 此外, 梗概$S_1, S_2, \cdots, S_d$S1​,S2​,⋯,Sd​分别对应于哈希函数$h_1, h_2, \cdots, h_d$h1​,h2​,⋯,hd​, 且$h_k()~(k = 1, 2, \cdots, n)$hk​() (k=1,2,⋯,n)可以将一个元素随机地映射到0或者1. 当元素$a_i$ai​到达的时候, 我们将其插入$S_0$S0​中, 并且在其上查找L2-重型元素, 并将找到的重型元素插入$Q_0$Q0​中. 之后, 对于$S_i~(i = 1, 2, \cdots, d)$Si​ (i=1,2,⋯,d), 我们依次进行如下操作: 如果$h_1(a_i)\cdot h_2(a_i) \cdots h_i(a_i) = 1$h1​(ai​)⋅h2​(ai​)⋯hi​(ai​)=1, 则我们将$a_i$ai​插入梗概$S_i$Si​中, 并且在$S_i$Si​上查找L2重型元素, 之后将找到的重型元素存入$Q_i$Qi​中.

以上过程处理完成以后, 我们就得到了$d+1$d+1个序列$Q_0, Q_1, \cdots, Q_d$Q0​,Q1​,⋯,Qd​, 分别用于从数据平面的梗概$S_0, S_1, \cdots, S_d$S0​,S1​,⋯,Sd​从提取出来的L2重型元素. 之后我们使用算法2来获取对$G-sum$G−sum的估计, 即对$\sum_0^n g(f_i)$∑0n​g(fi​)的估计. 在算法2中, $w_j(i)$wj​(i)是$Q_j$Qj​中的第$i$i个哈希桶中的元素的计数值.

为什么这两个算法是有效的, 我现在也不太明白. 我打算进一步调研原来文章中给出的相关文献, 理清这两个算法的内在逻辑. 我弄清楚并做好笔记以后会在这里给出链接.