一种链路丢包率的推测方法

摘要

本发明涉及一种基于内部监测器的链路丢包率的推测方法，该方法在初始逻辑拓扑树内部放置监测器，并收集初始逻辑树的所有观测数据，然后建立每棵子树对应的叶子节点的丢包序列，从而推测出它内部每条链路的丢包率。本发明具有低复杂度、估计出的丢包率更接近于真实丢包率的优点。

说明书

技术领域

本发明涉及一种网络推测方法，尤其是一种基于内部监测器的链路丢包率的推测方法。

背景技术

网络测量是实现对网络的监控与管理的必要条件。但是随着现在互联网及通信网络的规模与复杂度的不断增长，它们逐渐演化成一种松散控制的分布式系统。这种分布式网络使得网络内部链路的性能信息的收集变得很困难，传统的基于路由层的排队模型去分析网络性能的方法越来越不适应于这种大规模网络。近年来国际上提出了一种新的测量技术，称为网络层析成像。它主要通过端到端的测量来推断网络内部的性能参数，如链路丢包率、延迟。

链路丢包率是反映网络内部性能最重要的参数之一。目前网络层析技术中推断链路丢包率的方法主要是最大似然估计方法、EM(Expectation Maximiation，期望最大化，下同)以及伪似然估计方法等等。但是似然估计方法需要求解一组高阶方程的根，而EM方法需要通过不断的迭代去逼近一个极限值。随着网络节点数的增多，这些方法的复杂度与计算时间会急剧的增加，从而限制了这些方法在实际中的使用。

目前已有的推测链路丢失率的方法都是基于叶子节点的观测结果，对于内部节点的包丢失情况是毫无所知的。如果在某个内部节点部署了一个监测器，那么这个节点对应的包丢失序列就能被观测到。

发明内容

本发明的目的是提供一种低复杂度的基于内部监测器的链路丢包率的推测方法。

本发明的技术方案是：

S1：在指定的初始逻辑拓扑树中，基于子树深度受限的划分方法、监测器数目受限的划分方法对初始逻辑拓扑树进行划分，并在上述划分节点处放置监测器；

S2：收集初始逻辑树的所有叶子节点的观测数据以及所有内部监测器处的观测数据，根据这两部分数据建立每棵子树对应的叶子节点的丢包序列；

S3：对于每棵子树，根据步骤S2得到的丢包序列推测出它内部每条链路的丢包率；

S4：将所有子树的内部链路丢包率集合在一起，得到初始逻辑树的内部链路的丢包率。

步骤S1中所述的基于子树深度受限的划分方法、监测器数目受限的划分方法划分初始逻辑树，放置监测器的方法为：如果所有子树的深度是一定的，则采用子树深度受限的划分方法，使得监测器的数目最小化；如果监测器的数目是一定的，则采用基于监测器数目受限的划分方法，使得所有子树的深度的最大值最小化。

所述的子树深度受限的划分方法包括以下步骤：

S11：对LST进行初始化赋值LST＝T，这里LST为所有划分得到的子树中深度最大的那棵子树，T为初始逻辑拓扑树；

S12：在满足$H\left(k\right)=\underset{j\in R_{\mathrm{LST}}}{\max }H\left(j\right)$的条件下，得到一个叶子节点k，这里R_LST指的是LST的叶子节点的集合，H(j)是指节点j到LST的根节点的距离；

S13：根据fⁿ(k)＝f(f^(n-1)(k))递归地得到上述节点k的祖先节点在节点k与之间有h_max条链路，；

S14：在内部节点部署一个监测器，那么就能得到一棵以为根节点的子树，它的深度是h_max；

S15：原来的树T被部署的监测器分成了若干棵子树，在这些子树中找出LST，如果LST的深度大于h_max，转到第S12步，否则，退出。

所述的监测器数目受限的划分方法包括以下步骤：

