网络诊断

网络诊断又称网络断层扫描，是近代发展的一种新的网络测量与推论方法，透过可收集到的有限资讯来推估无法观测的网络资讯，主要分成主动诊断(active tomography)与被动诊断(passive tomography)两类问题。被动诊断是资料从个别节点搜集，去寻找路径上的资讯，问题在估计起始节点至终端节点之流量矩阵。主动诊断是借由设置接收节点，向接收节点发送大量的封包，根据接收节点收集到的测量数据，分析网络内部有兴趣的参数或识别网络拓扑结构。而衍生出来的统计问题称为统计反向问题(Statistical Inverse Problem)。

研究主题

网络诊断的概念最早由Vardi在1996年提出，现今的研究主要分为：

网络起始节点至终端节点的流量强度估计

所谓网络起始节点至终端节点(SD)流量强度估计主要是想要估计网络内各条SD路径的封包流量。其主要概念为假设我们能观测到网络内各节点互相传送封包的路径，以下简称连结和各条连结的封包流量，由各条连结所观测到的结果来估计各条SD路径的网络流量。

主要问题架构与符号定义如下： 假设网络模型内有 $n$ 个节点、$r$ 条连结、$c$ 条SD路径且定义A为$r$x$c$ 的路径矩阵。
举例来说，网络模型有4个节点(a,b,c,d)、7条连结、12条SD路径，如下方左图所示，且路径矩阵A可表达如下方右图所示。

令$X_{j}^{\left(k\right)}$表示第 $j$ 条SD路径在第 $k$ 期的封包流量，在此假设 $X_{j}^{\left(k\right)}\sim Poisson(\lambda _{j}),\;j=1,...,c,\;k=1,...,K$。
因此连结的流量与SD路径的流量可以表示成下列的线性模型

${\boldsymbol {Y^{\left(k\right)}=AX^{\left(k\right)}}},k=1,...,K$

其中，

${\boldsymbol {Y^{\left(k\right)}}}=\left(Y_{1}^{\left(k\right)},...,Y_{r}^{\left(k\right)}\right)'$表示从第1期到第$K$期各条连结上观察到的流量向量

${\boldsymbol {A}}$表示路径矩阵，由元素0和1构成

${\boldsymbol {X^{\left(k\right)}}}=\left(X_{1}^{\left(k\right)},...,X_{r}^{\left(k\right)}\right)'$表示从第1期到第$K$期各条SD路径的流量向量

