基于扩展吉尔伯特模型的链路丢包率测量方法

摘要

基于扩展吉尔伯特模型的链路丢包率测量方法，属于网络测量领域，本发明为解决现有报文丢失率测量技术的测量误差大的问题。本发明方法包括以下步骤：步骤一、根据叶节点观测到的测量结果序列初始化内部节点接收探测包序列；步骤二、由上而下对内部各节点接收探测包序列进行采样；步骤三、计算各链路丢包模型参数，并按照各节点接收探测包的情况计算链路丢包率；步骤四、根据丢包率判断采样得到的Markov链是否稳定？判断结果为否，返回执行步骤二；判断结果为是，执行步骤五；步骤五、继续采样N次，根据采样结果计算各链路丢包率的估计值。

说明书

技术领域

本发明涉及基于扩展吉尔伯特模型的链路丢包率测量方法，属于网络测量领域。

背景技术

图1为网络逻辑拓扑结构。用T＝(V，L)来描述网络的逻辑拓扑，其中V是节点集合， L是连接节点的链路集合。节点o是T的根节点，所有的探测报文从o被组播到整个网络 中。

节点集合表示所有的叶节点，即探测报文的接受节点。每个非叶节点至少有一 个子节点，子节点集合用d(k)＝{d_i(k)|1≤i≤n_k}表示，n_k是节点k子节点个数。每个非根 节点k都有一个父节点，用f(k)表示。链路(k，f(k))∈L记为链路k，定义f¹＝f和 fⁿ(k)＝f(f^n-1(k))，n为正整数。如果k＝fⁿ(j)成立，则称节点j是k的子孙节点，二者 之间的关系记为j＜k。把集合中所有节点最近的共同祖先记为a(U)，如果集合U 中所有节点的父节点相同，那么U中的节点就是兄弟节点。(V(k)，L(k))表示以节点k为根 的子树，该子树的叶节点集合为R(k)＝R∩V(k)。

随着网络规模扩大及网络安全需求的提高，利用中间结点协作对网络链路参数(丢包 率和延迟等)进行测量变得越来越困难。网络断层扫描技术(Network Tomography)可 以在无需中间节点协作的条件下，实现网络链路参数的测量，是目前备受国内外学术界关 注的新技术之一。

链路报文丢失率(简称丢包率)是反映网络性能状况的重要指标之一，也是网络断层 扫描技术需要重点解决的性能推测问题。在目前的网络断层扫描技术研究中，链路报文丢 失率推测技术主要基于伯努利(Bernoulli)模型进行链路丢包过程描述，即假设链路上各 个报文的丢失过程是相互独立的。有文献提出使用Gilbert模型进行链路丢包过程的描述， 如图2所示，p₁₀表示当前报文丢失后，下一报文传输成功的概率；p₀₁表示当前报文传输 成功，下一报文丢失的概率。在实际网络中，当前一个报文丢失时，后一个报文丢失的概 率很大(p₁₀＜＜1)；当前一个报文传输成功时，后一个报文传输成功的概率也很大 (p₀₁＜＜1)，故可知p₀₁+p₁₀＜1。Gilbert模型下的链路丢包率可通过公式 θ＝p₁₀/(p₀₁+p₁₀)进行计算。然后再使用最大似然估计(MLE)或期望最大化(EM) 算法进行模型参数的计算。

针对MLE算法和EM算法存在的丢包率过低估计问题，有文献提出了一种基于 Markov Chain Monte Carlo(简写为MCMC，马尔可夫链蒙特卡尔理论)的链路丢包率测 量方法，通过Gibbs采样获得稳定的Markov链进行链路丢包率的计算，但Bernoulli模型 在描述链路丢包过程上的局限性影响了该方法的准确性。

由于网络中报文丢失的主要原因是拥塞导致缓冲区溢出，因此报文丢失在时间域上具 有时态依赖性(Temporal Dependency)。如果一个报文丢失在某个节点上，而紧随其后的 报文在此节点上丢失的概率应该很大。针对报文丢失的时态依赖性，有文献提出了一种基 于吉尔伯特(Gilbert)模型的链路丢包率推测方法，使用MLE算法进行参数计算，与基 于Bernoulli模型的测量方法相比，该方法具有更好的准确性。但由于Gilbert模型只能描 述相邻两个报文之间的关系，因此随着链路丢包率的升高，其测量误差也明显增大。

