網絡診斷

網絡診斷又稱網絡斷層掃描，是近代發展的一種新的網絡測量與推論方法，透過可收集到的有限資訊來推估無法觀測的網絡資訊，主要分成主動診斷(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.