我们希望利用观测到的Y向量去估计X向量中的参数值$\mathrm {\lambda =\left(\lambda _{1},...,\lambda _{c}\right)'}$，但通常X向量的维度远大于Y向量的维度，因此X可能会有无限多解， 而目前发展出下列几种寻找最佳参数解的方法

1. 最大概似法
2. 参数可能解中让概似函数最大者
3. 借由EM算法找最大概似估计量
4. 动差法
5. 贝氏方法

例子

假设网络模型有2条连结、3条SD路径、1期的SD流量，即$r=2,c=3,K=1\$
令$X_{i}\sim Poisson(\lambda _{i}),\;i=1,2,3$ 且 $X_{1}+X_{2}=1,X_{1}+X_{3}=2$
如下图所示

则我们可以得到

$Y={\binom {1}{2}},A={\begin{pmatrix}1&1&0\\1&0&1\end{pmatrix}},X={\begin{pmatrix}X_{1}\\X_{2}\\X_{3}\end{pmatrix}}$

因此模型可表示成

${\binom {1}{2}}={\begin{pmatrix}1&1&0\\1&0&1\end{pmatrix}}\cdot {\begin{pmatrix}X_{1}\\X_{2}\\X_{3}\end{pmatrix}}$

以最大概似法求最佳解为例，

• 参数可能解中让概似函数最大者

先将所有可能的参数解找出。因为封包流量必须为正整数，因此只有以下两组解：

$X={\begin{pmatrix}1&0&1\end{pmatrix}}'$ 或 $X={\begin{pmatrix}0&1&2\end{pmatrix}}'$

将可能的参数解代入概似函数

$L(\lambda )=(\lambda _{1}\lambda _{3}+{\frac {\lambda _{2}\lambda _{3}^{2}}{2}})exp(-\lambda _{1}-\lambda _{2}-\lambda _{3})$

找出让概似函数最大的参数解，即为最佳参数解

$Find\;\lambda :max_{\lambda }L(\lambda )$

因为

$L({\begin{pmatrix}1&0&1\end{pmatrix}}')$ > $L({\begin{pmatrix}0&1&2\end{pmatrix}}')$

最佳解为

${\lambda }={\begin{pmatrix}1&0&1\end{pmatrix}}'$

• 借由EM算法找最大概似估计量

先将概似函数整理成期望值的型态

$\mathbf {\lambda } =E_{\lambda }[X|Y=AX]$

选定起始值$\lambda ^{\left(0\right)}$ ，运用EM算法，进行递回运算，直到找出让期望值最大的参数解

$\lambda ^{\left(n+1\right)}=E[X|Y,\lambda ^{\left(n\right)}]$

利用EM算法求解的缺点是当网络模型较大时，在计算上比较复杂；即使当期数够多时，EM算法仅能提高估计上的准确性并无法解决计算上的复杂。

针对EM算法的缺点，Vardi在1996年提出一种较为可行的方法，即利用动差法来估计参数解。

假设当各条连结流量观测的期数够多时，根据中央极限定理

${\bar {Y}}={\frac {1}{K}}\sum _{k=1}^{K}Y^{\left(k\right)}\;{dist.\to }\;N_{r}(A\lambda ,K^{\left(-1\right)}A\Lambda A'),\;\Lambda =diag(\lambda )$

利用动差法，令样本平均数等于母体平均数，样本共变异数等于母体共变异数，即

${\bar {Y}}=A\lambda$ ， $S=K^{\left(-1\right)}A\Lambda A'$

由上述式子即可估计出参数解

因此Vardi提出动差法可解决计算上的困难，也可以利用产生动差等式解决参数解不唯一的情况。

网络连结层级参数推估

所谓网络连结层级参数推估问题主要是想要推论网络连结的特性，例如节点传输之间资讯遗失率或延迟分配等。其主要概念为假设已知网络的形式，包含节点、路径等，一般常见为树状，以及假设已知网络特性的模型，搜集端点所测量的结果来找出有最大几率产生观察结果的网络参数。

若考虑封包遗失率下，其主要问题架构与符号定义如下：

假设有一个树状网络定义为

$T=\left\{{V},{E}\right\}$，

表示该网络有V个节点(包含起始节点0、终端节点R及中间节点I)、E条连结。令

$X=(X_{k})_{k\in V}$，

其中$X_{k}$表示封包传送是否通过节点$k$，即

• $X_{k}=0$表示没有通过$k$节点
• $X_{k}=1$表示有通过$k$节点
  

此外，若$X_{i}=1$且$X_{j}=1$，表示节点$i$与$j$之间的连结有封包通过，此处以$\alpha \,_{i}$表示封包通过的几率。

举例来说，

上图为一个树状网络

$T=\left\{{V}=\left\{0,1,2,3,4,5,6,7\right\},{E}=\left\{(0,1),(1,2),(1,3),(2,4),(2,5),(3,6),(3,7)\right\}\right\}$

数字表示节点，起始节点为0，中间节点为1、 2、 3，而终端节点为4、5、6、7，$\alpha \,_{i}$表示连结$i$的通过率。

令封包传送结果$X_{(R)}=(X_{k})_{k\in R}$，则其几率分配表示为

$p\,(x;\alpha )=P_{\alpha }(X_{(R)}=x)$。

并假设发送了$n$个封包，令$n(x)$表示$x$所获得的封包数，则 $n$个独立的观测值 $x^{1}$、$x^{2}$到$x^{n}$的分配为

$p(x^{1},x^{2},\cdots ,x^{n};\alpha )$

$=\prod _{m=1}^{n}p(x^{m};\alpha )$

$=\prod _{x\in \Omega }p(x;\alpha )^{n(x)}$，

因此问题的目标即为估计$\alpha$。

从起始节点传送封包，并观察终端节点封包通过情况。传送封包主要有两种情况，一种为一次只传送到一个接收的端点，称为单一传送；另一种为封包传送到特定的一些接收端点，称为多重传送。然而这两种传送方式较没有弹性，且无法使用不同的流量或不同时间下观察网域，因此Xi et al. (2006)及Lawrence et al. (2006)针对弹性传送(flexicast)封包的情况作探讨。

此种观察封包传送情况来对网络做推论产生了统计反向问题，即利用观察结果来诊断连结中的分配或特征。有许多统计方法可解决此类推论问题，Castro et al. (2004)提到像是降低复杂性的阶层统计模型(Complexity-Reducing Hierarchical Statistical Models)、动差或最大概似法为主的估计、EM及马可夫链蒙地卡罗(Markov Chain Monte Carlo, MCMC)演算方法等已被使用；且认为而使用统计方法来解决此问题的领域仍具有发展性，而未来应有更多现存的统计方法可加以应用。

以下兹列举一种问题情况：“针对多重传送为主的网络来推论该网络的封包遗失率”来说明网络连结参数中的遗失率推估问题。估计封包遗失率为Cáceres et al.(1999)首先研究，在假设连结遗失为独立的伯努利分配下，利用最大概似法来估计多重传送的树状网络中连结遗失率；他们亦证明此估计量具备强烈一致性，并透过最大概似估计量之渐近常态性来推导出这些估计的比率会收敛到真正的比率。

以最大概似法求估计之连结遗失率方法如下：首先计算对数概似函数，

$L(\alpha )=\log \,p(x^{1},x^{2},\cdots ,x^{n};\alpha )=\sum [{n(x)}log\,p(x;\alpha )]$；

则$\alpha$的最大概似估计量

${\hat {\alpha }}=argmax_{\alpha \in [0,1]}L(\alpha )$。

另外，Cáceres et al.(1999)亦利用终端节点接收封包几率来估计$\alpha$。令$R(k)$为第$k$个节点传送下来之终端节点所成集合，$\Omega (k)$为$R(k)$集合中至少有一个终端节点有收到封包之所有观测情况所成集合。假设$\gamma _{k}=P[\Omega (k)]$，则$\gamma _{k}$估计量为$\Sigma \left[{\frac {n(x)}{n}}\right]$， 即观察到的比例总和。令$k=f\,(j)$表示节点$k$为前一个节点$j$所传下来的，
且定义$f\,^{n}\,(j)=f(f\,^{n-1}\,(j))$，即前$n$个节点传下来。并令$l(k)$表示第$k$条连结所在从起始到终端节点的层级。定义

$\beta _{k}=P\,[\Omega (k)|X_{f(k)}=1]$，

表示给定从第$k$的节点传送的节点有通过下，其传送到的终端节点至少有一个有收到封包的几率。他们证明$\gamma _{k}$跟$\alpha$的关系为

$\gamma _{k}=\beta _{k}\prod _{i=1}^{l(k)}\alpha _{f\,^{i}(k)}$，

即将通过第k条连结所在从起始到终端节点的所有$\alpha _{k}$相乘，在该篇文章中亦提供求$\gamma _{k}$的演算程序。因此，利用观察到的样本结果，则可推估封包通过率，而封包遗失率则可求之。

例子

以两层的树状网络为例：

令通过此网络终端节点的可能情况集合为

$\Omega =\left\{00,01,10,11\right\}$，

其中

• 00表示封包皆没有通过节点2跟3，
• 10表示封包通过节点2但没有通过节点3，
• 01表示封包通过节点3但没有通过节点2，
• 11表示封包节点2跟3皆有通过。

可计算$\gamma _{i}$值如下：

$\gamma _{1}$= P[$\Omega$(1)]表示从第1个节点传送下来之终端节点中，至少有一个节点有收到封包的几率。

$\gamma _{2}$= P[$\Omega$(2)]表示从第2个节点传送下来之终端节点中，至少有一个节点有收到封包的几率。

$\gamma _{3}$= P[$\Omega$(3)]表示从第3个节点传送下来之终端节点中，至少有一个节点有收到封包的几率。

则

${\hat {\gamma }}_{1}={\hat {P}}(11)+{\hat {P}}(10)+{\hat {P}}(01)$,

${\hat {\gamma }}_{2}={\hat {P}}(11)+{\hat {P}}(10)$,

${\hat {\gamma }}_{3}={\hat {P}}(11)+{\hat {P}}(01)$

利用$\gamma _{k}$跟$\alpha$的关系式可得

${\hat {\alpha }}_{1}={\dfrac {{\hat {\gamma }}_{2}{\hat {\gamma }}_{3}}{{\hat {\gamma }}_{2}+{\hat {\gamma }}_{3}-{\hat {\gamma }}_{1}}}={\dfrac {({\hat {P}}(01)+{\hat {P}}(11))({\hat {P}}(10)+{\hat {P}}(11))}{{\hat {P}}(11)}}$，

${\hat {\alpha }}_{2}={\dfrac {{\hat {\gamma }}_{2}+{\hat {\gamma }}_{3}-{\hat {\gamma }}_{1}}{{\hat {\gamma }}_{3}}}={\dfrac {{\hat {P}}(11)}{{\hat {P}}(01)+{\hat {P}}(11)}}$

${\hat {\alpha }}_{3}={\dfrac {{\hat {\gamma }}_{2}+{\hat {\gamma }}_{3}-{\hat {\gamma }}_{1}}{{\hat {\gamma }}_{2}}}={\dfrac {{\hat {P}}(11)}{{\hat {P}}(10)+{\hat {P}}(11)}}$

补充

EM算法

EM算法为一种在具有无法观测的资料或是混合模型下计算最大概似估计量之一种有效率的反复程序，每次递回(iteration)包含下列两个步骤：

• E步骤(Expectation)

此步骤为在给定完全的资料及当下的参数估计值后，计算对数概似函数的条件期望值。

• M步骤(Maximization)

此步骤为在最大化E步骤中的条件期望值对数概似函数，即求最大概似估计量。

令$\mathbf {X}$表示观察到的资料，$\mathbf {Z}$表示遗失或无法观测的资料，及${\boldsymbol {\theta }}$表示欲估计的参数。 演算步骤如下：

1. 选择参数起始值 ${\boldsymbol {\theta }}^{(0)}$。
2. 第m次递回

• E步骤：

$Q({\boldsymbol {\theta }}|{\boldsymbol {\theta }}^{(m-1)})=E_{\mathbf {Z} \mid \mathbf {X} ,{\boldsymbol {\theta }}^{(m-1)}}[logf(\mathbf {x} ,\mathbf {z} \mid {\boldsymbol {\theta }})]$

• M步骤：

${\hat {\boldsymbol {\theta }}}=argmax_{{\boldsymbol {\theta }}\in {\boldsymbol {\Theta }}}E_{\mathbf {Z} \mid \mathbf {X} ,{\boldsymbol {\theta }}^{(m-1)}}[logf(\mathbf {x} ,\mathbf {z} \mid {\boldsymbol {\theta }})]$

参考文献

1. Cáceres, R., Duffield, N., Horowitz, J. and Towsley, D.(1999). Multicast-based inference of network-internal loss characteristics. IEEE Trans. Inform. Theory, 45 2462–2480.
2. Castro, R., Coates, M., Liang, G., Nowak, R.D. and Yu, B. (2004), Network tomography: recent developments, Statistical Science, 19, 499-517.
3. Lawrence, E., Michailidis, G. and Nair, V. N. (2006). Network delay tomography using flexicast experiments. J. Roy. Statist. Soc. Ser. B 68 785–813.
4. Lawrence, E., Michailidis, G. and Nair, V. N.(2007). “Statistical Inverse Problems in Active Network Tomography.”in Statistical Inverse Problems, Liu, R., Straderman, W. and Zhang, C. H.(editors), IMS Lecture Note Series.
5. Tebaldi, C. and West, M. (1998), Bayesian inference of network traffic using link count data (with discussion), Journal of the American Statistical Association, 93, 557-576.
6. Vardi, Y. (1996), Estimating source-destination traffic intensities from link data, Journal of the American Statistical Association, 91, 365-377.
7. Xi, B., Michailidis, G. and Nair, V. N. (2006). Estimating network loss rates using active tomography. J. Amer. Statist. Assoc. 101 1430–1438.