CN102710464A - 基于参考延迟插入结构的细粒度单流级别延迟检测方法 - Google Patents

Abstract

本发明提出了一种基于参考延迟插入结构的细粒度单流级别延迟检测方法，其包括如下步骤：在发送端设立参考包发生器；在接收端设立延时估计器；参考包发生器将带有时间戳的参考包从发送端周期性地注入到数据流中，参考包在传输过程中发生延迟，接收端接收参考包延迟样本，延时估值器收集参考包延迟样本并进行延迟检测。本发明通过设置参考包，只需保证它与数据包发送的时间足够接近，对其进行观测后就可以推断出数据包的延迟特性，这种方法降低了延迟估计误差。另外，与需要从多端点收集海量数据包时间戳的方案相比，本发明的检测结果直接在接收端获得，不需要发送端的所有常规数据包的时间戳，这种架构便于实施，性价比高，有利于广泛地推广应用。

Description

基于参考延迟插入结构的细粒度单流级别延迟检测方法

技术领域

本发明涉及计算机多媒体技术领域，特别涉及一种基于参考延迟插入结构的细粒度单流级别延迟检测方法。

背景技术

目前，互联网逐渐应用于许多新的领域，比如算法交易和高性能运算，这些应用领域对延迟的要求非常严格，达到微秒级。然而，现今的网络运营商非常欠缺细粒度的检测工具以定位并修正那些引起SLA违例的网络异常和延迟尖峰。最近有研究者提出了一种叫LDA的可扩展的延迟检测方案，但其只能对聚合流进行延迟检测，而由于不同的流即使在同一链路上传输也会表现出非常明显的差异，因此在排除应用级的特殊故障时我们需要单个流的延迟检测。还有一种延迟检测方案是基于主动探针的检测技术，这种检测技术主要应用于端到端系统，不能检测路由器的延迟问题，另外昂贵的高精度检测设备也无法广泛地应用于当今的网络。

发明内容

本发明旨在至少解决现有技术中存在的技术问题，特别创新地提出了一种基于参考延迟插入结构的细粒度单流级别延迟检测方法。

为了实现本发明的上述目的，本发明提供了一种基于参考延迟插入结构的细粒度单流级别延迟检测方法，其包括如下步骤：

S1：在发送端设立参考包发生器；

S2：在接收端设立延时估计器；

S3：参考包发生器将带有时间戳的参考包从发送端周期性地注入到数据流中，参考包在传输过程中发生延迟，接收端接收参考包延迟样本，延时估值器收集参考包延迟样本并进行延迟检测。

本发明相对于直接测量单流中每一个数据包的具体时延，通过设置一个参考包，只需保证它与数据包发送的时间足够接近，对其进行观测以后就可以推断出数据包的延迟特性，这种方法降低了延迟估计误差。另外，与需要从多端点收集海量数据包时间戳的方案相比，本发明的检测结果直接在接收端获得，不需要发送端的所有常规数据包的时间戳，这种架构便于实施，性价比高，有利于广泛地推广应用。

本发明的附加方面和优点将在下面的描述中部分给出，部分将从下面的描述中变得明显，或通过本发明的实践了解到。

附图说明

本发明的上述和/或附加的方面和优点从结合下面附图对实施例的描述中将变得明显和容易理解，其中：

图1是本发明基于参考延迟插入结构的细粒度单流级别延迟检测方法的流程图。

具体实施方式

下面详细描述本发明的实施例，所述实施例的示例在附图中示出，其中自始至终相同或类似的标号表示相同或类似的元件或具有相同或类似功能的元件。下面通过参考附图描述的实施例是示例性的，仅用于解释本发明，而不能理解为对本发明的限制。

本发明提供了一种基于参考延迟插入结构的细粒度单流级别延迟检测方法，如图1所示，其包括如下步骤：

S1：在发送端设立参考包发生器；

S2：在接收端设立延时估计器；

S3：参考包发生器将带有时间戳的参考包从发送端周期性地注入到数据流中，参考包在传输过程中发生延迟，接收端接收参考包延迟样本，延时估值器收集参考包延迟样本并进行延迟检测。