发明内容

本发明目的是为了解决现有报文丢失率测量技术的测量误差大的问题，提供了一种基 于扩展吉尔伯特模型的链路丢包率测量方法。

本发明所述基于扩展吉尔伯特模型的链路丢包率测量方法，从源节点o以组播方式向 叶节点发送n个探测包，叶节点观测到的测量结果序列X_k＝(x_k，1，x_k，2，...，x_k，n)，若叶 节点k接收到探测包i，则x_k，i＝1；否则x_k，i＝0，i＝1，2，...，n；

内部节点接收探测包序列Y_c＝(y_c，1，y_c，2，...，y_c，n)，若内部节点c接收到探测包i， 则y_c，i＝1；否则y_c，i＝0，c＝1，2，...，r，r为内部节点的数量；

链路(f(k)，k)上的丢包率为θ_k＝p_ab(a，b＝0，1，2，3)，整个网络丢包模型参数为 Θ＝(θ₁，θ₂，θ₃，...θ_r)，

该方法包括以下步骤：

步骤一、初始化：根据叶节点观测到的测量结果序列X_k初始化内部节点接收探测包序 列Y⁽⁰⁾，内部节点接收探测包序列Y⁽⁰⁾内部的因子按公式

进行初始化；

按公式

$p_{\mathrm{ab}}=\left(\begin{array}{cc}\underset{l=1}{\overset{M}{\Sigma }}{m}_l/m_0& a=0;b=1\\ \underset{l=4}{\overset{M}{\Sigma }}{m}_l/\underset{l=3}{\overset{M}{\Sigma }}{m}_l& a=3;b=3\\ \underset{l=b}{\overset{M}{\Sigma }}{m}_l/\underset{l=a}{\overset{M}{\Sigma }}{m}_l& a=\mathrm{1,2};b=a+1\\ 1-p_{\left(a\right)(b+1)}& a=\mathrm{0,1,2};b=0\\ 1-p_{\left(a\right)\left(a\right)}& a=3;b=0\end{array}\right)$

初始化各链路丢包模型参数Θ⁽⁰⁾，式中l为连续丢失报文的长度，l∈[0，M]，m_l表示 报文连续丢失长度为l的个数，M表示报文连续丢失长度的最大值；

步骤二、由上而下对内部各节点接收探测包序列进行采样，第Q次采样结果为Y^(Q)， 前Q次采样结果Y＝(Y⁽¹⁾，Y⁽²⁾，...，Y^(Q))，得到r条Markov链，

每个内部节点的采样，按如下公式判断该内部节点的条件后验概率分布：

$p(y_{c,j}=0|X,Y_{c,-j},\Theta )$

$\propto \underset{k\in R\left(c\right)}{\Pi }p\left(x_{k,j}\right|y_{c,j}=0)·\underset{m=1}{\overset{3}{\Pi }}p(y_{c,m}=0|y_{c,j-m},{\theta }_1)$

$=\underset{k\in R\left(c\right)}{\Pi }(1-x_{k,j})[p_{01}{y}_{c,j-1}+p_{12}(1-y_{c,j-1})y_{c,j-2}$

$+p_{23}(1-y_{c,j-1})(1-y_{c,j-2})y_{c,j-3}$

$+p_{33}(1-y_{c,j-1})(1-y_{c,j-2})(1-y_{c,j-3})]$

$p(y_{c,j}=1|X,Y_{c,-j},\Theta )$

$\propto \underset{k\in R\left(c\right)}{\Pi }p\left(x_{k,j}\right|y_{c,j}=1)·\underset{m=1}{\overset{3}{\Pi }}p(y_{c,j}=1|y_{c,j-m},{\theta }_1)$

$=\underset{k\in R\left(c\right)}{\Pi }[(1-x_{k,j}){\alpha }_k+x_{k,j}(1-{\alpha }_k)][\left(p_{00}{y}_{c,j-1}\right)$

$+p_{10}(1-y_{c,j-1})y_{c,j-2}+p_{20}(1-y_{c,j-1})(1-y_{c,j-2})y_{c,j-3}$

$+p_{30}(1-y_{c,j-1})(1-y_{c,j-2})(1-y_{c,j-3})]$

式中R(s)为内部节点c对应的叶节点集合；