S21：如果监测器的数目不超过M，对于二叉树而言，得到子树深度的最大值的上界为H_upper＝max{[log₂ M]+1，H-1-[log₂ M]}；

S22：利用子树深度受限的划分方法得到监测器的数目F(Hu_pper)，而且满足M≥F(H_upper)；

S23：令h＝H_upper，如果M≥F(h)，则h值减1，并循环再次判断，直到当满足M＜F(h)时退出，把最后得到的h值赋给H_end，并满足F(H_end)＞M≥F(H_end+1)的条件。

S24：令S＝H_end+1，得到子树的最大深度为S，然后根据子树深度受限的树的划分方法来部署F(H_end+1)≤M个监测器。

步骤S3中是采用显示公式方法或最大似然估计MLE方法或期望最大化EM方法推断出每棵子树内部每条链路的丢包率，根据子树的规模而定，当子树的规模比较小的时候，可以直接利用MLE算法来求，；当子树的规模比较大的时候，可以根据显式公式直接的求出来。

根据仿真结果表明，在初始逻辑树中放入监测器的方法求出的链路丢包率比不放监测器的方法在同等条件下求出的链路丢包率更接近真实的丢包率，而且分成的各棵子树的丢包率彼此独立，推断过程可以并行进行，从而减小了计算的复杂度。

附图说明

图1是本发明的基于内部监测器的链路丢包率的推测方法的流程图；

图2是本发明的基于子树深度受限的划分算法流程图；

图3是本发明的基于监测器数目受限的划分算法流程图。

具体实施方式

以下实施例用于说明本发明，但不用来限制本发明的范围。

参考图1，基于内部监测器的链路丢包率的推测方法是在网络接口上先后按以下步骤依次实现的：

步骤(1)：对于给定网络的逻辑拓扑树，在逻辑树的内部放置一些监测器，将它划分为若干棵子树。具体的划分算法有两种：1)所有子树的深度的最大值是给定的，怎样部署监测器使得监测器的数目最小化，我们给出了算法TDA-DL，其算法的流程图如图1所示，并且它是最优的；2)监测器的数目是给定的，怎样部署监测器使得所有子树的深度的最大值最小化。我们给出了算法TDA-ML，其算法的流程图如图2所示。当初始逻辑树被部署的监测器划分为若干棵子树后，每个监测器既作为某棵子树的根节点，起着包的发送者的作用。又作为另一棵子树的叶子节点，起着包的接收者的作用。

步骤(2)：收集初始逻辑树的所有叶子节点的观测数据以及所有内部监测器处的观测数据，由这两部分数据便可以得到每棵子树的对应的叶子节点的丢包序列。

步骤(3)：对每棵子树，根据它叶子节点的丢包序列可以推断出它内部每条链路的丢包率。具体的推测方法可以采用最大似然估计、EM(expectation maximiation)或者根据显式公式直接的求出，到底采用哪种方法可以根据子树的规模来定。当子树的规模比较小的时候，可以直接利用最大似然估计算法来求，因为最大似然估计算法的精度是全局最优的，而此时的计算复杂度也比较小。当子树的规模比较大的时候，可以根据显式公式直接的求出来，由于它只需要直接的数值计算，不需要解方程或迭代，大大减小了计算的复杂度。

步骤(4)：由于最初逻辑树的每条链路必然作为某个子树的链路存在，将所有子树的内部链路的丢包率集合在一起，就得到了初始逻辑树的内部每条链路的丢包率。

参考图2和图3，下面给出上述步骤的详细描述。

