基于t检测模型的网络坐标系统输入时延预处理方法

摘要

本发明公开了一种基于t检测模型的网络坐标系统输入时延预处理方法，其特征在于，每个网络节点记录其与部分邻居节点间最近H个直接测量时延值，在t检验模型下，依据该时延队列的时延观察值，估计出本节点间的下一时刻时延观察值的置信区间，以检测并抑制异常的时延观察值，得到其平滑输出时延结果。该算法基于概率论t检测模型，利用节点间历史记录时延样本信息，检测并抑制该节点间下一时刻异常的时延观察值，以得到平滑输出时延结果用来进行网络距离半测度空间嵌入，保证用其建立网络坐标系统时延预测的准确性及其收敛周期。

说明书

技术领域

本发明涉及互联网技术领域，具体涉及基于t检测模型的网络坐标系统输入时延预处理方法。

背景技术

近年来，随着IP网络规模指数级别的增长速度，网络结构异构性和复杂性程度增大，导致网络内部性能的可知性变差。同时又随着新的网络应用的不断涌现，用户对网络服务质量要求的不断上升，无论是网络服务提高商，还是用户，都希望能及时、准确的掌握反映网络当前性能的第一手资料，最大程度优化网络应用。在实际IP网络中，能反映网络运行性能和行为的参数很多，例如：带宽、时延、吞吐量等，而节点间时延是其关键参数之一，能够直接反映当前网络的性能状况。我们常把节点间时延称之为“网络距离”(Network Distance)。如在P2P(Peer-to-Peer)网络中DHT(Dynamic Hash Table)构造、Overlay路由、组播树构建等，它们都可以利用时延信息对其性能进行优化和提高。如何通过一种高效的测量的方式，来获取网络节点间的时延，是现在研究的热点问题。

为了得到网络距离，最简单而直接的方式就是在节点间的发起Ping探测数据包。然而这种方式测量次数，与网络规模存在指数级别的数量关系，由此给网络带来很大的测量开销。例如：在具有N台主机的网络中，需要测量O(N²)次，其效率低、可扩展性差。另一种是采用非直接测量方式，这仅仅需要部分节点间的有限次直接测量结果就能对其它所有节点间的距离进行预测，其复杂度降为O(N)；并且节点可以用几何方法相互独立地对网络时延进行存储、计算和处理等操作，方便网络应用。

基于网络坐标的时延预测方法，是近来提出的一类应用前景很好的非直接测量方法。该类方法是利用节点与部分邻居节点间的有限次直接测量时延信息，以测度空间嵌入理论为基础，将网络主机映射为虚拟空间中的点，并为其分配相应的虚拟坐标，由此就能够利用虚拟空间中两点之间测度距离来预测相应主机间的时延。网络坐标方法能以较小的测量开销预测时延，在实际网络环境中，它们在构建网络坐标系统时，通常要先取得所参考部分邻居节点间的一段时间内的有限次直接测量时延信息，分别将时延队列中数值大小上处于中间位置的时延值提取出来，形成静态稀疏时延矩阵作为建立网络坐标系统的输入时延。在这种情形下，因为构建坐标系统所输入的是静态稀疏时延矩阵，虽然节点间时延值稳定，但是并不能动态的反映网络中拥塞及拓扑变化。在现实场景中，无论是网络拥塞、网络负载均衡还是网络拓扑变化等等，都可以造成网络节点间的时延值不稳定。如果对这些参与网络坐标系统构建的输入时延不作任何处理，则无法保证用其建立网络坐标系统时延预测的准确性及其收敛周期。

发明内容

本发明所要解决的问题是：如何提供一种基于t检测模型的网络坐标系统输入时延预处理方法，该方法能克服现有技术中所存在的缺陷，保证了在复杂的网络背景环境下，网络距离半测度空间嵌入理论对其输入时延值稳定变化并且还能够及时反映当前网络状况的要求，保障了网络距离非直接测量的准确性。

本发明所提出的技术问题是这样解决的：提供一种基于t检测模型的网络坐标系统输入时延预处理方法，其特征在于，每个网络节点记录其与部分邻居节点间最近H个直接测量时延值，在t检验模型下，依据该时延队列的时延观察值，估计出本节点间的下一时刻时延观察值的置信区间，以检测并抑制异常的时延观察值，得到其平滑输出时延结果，具体步骤如下：