步骤三、按照公式

$p_{\mathrm{ab}}=\left(\begin{array}{cc}\underset{l=1}{\overset{M}{\Sigma }}{m}_l/m_0& a=0;b=1\\ \underset{l=4}{\overset{M}{\Sigma }}{m}_l/\underset{l=3}{\overset{M}{\Sigma }}{m}_l& a=3;b=3\\ \underset{l=b}{\overset{M}{\Sigma }}{m}_l/\underset{l=a}{\overset{M}{\Sigma }}{m}_l& a=\mathrm{1,2};b=a+1\\ 1-p_{\left(a\right)(b+1)}& a=\mathrm{0,1,2};b=0\\ 1-p_{\left(a\right)\left(a\right)}& a=3;b=0\end{array}\right)$

计算各链路丢包模型参数Θ，并按照各节点接收探测包的情况计算链路丢包率 A＝(α₁，α₂，α₃，...，α_Q)，Q为链路的数量，

第Q次的计算结果为Θ^(Q)与A^(Q)，前Q次丢包模型参数与丢包率为 Θ＝(Θ⁽¹⁾，Θ⁽²⁾，...，Θ^(Q))与A＝(A⁽¹⁾，A⁽²⁾，...，A^(Q))；

步骤四、根据丢包率A判断采样得到的r条Markov链是否稳定，

若稳定，执行步骤五；若不稳定，执行步骤二；

步骤五、继续采样N次，得到N个链路丢包率A′＝(A^(Q+1)，A^(Q+2)，...，A^(Q+N))，并根据公 式$\hat{A}=\frac{A^{(Q+1)}+A^{(Q+2)}+...+A^{(Q+N)}}{N}$

获取各链路丢包率的估计值完成链路丢包率测量，

其中，N＝40～80。

本发明的优点：针对目前基于网络断层扫描技术的链路报文丢失率测量方法存在的缺 陷，本文提出一种基于扩展Gilbert模型的链路丢包率测量方法，使用扩展Gilbert模型进 行链路丢包过程的描述。由于扩展Gilbert模型在描述链路丢包过程中的优势，使本方法 与基于Bernoulli模型及Gilbert模型的测量方法相比在测量准确性方面得到了提高。随着 链路丢包率的升高，这种优势更加明显，在链路丢包率达到50％时，测量准确率提高了 50％左右。

附图说明

图1是现有网络逻辑拓扑结构图；

图2是现有Gilbert丢包模型示意图；

图3是四状态扩展Gilbert丢包模型示意图；

图4是简易网络拓扑结构图；

图5是本发明所述基于扩展吉尔伯特模型的链路丢包率测量方法的流程图。

具体实施方式

具体实施方式一：下面结合图1至图5说明本实施方式，本实施方式所述基于扩展吉 尔伯特模型的链路丢包率测量方法，从源节点o以组播方式向叶节点发送n个探测包，叶 节点观测到的测量结果序列X_k＝(x_k，1，x_k，2，...，x_k，n)，若叶节点k接收到探测包i，则 x_k，i＝1；否则x_k，i＝0，i＝1，2，...，n；

内部节点接收探测包序列Y_c＝(y_c，1，y_c，2，...，y_c，n)，若内部节点c接收到探测包i， 则y_c，i＝1；否则y_c，i＝0，c＝1，2，...，r，r为内部节点的数量，同时也等于网络中的链路数 量；

链路(f(k)，k)上的丢包率为θ_k＝p_ab(a，b＝0，1，2，3)，整个网络丢包模型参数为 Θ＝(θ₁，θ₂，θ₃，...θ_r)，

该方法包括以下步骤：

步骤一、初始化：根据叶节点观测到的测量结果序列X_k初始化内部节点接收探测包序 列Y⁽⁰⁾，内部节点接收探测包序列Y⁽⁰⁾内部的因子按公式

进行初始化；

按公式

$p_{\mathrm{ab}}=\left(\begin{array}{cc}\underset{l=1}{\overset{M}{\Sigma }}{m}_l/m_0& a=0;b=1\\ \underset{l=4}{\overset{M}{\Sigma }}{m}_l/\underset{l=3}{\overset{M}{\Sigma }}{m}_l& a=3;b=3\\ \underset{l=b}{\overset{M}{\Sigma }}{m}_l/\underset{l=a}{\overset{M}{\Sigma }}{m}_l& a=\mathrm{1,2};b=a+1\\ 1-p_{\left(a\right)(b+1)}& a=\mathrm{0,1,2};b=0\\ 1-p_{\left(a\right)\left(a\right)}& a=3;b=0\end{array}\right)$

