基于通用PC的单向时延测量方法

刘爱东，黄 彬，张永辉

(1.海军航空工程学院兵器科学与技术系，山东烟台264001;2.海军航空工程学院研究生管理大队，山东烟台264001)

0 引言

网络性能代表了网络基础设施向上层应用提供的服务质量，单向时延是评价互联网性能的重要参数之一。在网络应用中，许多应用对不同方向上的时延指标具有不同的要求，测量单向时延指标可以比较准确的反映网络向应用实际提供的服务水平［1］。单向时延也是测量时延抖动、网络带宽等性能指标的基础，能够应用于SLA(service level agreement)和QoS(quality of service)的管理，也在网络性能监测、网络行为分析、拥塞控制算法研究等领域得到了广泛应用。

采用主动测量方法进行单向时延测量，在无端到端时钟同步机制时，时钟不同步是时延测量中误差的主要来源，目前国内外学者对单向时延测量问题做了大量研究，提出了基于软件算法的方法或基于外部时钟源的方法来消除时钟不同步的影响。基于软件算法的测量方法主要有基于模式识别时钟重置检测算法、基于漂移补偿的时间同步方法、基于拟合偏差法、分段最小优化法、最小面积法、基于凸集的优化法等［2-7］。这些方法均侧重于对时钟偏差 (clock skew)的纠正，并未解决时钟偏移 (clock offset)的影响。且由于互联网是一个不断增长的、分布的、不协作、异质的复杂巨系统，具有诸多不确定因素，这些算法因计算复杂，难以实时跟踪时延的变化，缺乏实用性。基于外部时钟源的方法主要是采用全球定位系统GPS与专用于分组捕获的DAG卡配合进行端到端时延测量。但是这种测量方式所需设备价格昂贵，且部署位置有限，不能得到大规模应用。

本文旨在找到一种基于通用PC架构的，不依赖于外部时间源且计算简单，能够实时追踪端到端时延变化，避免时钟不同步带来的影响的单向时延测量方法。

1 单向时延分析

1.1 单向时延定义

在RFC 2679中将单向时延指标分为单次测量单向时延指标和多次抽样统计测量时延指标两种［8］。本文主要研究单向时延指标，其定义为:在T时刻从源节点发送测量分组的第一位，在T+dT时刻目的节点收到测量分组的最后一位，则从源节点到目的节点在时刻T的单向时延为dT。

1.2 单向时延的构成

当测量分组从发送主机生成到接收主机接收到完整分组的过程中，经历的时延主要有以下几个时延组成:

(1)传输时延

传输时延是把测量分组发送到链路上的时间，即从分组的第一位直至最后一位到达链路的时间，设分组的大小为L，链路的容量为C，则传输时延为L/C。

(2)传播时延

传播时延是一个测量分组从链路的一端传播到链路的另一端，主要取决于链路的电气特性。对于一个链路，如果其物理长度为d，信号传播速度为v，则传播时延为d/v。

(3)路由器时延

当一个测量分组到达路由器后，路由器处理分组的时间称为处理时延。

由于网络负载的突发性，当一个分组到达路由器时并不能立即得到处理而被放入缓冲队列等待处理的时间称为排队时延。

由上所述，包含n跳的单向时延可以表示为

式中:L——测量分组的长度，Ci——第i跳链路的带宽，di——第i跳链路的物理长度，vi——第i跳链路的传播速率，pi——测量分组在第i个路由器上的处理时延，qi——测量分组在第i个路由器上的排队时延。

1.3 单向时延性质分析

当链路在测量期间保持稳定且测量分组长度一致时，传输时延、传播时延和处理时延是不变的，而排队时延随着网络负载情况的变化而不同，则式 (1)可以改写为

并且有

研究发现，无论是网络路径还是路由器，短时间内测量到其最小单向时延的概率非常大［9］，所以，间隔时间T发出两个测量分组到达接收端时均没有经历排队时延的概率也非常大，该结论在下文中将被使用。

1.4 单向时延的测量