在本实施方式中，在步骤S1之前还可以具有测量操作多样性和延时的瞬态定位的步骤，该测量操作多样性和延时的瞬态定位的方法为：使用真实路由器中的trace作为测量依据，分析SANJ，CHIC，WEB468和WEB700这四种类型数据包的平均时延。具体地，为了更为深入地捕捉每一组数据包的时延变化，计算它们各自的平均时延，在本实施方式中，分析数据包的方法为：根据包含源地址和目的地址的2元特性为数据包分组，计算平均延迟，并计算范围因子R，定义R为每组平均延迟的取值从百分之一到百分之九十九的分位点，即将延迟值分为一百份，R的引入能够获得几乎全部的延迟覆盖范围。

将时间平均分成固定间隔的时隙，对于每一组数据包k，时隙i，记录下此时数据包的个数n_i，k和平均等待时间d_i，k。那么，i时隙内数据包的总平均时延为：

$\stackrel{\‾}{d}=\frac{{\mathrm{\Σ}}_k{n}_{i,k}{d}_{i,k}}{{\mathrm{\Σ}}_k{n}_{i,k}}---\left(1\right)$

第k组数据包的总平均时延是：

$D_k=\frac{{\mathrm{\Σ}}_i{n}_{i,k}{d}_{i,k}}{{\mathrm{\Σ}}_i{n}_{i,k}}---\left(2\right)$

在D_k的定义式中，可以用代替d_i，k，即采用由数据包的个数n_i，k为权重的加权平均时延作为k组数据包在每一个时延中的特征，就能得到一个相当精确地近似值，替换后得到的平均时延为局部平均时延：

$D_k=\frac{{\mathrm{\Σ}}_i{n}_{i,k}\stackrel{\‾}{d}}{{\mathrm{\Σ}}_i{n}_{i,k}}=\frac{{\mathrm{\Σ}}_{i,j}{n}_{i,k}{n}_{i,j}{d}_{i,j}/{\mathrm{\Σ}}_l{n}_{i,l}}{{\mathrm{\Σ}}_i{n}_{i,k}}---\left(3\right)$

利用这种测量方法，当两条流的数据包在典型延迟突发持续时间内传输时，特别是在几乎相同的时间内传输时，这两条流的数据包的延迟性能表现出非常接近的一致性。因此，路由器可以在某一条链路上产生一条参考流，以给出参考流延迟检测的基本设定。然后，任意指定流的延迟都可以通过测量其周围的参考流的数据包来获取。这样就大大简化了检测的复杂度，对于不同的流所对应的参考流检测数据都是从同一条参考流获得的。

具体地，排队延迟在数据包发送时可以被成一个连续函数，发送端得到延迟随时间变化的函数，普通包所经受的延迟可以通过某一些延迟样本估计出来，而这些延迟样本是自于参考包的大量延迟样本。因此，插入误差可以通过改变在延迟曲线中插入的参考点的个数进行控制。

在本发明的一种优选实施方式中，基于参考延迟插入结构的细粒度单流级别延迟检测方法的具体步骤为：

在发送端设立一个参考包发生器，在接收端设立一个由计数器构成的延迟估值器。参考包发生器将带有时间戳的参考包从路由器的发送端周期性地注射到数据流中，这些参考包经历和普通数据包类似的排队时间或者其他效应，在传输过程中发生延迟，因此参考包可以在接收端提供相对延迟样本，接收端接收参考包延迟样本，延时估值器收集这些延迟样本并将它们传送给单流计数器进行延迟检测。

在本实施方式中，参考包发生器产生参考包的方法为：产生参考包的条件1为每发送n个普通包后发送一个参考包，产生参考包的条件2为每隔τ的时间间隔发送一个参考包，当条件1满足或条件2满足时，按照满足的条件的发送方式发送参考包。即当两个条件中的某一个满足时，就按照它的发送方式进行发送。在本实施方式中，还可以动态地监视参考包的利用程度以决定注射参考包的速率。这样一种发送参考包的策略要比固定包数和固定时间发送的方式都要好。根据参考包的利用率可以获得好的效果，在高使用率时降低参考包的发送率，在低利用率使提高参考包的发送率。

