Category Archives: 论文阅读笔记

How to Read a Paper 阅读笔记

ACM Sigcomm CCR 07′

阅读一篇论文可以有三遍:

第一遍:

  • 时间:10 分钟
  • 操作:阅读标题、摘要、Introduction、Conclusion、每章标题和小标题,过一遍 References
  • 收获:文章分类、Contributions、写作水平

第二遍:

  • 时间:1 小时
  • 操作
    1. 阅读正文,跳过证明
    2. 在文章的边角写下 key points
    3. 标记未来需要阅读的 references
  • 收获:没有理解也没有关系,如果不想理解它,就可以丢掉了。

第三遍:

  • 时间: 1 小时 到 5 小时
  • 目标: 尝试 虚拟 re-implement 这篇文章
  • 操作
    1. 识别和思考文章的每一个 assumption, 思考自己会如何处理它们
    2. 写下 future work
    3. 写下文章的 strong and weak points

Survey

  1. Google 搜索近年的 3 – 5 篇文章,读第一遍
  2. 读他们的 related work,看是否引用了 survey, 读 survey, done
  3. 否则,访问他们共同引用的作者,分析他们最近发表的会议
  4. 研究会议近年来的内容,并分析会议paper 的引用,找到并阅读最重要的那些

DPMS阅读笔记 – Optimal Deployment of Distributed Passive Measurement Monitors

From: ICC 2006 CCF C
Key Words: DPMS Huc Counter Distributed_Passive_Measurement
Author: 2 Biu Liu 4 Shifang Gao 5 Dapeng Wu from U of Florida

KYH的一句话总结:
在全网上放置monitor做流量测量,monitor放置的越多测量的越准,但是花费也会越大,所以是一个权衡。分析这个问题太复杂了,所以作者提出了一个 CCP 问题,假定用户有一个心理的monitor覆盖率阈值,求放置的方案达到这个阈值满足一个置信度即可。同时提出了 BCP 问题,假定用户有一个预算上限,在给定预算的情况下怎么放置满足覆盖率阈值和置信度,覆盖率取到最优解。显然都是NP-hard问题,直接用遗传算法求解。皆大欢喜。

0. Abstract:
通用的 centralized per-flow measurement 会导致内存带宽和大小问题。Paper 提出了 DPMS (Distributed Passive Measurement System,只需要在一些位置放置 monitors 来采样随机流量(stochastic),优化目标是覆盖率最大。

文章将问题建模为 SCCO (Stochastic Chance Constrained Optimization), 提出了 HI (Hybrid Intelligent)方法,包括 uncertain function approximation 和 genetic algorithm. tradeoff 是 覆盖率和 cost (small number of monitors).

1. Introduction:
Flow-level 被动测量分为 centralized / distributed.[1-3]指出 centralized 会有内存和带宽的问题。所以 paper 讨论 distributed. DPMS 通过降低采样速率来降低 内存带宽需求。但是提高速率 和 更多的 monitors 可以提高覆盖率。所以是一个 tradeoff.

IPMON[4] 是在 Sprint IP 放置了 distributed,但是没有考虑 tradeoff. [5]讨论了 tradeoff,但是没有考虑流的random. Paper 讨论了 tradeoff 和 random.

2. Formulation:

2.1.Setting
flow 定义为 Same Source Destination IP. Node-based monitor 能够在 node 内部实现,能够 monitor 所有 connceted 的 link. 假设 flow 是 single path, 所以我们能在任何一个path上观测流。. (KYH: 这个假设也太强了,把建模简单太多。) 采样速率在每个monitor上独立配置,不同的流在一个monitor上是相同的被采样速率。

(1)式给出了放置一个 monitor ci 的 cost. 为
C + a (采样速率 / 最大速率)^m.
其中 C 是恒定花费。 a, m 是常量 (KYH:真是一个简单的定义,另外,凭什么说速率的cost可以直接除出来)。

(2)给出了总花费: Sum(ci * xi). 其中 xi = 1 表示 monitor 放在 node i 上.

假设 1) 流是fluid,也就是单包size为无穷小(KYH:也就是可导,(●’◡’●)).2)随机变量 fj(t) 表示流 j 在 t 的traffic. 3) fj(t) 是 stationary 和 ergodic process 的.(KYH: ergodic process: 平稳随机过程中任一随机样本函数的时间平均值与无限多个随机样本函数在同一时刻的平均值相等,即时间平均等于集合平均。)有了3)的假设,fj(t)就变成了 fj. (KYH:这不就是作弊么。。。)