采用主动测量方法时，通用方法是在测量分组中打上发送端发送分组时的时间戳，在接收端记录接收测量分组时的时间戳，通过比较两个时间戳得到单向时延值。如上所述，时钟不同步对单项时延的测量带来了很大影响，如图1所示，时钟的不同步造成时延测量结果出现了随时间推移而增加的趋势。

图1 时钟不同步时单向时延测量结果

2 使用时间戳计数器测量单向时延分析

2.1 时间源的选择

2.1.1 时间戳计数器简介

时间戳计数器 (time stamp counter，TSC)是 Intel自Pentium系列CPU以来提供的一个部件，它以64位无符号整型数的方式，记录了自CPU上电以来所经过的时钟周期数，并且提供了一条RDTSC汇编指令供应用程序读取其值。为叙述方便，下文均称时间戳计数器为TSC。

2.1.2 采用TSC值作为时间源分析

(1)时间分辨率

采用TSC值作为时间源，其分辨率取决于CPU频率，若CPU频率为H，则TSC分辨率为1/H。目前，主流通用PC主机CPU频率已经超过2GHz，则以TSC值为时钟源，可以达到纳秒级的时钟分辨率，且只需一条汇编指令就能读取其值，相较于其他计时方式开销更小。

(2)计时稳定性

文献［10］中，比较了采用TSC值作为时间源与采用操作系统时钟作为时间源，这两种方法的开销大小，稳定性和准确性，证明前者要优于后者。由此，采用TSC值作为时间源是完全可行的。

2.2 时间戳分析

设参考时钟为标准时间，测量分组的发送端与接收端主机的时间源采用其TSC值，发送主机CPU上电的时刻为ts0，CPU频率为hs，ts为发送时的标准时刻，则发送端主机的时间戳函数为

同理，设接收端时钟的初始值为tr0，CPU频率为hr，tr为接收的标准时刻，则接收端主机的时间戳函数为

2.3 测量方法分析

设第i次测量中，真实时间时刻S时发送端发出测量分组，则由式 (4)，发送时间为

同理，设真实时间时刻R时接收端收到测量分组，则由式 (5)，接收时间为

而探测到的单向时延值ti为

联立 (6)、(7)、(8)整理得到

以接收端主机CPU频率为参考，有

由式 (10)改写式 (9)得到

令θ=tr0－ts0，则θ表示的含义为接收端和发送端主机CPU上电时间差。

综上 (11)式可写为

分析式 (12)，设相邻两次测量值分别为

则有

由式 (15)可以看出，相邻两项测量值之间的差值，当主机CPU频率测量准确且测量分组没有经过排队时延时，其值为零，当主机CPU频率测量不准确时，其值为一个不为零的常数，测量得到的单向时延值表现为一条有斜率的直线。

至此，按照式 (12)可以采用TSC值作为时间源进行单向时延的测量，所需量为双端主机的CPU上电时间差，接收端主机CPU频率，及收发双方收发测量分组时的时间。

综上所述，采用TSC值作为时间源测量单向时延时，其影响主要来自双端主机CPU频率的不一致，接收主机CPU频率值的准确与否和双端主机CPU的上电时间差测量准确与否，测量值理论分析结果如图2所示。如何测量到真实时延值的关键就在于消除上述3种影响带来的误差。

图2 测量值理论分析

2.4 各量测量方法与纠斜处理

2.4.1 CPU频率的测量

(1)利用NTP服务器测量CPU频率

NTP(Network Time Protocol)是一个基于TCP/IP的、跨越广域网或局域网的复杂的同步时间协议，通常可获得毫秒级的同步精度。网络中的NTP服务器之间采用GPS全球同步授时，同步精度可以达到微秒级，因此可以认为NTP服务器的时间即为标准时间。

文献［10］中提出了利用NTP服务器，周期向其请求时间戳，通过计算标准时间段内TSC增加的值来推算CPU主频的方法。这种方法能够比较准确的测量出CPU主频，但是并不是所有主机都支持NTP协议，也不是所有网络环境都有NTP服务器或者标准时间服务器，因此文献 ［10］提出的测量主频的方法并不能得到广泛应用。