初始化各链路丢包模型参数Θ⁽⁰⁾，式中l为连续丢失报文的长度，l∈[0，M]，m_l表示 报文连续丢失长度为l的个数，M表示报文连续丢失长度的最大值；

步骤二、由上而下对内部各节点接收探测包序列进行采样，第Q次采样结果为Y^(Q)， 前Q次采样结果Y＝(Y⁽¹⁾，Y⁽²⁾，...，Y^(Q))，得到r条Markov链，

每个内部节点的采样，按如下公式判断该内部节点的条件后验概率分布：

$p(y_{c,j}=0|X,Y_{c,-j},\Theta )$

$\propto \underset{k\in R\left(c\right)}{\Pi }p\left(x_{k,j}\right|y_{c,j}=0)·\underset{m=1}{\overset{3}{\Pi }}p(y_{c,m}=0|y_{c,j-m},{\theta }_1)$

$=\underset{k\in R\left(c\right)}{\Pi }(1-x_{k,j})[p_{01}{y}_{c,j-1}+p_{12}(1-y_{c,j-1})y_{c,j-2}$

$+p_{23}(1-y_{c,j-1})(1-y_{c,j-2})y_{c,j-3}$

$+p_{33}(1-y_{c,j-1})(1-y_{c,j-2})(1-y_{c,j-3})]$

$p(y_{c,j}=1|X,Y_{c,-j},\Theta )$

$\propto \underset{k\in R\left(c\right)}{\Pi }p\left(x_{k,j}\right|y_{c,j}=1)·\underset{m=1}{\overset{3}{\Pi }}p(y_{c,j}=1|y_{c,j-m},{\theta }_1)$

$=\underset{k\in R\left(c\right)}{\Pi }[(1-x_{k,j}){\alpha }_k+x_{k,j}(1-{\alpha }_k)][\left(p_{00}{y}_{c,j-1}\right)$

$+p_{10}(1-y_{c,j-1})y_{c,j-2}+p_{20}(1-y_{c,j-1})(1-y_{c,j-2})y_{c,j-3}$

$+p_{30}(1-y_{c,j-1})(1-y_{c,j-2})(1-y_{c,j-3})]$

式中R(s)为内部节点c对应的叶节点集合；

上述公式中的p₀₁、p₁₂、p₂₃……按公式

$p_{\mathrm{ab}}=\left(\begin{array}{cc}\underset{l=1}{\overset{M}{\Sigma }}{m}_l/m_0& a=0;b=1\\ \underset{l=4}{\overset{M}{\Sigma }}{m}_l/\underset{l=3}{\overset{M}{\Sigma }}{m}_l& a=3;b=3\\ \underset{l=b}{\overset{M}{\Sigma }}{m}_l/\underset{l=a}{\overset{M}{\Sigma }}{m}_l& a=\mathrm{1,2};b=a+1\\ 1-p_{\left(a\right)(b+1)}& a=\mathrm{0,1,2};b=0\\ 1-p_{\left(a\right)\left(a\right)}& a=3;b=0\end{array}\right)$获取。

步骤三、按照公式

$p_{\mathrm{ab}}=\left(\begin{array}{cc}\underset{l=1}{\overset{M}{\Sigma }}{m}_l/m_0& a=0;b=1\\ \underset{l=4}{\overset{M}{\Sigma }}{m}_l/\underset{l=3}{\overset{M}{\Sigma }}{m}_l& a=3;b=3\\ \underset{l=b}{\overset{M}{\Sigma }}{m}_l/\underset{l=a}{\overset{M}{\Sigma }}{m}_l& a=\mathrm{1,2};b=a+1\\ 1-p_{\left(a\right)(b+1)}& a=\mathrm{0,1,2};b=0\\ 1-p_{\left(a\right)\left(a\right)}& a=3;b=0\end{array}\right)$

计算各链路丢包模型参数Θ，并按照各节点接收探测包的情况计算链路丢包率 A＝(α₁，α₂，α₃，...，α_Q)，Q为链路的数量，

