非对称网络单向时延的最小范数估计

贾巧伶，高 勇

（四川大学 电子信息学院，四川 成都 610064）

0 引言

近年来，通信组网的发展成为一种趋势，网络性能的测量也越来越受到重视，而单向时延是评价通信网络性能的重要指标之一。单向时延是指数据包从发送端经由网络到达接收端所需的时间。往返时延(RTT,Round Trip Time)常被用作一种估计方法，它是记录数据包从发送端经通信网络到达接收端然后再返回发送端所需要的总时间，因此，单向时延可由RTT时延除以二均分得到。但是由于通信网络的非称性，这种估计方法并不准确。所以，常用的测量方法是分别记录数据包发送时间和到达时间，但是由于收发两端主机的时钟运行并不同步，从而导致了单向延时测量的不准确性。

当然，理想的方法是同步所有测量主机的时钟。GPS全球定位系统可以提供高精度的硬件时钟同步[1-2]，但是其价格及其昂贵，不利于一般的工程应用。因此，很多学者利用软件方法对时钟的同步算法进行了深入的研究，先后提出了点线垂直距离最小算法、曲线和线间最小面积算法、模糊聚类算法[3-5]等，这些算法都是为了消除时钟时滞和时钟偏差以获得高精度的时钟同步补偿。

区别于解决时钟不同步带来的问题，文献[6]提出了一种不需要时钟同步的单向时延测量方法，利用 Windows平台下提供的高精度性能计数器，建立两主机的性能计数器相对模型，推导出通信网络单向时延表达式，但是使用对包理论对待定项的更新有时会偏离正常水平，这将导致测得的单向时延波动范围较大。基于文献[6]中存在的问题，本文简化了实验仿真模型，不需要估计更新待定项，利用最小范数法对文献[6]中所建表达式进行处理，获得的单向时延波动范围更小,更准确。这种方法不需要两主机间的时钟同步，不仅适用于非对称通信网络，并且具有在线测量、高精度、低复杂度的优点。

1 模型建立

在Windows平台下有一个可以提供微秒级计数的高精度性能计数器，我们可以建立两主机间的性能计数器相对模型，推导出网络单向时延表达式[6]。

首先建立主机S和主机C的性能计数器相对模型，如图1所示。

图1 两主机的性能计数器相对模型

所以式(3)可写为：

注意到在Windows平台下，使用QueryPerformance Frequency()和 Query Performance Counter()函数[7]可获得机器内部定时器的时钟频率和计数，从而实现μs级的准确定时，但是根据文献[7]中所述性能计数器的取值有时会意外向前跳跃，但是从一次意外跳跃到下一次意外跳跃这段时间内，fs、 fc、均保持不变，因此，可以将q看作一个常量，由式(4)建立了两主机间的相对模型表达式。

2 算法推导

如图2所示，两主机建立TCP连接，主机S以周期间隔向主机C发送UDP数据包，记主机S发送第i个数据包时的性能计数器的值为，记主机 C在接受到第i个数据包时的性能计数器的值为()。

图2 单向时延发包模型

根据单向时延发包模型建立的仿真模型如图3，在主机S和主机C间建立TCP连接，主机S向主机C发送数据包，发送时记录主机S的性能计数器为1,iR，并且在主机C接收到数据包时记录其性能计数器的值为2,iR，主机C接收到数据包后立即发送回数据包，此时性能计数器的取值为3,iR，在主机S接收到返回的数据包时其性能计数器的取值为4,iR 。

图3 单向时延仿真模型

由式(6)、式(7)可知，该线性方程组的未知数多于方程个数，2个方程式，3个未知数q，其中可分别调用Que- ry Performance Frequency()和 Query Performance Cou-nter()函数获得[7]，因此该线性方程为欠定方程。

举一个简单的例子来说明欠定线性方程组的解，假定线性代数方程为：