①变量定义：

a、Sample是节点AB间有限次直接测量的时延值，A和B是网络坐标系统中的两个节点，其中A是本地节点，进行网络坐标的更新过程，B是A的参考邻居节点，该时延队列中包含节点AB间全部可能的时延值，称为总体，这是进行测度距离空间嵌入所需的时延集合，以一维数值的形式，作为要进行平滑处理的输入时延数据；

b、SA＝{Sa₁，Sa₂，...Sa_H}是来自总体Sample的简单随机样本，由节点AB间最近H次直接测量时延的个体Sa₁，Sa₂，...Sa_H组成，其个体Sa₁，Sa₂，...Sa_H是来自总体Sample中时延信息的观察结果，样本容量即历史记录时延窗口大小为H，H≥3，，并且，样本SA要随着总体Sample中最新取得的所直接测量的时延个体的到来而更新；

c、AVER是总体Sample中简单随机样本SA({Sa₁，Sa₂，...Sa_H})的样本均值，以该样本均值作为总体均值的最大似然估计；

d、MAXV是总体均值的置信区间上界，以简单随机样本SA({Sa₁，Sa₂，...Sa_H})的样本均值和样本方差作为其自变量：

$\mathrm{MAXV}=\bar{X}+\frac{S}{\sqrt{n}}{t}_{\alpha }(n-1);$

e、是简单随机样本SA的样本均值，S是简单随机样本SA的样本标准差，N是SA的样本容量，用到的是t检验法，1-α称为置信水平；

f、RTT_ID是输出结果，以该时延值作为网络距离半测度空间嵌入的输入，用于建立网络坐标系统；

②处理过程：

a、对于最新直接测量的时延个体，根据其格式字段中的“邻居节点ID值”判断出该时延个体所属于的总体Sample，提取出该时延个体格式字段中的“节点间原始时延值”作为本次待平滑处理的时延值；

b、根据该节点间历史窗口内的简单随机样本SA({Sa₁，Sa₂，...Sa_H})信息，计算出样本均值和样本标准差S，从而进一步计算出总体均值的置信区间上界MAXV，其中和AVER同为简单随机样本SA的样本均值，用于计算MAXV，而AVER作为总体均值的最大似然估计；

c、如果新到个体格式字段中“节点间原始时延值”大于MAXV，认为此次时延观察值存在异常，令平滑处理输出结果RTT_ID等于总体均值的最大似然估计值AVER；否则，令RTT_ID等于该新时延个体格式字段中的“节点间原始时延值”；

d、用该时延个体格式字段中的“节点间原始时延值”，更新样本SA的历史窗口内时延个体信息，保证样本容量保持为H；

e、用平滑处理输出结果RTT_ID，作为网络距离半测度空间的输入时延值，在网络坐标系统核心算法(如Vivaldi)下，更新该节点的坐标值；

f、等待新的个体时延观察值，如果有新的个体时延观察值到来，跳到步骤a；否则，继续等待。

本发明的有益结果是：利用已经得知部分节点间的直接测量时延数据，能够滤出该链路中的随机延迟污染事件，产生稳定变化的输出时延值，从而进行网络距离测度空间嵌入建立虚拟坐标系统。保证了在复杂的网络背景环境下，网络距离半测度空间嵌入理论对其输入时延值稳定变化并且还能够及时反映当前网络状况的要求，保障了网络距离非直接测量的准确性。

附图说明

图1时延个体格式示例；

图2算法功能示意图；

图3算法功能结构图；

图4RS-TDM算法工作流程图。

具体实施方式

下面结合附图对本发明作进一步描述：

如何高效地利用节点与部分选择节点间有限次直接测量获得的时延信息来构造一个稳定的满足一定测度空间定义的网络坐标系统，这对提高非直接测量方法的时延预测准确性非常重要。然而在实际网络中，节点间的时延信息容易遭受网络拥塞、网络负载均衡及网络拓扑变化等的影响。如果不对它们进行处理，将导致据此构建的网络坐标系统不稳定，而无法得到准确的时延预测结果。为此，本发明提出一种时延预处理算法，通过对参与网络坐标系统构建的输入时延的预处理，来提高网络坐标系统的稳定性。该算法利用节点间历史记录的时延信息，对该节点间下一时刻直接测量的时延值进行平滑处理，以抑制其随机波动；然后再将平滑处理过的时延数据作为输入，构建相对稳定的网络坐标系统。