首先建立待测网络的丢包模型。我们这里针对的待测网络是树状拓扑，而且它对应的逻辑拓扑结构(其实就是一棵逻辑树)是已知的，并且在测量的过程中保持不变。用符号将这棵逻辑树简记为T＝(V，L)，其中V是所有的节点集合，L是所有的链路集合。树的根节点0是探测包的发送者，所有的叶子节点是探测包的接收者，所有叶子节点构成的集合用R表示，显然有$R⋐V.$对于除了根节点以外的每个节点k∈V/{0}，都有一个唯一的父亲节点f(k)。进一步，递归地定义k的祖先节点j＝fⁿ(k)＝f(f^(n-1)(k))，也可以写成k＜j或者j＞k。为简单起见，我们用(f(k)，k)∈L来表示链路k。对于叶子节点以外的每一个节点k，它的孩子节点的数目为d(k)，孩子节点的集合为$D\left(k\right)=\left\{d_k^i\right|1\le i\le d\left(k\right)\}.$像图论中一样，我们把以节点k为根节点的子树记为T(k)＝(V(k)，L(k))，T(k)中包含的叶子节点的集合为R(k)＝R∩V(k)。

我们假定每条链路的丢包服从Bernoulli伯努利分布，而且不同链路上的丢包与同一条链路上的丢包彼此独立。探测包在链路k∈L上丢失的概率为θ_k。用随机过程X＝(X_k)_k∈V来表示探测包在网络中的丢失情况，其中X_k的取值为0或1。当探测包到达节点k时，X_k取值为1，否则取值为0。从而对于节点k和它的孩子节点j∈D(k)，它们的丢包满足如下关系：1)如果X_k＝0，那么有X_j＝0；2)P[X_j＝0|X_k＝1]＝θ_j及P[X_j＝1|X_k＝1]＝1-θ_j。如果从根节点发送了N个探测包，那么X_k⁽ⁱ⁾(1≤i≤N)表示在节点k处对应的0-1序列。如果$X_k^{\left(i\right)}=1,$表示节点k收到了第i个探测包，否则表示没有收到。

在若干待测网络的内部节点放置监测器，把原来的整棵逻辑树T分成若干棵子树。目前已有的推测链路丢失率的方法都是基于叶子节点的观测结果，对于内部节点的包丢失情况是毫无所知的。如果在某个内部节点部署了一个监测器，那么这个节点对应的包丢失序列就能被观测到。下面讨论的就是如何在原来的逻辑树中部署监测器，我们把这个问题转化为两个子问题：

1.如果所有子树的深度的最大值是给定的，那么怎样部署监测器使得监测器的数目最小化。

2.如果监测器的数目是给定的，那么怎样部署监测器使得所有子树的深度的最大值最小化。

我们用M来表示监测器的数目，用h_max来表示所有子树的最大深度。如果要使得监测器的数目尽量少，那么我们要尽可能的每棵子树的深度接近或等于h_max。对于每一个叶子节点k，定义H(k)为它到树的根节点的距离，那么树的深度$H=\underset{i\in R}{\max }H\left(i\right).$把所有划分得到的子树中深度最大的那棵子树(如果有多棵的话，任意选出其中一棵)用LST表示。对于第一个子问题，我们提出了一种名为子树深度受限TDA-DL的树的划分算法。如图2所示。

算法1：TDA-DL

初始化LST＝T，T是最初的深度最深的子树。

对于找到的LST，选出一个叶子节点k，它满足$H\left(k\right)=\underset{j\in R_{\mathrm{LST}}}{\max }H\left(j\right),$这里R_LST指的是LST的叶子节点的集合。

根据fⁿ(k)＝f(f^(n-1)(k))递归地找到上面选出的节点k的祖先节点由于LST的深度大于h_max，从而肯定存在。

在节点k与之间有h_max条链路，我们在内部节点部署一个监测器，那么就能得到一棵以为根节点的子树，它的深度是h_max。

原来的树T被部署的监测器分成了若干棵子树，在这些子树中找出LST，如果LST的深度大于h_max，转到第2步，否则，退出。

下面来证明这种算法是最优的。

如果h_max是给定的，M_alg表示TDA-DL算法所需要的监测器的数目，M_min表示理论上所需要的最少的监测器的数目。那么有M_alg＝M_min。