流能被测量当 Rate i 大于 flow j.

(3)式给出了采样率 rij = (qi xi yij) / fj . 其中 qi 是 node i 的采样率。xi 同上, yij = 1 表示流 j 通过 node i. 所以就是 Rate i / flow j

(4)式给出了采样到流 j 的概率, Rj = 1 – Sum i (1 – rij) (KYH: 就是 1 减所有节点都采样不到 j 的概率)

(5)式定义了采样覆盖率 M = Sum j (Rj) / n ,其中 n = number of flow.

2.2. SCCO Model
(KY:SCCO 这个名字可以看出,年轻的 Huc 这个时候还没有形成自己的起名风格)

因为 f> 向量是 stochastic, 所以 M 也是 stochastic. 因此引入 SCCO,通过 probabilistic bound 和置信度 b 来讨论问题。 (KY: f> 向量就是每一条流的Rate组成的一个一维向量,使用线性代数来讨论问题可以提高文章的姿势水平。)

用户最关心的是 coverage. 所以设计了CCP (Coverage Constraint Problem)问题. 优化目标是 Min 式(2) 满足
式(6) Pr{M >= T} >= b, 其中 T 是预定义的覆盖率阈值.

对ISP来说,最关心的是 Budget,应该添加一个 Budget 的限制.文中称 BCP (Budget Constraint Problem)问题。描述为
式(7) Mo = sup { r | Pr{M >= r} >= b}

(KY: 这个式子写的太难懂了。 首先 Mo 之前没有定义, o 应该指的是 optimistc, 所以这里求最优的 M 全网平均覆盖率。 sup 这里应该是上界 Supermum 意思。我先理解为了 支持集 和 支持度,都想不通。这个上界的表示真是不好。

所以是求集合 r 的上界。 当 r 持续上升的时候, Pr(M >= r) 的概率必然持续下降, 所以这个概率满足置信度 b 的 r 最大值就是所求 )

这些都在假设有 ISP 有确定的 budget B, 也是就满足
式(8) sum(ci xi) <= B.

总结:这章给出的核心假设有:

1) 流是 single path
2) 流无限可分
3) cost 满足 qi / L 的经验公式
4) fj(t) 可以看作 fj
5) 存在覆盖率阈值 T, ISP 预算 B

两个优化目标: CCP BCP

3. HI 算法

2中的算法和传统的随机过程优化为题都不同。但是如果 uncertain functions 是 determined, 那就和经典的优化问题一样了。所以核心是 determined 化这个问题。Paper提出 HI算法, 1) uncertain approximaiton 2) optimization. 3.1 Uncertain approximation (KY:引入上文提到的 f> 向量,下标为 k,也就是有 k 个 f> 向量)

式(9)给出 indicatior I(f>) = 1 if M(f>) >= T else 0
式(10)给出期望 E[I(f>)] = Pr{M(f>) >= T }

用 N’ 去 count 满足 M(f>) >= T 的情况,也就是
式(11) N' = Sum{ I(f>) }

这个就是经典的 SLLN (Strong Low of large number) 问题。
(KY:原文这里写错了,应该是 Strong Law, 强大数定义,即在无限次试验下,均值等于期望).

所以就有
式(12) N’ / N = E[ I( f> ) ] ,即均值 = 期望

带入就是
式(13) Pr{ M( f> ) >= T } = N’ / N

(KY: 至此,原文解出了 式(7) 中的优化目标,就是 count 一下 N’,虽然我有点不服。 )

然后给出了流程1:

random generate f_k > by flow rate distribution function // 这个function从哪来
N' = 0
for k=1 to N
__if M( f_k> ) >= T
____N'++
return N' / N // 这个值就是近似的覆盖率