在本实施方式中，接收端将处理混合在普通包中的参考包以获得它们的延迟。这个结构并不要求接收端为网络中所有的流维护计数器，而只要他们能够维护数据流中一小部分子流的特征。在本实施方式中，产生延迟估值器的方法为维护三种计数器，在这三种计数器种，一种计数器记录该数据组中延迟样本的数目，一种计数器记录该数据组中所有数据包所受的延迟总和，另外一种计数器记录每一个数据包延迟的平方和。这种混合的设置使计数器随着接收数据流而更新数据，因此，在本实施方式中，采用高速SRAM应用于这些计数器。

在延迟估值器内还包含了一个内插缓冲区，该内插缓冲区记录了在两个参考包之间到达所有包的相关信息。设置这个内插缓冲区是因为对每一个数据包的延迟数据是以两个参考包之间样本数据包的延时数据为自变量的函数。这个缓冲区并不需要储存完全的数据包，只需存储流号，相应的时间戳和字节计数器，该内插缓冲区的大小可以根据参考流发生器来静态地设定，由此可以计算出两个探针到达之间的缓冲包的数目上限，并将它设为内插缓冲区的大小。比如，在时间平均发生器场景中，对于给定的链路容量，就可以算出最多它在τ时间内能发出多少个包，这就能作为内插缓冲器的大小。

内插缓冲区的存在使得可以通过某一个数据包的左参考包和右参考包来估计它的时延，但它使得存储结构变得更加复杂了。在本发明的另一种优选实施方式中，采用某个数据包前到达的参考包作为参考来估计该数据包的延时，这并不需要内插缓冲区，只需记录下参考包所经历的延迟，这可以很方便地用一个计数器得到。

在本实施方式中，采用的延迟估计器为RLI估值器，在该RLI估值器中，令

为第i个参考包，

j=1，2，…n，为接收时间戳位于

和

之间的正常包。令

代表接收端的时间戳，

代表接收端对

的字节计数值，τ_l和τ_r代表a_l和a_r的接收时间戳，b为参考包的大小，l_c为链路容量。那么，则第j个参考包的延迟估计为：

其中，d_l为参考包

的延迟，d_r为参考包

的延迟。

公式（4）的等号右边第三项是对因普通包和参考包的大小引起的时间序列的不同所作的补偿。在本实施方式中，无论何时一个新的参考包到达时，a_l和a_r马上更新，其后的延时估计就可以通过计算得到。

在延时估计结果出来以后，设计的几个单流计数器可以作如下更新：

c(f_k)=c(f_k)+1

m(f_k)=m(f_k)+d_j           （5）

$v\left(f_k\right)=v\left(f_k\right)+{\tilde{d}}_j^2$

其中，f_k为接收到的单流中的第k个参考包，k为正整数。

当某一条流终止时，如果

分别代表参考包最后数目，均值和方差的值，那么该流的均值和方差分别可以如下计算：

$E\left[d_{\mathrm{fk}}\right]=\tilde{m}\left(f_k\right)/\tilde{c}\left(f_k\right)$

$\mathrm{Var}\left[d_{\mathrm{fk}}\right]=\frac{\tilde{v}\left(f_k\right)}{\tilde{c}{\left(f_k\right)}^2}-E{\left[d_{\mathrm{fk}}\right]}^2---\left(6\right)$

其中d_fk表示的是该流数据包延迟的一个随机变量，这些值在完成计算后都会和流记录一起输出。

以上RLI估值器要求在内插缓冲区中存储数据包，直到下一个参考包的到来，这就提高了系统的复杂度。因此，在本发明另外的优选实施方式中，采用RLI-L估值器，该估计器并不同时需要内插缓冲区的左右两个延迟样本来进行估值，而仅仅需要左延迟样本。对于所有在延迟为d_l和d_r的参考包

和

之间的普通包有：

在本实施方式汇中，RLI-L估值器和RLI估值器有着相同的数据更新方式，在此不作赘述。

本发明相对于直接测量单流中每一个数据包的具体时延，通过设置一个参考包，只需保证它与数据包发送的时间足够接近，对其进行观测以后就可以推断出数据包的延迟特性，这种方法降低了延迟估计误差。另外，与需要从多端点收集海量数据包时间戳的方案相比，本发明的检测结果直接在接收端获得，不需要发送端的所有常规数据包的时间戳。这种架构便于实施，性价比高，有利于广泛地推广应用。