下面我们给出上面结论的证明。如果节点j和k满足k＝fⁿ(j)或j＝fⁿ(k)，其中n为正整数，那么用d(j，k)＝n来表示节点j和k的距离。如果不满足，我们用j∨k来表示节点j和k最近的共同祖先节点，这个时候，节点j和k的距离定义为d(j，k)＝max{d(j，j ∨k)，d(k，j∨k)}。在TDA-DL算法的第2步中，选出LST中距离根节点中距离最远的一个叶子节点，用v_i表示第i次选出的节点。由于TDA-DL算法一共部署了M_alg个监测器，那么所有选出来的节点的集合是根据TDA-DL算法中监测器部署的方法，除了最后一棵子树，划分出的前M_alg棵子树的深度都等于h_max。那么对于任意的两个节点v_i和v_j(i≠j)，都满足d(v_i，v_j)≥h_max，当且仅当v_i＜v_j或v_j＜v_i时，d(v_i，v_j)＝h_max成立。下面我们证明无论采取什么样的部署策略都需要M_alg个监测器来覆盖选出来的M_alg个节点一个监测器覆盖的范围是到它的距离不大于h_max的所有的节点。如果d(v_i，v_j)＞h_max，那么需要两个监测器才能覆盖v_i和v_j。如果d(v_i，v_j)＝h_max，那么有v_i＜v_j或v_j＜v_i。不失一般性，假定为v_i＜v_j。表面看上去只需要在v_j处部署一个监测器就能把v_i和v_i都能覆盖，但实际上，此时v_j会作为另外一棵子树的叶子节点，我们需要另外一个监测器去覆盖它。所以在d(v_i，v_j)＝h_max的情况下仍然需要部署两个监测器去覆盖v_i和v_j。这说明对于选出的M_alg个节点，一个监测器不管部署在哪里都只能覆盖其中的一个。所以我们需要至少M_alg个监测器才能覆盖这M_alg个节点，这意味着M_alg≤M_min。由于M_min表示理论上所需要的最少的监测器的数目，从而有M_alg≥M_min。从而可以推出M_alg＝M_min。

由于TDA-DL是最优的，从而对于一个给定的网络和h_max，就可以用TDA-DL算法得到M_min，我们用M_min＝F(h_max)表示。

第二个子问题是怎样部署给定的M个监测器使得划分子树的深度的最大值最小化。这里我们提出了一种基于TDL-DL的名为TDL-ML的算法来解决这个问题，如图3所示。

算法2：TDA-ML

1.如果我们部署的监测器的数目不超过M，那么子树深度的最大值h_max会有一个上界，首先我们找出这个上界。对于二叉树而言，我们在原来子树的第[log₂ M]+1层的所有节点都部署上监测器，这至多需要$2^{\left[{\log }_{2}M\right]}\le M$个监测器。依照这种方法分成子树的深度的最大值为max{[log₂ M]+1，H-1-[log₂ M]}，记为H_upper，那么H_upper是h_max的一个上界。

2.用TDL-DL可以得到监测器的数目F(H_upper)，而且满足M≥F(H_upper)。令h＝H_upper，如果M≥F(h)，则h值减1，并循环再次判断，直到当满足M＜F(h)时退出，把最后得到的h值赋给H_end，它满足F(H_end)＞M≥F(H_end+1)。

3.令S＝H_end+1，根据TDL-DL算法我们需要部署F(H_end+1)≤M个监测器。如果在放置监测器数目不多于M的情况下，由于TDL-DL算法是最优的，那么H_end+1就是S的最小值。这个TDL-DL算法在S＝H_end+1时的部署策略也就是我们所需要的。

对于一棵树，给定所有叶子节点的观测结果，下面给出一个用观测结果求出链路丢失率的显式估计。