第Q次的计算结果为Θ^(Q)与A^(Q)，前Q次丢包模型参数与丢包率为 Θ＝(Θ⁽¹⁾，Θ⁽²⁾，...，Θ^(Q))与A＝(A⁽¹⁾，A⁽²⁾，...，A^(Q))；

步骤四、根据丢包率A判断采样得到的r条Markov链是否稳定，

若稳定，执行步骤五；若不稳定，执行步骤二；

步骤五、继续采样N次，得到N个链路丢包率A′＝(A^(Q+1)，A^(Q+2)，...，A^(Q+N))，并根据公 式$\hat{A}=\frac{A^{(Q+1)}+A^{(Q+2)}+...+A^{(Q+N)}}{N}$

获取各链路丢包率的估计值完成链路丢包率测量，

其中，N＝40～80。

下面结合图3和图4给出一个具体的实施例：

图3为四状态扩展Gilbert模型(LRL模型)结构，其相关参数定义如下：

(1)S_l(l＝0，1，2，3)：链路连续发生l次报文丢失的状态，l＝0时为报文传输成功的 状态；

(2)p_ab(a，b＝0，1，2，3)：链路丢包由状态a转换到状态b的概率。

在给定链路丢包率先验概率分布的情况下，通过Gibbs采样连续抽样获得各参数及隐藏 变量的Markov链，在Markov链稳定后，继续抽样若干轮次得到链路丢包模型参数的估计值 。图4给出一个四节点的网络拓扑，从源节点o以组播方式向叶节点(节点2和节点3)发送 n个探测包，叶节点观测到的测量结果序列X_k＝(x_k，1，x_k，2，...，x_k，n)，k＝2，3，若叶节点k接收 到第j(j＝1，2，...n)个探测包，则x_k，j＝1；否则x_k，j＝0。内部节点(节点1)接收探测包序列 Y_i＝(y_i，1，y_i，2，...，y_i，n)，i＝1，若内部节点i接收到第j(j＝1，2，...n)个探测包，则y_i，j＝1；否则 y_i，j＝0。链路(f(r)，r)上的丢包率为θ_r，整个网络丢包模型参数为Θ＝(θ₁，θ₂，θ₃)。

假设各链路报文丢失的先验概率符合Beta分布：

θ_r～Beta(a_r，b_r)，r＝1，2，3

联合后验概率分布密度函数为：

$p(\Theta ,X,Y)\propto \underset{j=1}{\overset{n}{\Pi }}\underset{k=2}{\overset{3}{\Pi }}p\left(y_{i,j}\right|\Theta ,X)·p(\Theta ,X)$

$\propto \left[{{\theta }_1}^{a_1-1+\underset{j=1}{\overset{n}{\Sigma }}(1-y_{1,j})}{(1-{\theta }_1)}^{b_1-1+\underset{j=1}{\overset{n}{\Sigma }}{y}_{1,j}}\right]$

$·\left[{{\theta }_2}^{a_2-1+\underset{j=1}{\overset{n}{\Sigma }}{y}_{1,j}(1-x_{2,j})}{(1-{\theta }_2)}^{b_2-1+\underset{j=1}{\overset{n}{\Sigma }}{y}_{1,j}{x}_{2,j}}\right]$

$·\left[{{\theta }_3}^{a_3-1+\underset{j=1}{\overset{n}{\Sigma }}{y}_{1,j}(1-x_{3,j})}{(1-{\theta }_3)}^{b_3-1+\underset{j=1}{\overset{n}{\Sigma }}{y}_{1,j}{x}_{3,j}}\right]$

由联合后验概率分布密度函数可以得到链路丢包模型参数Θ及隐藏变量Y的条件后验 概率分布，通过条件后验概率分布抽样抽取Θ和Y，获得稳定的Markov链，从而计算各链 路丢包模型参数的估计值。

具体实施方式二：本实施方式对实施方式一作进一步说明，N＝50。

具体实施方式三：本实施方式对实施方式一作进一步说明，步骤四中根据丢包率A判 断采样得到的Markov链是否稳定的过程为：

前Q次采样中的前10％采样值与后20％抽样值数学期望的绝对误差是否超过门限值， 若超过，表示稳定；若不超过，表示不稳定；

门限值取值范围为1×10^-3～2×10^-3。