为了提高网络坐标系统的稳定性，改善网络距离预测准确性，本发明提出了针对网络坐标系统输入时延的预处理方法，即基于t检测模型的时延数据平滑处理算法(RTT Smoothing Algorithm based on t Detection Model，RS-TDM)。在RS-TDM算法中，每个网络节点记录其与部分邻居节点间最近H个(H≥3)直接测量时延值，在t检验模型下，依据该时延队列的时延观察值，估计出本节点间的下一时刻时延观察值的置信区间，以检测并抑制异常的时延观察值，得到其平滑输出时延结果。在RS-TDM算法中，我们将一节点对全部可能的直接测量时延值称为总体(Sample)，该总体中的每一个可能的时延观察值称为个体。将最近H次直接测量时延记为Sa₁，Sa₂，...Sa_H，并将Sa₁，Sa₂，...Sa_H称为来自总体Sample的一个样本，H为样本容量。由该样本可以计算出样本均值和样本方差，并基于t检验模型计算出总体均值的置信区间。因为样本均值是总体均值的无偏估计，可以用计算出来的总体均值的置信区间，来检验下一时刻样本均值的可信程度，如果下一时刻样本时延观察值在所计算的总体均值的置信区间内，则用该时延样本观察值，作为建立网络坐标系统的输入时延值；若该时延样本观察值并不在所计算的总体均值的置信区间内，RS-TDM算法采用前面计算的样本均值作为总体均值的最大似然估计值，作为网络距离半测度空间的输入时延值。

该算法基于概率论t检测模型，利用节点间历史记录时延样本信息，检测并抑制该节点间下一时刻异常的时延观察值，以得到平滑输出时延结果用来进行网络距离半测度空间嵌入，保证用其建立网络坐标系统时延预测的准确性及其收敛周期。

基于t检测模型的时延数据平滑处理算法(RS-TDM)：在RS-TDM算法中，每个网络节点记录其与部分邻居节点间最近H个(H≥3)直接测量时延值，在t检验模型下，依据该时延队列的时延观察值，估计出本节点间的下一时刻时延观察值的置信区间，以检测并抑制异常的时延观察值，得到其平滑输出时延结果。在RS-TDM算法中，我们将一节点对全部可能的直接测量时延值称为总体(Sample)，该总体中的每一个可能的时延观察值称为个体。将最近H次直接测量时延记为Sa₁，Sa₂，...Sa_H，并将Sa₁，Sa₂，...Sa_H称为来自总体Sample的一个样本，H为样本容量。由该样本可以计算出样本均值和样本方差，并基于t检验模型计算出总体均值的置信区间。因为样本均值是总体均值的无偏估计，可以用计算出来的总体均值的置信区间，来检验下一时刻样本均值的可信程度，如果下一时刻样本时延观察值在所计算的总体均值的置信区间内，则用该时延样本观察值，作为建立网络坐标系统的输入时延值；若该时延样本观察值并不在所计算的总体均值的置信区间内，RS-TDM算法采用前面计算的样本均值作为总体均值的最大似然估计值，作为网络距离半测度空间的输入时延值。

RS-TDM算法样本容量的选择策略：简单随机样本容量为H(H≥3)，并以最新的直接测量时延个体观察值来更新该简单随机样本，以该样本中的个体时延观察值，作为平滑处理输出时延值的判断依据信息。

RS-TDM算法时延总体均值置信区间的选择策略：简单随机样本中，保存有最近H次所直接测量的时延个体信息。在该容量为H的简单随机样本中，计算出其时延样本均值和时延样本方差，并用其在t检验模型下计算出时延总体均值的置信区间。

RS-TDM算法的平滑处理结果：因为样本均值是总体均值的无偏估计，可以用计算出来的总体均值的置信区间，来检验下一时刻样本均值的可信程度，如果下一时刻样本时延观察值在所计算的总体均值的置信区间内，则用该时延样本观察值，作为建立网络坐标系统的输入时延值；若该时延样本观察值并不在所计算的总体均值的置信区间内，RS-TDM算法采用前面计算的样本均值作为总体均值的最大似然估计值，作为网络距离半测度空间的输入时延值。其特点是：如果所参考样本的个体时延观察值波动范围大，将导致总体均值置信区间间隔变大，RS-TDM算法容许输出时延值在总体均值置信区间内变化，而置信区间的上边界能够抑制输出时延数据跨越数量级的变化，形成稳定的平滑处理输出结果。

