法律状态公告日
法律状态信息
法律状态
2019-03-01
授权
授权
2017-01-11
实质审查的生效 IPC(主分类):H04L12/801 申请日:20161015
实质审查的生效
2016-12-14
公开
公开
技术领域
本发明属于网络拥塞控制领域，具体涉及一种IP网络拥塞链路丢包率范围推断方法。
背景技术
随着IP网络规模的不断扩大和网络结构的复杂多样化，IP网络多链路拥塞现象时有发生，如何及时准确地发现并诊断网络故障(拥塞链路)成为一个研究热点。
IP网络断层扫描(tomography)技术能够通过少量端到端(End-to-End，E2E)路径性能主动探测，利用统计学等相关技术推断IP网络内部各链路性能(如:时延、带宽、丢包率等)，不需要直接访问IP网络内部各路由器/交换机，间接推断出IP网络内部各链路性能。
借助网络tomography技术推断IP网络内部链路性能主要包括三类方法：
(1)analog tomography：该方法是借助单时隙E2E路径性能探测，构建系统线性方程组计算各链路性能值，以实现拥塞链路的推断。但是由于Tomography技术本身要借助少量路径探测覆盖尽可能全部的待测链路，这就易造成方程组系数矩阵奇异，为得到链路性能(如:丢包率)唯一解，需对方程组系数矩阵满秩扩展。另外，因方程组求解涉及复杂的求逆计算，大规模IP网络多链路拥塞极易引发维数灾难，实时性无法保证，甚至导致方法失效。因此，要求各E2E路径性能主动探测时需要保证较高的时钟同步。但由于目前IP网络中路由器的单播支持度高于多播，时钟同步难以保证；而利用类似多播的单播背靠背包测量来获取报文级的相关性以及借助模拟多播的包群探测方法会因时间相关性问题导致该方法推断性能较差。
(2)Boolean tomography：该方法是一种借助布尔(Boolean)代数模型推断拥塞链路的方法，根据各E2E路径性能，推断拥塞路径途经链路的性能状态，利用布尔值指示链路的状态。其中，Nguyen HX等人提出的CLINK算法将概率模型引入到拥塞链路推断中，通过多时隙路径性能探测，避开了单时隙路径探测对时钟同步的强依赖。但是，该算法仅能推断出链路是否拥塞，而无法推断出链路的拥塞程度，拥塞链路性能分辨率低。且CLINK算法在大规模IP网络多链路拥塞场景下，特别是E2E路径中存在多条拥塞链路时，以最小链路覆盖集为准则，当拥塞链路数较多时，特别是一条路径中有多条链路发生拥塞时，仅能定位其中最有可能发生拥塞的一条链路，导致推断性能明显下降。
(3)Range tomography：该方法借助单时隙E2E路径性能探测，以“E2E路径中共享数目最多的瓶颈链路为最有可能发生拥塞的链路”这一经验知识推断拥塞链路及其丢包率范围。但是由于Range tomography假设IP网络中发生拥塞的链路数较少，且以瓶颈链路共享数多少作为拥塞链路推断的经验知识，那么在复杂的IP网络多链路拥塞场景下，该推断方法会存在较大误差，推断性能显著下降。
上述三类算法都存在推断性能较差的问题，而目前也没有文献提出最新的针对大规模IP网络多链路拥塞场景下的链路性能范围推断方法。
发明内容
本发明的目的是针对上述现有技术的不足，而提供一种IP网络拥塞链路丢包率范围推断方法，以解决现有推断方法推断性能较差的问题。
为解决上述技术问题，本发明采用的一个技术方案是：提供一种IP网络拥塞链路丢包率范围推断方法，推断方法的步骤如下：
(1)贝叶斯网模型构建：对初始的待测IP网络进行贝叶斯网模型建模，将待测IP网络中的端到端路径、链路的状态值及各路径与其途径链路的关系分别建模为所述贝叶斯网模型G中的节点和有向边；
(2)拥塞先验概率求解：对待测IP网络中端到端路径进行N次快照，N≥1，获取所述待测IP网络中各端到端路径性能及拓扑结构的探测结果，根据所述探测结果计算各链路拥塞先验概率，包括：
①.简化所述贝叶斯网模型G：根据所述探测结果对所述贝叶斯网模型G进行简化，得到简化模型G'；
②.求解拥塞先验概率：根据所述探测结果，结合所述简化模型G'，学习所述待测IP网络中链路拥塞先验知识，获取各链路拥塞先验概率；
(3)拥塞链路及其丢包率范围推断：根据当前时刻所进行的1次快照获取的各端到端路径性能及拓扑结构探测信息，推断拥塞链路及其丢包率范围，包括：
①.二次简化所述贝叶斯网模型G：对所述简化模型G'再次进行简化，得到所述贝叶斯网模型的二次简化模型G”；
②.推断拥塞链路：结合二次简化模型G”，推断此时最有可能发生拥塞的链路lm；
③.推断拥塞链路丢包率范围：根据推得的所述链路lm对其丢包率范围进行推断；
④.推断其余的拥塞链路及其丢包率范围：根据上一步骤得到的所述链路lm的丢包率范围进行路径移除及丢包率更新，再重复步骤②～④，直至推断过程结束。
在本发明另一个实施例中，所述步骤(3)②推断拥塞链路是基于贝叶斯最大后验估计准则实现的，包括：
A.在所述二次简化模型G”的拥塞路径集合Ρ中，找到具有最小丢包率的路径Pb；
B.基于所述二次简化模型G”，根据贝叶斯原理以及贝叶斯最大后验估计准则推断出最有可能的拥塞链路集合；
C.结合推断出的拥塞链路集合，借助贝叶斯最大后验估计的代价值Cp对拥塞链路进行定位，根据贝叶斯最大后验估计准则，路径Pb中Cp值最小的链路即拥塞路径中最有可能发生拥塞的链路lm，Cp的公式如下：
其中，pj为链路lj的拥塞先验概率，score(lj)为当前时刻待测IP网络中链路lj的路径共享数。
在本发明另一个实施例中，所述步骤B推断各拥塞路径中最有可能的拥塞链路集合时，依据如下最大评分参量表达式：
上述表达式经过简化处理可得：
其中，xj为链路lj以布尔形式表达的状态值，nε为所述拥塞路径集合Ρ中路径途经的链路数。
在本发明另一个实施例中，所述步骤(3)③推断拥塞链路丢包率范围的方法包括：
a.路径集合聚类：在所述拥塞路径集合Ρ中，对包含所述链路lm且与路径Pb相关的路径进行性能相似路径聚类，得到聚类路径集合Ω，所述相关且性能相似路径是指包含同一条链路且丢包率差值的绝对值小于第一阈值的路径；
b.性能相似系数确定：利用所述聚类路径集合Ω中各路径丢包率值，计算路径性能相似系数δ；
c.丢包率范围推断:所述聚类路径集合Ω中，链路lm的丢包率推断范围的计算公式如下：
其中，为所述聚类路径集合Ω中各路径性能平均值，且
在本发明另一个实施例中，所述步骤C中定位最有可能发生拥塞的链路lm时，若所述聚类路径集合Ω中存在不止一条具有相同最小Cp值的链路，则根据初始待测IP网络中链路lj的共享路径数num(lj)值进一步进行判断，将num(lj)值最大的链路确定为最容易拥塞的链路lm。
在本发明另一个实施例中，所述步骤(3)④进行路径移除及丢包率更新的方法如下：
Ⅰ.判断所述聚类路径集合Ω中的每个路径的丢包率是否落在根据步骤③推断得到的链路lm的丢包率范围内，如果在，则将相应路径从所述聚类路径集合Ω中移除，并移除此路径途经的所有链路；如果不在，则不移除此路径，对该路径途径的链路进行下一轮拥塞推断；
Ⅱ.对所述聚类路径集合Ω和Ω'中超出根据步骤③推断得到的链路lm的丢包率范围的路径进行丢包率更新，更新迭代公式如下：
其中，为所述聚类路径集合Ω经过路径移除后的剩余各路径性能平均值；所述Ω'为丢包率与路径Pb的丢包率数值之差大于第二阈值且途经所述链路lm的路径的集合。
在本发明另一个实施例中，所述步骤(3)④推断过程结束的判断原则是所述拥塞路径集合Ρ为空集。
在本发明另一个实施例中，所述步骤(2)②求解拥塞先验概率的过程包括如下步骤：
ⅰ.根据所述探测结果，生成所述简化模型G'的拥塞选路矩阵；
ⅱ.根据所述拥塞选路矩阵构建所述简化模型G'下各对应链路拥塞先验概率求解的布尔代数方程组；
ⅲ.利用所述布尔代数方程组求解所述各链路拥塞先验概率。
在本发明另一个实施例中，所述第一阈值为0.05。
在本发明另一个实施例中，所述第二阈值为0.05。
本发明的有益效果是：本发明的IP网络拥塞链路丢包率范围推断方法借助多时隙E2E路径探测，避开了单时隙探测对时钟同步的强依赖；通过构建待测IP网络贝叶斯网模型,学习各链路拥塞先验概率，作为定位拥塞链路经验知识，定位拥塞链路lm，借助贪婪启发式搜索循环推断出整个待测IP网络中各拥塞链路及其丢包率范围，大大提升了推断性能。通过模拟实验、仿真实验以及Internet实测实验均证实了本发明的推断方法不仅在拥塞链路定位性能上优于CLINK算法及Range>
该方法基于各链路拥塞BMAP准则得出推断时刻各链路拥塞最大后验代价值Cp，定位拥塞路径中最容易发生拥塞的链路lm，代替传统以瓶颈链路作为拥塞链路定位的经验方法，提高拥塞链路定位准确性。
另外，该方法提出聚类途经拥塞链路lm且性能相近路径到聚类路径集合Ω，在集合中动态计算路径集合Ω中的性能相似系数δ，作为推断拥塞链路lm丢包率范围的依据，避免了拥塞链路丢包率范围推断过大造成对多链路拥塞E2E路径的直接移除，保证了拥塞E2E路径中不止一条链路拥塞时，拥塞链路及其性能范围能够被再次推断，有效避免了基于最小链路覆盖集理论造成的拥塞链路推断误差，提高了算法推断性能。
附图说明
图1是本发明IP网络拥塞链路丢包率范围推断方法一实施例的流程图；
图2是本发明IP网络拥塞链路丢包率范围推断方法一实施例中初始待测IP网络的贝叶斯网模型图；
图3是本发明IP网络拥塞链路丢包率范围推断方法一实施例中利用贪婪启发式搜索循环推断拥塞链路及其丢包率范围方法实施例的原理框图；
图4是本发明IP网络拥塞链路丢包率范围推断方法一实施例中利用贪婪启发式搜索循环推断拥塞链路及其丢包率范围方法实施例的流程图；
图5为本发明IP网络拥塞链路丢包率范围推断方法实施例与CLINK、Range tomography算法在多个网络模型中的不同拥塞比例下的推断性能比较图；
图6为本发明IP网络拥塞链路丢包率范围推断方法实施例与CLINK、Range tomography算法在多个网络模型中的不同网络规模下的推断性能比较图；
图7为本发明IP网络拥塞链路丢包率范围推断方法实施例与CLINK、Range tomography算法的推断性能仿真试验流程图；
图8为本发明IP网络拥塞链路丢包率范围推断方法实施例与CLINK、Range tomography算法的Emulab仿真实验结果图。
具体实施方式
为了便于理解本发明，下面结合附图和具体实施例，对本发明进行更详细的说明。附图中给出了本发明的较佳的实施例。但是，本发明可以以许多不同的形式来实现，并不限于本说明书所描述的实施例。相反地，提供这些实施例的目的是使对本发明的公开内容的理解更加透彻全面。
需要说明的是，除非另有定义，本说明书所使用的所有的技术和科学术语与属于本发明的技术领域的技术人员通常理解的含义相同。在本发明的说明书中所使用的术语只是为了描述具体的实施例的目的，不是用于限制本发明。本说明书所使用的术语“和/或”包括一个或多个相关的所列项目的任意的和所有的组合。
如图1所示为本发明提供的一种IP网络拥塞链路丢包率范围推断方法优选实施例的流程图，由图1可知，该方法的步骤如下：
第一步S1：贝叶斯网模型构建，对初始的待测IP网络进行贝叶斯网模型建模，将待测IP网络中的端对端(E2E)路径的测量数据值、链路的状态值建模为贝叶斯网模型G中的节点，将路径与路径途径链路的关系建模为贝叶斯网模型G中的有向边。
本发明利用主动检测的tomography方法推断网络内部各链路性能，具体过程如下：
1>.各探针部署路由器节点向其他节点发送ICP/UDP包(ping及traceroute)，尽可能覆盖整个待测IP网络，ping获取到各探测E2E路径的性能(丢包率、可用带宽、时延等)，traceroute获取到各探测E2E路径途经的链路关系；
2>.借助上述探测获取到的信息，构建待测IP网络内部各链路性能与探测E2E路径性能之间的关系方程或者数学模型，用于对IP网络内部链路性能进行计算或推理。
本实施例的数学模型优选贝叶斯网络模型。贝叶斯网络是一个表示因果关系的有向无环图G＝(ν,ε)，由代表变量节点及连接这些节点有向边构成，ν为节点，代表随机变量，ε为连接节点的有向边，代表了节点间的互相关系(由父节点指向其子节点)，用条件概率进行表达关系强度，没有父节点的用先验概率进行信息表达。根据贝叶斯网络的因果关系以及已知的条件概率和先验概率，可由已知节点的状态(证据节点)推理未知节点(隐藏节点)的状态。
本实施例的待测IP网络构建的贝叶斯网络模型如图2所示，各E2E路径状态变量集合yi为第i条路径的状态变量，各E2E路径途经链路的状态变量集合：xj为第j条链路的状态变量，其中，np为待测IP网络中E2E路径总数，nc为各E2E路径途经的链路总数。在构建IP网络拥塞链路推断的贝叶斯网模型时，Y中的各元素构成模型中的观测变量(证据节点)，X中的各元素构成模型中的隐藏变量(隐藏节点)，各E2E路径及途经链路的连接关系构成模型的有向边。
如图3所示为本发明提供的贪婪启发式拥塞链路及其丢包率范围推断方法(简称CLLRRI)的原理框图，该方法利用主动E2E路径性能探测方法推断网络内部各链路性能，学习各链路拥塞先验概率，作为定位拥塞链路经验知识，计算各E2E路径拥塞概率，生成拥塞选路矩阵，从而计算出各链路拥塞先验概率，再基于(Bayesian Maximum A-Posteriori，BMAP)准则定位拥塞链路，根据当前时刻对IP网络进行的1次性能探测(快照)推断各拥塞链路丢包率范围，具体过程包括如下的步骤S2和S3。
第二步S2：拥塞先验概率求解，对待测IP网络中端到端路径进行N次快照(snapshots)，N≥1，这里的快照是指对对待测IP网络的E2E路径进行性能探测，获取待测IP网络中各端到端路径性能及拓扑结构(这里的拓扑结构是指各E2E路径与其途径链路的对应关系)的探测结果，根据探测结果计算各链路拥塞先验概率。
该方法首先要进行链路拥塞先验知识学习，通过在待测IP网络各叶子节点(指没有子节点的节点，又称为终端节点)部署探针，借助tomography技术，对各E2E路径进行N次性能探测，N≥1，获取各E2E路径性能(丢包率)及各E2E路径途经链路，求解出各链路拥塞先验概率，求解过程如下：
在推断IP网络内部的拥塞链路时，拥塞链路只存在于拥塞路径中，正常路径途经的各链路必为正常状态，不必再进行性能推断。因此，可在链路拥塞先验知识学习过程中，根据N次E2E路径性能探测结果，对拥塞次数小于设置阈值的路径视为正常(如:设置阈值为0，就表明对路径性能要求极高，多次路径性能探测中只要该路径出现1次拥塞，该路径即被视为拥塞路径)，将正常路径对应的观测变量yi及途经链路对应的隐藏变量xj以及有向边从IP网络构建的贝叶斯网推断模型中移除，即对贝叶斯网模型G进行简化，剩余的贝叶斯网模型为一次简化模型G'。
之后根据探测结果，结合简化模型G'，学习待测IP网络中链路拥塞先验知识，获取各链路拥塞先验概率，具体过程如下：
构建拥塞选路矩阵:首先根据图2所示的贝叶斯网模型G构建一个选路矩阵，该选路矩阵的各行为E2E路径Pi(i＝1,2,...np)，各列为IP网络中所有链路lj(j＝1,2,..nc)，按照顺序从小到大依次排列。
本发明借鉴Boolean tomography对性能的表述，将路径及链路性能利用Boolean二进制代数值0、1表示，借助Boolean代数模型对待测IP网络进行拥塞链路推断，即在该待测IP网络中，当第i条路径通时，yi＝0，当第i条路径拥塞时，yi＝1；当第j条链路通时，xj＝0，当第j条链路拥塞时，xj＝1。
根据上述原理，本实施例中当某条E2E路径Pi途经某条链路lj时，选路矩阵对应位置处的元素值Dij＝1，否则Dij＝0；然后，将该选路矩阵中的正常路径及途径链路对应的矩阵行元素和列元素移除，即得对应于简化模型G'的拥塞选路矩阵。
构建各对应链路拥塞先验概率求解的布尔代数方程组:将各端对端路径与该路径途径的各链路之间关系用Boolean代数模型表示为：
式(1)中，为Boolean值最大化操作符，nε为第i条路径途经的链路数；D′ij为拥塞选路矩阵中的元素值，若第j条链路存在于第i条路径中，D′ij＝1，反之，D'ij＝0。
为了对拥塞链路先验概率进行求解，对式(1)两边取数学期望E，转换后可得路径拥塞与链路拥塞关系表达式如(2)式所示。
E[yi]为化简后端对端路径的拥塞概率，其数值是通过N次快照探测出的每次各端对端路径状态Boolean值yi＝{0,1}求和取平均得到的，用表示；pj为第j条链路的拥塞先验概率。
为便于计算，对式(2)两边同时取对数，可得出简化模型G'下拥塞链路先验概率求解布尔代数方程组，整理可得如下式(3)：
利用布尔代数方程组求解各链路拥塞先验概率:将各E2E路径拥塞概率及拥塞选路矩阵中的元素值D'ij带入式(3)，即可求得拥塞路径途经各链路的拥塞先验概率pj。但是，在借助tomography技术进行拥塞链路推断时，通常利用尽可能少的E2E路径探测，覆盖尽可能多的链路，并且通过前述化简操作，易造成式(3)中化简拥塞矩阵对应的E2E路径数小于算法覆盖的链路数，使得式(3)所示的布尔线性方程组系数矩阵不满秩，将无法求出线性方程组唯一解。本发明可通过Vardi>j，这里不再赘述。
第三步S3：得到各链路拥塞先验概率pj之后，就可以按照图4所示的贪婪启发式拥塞链路及其丢包率范围推断流程图，根据当前时刻所进行的1次快照获取的各端到端路径性能及拓扑结构探测信息，推断拥塞链路及其丢包率范围，具体过程如下：
(1)对简化模型G'再次进行简化，得到贝叶斯网络模型的二次简化模型G”：在当前时刻推断拥塞链路及其丢包率范围时，根据当前1次快照获取的各端到端路径性能及拓扑结构探测信息(包括各拥塞路径的丢包率测量值及各路径途径的链路关系)，移除正常E2E路径及其途经链路，将二次简化模型G”中剩余的拥塞路径定义为剩余的拥塞路径集合Ρ，在剩余的拥塞路径集合Ρ中找到具有最小丢包率测量值的路径Pb，再在路径Pb中基于贝叶斯最大后验估计BMAP准则确定最容易发生拥塞的链路lm。
拥塞链路lm的推断过程如下：根据路径E2E性能测量结果，如果路径为正常状态，则其途经的所有链路状态均正常；如果路径为拥塞状态，则该路径途经的链路至少有一条发生拥塞。因此，E2E路径与该路径途经各链路之间应存在如(4)式所示的概率关系：
P(yi＝0|pa(yi)＝{0,...,0})＝1
基于当前剩余贝叶斯网络模型G”，根据各拥塞E2E路径性能集合Y|yi＝1，推理贝叶斯网模型中的隐藏变量X最有可能的一组取值(拥塞链路集合χ|xj＝1)。由贝叶斯原理以及BMAP准则利用最大评分参量(argmax)进行求解，其公式如下:
式(5)中，P(Y)仅与IP网络状态及路径性能探测结果有关，而与链路选取无关，故式(5)可简化为：
argmaxP(X|Y)＝argmaxP(X,Y)＝argmax{P(xj)·P[(yi|pa(yi)]}(6)
式(6)中，pa(yi)为贝叶斯网中yi的父节点。
为了最大化目标函数，由式(4)可知，P[yi|pa(yi)]最大值等于1。由于IP网络中各链路状态是概率独立的随机变量，对当前IP网络进行1次E2E路径性能探测，推断各链路拥塞概率分布律的过程，服从贝努利概率模型中的二项概率公式n＝1，故待测IP网络各链路拥塞全概率公式如(7)式所示:
推断最有可能发生拥塞的链路集合，即求解式(7)中P(xj)取得最大值时对应xj＝1的拥塞链路，即:
对式(8)两边取对数可得(9)式:
式(9)中，lg(1-pj)的取值与链路状态xj取值无关，故求解argmaxP(X|Y)即求解xj·lg[pj/(1-pj)]的最大值，而取得最大值时对应的链路集合即各拥塞路径中最容易发生拥塞的链路组成的集合。因此，式(9)可简化为(10)式:
借助BMAP代价值Cp来定位路径Pb中的拥塞链路。Cp表达式如(11)式所示:
其中，pj为链路拥塞学习过程中学习到的各链路lj的拥塞先验概率，score(lj)为当前时刻链路lj在E2E拥塞路径中的路径共享数。根据BMAP准则，Cp值最小的链路即拥塞路径中最容易发生拥塞的链路lm，需要说明的是这里的各链路lj均为路径Pb中的链路。
另外，如果聚类路径集合Ω中存在不止一条具有相同最小Cp值的链路，则根据初始待测IP网络中各链路lj的共享路径数num(lj)值进一步进行判断，将num(lj)值最大的链路确定为最容易拥塞的链路lm。
(2)确定最容易发生拥塞的链路lm后，就可以推断该链路lm的丢包率范围，具体过程如下：
a.路径集合聚类，对拥塞路径集合Ρ中，对包含链路lm且与路径Pb相关的路径进行性能(路径丢包率)相似路径聚类，得到聚类路径集合Ω。这里的性能相似路径是指包含同一条链路且丢包率差值的绝对值小于第一阈值的路径，这里的第一阈值优选0.05，则对应的数学表达式为|Φ(P1)-Φ(Pb)|＜0.05，该表达式中的P1与Pb即为相关且性能相似的路径。
在待测IP网络中，各路径的传输率Ψi与该路径途经各链路的传输率之间关系式如下：
其中，Ψi为第i条路径Pi的传输率，为该路径下途经的第j条链路的传输率。由于传输率＝1-丢包率，根据公式(12)可得出路径丢包率与途经各链路丢包率之间的关系表达式：
其中，Φ(Pi)为路径Pi的丢包率，φ(lj)为该路径途经的第j条链路的丢包率。
在IP网络中，E2E路径中每增加一条拥塞链路(通常，以丢包率≥0.05的链路界定为拥塞链路)，路径丢包率至少增加约0.05。为了确保推断出拥塞链路lm后，包含链路lm路径中其他拥塞链路能被继续推断，而不以最小链路覆盖集理论移除该链路所在路径，带来推断误差。本发明提出的推断方法中，将途经链路lm的各路径丢包率与路径Pb的丢包率数值之差大于第二阈值的路径存放至另一个路径集合Ω'中，这里的第二阈值优选0.05。
b.性能相似系数确定，为了避免Range tomography算法中需要通过大量实验确定a-similar系数的繁琐过程，本发明的推断方法提出一种利用聚类路径集合Ω中各E2E路径丢包率值，在线动态计算各条路径的性能相似系数δ的方法，δ求解公式如下:
其中，分别为聚类路径集合Ω中丢包率的最大值和最小值，这里聚类路径集合Ω中各路径丢包率都已通过对当前IP网络进行的E2E路径性能探测得到。
c.丢包率范围推断，聚类路径集合Ω中，链路lm的丢包率推断范围满足如下不等式:
聚类路径集合Ω中，各E2E路径性能平均值为：且满足如下不等式:
将式(15)、(16)代入式(14)，可得如下不等式:
由上式可得拥塞链路lm的丢包率范围，计算公式如下:
对上述公式(18)进行证明：当时，根据公式(17)可得整理后为：当时，根据公式(17)可得整理后为：由此可得
(3)推断其余的拥塞链路及其丢包率范围，由于大规模IP网络存在多链路拥塞现象，为了能够推断拥塞E2E路径是否存在其他拥塞链路，对集合Ω中的路径进行判断，具体判断方法如下:
①判断聚类路径集合Ω中的每个路径的丢包率是否落在推断出的链路lm的丢包率范围内，如果在，意味着此路径不再包含其他拥塞链路，则将相应路径从聚类路径集合Ω中移除，不再进入下一轮推断，并移除此路径途经的所有链路；如果不在，则不移除此路径，对该路径途径的链路进行下一轮拥塞推断；
②对聚类路径集合Ω和Ω'中超出链路lm的丢包率范围的路径进行丢包率更新，更新迭代公式如下：
其中，这里的为聚类路径集合Ω经过路径移除后的剩余各路径性能平均值，即经过路径移除后当前路径集合中各E2E路径性能平均值。
通过路径移除以及路径丢包率更新后，再次推断当前剩余路径集合Ρ中的拥塞链路及其丢包率范围，如此循环，直到路径集合Ρ为空集φ时，推断过程结束。
本发明推断方法的推断过程如图4所示，具体流程如下：
1)借助N次E2E路径性能探测结果，学习待测IP网络各链路拥塞先验概率pj；
2)根据当前时刻各E2E路径丢包率，在最小丢包率路径pb中，基于BMAP准则，推断pb中最有可能发生拥塞的链路lm；
3)聚类包含拥塞链路lm且性能相似的路径集合Ω；
4)利用Ω中的路径性能相似系数δ推断Ω丢包率范围；
5)判断Ω中各路径丢包率是否落在lm推断的丢包率范围内，如果在，移除此路径，如果路径丢包率不在lm的丢包率范围内，则对该路径途经的其他链路继续进行下一轮拥塞推断，不移除此路径，进入第6)步；
6)更新包含lm的路径丢包率；
7)返回第2)步，循环推断拥塞链路及其丢包率范围，直到拥塞路径集合为空，推断过程结束。
该方法实施例的伪代码如下：
本发明的推断方法在进行拥塞链路lm丢包率范围推断时，引入了性能相似路径聚类策略，避免了拥塞链路丢包率范围推断过大造成对多链路拥塞E2E路径的直接移除，保证了拥塞E2E路径中不止一条链路拥塞时，拥塞链路及其性能范围能够被再次推断，有效避免了基于最小链路覆盖集理论造成的拥塞链路推断误差，提高了算法推断性能。
下面通过实验来验证本发明IP网络拥塞链路丢包率范围推断方法的有效性。
时间复杂度分析：本发明提出的推断方法CLLRRI借助贪婪启发式搜索策略，利用Java语言在Eclipse MARS.1平台上进行程序编写，并在相同IP网络拥塞场景中，与CLINK算法及Range tomography算法进行模拟实验、仿真实验及实测Internet实验比较，实验验证了本发明提出的推断方法CLLRRI在拥塞链路定位及其丢包率范围推断中的有效性及准确性。在对300个节点、527条链路组成的IP网络拓扑仿真模型中，本发明的推断方法推断拥塞链路及其丢包率范围的运行时间不超过2s，保证了实时性需求。
实验评价：通常，评价方法性能的实验方法有三种:模拟实验，仿真实验和实测实验。其中，模拟实验方法标准答案(benchmark)已知，实验细节可以完全掌握，但缺点是不够真实；仿真实验方法兼顾实验的可控性与真实性，操作灵活；实测实验环境真实，但较难获取benchmark。因此，为了客观评价本发明提出算法的性能表现，分别采用模拟实验、Emulab仿真实验以及Internet实测实验三种方法分别对本发明的推断方法CLLRRI与CLINK算法、Range tomography算法进行性能比较评价。
1.模拟实验评价
为了验证推理算法的有效性及准确性，本发明借助Brite拓扑生成器，分别生成三种不同类型，规模的IP网络拓扑模型。其中，Waxman模型中的节点度数值随着节点数量的增加而增加，但无法生成节点众多但节点平均度值较小的网络。因IP网络规模的不断扩大，新路由器节点加入通常倾向于与具有高度数值的“大节点”连接。BA及GLP正是基于这两个特征构造的具有度分布呈幂率特征的无标度网络模型。三种拓扑网络模型均体现了Internet特性，为了更好地验证本发明的推断方法CLLRRI在不同网络环境中的拥塞链路推理性能，在Eclipse MARS.1平台下将三种不同网络模型拓扑文件导入。
1.1验证方法及场景设置
使用丢包率模型LM1仿真IP网络中各链路拥塞事件，由于IP网络中各拥塞链路的丢包率通常不超过0.2。因此，在模拟真实IP网络环境的实验中，设置各拥塞链路的丢包率在[0.05，0.2]范围之间波动，正常链路丢包率范围为[0，0.01]。一旦链路被分配丢包率后，模拟实际IP网络链路丢包服从Bernoulli随机过程产生丢包事件。
由于实际IP网络单时隙路径性能探测中，各E2E路径性能测量无法保证时钟同步，因此，同一链路在不同E2E路径中的丢包率也不尽不同。但是，由于链路状态有一定持续性，不同E2E路径中的同一条链路，其丢包率在较短时间内变化不大。因此，本发明利用随机数发生器，根据拥塞链路比例f，在IP网络拓扑模型中，随机产生一定数目的拥塞链路，并给拥塞链路赋丢包率，丢包率数值为[0.05，0.2]之间任意一随机数值。由式(13)可得出各E2E路径的丢包率数值，以此来模拟E2E路径性能测量结果。
在进行拥塞链路推断时，由于对各E2E路径发包探测的间隔时间较短，如某链路为拥塞状态，在包含此链路的路径中，其丢包率相差不大。因此，为了模拟同一条链路在不同E2E路径中的丢包情况，在同一次拥塞事件中，E2E路径中的共享链路丢包率[-0.02，0.02]之间随机发生改变。
为了验证本发明提出的CLLRRI方法在拥塞链路定位及丢包率范围推断中的有效性及准确性，利用式(20)所示检测率(Detection Rate，DR)、误报率(False Positive Rate，FPR)以及丢包率范围推断准确率(Accuracy)对不同算法的推断性能进行评价，结果均为实验场景及设置参数不变的情况下，10次实验取平均值后得出。
式(20)中，F代表实际拥塞链路(Benchmark)，X代表算法推断出的拥塞链路，Q代表算法准确推断出拥塞链路丢包率范围的链路数目。
1.2不同拥塞链路比例下的推断性能比较
为了验证本发明提出的推断方法CLLRRI在不同拥塞链路比例f下中的推断性能，利用Brite拓扑生成器分别模拟100个节点的Waxman、BA及GLP网络拓扑，设置f＝[0.1～0.5]随机产生拥塞链路。
首先，根据连续30次E2E路径探测的链路拥塞事件，得到每次各E2E路径的拥塞情况，求出待测IP网络中各链路的拥塞先验概率。然后，根据当前链路拥塞事件产生的E2E路径拥塞测量值，分别利用CLINK算法，Range tomography算法及本发明提出的CLLRRI方法分别进行拥塞链路定位实验，拥塞链路定位推断性能如图5a～图5c所示。由于CLINK算法仅能定位出拥塞链路而无法进行拥塞链路丢包率范围推断，因此，在拥塞链路丢包率范围推理准确率ACCURACY性能曲线图中缺少CLINK算法的性能曲线。
(1)拥塞链路定位性能分析
由图5a～图5c中DR及FPR所示推断结果可以看出，对三种不同的拓扑网络模型Waxman、BA及GLP，三种算法均在GLP模型下的推断性能最好，其次是BA模型，Waxman模型最差。这与网络拓扑模型的结构有很大关系，由于GLP及BA均为幂率特性模型，且GLP为强幂率特性模型，E2E路径长度较短，共享路由器的节点数较多(部分路由器度值较大)，而Waxman模型路径长度较长，因途经链路数较多导致算法推断性能下降明显。本发明提出的CLLRRI方法及CLINK算法均对待测IP网络各链路进行了拥塞先验知识学习，而Range tomography算法仅以“E2E路径中共享数目最多的瓶颈链路为最有可能发生拥塞的链路”这一经验知识进行拥塞链路定位，未充分考虑各待测IP网络实际的链路拥塞情况，因此，多链路拥塞时，Range tomography算法的推断性能下降明显。在Waxman模型中，CLLRRI方法DR较Range tomography算法高10％以上，并且随着f增大，CLLRRI方法鲁棒性较强，当f达到0.3时，较Range tomography高出20％以上，而当f达到0.5时，高出近40％。CLLRRI方法在BA及GLP模型下的推断性能鲁棒性较强，未出现明显下降，特别是在GLP模型下，当f达到0.5时，DR始终保持在92％以上，较f＝0.1时(平均DR＝98％)下降不超过10％，显示出CLLRRI方法具有较高的鲁棒性。同样，三种算法的FPR均在GLP模型下最低，始终保持在10％以下，在BA模型下不超过20％，在Waxman模型下不超过30％。
CLLRRI方法及CLINK算法均通过多时隙路径性能探测，获取了各链路拥塞先验知识，对拥塞链路进行定位。但是，由于CLINK算法基于最小链路覆盖集理论(在推断出E2E路径中的一条拥塞链路后，即将此路径移除，不再推断该路径是否还存在其他拥塞链路)；而CLLRRI方法借助E2E路径丢包率，通过贪婪启发式定位E2E路径中可能发生拥塞的链路，推断性能较CLINK算法有显著提高。
(2)拥塞链路丢包率推断性能分析
为了验证CLLRRI方法对拥塞链路丢包率范围推断的准确性(Accuracy)，在不同类型的网络模型下，CLLRRI及Range tomography算法的Accuracy性能比较结果如图5a～图5c中Accuracy所示。CLLRRI方法在不同f下，Accuracy始终高于Range tomography算法，特别是在GLP模型下，CLLRRI方法的Accuracy始终保持在95％左右。随着f增加，Range tomography算法推断性能下降明显，当拥塞链路比例达到0.5时，Range tomography算法的Accuracy不足50％。而本发明提出的CLLRRI方法始终保持了较强的鲁棒性，特别是在GLP模型下，随着f增大，Accuracy降低不明显，当f达到0.5时，Accuracy仍高达90％左右。
由于CLINK及Range tomography算法均基于最小链路覆盖集理论，CLINK算法在确定了某E2E路径中的拥塞链路后，不再推断该路径中其他链路；Range tomography算法仅以“E2E路径中共享数目最多的瓶颈链路为最有可能发生拥塞的链路”这一专家先验知识作为拥塞链路推断的唯一依据，认为具有最小丢包率数值的拥塞路径，是由其中一条链路拥塞造成的，当拥塞链路数较多时，推断性能下降明显。CLLRRI方法基于BMAP准则，定位E2E拥塞路径中最容易发生拥塞的链路，推断丢包率范围，避免了E2E路径中存在多条拥塞链路，CLINK算法无法推断，以及Range tomography算法错误移除导致的推断误差。
1.3不同网络规模下的推断性能比较
为了验证本发明的CLLRRI方法在不同网络规模下的推断性能，利用Bri te拓扑生成器分别生成50～300个节点网络规模的Waxman、BA及GLP模型，并设置f＝0.2，随机产生网络中各拥塞链路。利用CLINK、Range tomography以及本发明提出的CLLRRI方法分别进行拥塞链路推断，不同网络拓扑模型下，三种方法的DR、FPR分别如图6a～图6c中DR、FPR所示，CLLRRI及Range tomography算法拥塞链路丢包率范围推理准确率如图6a～图6c中Accuracy所示。
由图6a～图6c的DR、FPR中可以看出，随着网络规模的增大，三种方法在不同网络拓扑模型下，推断性能虽有一定的下降趋势(DR降低，FPR升高)，但从总体来看，变化不明显，说明网络规模增大对各算法推断性能影响不大。
在不同网络拓扑模型下，Range tomography算法和CLLRRI方法推断拥塞链路丢包率范围准确率如图6a～图6c中Accuracy所示。CLLRRI方法的Accuracy均高于Range tomography算法，且随着网络规模的增大，算法Accuracy始终保持稳定，验证了CLLRRI方法在不同网络规模下，特别是大规模IP网络中，具有较高的推断性能。
2.仿真实验评价
由于实际IP网络自治系统(简称AS)内部链路性能很难获知，研究发现，大多数IP网络拓扑服从幂率规则。因此，为了验证CLLRRI方法在实际网络中的拥塞链路推断性能，在Emulab仿真试验平台上设计了IP网络仿真实验场景，如图7所示为本发明推断方法实施例与CLINK、Range tomography算法的推断性能仿真试验流程图：
1)利用Brite拓扑工具产生IP网络拓扑文件：本实验使用Brite拓扑生成器生成20个节点的服从幂率规则的GLP拓扑模型20GLP.brite；
2)在Emulab仿真实验平台上导入此Brite文件，搭建被测IP网络，，设置链路参数，制造拥塞事件；对网络中的各叶子节点路由器部署探针，并将性能监控台接入被测IP网络；设置各链路带宽100Mbps，时延15ms；AS内部为OSPF协议，E2E路径服从最短路径优先选路规则；链路丢包采用LM1丢包模型，链路拥塞时，丢包率数值服从[0.05，0.2]均匀分布；链路正常时，丢包率数值服从[0，0.01]均匀分布.为每条链路赋初始丢包率后，链路丢包服从Bernoulli随机过程，每隔2min以20％的比例链路随机产生丢包事件；
3)由性能监控台给各探针下达测量任务，测得E2E路径途经链路及E2E路径性能数据，并上传至性能监控台.分别利用本发明提出的CLLRRI方法、CLINK及Range tomography算法对当前时刻拥塞链路及其丢包率范围进行推断。
为了验证拥塞链路推断算法在Emulab仿真实验平台下的推断性能，设置f＝[0.1～0.5]，产生不同比例的拥塞链路事件。利用本发明提出的CLLRRI方法，CLINK及Range tomography算法分别推断当前时刻拥塞链路及其丢包率范围，并与此时的benchmark(即链路丢包率大于0.05的链路集合)进行比较，验证算法性能.每组实验结果均在相同参数设置情况下，连续10次取平均后得出，实验结果如图8所示。
由图8中DR可以看出，在Emulab仿真实验中，三种算法的DR同样随着f的增大呈下降趋势。其中，CLLRRI方法DR最高，f不超过0.2的情况下，DR始终保持97％以上，CLINK及Range tomography算法DR也均在90％左右，但随着f增大下降明显；f＝0.5时，CLLRRI方法DR仍保持在85％以上，而CLINK算法不足65％，Range tomography算法不足60％。图8的FPR中，本发明提出的CLLRRI方法不超过10％，且随着f的增大保持较高的稳定性。由图8中的Accuracy可以看出，CLLRRI与Range tomography算法均实现了较高的丢包率范围推理精度；当f增大到0.5时，Accuracy仍能保持在75％以上。
由图8可以看出，当IP网络规模较小时，本发明提出的CLLRRI方法与Range tomography算法Accuracy相差并不大。但是，随着IP网络规模的增大，在多链路拥塞场景中，CLLRRI方法的拥塞链路及其丢包率范围推断性能优越性较为明显。通过实验，Emulab仿真实验平台下所得实验结论与模拟实验中基本一致，不同节点网络规模下不同算法的推断性能这里就不再赘述了。
3. Internet实测实验评价
为了验证CLLRRI方法在实际Internet网络中的推断性能，在PlanetLab网络平台中进行实测实验，实验部署在分布于全球的50个PlanetLab节点上。由于Internet实测网络中各链路丢包率数值无法准确获知，即缺少式(17)中的实际拥塞链路集合F，因此，利用以下现有方法进行算法性能评价。
首先，将待测IP网络中各E2E路径集合以随机方式分为两大小相等的路径集合：推断路径集合I及验证路径集合V；然后，在推断路径集合I中，对各E2E路径每隔4分钟进行一次快照，共进行30次。
1)利用traceroute获取每次snapshots中，各E2E路径途经路由器节点，由此得到各E2E路径途经链路，由于路由器有多个端口，同一个路由器可能由多个端口与其他路由器相连，将多个IP地址(端口)但归属同一路由器的节点进行合并；
2)利用ping从发包路由器节点向各端节点发送100个40字节UDP包，其中，20字节的IP头，8字节的UDP头，12字节的包序列及发送时间，获取每次E2E路径性能测量结果.根据推断路径集合I中30次snapshots得到的数据，分别进行推断路径集合I中各链路拥塞先验概率的求解；
3)对待测IP网络各E2E路径进行当前时刻1次snapshots，得到各E2E路径途经链路以及路径性能探测结果，分别利用算法CLINK、Range tomography及CLLRRI推断路径集合I中的拥塞链路及其丢包率范围；
4)根据E2E路径中至少存在一条拥塞链路，则路径拥塞的原则分别以各算法推断出的拥塞链路集合确定验证路径集合V中的拥塞路径集合，并对照该路径在当前1次snapshots中得到的实际路径丢包率测量值，判断各算法推断准确性。
Internet网络实测实验中，各算法拥塞链路推断性能如下表1所示。CLINK算法仅能推断出待测IP网络中发生拥塞的链路，缺少链路丢包率范围推断性能Accuracy值。
表1 Internet实测实验中各算法推断精度
从表1可以看出，CLLRRI方法DR最高，Range tomography算法次之，CLINK算法最低.另外，由于CLINK算法仅能推断出链路拥塞与否，不能推断拥塞链路丢包率范围，而Range tomography及CLLRRI方法能够实现更高粒度的链路性能推断，为链路的拥塞程度判断提供了依据。从Accuracy结果可以看出，CLLRRI方法的Accuracy高于Range tomography算法，验证了CLLRRI方法在实际IP网络拥塞链路及其丢包率范围推断中具有更高的准确性。
本发明提出的CLLRRI方法在进行当前时刻拥塞链路推断时，借助了贝叶斯原理，对待测IP网络中各E2E路径途经链路进行了拥塞先验概率学习，引入了相关且性能相似路径集合，推断出拥塞E2E路径中最有可能发生拥塞的链路及其丢包率范围，实验验证了本发明方法的准确性及鲁棒性。
本发明的IP网络拥塞链路丢包率范围推断方法针对由路由器/交换机组成的大规模IP网络存在多链路拥塞等问题，提出了一种拥塞链路及其丢包率范围推断方法CLLRRI，通过构建待测IP网络贝叶斯网模型，借助链路拥塞贝叶斯MAP准则，推断E2E拥塞路径中最容易发生拥塞的链路，代替传统以瓶颈链路作为拥塞链路选取的经验方法；通过聚类与拥塞链路相关且性能相近的路径集合，在集合中动态计算路径性能相似系数，借助相似系数贪婪启发式循环推断各拥塞链路及其丢包率范围。模拟实验、仿真实验及实测实验均验证了提出算法的准确性及鲁棒性。
以上所述仅为本发明的实施例，并非因此限制本发明的专利范围，凡是利用本发明说明书及附图内容所作的等效结构变换，或直接或间接运用在其他相关的技术领域，均包括在本发明的专利保护范围内。
机译： 使用从VOIP数据流中提取的信号来区分网络拥塞和链路损耗
机译： 调制解调器中继协议冗余，可在IP网络上进行可靠的低速调制解调器通信，且丢包率很高
机译： 调制解调器中继协议冗余，可在IP网络上进行可靠的低速调制解调器通信，且丢包率很高