如图 4所示，直线 x1+2x2=10上的所有点(x1,x2)都是方程的解。如果想得到唯一的解，必须加一个约束条件。将解x的范数最小作为约束条件，这样得到的唯一解为最小范数解。x的范数最小相当于向量x的端点到原点的距离最小，所以最小范数解又称为最短距离解。

图4 欠定方程式(8)的解

对于式(8)的最小范数解，就是与原点距离最短的解，即为图4中所示坐标(2,4)的点。

更一般的，设 X0=Gb 为欠定方程组 A X= b 的最小范数解，则 X0为欠定方程组所有解中范数最小的解，即：

欠定方程的最小范数解为[9]：

其中G为A的右伪逆矩阵，即：

其中I为单位矩阵。

因此利用上述理论，在建立2台主机TCP连接的情况下，主机S向主机C周期的发送数据包，主机C接收到数据包后立即向主机S发回数据包，可根据最近一次的性能计数器取值，结合式(6)、式(7)估计出上下行单向时延

3 仿真结果及分析

在第三代移动通信标准CDMA2000无线通信网络状态下，通过两块无线上网卡实现网络互连，网络带宽为3.1 Mb/s，获得一组实验数据，如图5所示。

图5 无线网中两主机时延

图5(e)是往返时延RTT的均分，即上下行时延相等，可看出无线通信网络受到干扰大，时延波动性也很大；其中，图5(a)、图5 (b)是使用本文中所述的最小范数估计法获得的上下行时延，图 5(c)、图 5 (d)是使用文献[6]中的对包方法估计的上下行时延，它们都体现了通信网络的非对称性，并且主机S到主机C的上行时延平均水平要大于主机C到主机S的下行时延平均水平，这是因为对于实际网络来说，上行网络平均带宽要小于下行网络平均带宽。从图5中可以看出由于使用对包方法在定时更新待定项时会偏离正常水平，导致所得结果波动范围很大，而使用最小范数法估计的时延比用对包法获得的时延更精确，波动性更小，减小了使用对包方法中极大（或极小）尖峰值的出现。

4 结语

本文利用Windows平台下提供的微秒级计数的高精度性能计数器构建了仿真模型，通过搭建平台建立两主机间的TCP连接，根据所得数据建立数学表达式，利用最小范数估计法获得单向时延，经过实验验证本文方法比使用对包方法得到的结果波动性更小，更精确，并且只需根据最近一次的性能计数器取值就能更好的跟踪性能计数器数据的变化以及时反映网络时延的变化，具有可在线测量、精度高、不需要时钟同步和适用于下一代互联网通信[10]的优点。

[1] 胡志坚,张承学,杜志伟.基于 GPS的同步时钟的研制及其应用[J].小型微型计算机系统，2005,26(8):14 33-1435.

[2] 秦明伟，姚远程，李云.网络时延测量中的时间同步系统应用研究[J].通信技术，2008,41(08):149-153.

[3] 聂玉婷,高仲合.单向时延测量中的时间同步问题[J].通信技术，2009, 42(10):125-127.

[4] 王卓，朱德森，汪秉文.单向时延测量的实时时钟同步算法[J].华中科技大学学报:自然科学版，2008,36(02):22-25.

[5] 王洪波,林宇,金跃辉,等.一个消除单向时延测量 中 时钟频差和时钟重置的新方法[J].电子学报，2005:584-589.

[6] 秦张淼,周卫红,薛竞翔.基于高精度性能计数器的网络单向时延研究[J].小微型计算机系统，2010,5(05):912-915.

[7] Microsoft Corporation. Query Performance Frequency function[EB/OL].(2005-01-09)[2011-11-05].http://msdn.microsoftcom/en-us/library/ms644905(VS.85).

[8] 周金森. 广义逆矩阵与线性方程组的解[J].漳州职业技术学院学报，2006,8(02):15-17.

[9] 张峥嵘,严涛. 关于线性方程组 Ax=b的解的注记[J].南京师大学报:自然科学版，2001,24(01):21-24.

[10] 于溯，下一代互联网广域网接入研究[J].信息安全与通信保密，2011(10):65-68.