（通信与信息系统专业论文）ip网络中端到端时延特性的测量与估计.pdf

摘要 摘要 随着i n t e r n e t 规模和复杂性的不断增加，网络设计规划和管理操作越来越困难， 高效准确的描述i n t e m e t 运行状况和网络特性是网络运营和维护的关键。时延是 网络性能指标中的重要参数，在实际应用中，网络特性的表现大多依赖于某一个 方向上的性能，端到端时延的测量与估计就变得尤为重要。 本文提出了一种新的估计端到端时延的方法一往返规划算法，对正向与反向 相对两个方向上的时延进行测量，并假定每一个方向上经历最小时延的分组不经 历排队时延。把不同分组在两个方向上经历的最小时延之和看成是同一个分组经 历的“往返时延”。而当两个方向上经历最小时延的分组不在同一时刻发送时，这 个“往返时延”会受通信双方时钟频差的影响，本文采用调整其中任一分组发送时 刻的方法消除了此影响。通过理论验证了新方法较传统方法不会增加算法复杂 度，并通过实际测量证明了新方法具有更好的性能。 本文对i n t e m e t 端到端时延特性进行了分析，以实例说明了端到端时延具有一 定的自相似性和很强的非线性，构造了合适的泛函网络模型进行系统辨识，同时 对三条不同类型链路实测的端到端时延数据进行了验证，结果表明所构造的泛函 网络模型能较准确描述i n t e m e t 端到端时延的动力学特征。 关键词：端到端时延时间差频差往返时延泛函网络 a b s t r a c t a b s t r a c t w i t ht h ee x t e n d i n gs c a l ea n di n c r e a s i n gc o m p l e x i t yo fi n t e r n e t ，i ti sm o r ea n d m o r ed i f f i c u l tt od e s i g na n dm a n a g en e t w o r k s e f f i c i e n t l ya n de x a c t l yd e p i c t i n g i n t e m e tr t m n i n gs t a t u sa n dn e t w o r kc h a r a c t e r i s t i c si st h ek e yo fn e t w o r km a n a g e m e n t a n dm a i n t e n a n c e d e l a yi sa ni m p o r t a n tp a r a m e t e ri nn e t w o r kc h a r a c t e r i s t i c s ，w h o s e b e h a v i o rm o s t l yd e p e n d so nt h ep e r f o r m a n c ei no n ed i r e c t i o n s ot h em e a s u r e m e n ta n d e s t i m a t i o no fe n d - t o - e n dd e l a yi se s p e c i a l l yi m p o r t a n t i nt h i sd i s s e r t a t i o n ，an e wm e t h o dn a m e dr o u n d - t r i pp r o g r a m m i n ga l g o r i t h mi s p r o p o s e df o re s t i m a t i n ge n d - t o - e n dd e l a y i tm e a s u r e st h ef o r w a r da n db a c k w a r d d e l a y ss i m u l t a n e o u s l ya n da s s u m e st h a tt h ep a c k e tw h i c he x p e r i e n c e st h em i n i m u m d e l a yd o e s n ts u f f e rq u e u i n gd e l a yi ne a c hd i r e c t i o n t h es u mo ff o r w a r da n db a c k w a r d d e l a y so fd i f f e r e n tp a c k e t si sr e g a r d e d 嬲o n ep a c k e t s r o u n d - t r i pd e l a y m o r e o v e ri f t h ep a c k e t si nt w od i r e c t i o n sw h i c he x p e r i e n c el e a s te n d - t o - e n dd e l a y sw e r es e n ta t d i f f e r e n tt i m e ，t h i s r o u n d - t r i pd e l a y w o u l db ea f f e c t e db yc l o c ks k e w o u ra l g o r i t h m a d j u s t so n ep a c k e t ss e n d i n gt i m et oa n o t h e rt oa v o i dt h ee f f e c to fs k e w t h e o r e t i c a n a l y s i s s h o wt h a to u ra l g o r i t h mw i l ln o ti n c r e a s e c o m p l e x i t ya n dp r a c t i c a l m e a s u r e m e n t sp r o v et h a ti tp e r f o r m sb e t t e rc o m p a r e d 、i t he x i s t e n ta l g o r i t h m s t h ec h a r a c t e r i s t i c so fi n t e m e te n d t o - e n dd e l a ya r ea n a l y z e da n dm e a s u r e m e n t r e s u l t ss h o wt h a te n d - t o e n dd e l a yt i m es e r i e sb e h a v e ss e l f - s i m i l a ra n ds t r o n g n o n - l i n e a r af u n c t i o n a ln e t w o r km o d e li sp u tf o r w a r d m e a s u r e m e n tr e s u l t so nt h r e e d i f f e r e n tt y p e so fe n d - t o - e n dd e l a ym e a s u r e m e n tl i n k si n d i c a t et h a tt h ep r o p o s e d f u n c t i o n a ln e t w o r km o d e lc o u l dm a t c ht h ec h a r a c t e r i s t i c so fi n t e m e te n d t o - e n dd e l a y k e y w o r d ：e n d t o - e n dd e l a y o f f s e ts k e w r o u n d t r i pd e l a y f u n c t i o n a l l i e t w o r k 创新性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究成果。尽我 所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不包含其他人已经发表或 撰写过的研究成果；也不包含为获得西安电子科技大学或其它教育机构的学位或证书而使用 过的材料。与我一同工作的同志对本研究所做的任何贡献均己在论文中做了明确的说明并表 示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名：鲻 日期：趔塑呈业 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究生在校攻读 学位期间论文工作的知识产权单位属西安电子科技大学。本人保证毕业离校后，发表论文或 使用论文工作成果时署名单位仍然为西安电子科技大学。学校有权保留送交论文的复印件， 允许查阅和借阅论文；学校可以公布论文的全部或部分内容，可以允许采用影印、缩印或其 它复制手段保存论文。( 保密的论文在解密后遵守此规定) 本人签名：磁 导师躲赴 日期：型塑! 墨：! 兰 日期：p ? ! 生 第一章绪论 第一章绪论 1 1i p 网络的发展 i n t e m e t 最早来源于美国国防部高级研究计划局d a r p a ( d e f e n s ea d v a n c e d r e s e a r c hp r o j e c t sa g e n c y ) 的前身a r p a 建立的a r p a n e t ，它于1 9 6 9 年投入使用， 主要用于军事研究。最初的a r p a n e t 只有四台主机，其设计目标是：网络必须 能够经受住故障的考验而维持正常工作，一旦发生战争，当网络的某一部分因遭 受攻击而失去工作能力时，网络的其它部分应能够维持正常通信。二十世纪八十 年代初期a r p a 和美国国防部通信局研制成功用于异构网络的t c p i p 协议并投入 使用，作为i n t e m e t 的早期骨干网，a r p a n e t 奠定了i n t e m e t 存在和发展的基础l l j 。 到九十年代初期，在c e r n ( 位于瑞士的欧洲粒子物理实验室) 7 - 作的物理学家t i m b e m e r s l e e 发明了w o r l dw i d ew e b ，使用超文本标记语言( h y p e r - t e x tm a r k u p l a n g u a g e ，h t m l ) ，使在网页中包括超文本链接成为可能，因而使得普通用户可以 通过浏览器自由地访问网络上的信息，从而促使了i n t e r n e t 的巨大发展。其应用范 围也由最早的军事、国防，扩展到美国国内的学术机构，从而迅速覆盖了全球的 各个领域，运营性质也由科研、教育为主逐渐转向商业化【2 j 。 中国i n t e m e t 的发展与世界上大多数国家类似，都是由学术网络发展而来的。 1 9 8 7 年中科院高能物理所首先租用线路实现国际远程联网，并于1 9 8 8 年实现了与 欧洲和北美地区电子邮件通信。1 9 9 4 年5 月，以“中国科学院北京大学 清华大学为核心的中国国家计算机网络设施( t h en a t i o n a lc o m p u t i n ga n d n e t w o r k i n gf a c i l i t yo fc h i n a ) 与国际互联网联通，表明i n t e r a c t 在中国实现开放。随 着经济发展的全球化以及通信信息技术的迅猛发展，中国的互联网发展突飞猛进。 最近召开的2 0 0 8 年中国互联网大会指出，截至今年上半年中国网民人数突破2 5 3 亿，已成为世界上网民最多的国家，几乎每五个人中就有一个网民。近年来中国 互联网始终保持快速发展，无论是固定网、移动网、还是互联网，中国的网络规 模容量及用户数都居世界第一，今年六月与去年同期相比，中国网民人数在一年 之内增加了9 1 0 0 万人，同比增长5 6 2 ，是历年来网民增加最多的一年p j 。 1 2 研究意义与背景 网络特性的有效测量和准确估计是网络运营和维护的重要因素。由于i n t e m e t 的分布化、不协作、异质等特点，直接从各种网络设备收集数据，反映网络的实 际运行情况，只局限在可管理的较小范围之内。而掌握更大范围、更具有普遍意 义的网络运行参数，对现代网络发展具有很强的现实意义【4 1 ，具体来说，研究i p 2 l p 网络中端到端时延特性的测量与估计 网络测量的意义主要表现在以下几个方面： ( 1 ) i p 网络性能监控的需要 网络测量为网络开通后提供性能检验、考核指标的手段，为网络工程提供验收 依据，为网络运营提供实时或阶段性性能监控工具，通过测量可进行网络诊断， 通过网络流( f l o w ) 的测量可提供计费依据等等； ( 2 ) i p 网络安全评估、入侵检测与防护的需要 网络安全是用户和i s p 、a s p ( a p p l i c a t i o ns e r v i c ep r o v i d e r ) 考虑的首要问题之 一，借助于端口扫描等手段对i p 网络进行脆弱性分析( v u l n e r a b i l i t ya n a l y s i s ) ，能 使网管人员及时查漏补缺，合理配置防火墙及网络参数，制定相应的安全策略， 在入侵还没有发生前尽量杜绝它； ( 3 ) 研究网络新技术的基础 网络测量为q o s 控制技术如资源预约协议( r s v p ) 的接入控制、拥塞控制技术 提供了定量选择参数的依据； “) 网络管理的有力补充 计算机网络的巨大发展，促进了网络管理研究的发展，从而刺激了对网络测量 的需求。过去的集中式网管由于缺乏伸缩性、灵活性，难以适应网络规模和复杂 性的飞速发展，分布式网络管理成为一个重要的研究方向； ( 5 ) 与信息战密切相关 在最近的几场战争中，如海湾战争、科索沃战争、阿富汗战争、伊拉克战争， 信息优势对整个战争的胜败具有主导地位，谁掌握了信息权，谁就会赢得战争的 胜利。 时延是网络性能指标中的重要参数。它体现了不同业务数据流竞争网络资源的 效果，反映出报文传输过程中排队拥塞的情况，是网络服务质量优劣的关键衡量 标准。它对网络的运营管理、协议开发与技术发展具有重要意义： ( 1 ) 它是评估网络服务质量( q o s ) ，验证网络运营商与客户之间服务等级协议 ( s l a ) 的重要指标之一； ( 2 ) 能用来研究有效的拥塞控制机制，根据获得的时延动力学特征及建立的模 型，预测时延的变化情况来调整传输策略。这样使得到的算法、设定的参数更符 合实际网络运行规律； ( 3 ) 对于时延敏感型业务，如流媒体应用，可作为播放( p l a yo u t ) 控制、接入控制 的依据： ( 4 ) 可作为度量网络路径性能的指标( m e t r i c ) ，用以进行路由优化和路由动态更 新； ( 5 ) 可用作网络优化的依据，据其制定负载均衡策略，同时能给新的网络应用， 如c d n ( c o n t e n t i o nd i s t r i b u t i o nn e t w o r k ) 提供支持。 第一章绪论 ( 6 ) 时延测量还可以为可用带宽、报文丢失率等其它特性参数的估计提供极其有 用的信息。 1 3 本文研究的主要内容及章节安排 本文所研究的内容来自国家自然科学基金项目i p 网络时钟同步算法，受西 安市科技攻关项目、高等学校学科创新引智计划等资助。研究了i p 网络端到端时 延的测量与估计，提出了一种往返规划算法，估计收发时钟的频差和初始相位差， 以获得端到端时延的准确估计。克服了常用的端到端时延测量大多依赖于g p s 接 收机或采用n t p 协议来实现收发端时钟的同步，而g p s 接收机在某些接收环境下 不能使用、n t p 协议的精度不能满足要求的缺点。我们在多条不同的链路上进行 了测试，理论与结果均表明该算法在不增加算法复杂度的情况下能有效消除收发 时钟不同步的影响。 研究了i n t e m e t 端到端时延动力学特征。对多条链路测试发现：i n t e m e t 端到端 时延具有非线性、非平稳的特征，而且不同链路其自相似性( s e l f - s i m i l a r i t y ) 程度不 同。通过构造合适的网络结构及泛函神经元函数，利用泛函网络进行系统辨识， 准确描述了端到端时延的非线性特征，同时对泛函神经元函数的参数进行自适应 修正，适应了时延的非平稳性。对三条不同类型链路实测的端到端时延数据进行 验证，结果表明所构造的网络结构以及提出的自适应算法能准确描述i n t e m e t 端到 端时延的动力学特征。 本文共分五章。第一章概述了口网络发展现状及网络端到端时延测量的研究 意义；第二章介绍了时延测量的基本理论、方法并描述了几种经典的时钟同步算 法；第三章提出了一种新的估计端到端时延的方法一往返规划算法，并与其它两 种经典的时钟同步算法进行比较，对其性能进行了验证；第四章以测量实例证明 了端到端时延的自相似性和非线性特征，并设计出一种泛函网络模型对未发生的 时延进行估计，并应用于测量实例，对其性能进行了评估；第五章总结全文，并 提出了下一步的工作内容。 第二章时延测量基本理论与几种经典时钟同步算法 第二章时延测量基本理论与几种经典时钟同步算法 端到端性能测量是网络测量的重要内容之一，测试数据包往往要跨越多个自治 域，依靠网络管理工具难以实现直接测量，因此需要设计专门的测量方法。本章 主要介绍网络测量技术基本理论、端到端时延测量的基本方法以及几种经典的端 到端时延的估计方法。 2 1 网络测量基本理论与方法 网络测量就是按照一定的方法和技术，利用软件或硬件工具来测试网络运行状 态，表征网络特征的一系列活动的总和。网络测量一般包含三个要素1 ) n 量对象， 就是被测量的节点和链路以及待测量节点、链路或者网络上的某种特性；2 ) n 量环 境，包括测量点的选取，测量时间的确定，测量设备、通信链路类型等：3 ) 测量方 法，就是针对某一具体的网络行为指标，应选取合适的测量方法，测量方法至少 应满足稳健性即被测网络的一点变化，不会使测量方法失效；其次，可重复 性即同样的网络条件，多次测量结果应一致；再次，准确性测量结果应 能反映网络的真实情况。 2 1 1 基本理论 目前，i n t e m e tt 程任务组( i e t f ) 的i p p m ( i pp e r f o r m a n c em e t r i c ) t 作组已定义 了一些i n t e m e t 度量的指标，并指出了度量的框架。常用的按指标内容可以划分为 ( 1 ) 连通性：各网络组件间的互连通性； ( 2 ) 吞吐量：单位时间内通过网络传送给定点的数据量； ( 3 ) 分组转发率：单位时间内转发的数据包的数量； ( 4 ) 带宽：单位时间内所能传送的比特数； ( 5 ) 信道利用率：一段时间内信道处在占用状态的时间与总时间的比值； ( 6 ) 瓶颈带宽：端到端路径上的最大带宽； ( 7 ) 可用带宽：一条端到端路径在不降低竞争业务( c r o s st r a f f i c ) 吞吐率的前提下能给 一个新的数据流提供的最大吞吐率，即最大剩余带宽； ( 8 ) 带宽利用率：实际使用的带宽与链路容量的比率； ( 9 ) 包丢弃数：在一段时间内网络传输及处理中丢失或出错的信息包数： ( 1 0 ) 包丢弃率：包丢弃数与总包数的比率； ( 1 1 ) 时延：数据分组在网络传输中的延迟时间( 包括单向时延和往返时延) ； ( 1 2 ) 时延抖动：连续的数据分组传输延时的变化； 6 i p 网络中端到端时延特性的测量与估计 ( 1 3 ) 批量传输容量：网络传输单个具有拥塞意识的连接( 如能使用t c p 协议的连接) 能传输的最大数据速率。 按指标内容划分是基础的性能指标体系，它反映了对i p 网络系统的基本测试内 容。 2 1 2 基本方法 网络测量方法的划分有几种形式： ( 1 ) 主动测量和被动测量 主动测量是将测量分组注入网络进行测量，优点是易于控制，缺点是给系统增 加了额外的负载，影响系统性能；被动测型5 】是在网络的测量点处布置数据采集器， 收集流经该点的网络业务流，进行分析、提取业务的特征，获得性能数据，优点 是对系统性能影响小，缺点是难以分离出网段、不易控制。 ( 2 ) 单点测量和多点测量 大部分的网络测量都是分布式的多点测量。 ( 3 ) 合作测量和非合作测量 合作测量对网络运营者来说，可以掌握网络的运行情况，业务分布情况，找出 瓶颈等，以便有效的管理网络、充分利用网络资源。非合作测量是指被测网络不 乐意被别人测量，测量的目的是想了解对方网络的情况，这在军事上有非常重要 的意义。 ( 4 ) 单向测试和环回测试 单向测试是指探测分组在网络的源端进入网络，在目的端输出，根据输出参数 来评价网络性能；环回测试是指探测分组在网络源端进入网络，到达目的端后转 发回源端输出，根据输出参数来评估网络性能。环回测试的主要优势是测试配置 简单，成本低。但在某些情况下，进行单向测试更有意义： 1 )在i p 网络里，从源端到目的端的路径可能和目的端到源端的路径不一样 ( 不对称路径) ，路径所经过的路由也不一样，因此，每个路径单独测试 而不是像环回测试将两个不同路径一起测试，突出了两个路径的不同特 性，而这两个路径可能是属于不同的网络运营商，或者根本不同的网络； 2 )即使两个路径对称，由于不对称队列，它们可能具有根本不同的性能属 性； 3 )一个应用性能可能主要取决于一个方向上的性能。例如，使用t c p 的文 件传输可能更取决于数据流动方向上的性能，而跟应答方向上的性能基 本无关。 采用单向测试时，测试点往往位于不同的地点，就必须解决主机时钟之间同步 第二章时延测量基本理论与几种经典时钟同步算法 7 的问题。 2 2 1 时延概述 2 2 端到端时延的测量 网络的时延主要分为往返时延( r o u n d t r i pt i m e ，r y r ) 和单向时延( 即端到端时延， e n d t o - e n dd e l a yo ro n ew a yd e l a y ) 两类。往返时延是指一个固定大小的i p 数据报 从源端到目的端又从目的端回到源端往返所需要的时间间隔；端到端时延是指发 送固定大小的i p 探测数据报，到达目的端时刻与离开源端时刻之差【6 j 。 在实际测量中，由i p 报文到达目的端的时间戳减去其从源端发送时的时间戳 就是端到端时延的估计值。但是这两个时间戳必须使用相同的时钟进行记录，否 则不同时钟之间的差异会给时延测量带来严重的误差。影响m 报文网络时延的因 素主要有三大类1 ) 网络本身的性能，即完全独立于网络测量方法，仅与网络本身 的硬件特性相关，包括网络的物理层介质、传输所需的路由转发等分组处理的次 数和速度、网络数据链路层协议的不同实现方式等；2 ) 用于测量的数据报文的特性， 这与网络测量的具体方式密切相关，主要包括承载测量报文的协议类型、报文长 度、发送频率等；3 ) 当前的网络流量，网络负载比较重时，其传输和处理速度就会 大大下降，此时的i p 数据报文就会经历较长的时延。 一般说来，分组的端到端时延由4 个部分组成：传播时延、传输时延、处理时 延、排队时延。 ( 1 ) 传播时延f 。( p r o p a g a t i o nd e l a y ) 是分组的第一个比特从发送节点到达接收节 点在传输链路上经历的时间，f 。由电磁波通过通信链路的物理信道的传播时间所决 定； ( 2 ) 传输时延t , ( t r a n s m i s s i o nd e l a y ) 是发送节点在传输链路上开始发送分组的第 一个比特至发送完该分组的最后一个比特所需要的时间，f f 主要由连接速度或容量 决定： ( 3 ) 处理时延f 。( p r o c e s s i n gd e l a y ) 是分组从一个节点的输入端到达该节点的输出 端所经历的时延，它受每个节点的计算能力和可用的硬件的影响； ( 4 ) 排队时延乞( q u e u i n gd e l a y ) 是分组在路由器的缓冲区中传输或处理前的等待 时间，t o 由路由器中的交换结构决定。若节点的传输队列在节点的输出端，则排队 时延是指分组进入传输队列到该分组实际进入传输的时延，若节点的输入端有一 个等待队列，则排队时延是指分组进入等待队列到分组进入节点进行处理的时延。 i p 网络中端到端时延特性的测量与估计 2 2 2 时延测试方法 图2 1 端到端时延实测结果 一个未经同步的实际端到端时延测量结果如图2 1 所示，其中横轴是分组序列 号，纵轴是时延测量值( 淞) ，由图可见测量结果为负值且有一个近似线性的趋势， 这说明收发双方时钟之间存在明显的时间差和频率差。单向时延测量最主要的问 题是解决两个待测节点之间本地时钟的不同步。而时钟同步问题是国防建设和国 民经济很多领域都需要解决的问题。因而也产生了各种不同精度的时钟同步方法 和授时系统。如短波授时、长波授时、电话网授时、i n t e m e t 授时、卫星授时等等。 从方法上讲，时钟同步方法有以下3 种： ( 1 ) 搬钟( c l o c kt r a n s p o r t a t i o n ) 时间同步法 用一个标准钟作为搬钟，然后用此搬钟比对校准系统中的时钟。首先让系统的 标准时钟比对校准这个搬钟，然后将系统的其它时钟与搬钟同步对比，实现系统 其它时钟与系统统一标准时钟同步。搬钟方法虽然简单，但是在搬运过程中会受 到搬运方法和环境的影响。甚至在搬至异地后由于地理条件的不同，环境不同可 能会引起标准钟的变化。另外，要保持较高精度的时钟同步，就需要经常进行搬 钟同步对比，很不方便。因此这种方法不能实时或近实时作时钟同步，现在很少 采用。 ( 2 ) 单向时间同步法 在单向时间同步法中，主站通过各种途径将同步信息传送给从站，从站根据这 些同步信息采用一定的算法校正到主站的时间和频率上。为了精确定时，同步信 息应该包括主站精确坐标、主站系统频率及时间等。从站利用直接或间接得到的 自己的坐标与主站给定的坐标计算信号传播的时延，然后利用计算得到的时延、 主站系统时间、距离时延校正以及从站接收机时延校正就可以较正本站的时间， 利用主站发送过来的系统频率就可以较正本站频率。在同步精度要求比较高时， 也可以用主站的系统时间采用比时法来校正从站频率。由于传播途径环境的复杂 性，距离时延误差因传播信号的途径的不同而差异很大。总得来说，单向时间同 步法的时刻同步精度大部分只能达到微秒级别，校频精度一般比主站频率准确度 小一两个数量级。但是该方法所用设备相对简单。 第二章时延测量基本理论与几种经典时钟同步算法 9 ( 3 ) 双向时间同步法 主站 从站 图2 2 双向时i 司同步法原理不慈图 双向时钟同步法的原理如图2 2 所示。设主站和从站的钟差为f ( 某时刻主站时 钟时刻与从站时钟时刻之差) ，主站在其时刻口发带有该时刻信息的伪码信号给从 站，从站测得信号到达时本地时钟时刻为c ，假设信号从主站到达从站不受环境影 响的理想情况下所需时间为t ，而由环境影响引起的误差传播时间为乞，那么从站 得到测量的伪时延( 同步前) r l = 玎一学= a t + f + 屯 ( 2 1 ) 从站随后把这个测量值发给主站，同样在从站时钟的碚时刻发送带有该时刻信息的 伪码信号给主站，主站测得信号到达本地时钟时刻伪彳，因为是同样的传输途径 所以传播所用时间也为f + t ，则主站得到的伪时延 t 2 = r 一蝠= t + t a t ( 2 - 2 ) 主站把两个伪时延相减就可以消去传播时间和误差时间，即，1 一t 2 = 2 a t ，然后主站 把计算出来两站的钟差发给从站用以校正。从站根据钟差和主站时间校正本地时 间，根据主站频率校正本站频率。 由于双向时间比对在原理上可以消除共同的传播路径误差，所以这种方法可以 使同步精度达到纳秒级，校频精度一般比主站频率准确度小一两个数量级。但是 主站需要配备昂贵的高精度原子基准，而且主站和从站都要向对方发送信号并进 行伪时延测量，所以系统设备相对于单向时间同步法较复杂，成本较高。尤其是 主站，因为要同时和很多从站实现同步，工作量特别大，可靠性差。我国的“北 斗一号导航系统就是用此方法来实现定时和校频的。 在已有的单向时延测量实验中，大多数均借助于g p s ( g l o b a lp o s i t i o n i n gs y s t e m ) 接收机或n t p ( n e t w o r kt i m ep r o t o c 0 1 ) 来实现同步。 1 基于g p s 授时的时钟同步 g p s 是美国国防部为满足军事部门对海上、陆地和空中设施进行高精度导航和 定位而建立的导航与定位系统，它具有全球性、全天候、连续的精密三维导航和 定位能力，同时具有良好的抗干扰和保密性，在军事和民用方面都得到了很大的 应用。 1 0 i p 网络中端到端时延特性的测量与估计 是f x 2 儿乙)墨( 弓咒白) 图2 3g p s 工作原理示意图 g p s 基本定位原理如图2 3 所示：卫星不间断的发射自身的星历参数和时间信 息，用户接收到这些信息后，经过计算求出接收机的三维位置、三维方向及运动 速度和时间信息。每颗卫星连续不断的向g p s 接收机发送可跟踪的唯一编码序列， g p s 接收机可根据编码辨认相关的卫星，进而计算出接收机的确切位置和准确时 间。因此，测出每颗可视卫星的导航信号从卫星到用户接收设备天线的传播时间 乘上电波传播速度，即可计算出卫星到用户接收设备天线间的距离。测量传播时 间要用到两个不同的时钟，第一个时钟在卫星上，记录信号发射时间，第二个时 钟在接收机上，记录信号接收时间。这两个时钟不同步，因而在时间的测量上存 在偏差，所以需要4 颗卫星的信号，组建以下方程组： ( 五一吒) 2 + ( 乃一儿) 2 + ( 而一乞) 2 = c 2 ( 岛+ a t q ) 2 鬟悠二嬲搿凳二：二 ， ( 毛一吒) 2 + ( 乃一儿) 2 + ( z 3 一气) 2 = c 2 ( 岛+ ，一巧) 2 ( x 4 一旄) 2 + ( 儿一儿) 2 + ( z 4 一乙) 2 = c 2 ( 反+ f 一) 2 其中五，咒，刁是卫星位置，屯，y u ，乞是用户位置，c 是无线电波速度，房是用户测 得与第f 个卫星之间的伪距( 分别采用用户时钟和卫星时钟) ，f 是用户时钟和g p s 主时钟标准时间的时间差，t 是卫星f 上原子钟与g p s 主时钟标准时间的时间差。 由方程组可知，要求预先知道卫星位置坐标、屏、t ，卫星位置坐标可根据控制 部分测出并由加在信号中的卫星天文历数据推算出来，肛由接收机测量和导航电 文获得，z i 可由导航电文获得，代入方程组可计算出接收机的坐标和出，这就是 g p s 定位和授时原理。 g p s 由3 部分组成：空间部分、控制部分和用户设备部分。g p s 的空间星座部 分由2 4 颗导航卫星( n a v s t a r ) 组成，g p s 卫星的基本功能是接收和存储来自地面监 控站的导航信息，接收并执行监控站的控制指令，通过星载的高精度铷钟和铯钟 提供精密的时间基准，卫星上设有微处理机进行部分必要的数据处理工作，向用 户发送导航和定位信息，在地面监控站的指令下通过推进器调整卫星的姿态和启 第二章时延测量基本理论与几种经典时钟同步算法 1 1 用备用卫星；控制部分主要由分布在全球的5 个地面站组成，包括主控站、监测 站、地面注入站，主控站协调和管理所有地面监控系统的工作，监控站是在主控 站直接控制下的数据自动采集中心，站内设有双频g p s 接收机、高精度原子钟、 计算机和若干环境数据传感器，接收机对g p s 卫星进行连续观测，以采集数据和 检测卫星的工作状况，原子钟提供时间标准而环境传感器收集有关当地的气象数 据，所有观测数据由计算机进行初步处理并存储和传送到主控站，地面注入站的 主要任务是在主控站的控制下，将主控站推算和编制的星历、钟差、导航电文和 其它控制指令注入到相应卫星的存储系统，并监测注入信息的正确性；用户设备 部分的主要任务是接收g p s 卫星发射的信号，以获得必要的导航和定位信息及参 数，经过数据处理，完成导航和定位的工作，它主要由g p s 接收机硬件( 包括主机、 天线、电源) 、数据处理软件以及微处理机和其终端设备组成。 基于g p s 授时的时钟同步方法可以达到亚纳秒级的精度，但为了获得亚纳秒 级的精度所需要的接收机比较昂贵，而且在有遮挡时接收机有时不能接收卫星信 号，在某些场合如保密性要求较高时不适用。 2 基于n t p 的时钟同步方法1 7 j n t p 最早由美国特拉华大学( u n i v e r s i t yo f d e l a w a r e ) d a v i dl m i l l s 教授于1 9 8 5 年提出。n t p 是通过网络实现计算机时钟的同步，最典型的操作模式是客户服务 器模式。由于时间同步工作是通过网络实现的，而网络传输是需要时间的。这样 客户机接收到服务器返回报文中的时间戳，并不能代表服务器当前的准确时间， 而是一段时间之前的时间信息，这一段时间就是网络传送所花费的时间。因此， 要获得准确的当前时间就必须考虑网络延迟造成的影响。如果仅仅依靠网络的单 程传送来获取网络的延迟信息也是不精确的，这是因为同步两端的时钟是不一致 的，仅仅依靠两个时间戳不能确定网络时延。实际上，可以通过计算报文的往返 时间来估计网络时延。如图2 4 所示，z 是客户机发送请求报文时客户机的时钟读 数( o r i g i n a t et i m e s t a r n p ) ；正是服务器接收到客户机请求报文时服务器的时钟读数 ( r e c e i v et i m e s t a m p ) ；互是服务器返回响应报文时服务器的时钟读数( t r a n s m i t t i m e s t a m p ) ；正是客户机接收到服务器的响应报文时的客户机时钟读数。 为 淤么 客户机 服务器 图2 4 n t p 工作原理 则客户机和服务器之间的时问偏移量秒和报文在网络的往返传输延时d 分别 i p 网络中端到端时延特性的测量与估计 秒= i 1u t ：一互) + ( 巧一瓦) ( 2 - 4 ) d = ( 五一五) 一( 五一互) ( 2 - 5 ) 这里假定从客户到服务器和从服务器到客户的时延相等，而且假定偏移量秒不 随时间变化，即不考虑两者时钟之间的频率差( s k e w ) 和抖动0 i t t e r ) 。此时同步问题 就归结为对p 的估计。n t p 同步算法就是基于这样二_ 个准则，通过各种算法来获 取对偏移量的准确估计。同时由于网络传输的往返路径往往是不对称的，这不仅 有路由器、网关等设备负荷的影响，而且在一次往返传输过程中，路由表的改变 也会影响到往返时延的测量。 图2 5n t p 基本实现模型 n t p 系统采用层次式时间分布模型，其网络结构包括主时间服务器、从时间服 务器及客户与节点间的传输路径。n t p 基本实现模式如图2 5 所示，在客户机自身 对应的独立定时器驱动下，发送进程收集数据库信息，并把n t p 消息发送到对端 机。各消息含有在发送时刻的本地时间戳，加上接收到的时间戳，以及其它用以 确定分层和管理协同的必要信息；接收进程负责接收n t p 消息及其它协议的消息 以及来自直接相连的时钟的信息，当接收到n t p 消息时计算服务器时钟和本地时 钟之间的偏移，采用过滤算法舍弃低劣的数据，将结果和其它用于确定误差的信 息和选择服务器的信息一起存入数据库；更新进程是在接收到消息的情况下启动， 它处理来自各服务器的偏移数据，用时间选择算法选择最佳者；本地时钟进程是 用来对更新进程产生的偏移数据进行操作，使用时钟调节算法来调节本地时钟的 相位和频率，通过本地时钟的步进改变和渐进相位调节，以把时钟偏移减少到零， 使得本地时钟能够向系统中的其它用户提供稳定的时间信息来源，并且为n t p 本 身的运行提供稳定准确的时间数据。 n t p 是一个跨广域网或局域网的复杂的同步时间协议，它通常可获得毫秒级的 精度。 n t p 协议被广泛的应用于互联网中，很多研究人员致力于n t p 协议的研究： 文献【8 】描述了对n t p 版本3 从精度、稳定性和可靠性方面的改进方法；也有很多 类似n t p 的协议出现，如服务器时间协议s t p ( s e r v e rt i m ep r o t o c 0 1 ) n 是i b m 在 2 0 0 5 年7 月正式推出的，它采用了与n t p 相类似的基于信息的分层机制；文献 1 0 】 提出了把负载平滑技术用于每个需要同步的节点以获得更高的同步精度；a 第二章时延测量基本理论与几种经典时钟同步算法 1 3 s o b e i h 等基于n t p 客户服务器模式提出了一种a p 2 p ( a l m o s tp e e r - t o p e e r ) 方法【l i 】， 能从连续的同步标准节点故障中迅速恢复，但是同步精度最高也只能达到几十微 秒。 2 3 几种经典时钟同步算法 在上一节介绍的同步方法中，g p s 接收机一般价格昂贵而且与接收环境相关， n t p 的精度太低，因而人们试图找到一种不依赖于g p s 接收机且比n t p 精度高的 方法来实现端到端时延的估计。在测量时，这一类方法中数据包的发送和到达时 间分别以发送端和接收端的本地时钟为参考，基于时延特征采用数学分析来估计 收发时钟的频率差( 两个时钟“走”的快慢程度之比) 和初始时间差( 两个时钟在开 始测量时刻的时间差) 。本节着重介绍几种经典的基于数学分析的时钟同步算法。 2 3 1vp a x s o n 算法【1 2 】 p a x s o n 分析了端到端时延特性【1 3 】，测量正向与反向两个方向上的原始数据， 分别提出了消除初始时间差与频率差的方法： 1 时间差的消除 假定通信双方两时钟之间的频差为零，并假定分组在正向与反向经历的时延相 等为r ，用c ，表示收发时钟的时间差。若分组从源端出发的时刻为岛( 以发端 时钟为基准) ，到达收端的时刻为，；( 以收端时钟为基准) ，而另一个分组在反方向上 测量得到的发送时刻为巧、接收时刻为岛，则 r t = 五+ 丁+ a c r ( 2 - 6 ) j 2 = r z + a t 一c ，j ( 2 - 7 ) 则上两式相减可得 c j 2 ( 2 8 ) 2 频差的消除 假定时钟之间的频差是线性的。用7 7 表示收端时钟c 比发端时钟e 走的快慢 的程度，即如果e 标记一段时间间隔为r ，则c ，标记这段时间间隔为班r 。用q 、 g ，分别表示发端与收端时钟的线性趋势，假定分组p 。以发端时钟为基准的发送时 刻为r ，以收端时钟为基准的接收时刻为才，类似的，分p 2 的发送时亥0 为巧， 接收时刻为砰，而且假定每个分组的传输时间是恒定的，则测量得到的端到端时 延 红= 刀一贮，唬= 彳一巧 ( 2 9 ) 则 伊网络中端到端时延特性的测量与估计 欢= 磊+ g ( 巧- r j ) ( 2 1 0 ) 则 g = 霭r - r 一l = ，7 一l ( 2 - 1 1 ) 同理可得 g ，：i - 1 ( 2 - 1 2 ) 若刁= l + 占，当l s l l ， q = s ，g ，= 一三l + s 一g ( 2 - 1 3 ) 由于时钟频差往往是千分之几或万分之几的量级，式( 2 1 3 ) 1 撇将不会带来 太大的误差。即正向与反向时延的斜率相等但趋势是相反的。 假定有力个观察值。，1 f 刀，其中是观察的时间，不失一般性，假定时 延具有下降的趋势，令 l _ 鬣一州孵户1 也就是l 等于1 时代表了一个新的累积最小值，令 鸩= ( 2 1 4 ) 表示从第一个到第歹个观察值累积最小值的个数。当测量值没有下降趋势时，m ， 的分布将不依赖于气，也就是我们能够找到一些累积最小值但不会很多。如果我 们找到鸠= 后，就是薯有七个累积最小值，我们希望计算获得累积最小值的概率 r ( n ，七) = p 【心明，如果这个概率足够小，就推翻下降趋势的假定，可以递归的 计算尺( 甩，k ) r ( 甩，七) = 1 ，k = 0 ! ，k = ，l ( 2 - 1 5 ) r(n-1,k-1)+(n-1)r(n-1,k)，七 0 ；a c = 口 ( 2 - 2 6 ) 其中c 表示所有时延固定部分测量值序列，孑是对c 的估计；式( 2 2 6 ) 表示每条链 路时延的固定部分都不小于零，且已知拓扑中多条环路的固定时延之和。 目标函数( 2 ) ： s = p , j l o g p o ( 2 - 2 7 ) e u e c 限制条件： 岛o ，p , j = 1 ，p u = 屈 ( 2 - 2 8 ) e q qe q r l 其中g 表示网络拓扑中所有链路集合，n 表示分组选择f 一_ ，链路的概率，r 代 表链路中的环路，屏表示分组选择环路k 的概率。 2 3 4w e i x u a ng u 等人的算法1 1 7 】 w e i x u a r lg u 等人分析了探测分组输入时间间隔与输出时间间隔的关系，推导 第二章时延测量基本理论与几种经典时钟同步算法 1 7 出单向排队时延的描述形式提出了排队时延分布特性的估计方法。 f 和，分别表示第f 组分组对2 个探测分组发送时间间隔和接收时间间隔， 刃和彳分别表示这两个分组的端到端时延，卅= 4 + e ，刃= 彳+ 谚，q 和v f 分别 是时延的固定部分和可变部分 罗= ，一卅+ 砰 = ，+ ( 订一q ) ( 2 - 2 9 ) 用置表示两个时间间隔之差 t = 罗一7 = v ；一v ； ( 2 - 3 0 ) 当，足够大，使得分组对内2 个分组不在链路的同一个输出队列中出现，那 么测量期间这一串探测分组经历的端到端单向排队时延就是独立且