(2)利用系统时间估算CPU频率

利用操作系统的时间为参考时间，可以估算出CPU频率。例如，在以操作系统时间为参考的1s内，TCS值增加的数值即为CPU主频。

由于系统负载的影响，系统时间计时会出现一定的波动，导致测量得到的结果也会出现小范围波动，因此，采用这种方式估算CPU频率时应当统计一段时间内的所有测得的CPU频率值，取其统计平均值，这样测量结果随着测量时间的增加而趋于稳定。

由于调用系统计时也需要一定的时间开销，导致TSC寄存器增加的值偏大，即测得的CPU频率大于实际CPU频率，在测量单向时延时会导致 (15)式的值不为零，所以在进行单向时延测量值的计算与处理时要有纠斜处理，关于纠斜的方法将在下文阐述。

2.4.2 发送端与接收端的CPU频率差测量

所以得到

由上文，间隔时间T发出两个测量分组到达接收端时没有经历排队时延的概率很大，即取最小的概率

很大，则在多次测量中必然能够测量到准确的α值，且

2.4.3 CPU上电时间差的测量

设测量分组的发送端与接收端主机分别为A机与B机，测量时，测量分组在A、B间往返均为同一条链路。定义从A机到B机的链路为前向路径，对应的单向时延为前向时延，设其最小值为tAB，同样的定义从B机到A机的链路为后向路径，对应的单向时延为后向时延，设其最小值为tBA，如图3所示。

由上文分析可得，在测量次数足够多时，前向时延和后向时延均能取得最小值，即tAB、tBA，则由图有

设A机CPU频率为hs，其CPU上电时刻为ts0，t1时刻TSC寄存器值为N1，t4时刻TSC寄存器值为N4，同理，设B机CPU频率为hr，其CPU上电时刻为tr0，t2时刻TSC寄存器值为N2，t3时刻TSC寄存器值为N3。

结合 (6)、(7)、(8)、(9)得到

又θ=tr0－ts0，hs=αhr，且往返均为同一条链路，有tAB=tBA，结合式 (18)、(19)，得到

则在已测得hr和α的基础上，按照式 (22)可以计算出θ的大小，其准确度取决于hr测量的准确与否。

2.4.4 纠斜处理

由上文可知，采用利用操作系统时间计算CPU频率时，得到的接收端频率估值大于实际值，造成实际测量结果近似为一条有斜率的直线，明显不符合实际情况，为了得到正确的单向时延测量值需要做进一步的纠斜处理。

图3 CPU上电时间差测量

设在相邻测量分组没有经历排队时延且接收端CPU频率估计不准的情况下，按照式 (15)令

则对任意的相邻测量分组之间，有

得到

其中n表示测量的次数，整理得

结合式 (12)，在实时测量时，对测量得到的时延值进行纠斜处理，有

3 测量实例

3.1 测量分组与链路选择

测量分组选用UDP分组，以发送端主机系统时间为参考，间隔1s周期发送测量分组，分组包含的内容为发送时刻发送主机的TSC寄存器值，即发送端的时间戳，分组大小为100字节。

测量选择的链路为:从山东烟台的某电信接入点到山东烟台的某联通接入点，测量期间使用用Trace Route工具进行追踪，结果显示测量期间链路保持稳定，且往返链路为同一条，所经路由IP地址如表1所示。

表1 测量实例链路包含路由的IP地址

3.2 测量结果和说明

接收端主机CPU频率测量采用利用系统时间估算CPU频率的方式，其测量结果如图4所示。

图4 利用系统时间测量CPU频率的结果

在单向时延测量开始前，双方主机协作发送测量分组，按照上文所述方法进行了CPU上电时间差的测量，测量得到双端主机CPU上电时间差为238.5126 s。

图5左图中的是经过测量得到的t'i值，未消除CPU上电时间差的影响，右图中的是消除CPU上电时间差影响之后的测量值。由图5可以发现由于接收端主机CPU频率在测量时不准确，造成单向时延测量值表现下降的趋势。