根据步骤1中逻辑树的丢包模型，对于任何一个内部节点k，可以建立一个一个以它为分叉节点的二层树。这个二层树由一条输入虚拟链路和若干条输出虚拟链路组成。输入虚拟链路代表的是从根节点0到节点k的路径，每条输出虚拟链路代表的是以k的一个孩子节点为根节点的子树。输入虚拟链路的丢包率p_k表示的从根节点发送的探测包没有达到节点k的概率，可以用链路上的丢包率表示

$p_k=1-(1-{\theta }_k)\underset{j>k}{\Pi }(1-{\theta }_j)---\left(1\right)$

从而链路k的丢包率可以用输入虚拟链路的丢包率p_k表示

θ_k＝1-(1-p_k)/(1-p_f(k))    (2)

每条输出虚拟链路代表的是以k的一个孩子节点为根节点的子树，这些子树的集合可以表示为$\left\{T\left(d_k^i\right)\right|1\le i\le d\left(k\right)\},$其中d(k)是节点k的孩子节点的数目。子树T(d_kⁱ)中的叶子节点的集合是R(d_kⁱ)，它是R(k)的子集。对于子树T(k)，定义一个新的随机变量T_k。

$T_k=\left(\begin{array}{c}1,\exists i,i\in R\left(k\right),X_i=1\\ 0,\forall i,i\in R\left(k\right),X_i=0\end{array}\right)$

其中X_i表示在叶子节点k处探测包是否丢失。如果探测包的发送数目为N，那么0-1序列{T_k⁽¹⁾，T_k⁽²⁾，…，T_k^(N)}表示的是子树T(k)对应的丢包情况。子树T(k)的丢包率定义为对于某个探测包，它的每一个叶子节点都没有收到的概率，可以表示成l_k＝P[T_k＝0]。

如果内部节点k有d(k)个孩子节点，那么它的输出虚拟链路为T(d_k¹)，T(d_k²)，…，T(d_k^d(k))。我们做如下定义：

$r_{b_1{b}_2...b_m}\left(k\right)=P\{T_{d_k^1}=b_1;T_{d_k^2}=b_2;...T_{d_k^m}=b_m\}$

以及$r_{b_i}^{\left(i\right)}\left(k\right)=P\{T_{d_k^i}=b_i\}$

其中b_i∈{0，1}(1≤i≤m)。

它们的估计值可以用叶子节点的观测结果直接表示出来：

以及

其中n($T_{d_k^1}=b_1;T_{d_k^2}=b_2;...T_{d_k^m}=b_m$)是观测样本中满足$T_{d_k^1}=b_1;T_{d_k^2}=b_2;...T_{d_k^m}=b_m$的数目，n($T_{d_k^i}=b_i$)是观测样本中满足$T_{d_k^i}=b_i$的数目。下面我们给出输入虚拟链路的丢包率p_k与及的关系式。

对于任一个内部节点k∈V/R∪{0}，

$p_k=1-\overline{p_k}=1-{\left[\frac{\underset{i=1}{\overset{d\left(k\right)}{\Sigma }}{r}_1^{\left(i\right)}\left(k\right)}{r_{11...1}\left(k\right)}\right]}^{1/(d\left(k\right)-1)}---\left(3\right)$

其中r_11...1(k)表示概率$r_{11...1}\left(k\right)=P\{T_{d_k^1}=1;T_{d_k^2}=1;...T_{d_k^{d\left(k\right)}}=1\}.$

根据公式(2)，链路k上的丢包率θ_k的估计值可以表示为

由公式(3)可以得到其中以及根据大数定理，当N→∞时，收敛于真实值r_11...1(k)以及收敛于真实值r₁⁽ⁱ⁾(k)，从而有以及这说明公式(4)中的估计式是θ_k的一致估计，这个估计式是用叶子节点的观测结果显式的求出链路上的丢包率。从而我们可以利用显示公式(3)与(4)求出各个子树内部每条链路的丢包率。