CCP问题就算解了,对于BCP, 要求 Pr{M >= Mo } >= b, 显然等价于 Pr{M >= Mo} = b.

式(14)给了一个 indicator I(f>) = 1 if M >= Mo else 0
同样给一个 counter N’ 来记录 M(f_k>) >= Mo, k = 1 to N

同样用 SLLN 的方法,得到
式(15) N' / N = E[ I(f>) ] = Pr{ M >= Mo } = b

-> N' = ceil(bN),给出了流程2

random generate f_k > by distribution function // 这又是什么function
N' = ceil( bN )
for k = 1 to N
__get M_k by f_k>
sort(M_k)
return M_N'

3.2. Optimization Method

[6]中证明了 budget maximum coverage problem 是 NP-hard, 所以用 heurisitc 求解。

GA (Genetic Algorithm) 遗传算法大法好[7,8], 因为
1) 对于大范围的目标函数,找到全局最优解效率高
2) Tabu, Simulated Annealing 模拟退火 同样有 1) 的特点,但是DPMS用它们写代码太难了
3) GA 的收敛性已经被证明了[9,10].

流程为:
1) 随机产生染色体 chromosomes 作为 solution candidates
2) evaluation and selection
3) 产生新的 chromosomes by 2) 的交叉 和 变异 crossover & mutation
4) 判断收敛 或者 predefined iteration times

染色体定义为 V = ( x1…xl, q1…ql ), x1 = 1 代表 1号node有monitor,q是采样率。 然后产生他们的 crossover, 通过 V1 和 V2 交换第 n1 到 n2 位置的基因,产生 V1′ 和 V2’,这样就有遗传算法的族群了. 然后randomly产生 position m1-m2 的值,这样就有变异了.

然后是评估,通过 rank-based, 通过它们产生的 object 来排序,下标代表位次, 然后归一化它们的匹配度fitness通过fitness(Vi) = a (1-a)^(i-1). Paper 特别指出,实现上用了 轮盘算法 roulette-wheel

(KY: 这块建模求解就是怎么粗暴怎么来)

4. Experiments and Evaluation

4.1. Settings

生成了 4 种分布的流量: Bimodal, Uniform, Exponential, Constant (双峰,均匀,指数,常数). Bimodal 是通过混合两个 Exponential 产生的. Constant 的 Rate 是 300Mb/s.

用了 14 node 的网络拓扑[12],(1)式中, C,a,最大速率,m 分别为 1,0.5,500,2. 置信度为 0.9.

4.2. Result

图4表示覆盖率和Cost之间的关系,对应CCP问题. 其中 curvers of deployment cost are approximately the convex functions of coverage, which means differential coefficient of cost is larger when coverage constraint is increased.

图5表示覆盖率和 Budget 之间的关系,对应BCP问题。观察到斜率在持续减小,说明后面加钱对覆盖率的增加作用变小了。

图6和图7是图5和图6在 calculation(HI) 和 simulation 之间的差异情况.Paper说,因为 uncertain 的存在,讨论最优解不可行,只能通过 simulation 来检验 HI,图上表明没有差异. (KY: 但是这里的 simulation 是什么,没有说清楚。)

About 10 minutes 在 P4 1.7GHz 上计算出 CCP 和 BCP 的结果. Paper 说 inherent parallelism 可以大幅降低 HI 的时间,然后用文字分析了一番。(KY:我对在 Result 里面分析一番这种做法有一点意见。)

网络拓扑会变,但是mid-nodes一般不会变,或者被 ISP 人为的变,而不是 Random,所以不用考虑。Routing Path会变,但是 not hard to detect,也不是问题. 最后作者给了一个结论,去掉一两个node而不改变部署策略,即使node上有monitor, 其实对覆盖率没有什么影响。全文戛然而止。

(KY:既然都这么说了,我觉得这个问题的 beach mark 应该是,随机的放 n 的 monitor 和作者提出的放 monitor 的方案来比覆盖率,说不定都差不多 (手动斜眼))