在本说明书的描述中，参考术语“一个实施例”、“一些实施例”、“示例”、“具体示例”、或“一些示例”等的描述意指结合该实施例或示例描述的具体特征、结构、材料或者特点包含于本发明的至少一个实施例或示例中。在本说明书中，对上述术语的示意性表述不一定指的是相同的实施例或示例。而且，描述的具体特征、结构、材料或者特点可以在任何的一个或多个实施例或示例中以合适的方式结合。

尽管已经示出和描述了本发明的实施例，本领域的普通技术人员可以理解：在不脱离本发明的原理和宗旨的情况下可以对这些实施例进行多种变化、修改、替换和变型，本发明的范围由权利要求及其等同物限定。

Claims (7)

1.一种基于参考延迟插入结构的细粒度单流级别延迟检测方法，其特征在于，包括如下步骤：

S1：在发送端设立参考包发生器；

S2：在接收端设立延时估计器；

S3：参考包发生器将带有时间戳的参考包从发送端周期性地注入到数据流中，参考包在传输过程中发生延迟，接收端接收参考包延迟样本，延时估值器收集参考包延迟样本并进行延迟检测。

2.如权利要求1所述的基于参考延迟插入结构的细粒度单流级别延迟检测方法，其特征在于，在步骤S1之前还具有以下步骤：测量操作多样性和延时的瞬态定位。

3.如权利要求2所述的基于参考延迟插入结构的细粒度单流级别延迟检测方法，其特征在于，测量操作多样性和延时的瞬态定位的方法为：使用真实路由器中的trace作为测量依据，分析SANJ，CHIC，WEB468和WEB700这四种类型数据包的平均时延。

4.如权利要求3所述的基于参考延迟插入结构的细粒度单流级别延迟检测方法，其特征在于，分析数据包的方法为：根据包含源地址和目的地址的2元特性为数据包分组，计算平均延迟，并计算范围因子R为每组平均时延取值从1到99的分位点，将时间平均分成固定间隙的时隙，对于每一组数据包k，时隙i，记录下此时数据包的个数n和平均等待时间d，那么，i间隙内数据包的总平均时延为:

局部平均时延为: $D_k=\frac{{\mathrm{\Σ}}_i{n}_{i,k}\stackrel{\‾}{d}}{{\mathrm{\Σ}}_i{n}_{i,k}}=\frac{{\mathrm{\Σ}}_{i,j}{n}_{i,k}{n}_{i,j}{d}_{i,j}/{\mathrm{\Σ}}_l{n}_{i,l}}{{\mathrm{\Σ}}_i{n}_{i,k}}.$

5.如权利要求1所述的基于参考延迟插入结构的细粒度单流级别延迟检测方法，其特征在于，产生参考包的方法为：产生参考包的条件1为每发送n个普通包后发送一个参考包，产生参考包的条件2为每隔τ的时间间隔发送一个参考包，当条件1或条件2中的某一个条件满足时，按照满足的条件的发送方式发送参考包。

6.如权利要求1所述的基于参考延迟插入结构的细粒度单流级别延迟检测方法，其特征在于，产生延迟估值器的方法为：维护三种计数器，所述计数器记录数据组中延迟样本的数目，所述数据组中所有数据包所受的延迟总和以及每一个数据包的延迟的平方和。

7.如权利要求1所述的基于参考延迟插入结构的细粒度单流级别延迟检测方法，其特征在于，延迟估计器进行延迟检测的方法为：

延迟估计器令为第i个参考包，

j=1，2，…n为接收时间戳位于和

之间的正常包，令

代表接收端的时间戳，

代表接收端对

的字节计数值，τ_l和τ_r代表a_l和a_r的接收时间戳，b为参考包的大小，l_c为链路容量，则第j个参考包的延迟估计

为：

其中，d_l为参考包的延迟，d_r为参考包

的延迟。

无论何时一个新的参考数据包到达时，a_l和a_r将马上更新，其后的延时估计就可以依次计算得到。

Images