渐进式定位的网络监控的贝叶斯方法

本文为论文《A Bayesian Approach to Network Monitoring for Progressive Failure Localization》读书笔记。

研究背景

布尔网络断层扫描 BNT

布尔网络断层扫描通过使用端到端监控路径来定位网络故障。但是对监视路径的结果的观察会导致布尔方程组通常被低估，因此允许多个解决方案。

渐进式探测活动

可以有效减少评估网络状态所需的探测数量。根据先前观测结果定位监视路径的预期效用。

弊端：

• 较大的状态空间大小

• 较大的计算后验概率的计算成本_{在失败路径数量上呈指数级}

因此，需要提出方法简化。

渐进式探测策略 PMP

据先前的观察结果选择下一个要探测的路径的决策策略，这样我们就可以识别最小步数 (路径数) 中最大节点数的状态

假设：

1. 同时故障的数量没有界限
2. 监视节点的位置不可控
3. 给定的路由算法

提出模型

后验概率贪婪 PoPGreedy

这是一种贝叶斯策略，根据当前效用最大化规则逐步选择下一步探索的路径，并更新下一步的整体观察结果

算法：

给定一个表示网络拓扑的图 $G$，一组路径 $M$ 和节点失效的先验概率 $p$

1. 每次迭代，求出最大化效用的路径

2. 随机选择一条最大化效用路径来断开连接

3. 一个动作对应于监控一条新路径 $m*$ 并更新当前路径失效概率估计值的决策

   若 $m*$ 失败，删除所有属于 $m^$ 的动作_{他们肯定失败}

   若 $m*$ 在被修剪掉工作节点后仅由一个节点组成，那么该节点一定是断开的

   若 <% raw %>$m*$ 起作用，则删除属于 $m*$ <% endraw %>的子集的探测路径所对应的动作集_{它们的结果是已知的，不需要测试它们}

4. 检查是否可以通过排除来定位断裂的节点

5. 如果没有更多的有效路径可供测试，计算所有节点的失效概率并进行排序

6. 返回有序序列

失败中心贪婪 FaCeGreedy

观察到一组给定探测路径的结果的情况下，定义节点 $v$ 的失效中心度，以近似路径状态概率后验估计值, 算法1可以通过以下修改来适应使用中心性度量而不是精确的条件概率：

• 将概率 $p$ 改为初始节点中心性 $c$
• 第六行与第七行: 将 $U(a|OT)$ 替换为 $Uc(a|OT)$
• 第8行: 将 $P (Sv| OT)$ 替换为 $c(v | OT)$

动态故障

某些网络组件的状态可能会由于新的故障，拥塞或恢复干预而发生变化，通过监视给定路径获得的信息可能很快就会过时。
对此对于 DPoPGreedy和DFaCeGreedy 提出变体，定义一个滑动观察窗，仅考虑一组最近探测的路径，以解决信息过时的问题。

实验

实验指标

结果

优于经典布尔网络断层成像的最新解决方案以及基于顺序图的渐进式组方法