具体实施例：

如图1～图4所示，在基于IP网络坐标的非直接时延测量系统中，t时刻每个节点N保持一张表，该表有两个域，[ID，RTT_ID]_N，其中ID为节点N的邻居节点的标识号，RTT_ID为节点N与该邻居节点进行测度空间嵌入的时延值。

基于t检测模型的时延数据平滑处理算法(RS-TDM)是针对网络坐标系统输入时延的预处理方法，该算法通过历史时延记录值，来平滑处理作为网络坐标系统核心算法(如Vivaldi算法)的输入时延值，以满足网络距离半测度空间嵌入理论对其输入时延值稳定变化并且还能够及时反映当前网络状况的要求。

基于t检测模型的时延数据平滑处理算法(RS-TDM)

为方便描述，我们取网络坐标系统中的两个节点A和B。其中A是本地节点，进行网络坐标的更新过程，B是A的参考邻居节点，节点AB间的时延值，作为RS-TDM算法的输入时延，并用得到平滑处理结果作为网络坐标系统的输入时延。

(1)变量描述

1).Sample是节点AB间有限次直接测量的时延值，该时延队列中包含节点AB间全部可能的时延值，称为总体，这是进行测度距离空间嵌入所需的时延集合，以一维数值的形式，作为RS-TDM算法要进行平滑处理的输入时延数据。。

2).SA＝{Sa₁，Sa₂，...Sa_H}是来自总体Sample的简单随机样本，由节点AB间最近H次直接测量时延的个体Sa₁，Sa₂，...Sa_H组成，其个体Sa₁，Sa₂，...Sa_H是来自总体Sample中时延信息的观察结果。在这里，样本容量(即历史记录时延窗口大小)为H(H≥3)，并且，样本SA要随着总体Sample中最新取得的所直接测量的时延个体的到来而更新。

3).AVER是总体Sample中简单随机样本SA({Sa₁，Sa₂，...Sa_H})的样本均值，在RS-TDM算法中，以该样本均值作为总体均值的最大似然估计。

4).MAXV是总体均值的置信区间上界，以简单随机样本SA({Sa₁，Sa₂，...Sa_H})的样本均值和样本方差作为其自变量。

$\mathrm{MAXV}=\bar{X}+\frac{S}{\sqrt{n}}{t}_{\alpha }(n-1)$

5).是简单随机样本SA的样本均值，S是简单随机样本SA的样本标准差，N是SA的样本容量，在RS-TDM算法中用到的是t检验法，1-α称为置信水平。

6).RTT_ID是RS-TDM算法的输出结果，以该时延值作为网络距离半测度空间嵌入的输入，用于建立网络坐标系统。

(2)算法过程

算法输入：样本观察值SA

算法输出：平滑处理结果RTT_ID

算法步骤：

1).对于最新直接测量的时延个体，根据其格式字段中的“邻居节点ID值”判断出该时延个体所属于的总体Sample，提取出该时延个体格式字段中的“节点间原始时延值”作为本次待平滑处理的时延值。

2).根据该节点间历史窗口内的简单随机样本SA({Sa₁，Sa₂，...Sa_H})信息，计算出样本均值和样本标准差S，从而进一步计算出总体均值的置信区间上界MAXV。其中和AVER同为简单随机样本SA的样本均值，用于计算MAXV，而AVER作为总体均值的最大似然估计。

3).如果新到个体格式字段中“节点间原始时延值”大于MAXV，在RS-TDM算法中认为此次时延观察值存在异常，令平滑处理输出结果RTT_ID等于总体均值的最大似然估计值AVER。否则，令RTT_ID等于该新时延个体格式字段中的“节点间原始时延值”。

4).用该时延个体格式字段中的“节点间原始时延值”，更新样本SA的历史窗口内时延个体信息，保证样本容量保持为H(H≥3)。

5).用平滑处理输出结果RTT_ID，作为网络距离半测度空间的输入时延值，在网络坐标系统核心算法(如Vivaldi)下，更新该节点的坐标值。

等待新的个体时延观察值，如果有新的个体时延观察值到来，跳到步骤1；否则，继续等待。