图5 消除CPU上电时间差前后对比

图6 中是对已消除CPU上电时间差影响的测量值进行纠斜处理的结果。

图6 纠斜前后对比

图7 显示是的对原始测量值进行各步纠正，并得到最终结果的效果图。

图7 各步纠正效果对比

4 结束语

本文首次采用时间戳计数器值作为时间戳来源，应用到单向时延测量的方法中。通过理论推导，证明了该方法测量单向时延的可行性，并且阐述了消除误差的理论方法，通过测量CPU频率差，双端主机协作测量CPU上电时间差及对测量结果进行纠斜的方式得到可信的测量结果。由于采用时间戳计数器值取代操作系统时间，避免了目前各种单向时延测量方法所要面对的时钟偏差和时钟偏移的问题，并且通过实例测量，验证了该方法的有效性。

［1］YANG Jiahai，WU Jianping，AN Changqing.The theory and application of internet measurement［M］.Beijing:Post＆ Telecom Press，2009:98-165(in Chinese).［杨家海，吴建平，安长青.互联网络测量理论与应用［M］.北京:人民邮电出版社，2009:98-165.］

［2］YANG Tan，SUN Hanlin，JIN Yuehui，et al.An glgorithm for adaptive detection of clock reset based on pattern recognition ［J］.Chinese High Technology Letters，2008(5):441-446(in Chinese).［杨谈，孙韩林，金跃辉，等.基于模式识别的自适应时钟重置检测算法 ［J］.高技术通讯，2008(5):441-446.］

［3］QUAN Yujuan，LIU Guixiong，LIU Bo，et al.A RCR clock synchronization model with drift compensation［J］.Journal of South China University of Technology，2010，38(5):76-79(in Chinese).［全渝娟，刘桂雄，刘波，等.具有漂移补偿的RCR时钟同步模型［J］.华南理工大学学报 (自然科学版)，2010，38(5):76-79.］

［4］ZHAO Ying，WANG Yini，MA Yan，et al.Clock synchronnization based on fitting offset［J］.Computer Engineering，2008，34(16):13-15(in Chinese).［赵英，王旖旎，马严，等.基于拟合偏差的时钟同步 ［J］.计算机工程，2008，34(16):13-15.］

［5］NIE Yuting，GAO Zhonghe.Time synchronization in one-way delay measurement［J］.Coummunications Technology， 2009， 10(42):125-127(in Chinese).［聂玉婷，高仲合.单向时延测量中的时间同步问题 ［J］.通信技术，2009，10(42):125-127.］

［6］LI Leimin，SUN Jie.Study of time synchronization alglorithm based on subsection ［J］.Computer Engineering and Applications，2008，44(23):110-113(in Chinese).［李磊民，孙杰.基于分段过滤时间同步算法研究［J］.计算机工程与应用，2008，44(23):110-113.］

［7］WANG Yini，ZHAO Ying.Client system of clock synchro nization based on clock drift rate［J］.Computer Applications and Software，2009，26(12):18-20(in Chinese).［王旖旎，赵英.基于时钟漂移率的时钟同步客户端系统［J］.计算机研究与软件，2009，26(12):18-20.］

［8］Almes G，Kalidindi S，Zekauskas M.A one-way delay metric for IPPM ［Z］.RFC 2679:Internet Engineering Task Force，1999.

［9］Pagugiannaki EMoon S，Fraleigh C.Measurement and analysis of single-hop delay on an IPbackbone network［J］.IEEE Journal on Selected Areas in Communications，2003，21(6):908-921.

［10］LI Wenwei，ZHANG Dafang，XIE Gaogang，et al.A high precision approach of network delay measurement based on general PC［J］.Journal of Software，2006，27(2):275-284(in Chinese).［黎文伟，张大方，谢高岗，等.基于通用PC架构的高精度网络时延测量 ［J］.软件学报，2006，17(2):275-284.］