（通信与信息系统专业论文）互联网端到端时延测量方法的研究与实现.pdf

摘要 随着i n t e m e t 规模和复杂性的不断增加，网络设计、优化和管理操作越来越困 难，高效准确地描述i n t e m e t 运行状况和网络特性是网络运营和维护的关键。时延 是网络性能指标中的重要参数，在实际应用中，网络特性的表现大多依赖于某一 个方向上的性能，因此端到端单向时延的测量与估计就变得尤为重要。 本文提出了一种新的监控网络上端到端时延状况变化的方法，基于统计平均的 理论，计算网络上两测试端的时钟频差，从而较为准确的监控端到端时延变化。 根据发送端与接收端的不同间隔，采用大间隔大量采样取比值并求平均的方法来 估算两时钟的频率差，然后根据求得的频率差实时调整时延状况曲线，真实反映 出网络时延的变化趋势。通过对网络拓扑结构和网络协议的详细分析，从理论上 证明了算法的正确性，并且在v c h 6 0 环境下，通过网络编程实现了对该理论的 验证。实验证明该方法能准确有效地反映网络时延变化，为分析网络性能提供有 力支持。 关键词：时钟同步端到端时延时钟频差网络编程 a b s 仃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 a c t ，i ti sm o r ea n dm o r e d 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 t oe v a l u a t ei n t e r n e tr u n n i n gs t a t u sa n dt ok n o w n e t w o r kc h a r a c t e r i s t i c se f f i c i e n t l ya n de x a c t l yi st h ek e yt a s k sf o rn 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 so n eo ft h ei m p o r t a n tp a r a m e t e r si nn e t w o r kc h a r a c t e r i s t i c s ， t h eb e h a v i o ro fw h i c hi sm o s t l yd e p e n d e n to nt h ep e r f o r m a n c eo fo n ew a y s oi ti s e s p e c i a l l yi m p o r t a n tt om e a s u r ea n de s t i m a t et h ee n d - t o e n dd e l a y an e wm e t h o do nm o n i t o r i n gt h ed e l a yp e r f o r m a n c eo ft h en e t w o r kf r o me n dt o e n di sp r o p o s e di nt h i sd i s s e r t a t i o n t h i sm e t h o di sb a s e do nt h es t a t i s t i c sa n da v e r a g e b yc a l c u l a t i n gt h ec l o c kf r e q u e n c yd i f f e r e n c eo ft h et w ot e r m i n a l so nt h en e t w o r k , t h ee n d - t o - e n dd e l a yv a r i a t i o nc a nb em o n j i t o r e dm o r ea c c u r a t e l y a c c o r d i n gt ot h e d i f f e r e n ti n t e r v a l sb e t w e e ns e n d e ra n dt h er e c e i v e r , u s i n gl a r g ei n t e r v a la n dl a r g e n u m b e ro fs a m p l e so b t a i n e d , t h ea v e r a g er a t i oi sc a l c u l a t e d , w h i c hc a nb ea p p l i e dt o a p p r o x i m a t et h er e a lc l o c kf r e q u e n c yd i f f e r e n c e f u r t h e r m o r e ，t h ea p p r o x i m a t ev a l u e c a nb eu s e dt oa d j u s tt h ed e l a yc u r v ei nt i m ei no r d e rt og e tt h et r u es t a t u so ft h e n e t w o r k i no r d e rt ov a l i d a t et h i sm e t h o d , t h et o p o l o g ya n dt h en e t w o r kp r o t o c o l sa r e a l s oa n a l y z e d b yp r o g r a m m i n gt h ec o d ei nv c 十+ - 6 0e n v i r o n m e n tat e s t i n gt o o li s i m p l e m e n t e d b o t ht h e o r e t i ca n a l y s i sa n de x p e r i m e n tr e s u l t ss h o wt h a tt h i sm e t h o di s u s e f u l l yo nr e f l e c t i n gt h ec h a n g e so fn e t w o r kd e l a ya n dc a nb eu s e dt op r o v i d es t r o n g s u p p o r tf o rt h ea n a l y s i so fn e t w o r kp e r f o r m a n c e k e y w o r d ：c l o c ks y n c h r o n i z a t i o n e n d - t o - e n dd e l a y c l o c kf r e q u e n c yd i f f e r e n c en e t w o r k p r o g r a m m i n g 西安电子科技大学 学位论文创新性声明 秉承学校严谨的学风和优良的科学道德，本人声明所呈交的论文是我个人在 导师指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以标 注和致谢中所罗列的内容以外，论文中不包含其他人已经发表或撰写过的研究成 果；也不包含为获得西安电子科技大学或其它教育机构的学位或证书而使用过的 材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中做了明确的说 明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切的法律责任。 本人签名：孝虹 西安电子科技大学 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究 生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。学校有权保 留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全部或部分内 容，可以允许采用影印、缩印或其它复制手段保存论文。同时本人保证，毕业后 结合学位论文研究课题再撰写的文章一律署名单位为西安电子科技大学。 ( 保密的论文在解密后遵守此规定) 本学位论文属于保密，在解密后适用本授权书。 本人签名：窭丕也 导师签名：陟角导师签名：垡! 趟日期纠生塑 第一章绪论 第一章绪论 1 1i p 网络的发展 i n t e r n 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 r n e t 的早期骨干网，a r p a n e t 奠定了i n t e r n e t 存在和发展的基础【l 】。 到九十年代初期，在c e r n ( 位于瑞士的欧洲粒子物理实验室) - r 作的物理学家t u n 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 m e t 的巨大发展。其应用 范围也由最早的军事、国防，扩展到美国国内的学术机构，从而迅速覆盖了全球 的各个领域，运营性质也由科研、教育为主逐渐转向商业化1 2 。 中国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 f c h i n a ) 与国际互联网联通，表明i n t e r n e t 在中国实现开放。随 着经济发展的全球化以及通信信息技术的迅猛发展，中国的互联网发展突飞猛进。 2 0 0 8 年中国互联网大会指出，截至今年上半年中国网民人数突破2 5 7 亿，已成为 世界上网民最多的国家，几乎每五个人中就有一个网民。近年来中国互联网始终 保持快速发展，无论是固定网、移动网、还是互联网，中国的网络规模容量及用 户数都居世界第一，今年六月与去年同期相比，中国网民人数在一年之内增加了 9 1 0 0 万人，同比增长5 6 2 ，是历年来网民增加最多的一年【3 j 。 1 2 研究意义与背景 随着网络的发展和大规模普及，网络已经深入每一个人的生活，与我们每一个 人息息相关。可以说，网络性能的好坏决定了我们生活质量的好坏。因此，人们 越来越多的关注网络性能，网络性能测试技术也相应的得到了快速发展。 作为网络运营和维护的重要因素，网络测量的结果应该能够准确反映出网络的 2 互联网端到端时延测量方法的研究与实现 状况，提供我们需要的数据。根据网络性能的不同体现，网络性能测试也包括不 同的内容，如网络时延，网络瓶颈带宽，网络拓扑结构，网络流量监控等。其中， 网络时延无疑是最重要的内容之一，它体现了不同业务数据流竞争网络资源的效 果，反映出报文在传输过程中排队拥塞的情况，是网络服务质量优劣的关键衡量 标准。同时它也是网络状况变化的最基本反应，网络的其他性能指标也大都与其 有一定的关系。因此网络时延测试技术备受国内外重视，发展也最为迅速。 网络时延测试的关键技术是如何解决测试两端的时钟同步问题。如果测试两端 的时钟是不同步的，比如说存在时间上的不确定差值或者存在机器时钟频率上的 不同，这样一来将导致测量结果并非真实值，甚至出现较大误差，严重影响人们 对网络时延状况的判断和分析。因此测量网络时延的过程实质上就是通过一系列 分析和计算，使得测试两端时钟同步的过程。 最早的网络时钟同步技术是1 9 8 1 年提出的因特网时钟服务( i n t e r a c tc l o c k p r o t o c o l ，r f c 7 7 8 ) 【4 】，该服务使用i c m p ( 因特网控制消息协议) 协议的时间戳 请求和响应来完成因特网中主机的时间查询和同步。然后是1 9 8 3 年提出的时间协 议( l a n ep r o t o c o l ，r f c 8 6 8 ) 1 5 】，该协议可以在t c p 或u d p 上通信，来实现网络 中时间的查询和同步，可以精确到1 秒。 由于在此前出现的网络时钟同步技术不能提供较高的精确度，难以满足实际的 需要，在经过几年的讨论和研究之后，1 9 8 8 年正式提出了网络时间协议( n e t w o r k t a n ep r o t o c o l ，n t p ，r f c l 0 5 9 ) 。其后，n t p 经过不断地改进和完善，进一步提 高了计算精度和算法稳定性。在1 9 9 2 年的时候正式提出了网络时间协议第三版， 这也是目前广泛使用的网络时间协议版本，并成为当今国际上许多网络时钟同步 机制的标准。 在此之后，随着科学技术的发展和研究的深入，越来越多的方法被用于解决时 钟同步问题。相比于国外的研究，国内在时钟同步问题上的研究起步较晚，但是 借助较为成熟的技术，也取得了良好的成果。 1 3 本文研究的主要内容及章节安排 本文研究了i l l 网络端到端时延的测量与估计，提出了一种基于统计平均的时 钟频率差算法，用于计算收发时钟的频率差，以获得端到端时延状态的准确估计。 常用的端到端时延测量大多依赖于g p s 接收机或采用n t p 协议来实现收发端时钟 的同步，而g p s 接收机在某些接收环境下不能使用并且g p s 接收机价格较贵，不 适合大规模普及；n t p 协议的精度往往达不到特定要求。本文提供的算法克服了 上述的缺点，只需通过软件就可以实现对网络时延状况的实时监控，并且计算方 法简洁，测试精度可控。我们在多条不同的链路上进行了测试，理论与结果均表 第一章绪论 明该算法能有效消除由于收发时钟频率不同给网络时延测量带来的影响。同时介 绍了当前网络中时延产生的机制，通过对网络拓扑结构和网络协议的分析，从理 论上证明了算法的可行性，并通过网络编程实现了对算法的验证。 本文共分五章。第一章概述了口网络发展现状及网络端到端时延测量的研究 意义，介绍了本文的工作安排；第二章详细介绍了网络测量的基本理论及端到端 时延的测量理论，描述了网络时钟同步的相关概念，介绍了几种经典的网络时钟 同步算法，分析了这些算法的原理和特点；第三章提供了一种新的估计端到端时 延的方法，监控网络时延的变化趋势，介绍原理并在实际网络中对算法进行了测 试验证；第四章主要介绍了该算法的具体实现，分别从网络协议、网络编程、网 络应用等角度介绍了程序所涉及到的理论及实现；第五章总结全文，并提出了下 一步的工作内容。 第二章时延测量基本理论及经典算法分析 第二章时延测量基本理论及经典算法分析 2 1 网络测量 2 1 1 网络测量概论 所谓网络测量是指遵照一定的方法和技术，利用软件和硬件工具来测试或验 证表征网络性能的指标的一系列活动的总和。由此可以看出，网络测量是一种技 术，它通过收集数据或分组的踪迹来显示和分析在不同网络应用下网络中分组的 活动情况。从研究的实质上看，网络测量可以把因特网从技术上升到科学，并且 能够更好地指导应用。可以说，对因特网的测量是对因特网进行控制的基础和前 奏。因此，当前网络测量已成为网络研究的重点之一。 在国外，互联网性能监测这一行业己经非常发达，从事互联网性能监测的知 名企业有许多，如c a ，m e r c u r yi n t e r a c t i v e ，k e y n o t e ，b m c 等1 6 j 。 在我国，由于受网络带宽、互联网普及程度、网上交易环境等影响，互联网 性能监测这一行业发展相对较晚。但是，随着目前政府对网络经济的大力支持和 软硬件环境的不断完善，这一市场已经初露端倪。跨国公司在华业务的发展、金 融证券业网上交易的开展、传统企业的网上贸易以及一些电子商务企业对自身竞 争能力的要求已经为这个市场的发展打下了初步的客户基础。因此，第三方互联 网性能监测服务提供商及相应科技应运而生，并且已经获得良好的市场反应。未 来几年，随着我国全民上网的普及和电子商务交易环境的日趋成熟以及网络竞争 的日趋激烈，互联网性能监测这一市场空间将得到极大的拓展。 另外，互联网性能监测这一行业正在细化。从t c p i p 体系结构来看，从接口 层到应用层，针对每一层不同协议有不同的产品。从网络应用来看，从公共网到 服务器再到后台数据库，针对每一部分都有监测工具。从功能来看，对网络安全、 速度、可用性等都有监测手段。这一市场的发展得益于完善的网络基础设施和相 对成熟的电子商务环境。 2 1 2 网络测量的内容及分类 网络测量是一个系统的概念，主要包含以下三个要素 7 1 1 、测量对象，也就是被测量的节点和链路，以及被测量节点、链路或网络的 某种或某些特性。 2 、测量环境，包括测量点的选取，测量时间的确定，测量设备、通信链路的 类型等。 6 互联网端到端时延测量方法的研究与实现 3 、测量方法，也就是针对某一具体的网络行为指标，选取合适的测量手段。 根据测量目的，指定需要的测量对象，配置测量环境，选择合适的测量方法， 是准确完成网络测量任务的根本。 网络测量按照要素的不同可以分为多种方式，其中最主要的就是按照测量方法 分类。按照测量方法的不同，网络测量可分为主动测量和被动测量两种方式，主 动测量是通过主动产生流量直接测量网络的属性，可以使用直接分析的方法。但 是主动测量所产生的流量会对被测网络的性能产生负面的影响，因此，主动测量 系统开发需要仔细考虑对网络实际传输流量的影响。被动测量则完全取决于被测 网络中目前已有的流量，它的最大优点是在测量期间不影响被测网络的流量，但 会引起测量、分析、存储等资源短缺的问题。 1 、主动测量 主动意味着测量过程中产生新的网络流量，主动流量可以引起网络部件的特殊 响应，也可以用于观测网络的性能。主动测量给网络增加潜在的载荷负担，特别 是如果没有仔细设计使得该方法产生的流量最小，那么附加的流量会扰乱网络， 影响分析结果。例如：如果为了测量在i p 网络中瓶颈链路的带宽，定期地向网络 发送大量的t c p 传输，由此产生的附加流量可能会引起h e i s e n b e r g 效应，并使测 量的网络吞吐量低于实际链路的瓶颈带宽。 其次，主动测量至少需要多个网络部件以某种形式参与，如使用p i n g 估计主 机a 到主机b 的往返时延( r o u n d - t r i pt i m e ，r t t ) ，需要主机b 响应i c m pe c h o 请求信息。不同机器之间主动测量的合作方式分为被动合作和主动合作，如：响 应i c m p 请求、匿名f t p 服务器允许主机和服务器之间实现吞吐量测量，这种合 作称为被动合作。另一种合作方式是主动合作，需要具体的安排，如果要测量a 至b 之间单向延迟的对称性，从b 到a 和从a 到b 都需要进行延迟测量，因而b 需要主动参与测量。 主动测量在性能参数的测量中应用十分广泛，目前大多数测量系统都涉及到主 动测量。 2 、被动测量 被动测量t s l 是指在链路或设备( 如路由器，交换机等) 上利用测量设备对网络 进行监测，而不需要产生多余流量的测量方法。在被动测量方式中，记录网络活 动的探针被接入到网络中，在大多数情况下探针接到网络节点之间的连接处，汇 总和记录那条链路上业务流量的信息。被动测量的优点在于理论上它不产生多余 流量，不会增加网络负担，其缺点在于被动测量基本上是基于对单个设备的监测， 很难对网络端到端的性能进行分析，并且可能会有较大的数据采集量，另外还存 在用户数据泄漏等安全性和隐私问题。 有时为了能够从被动收集的数据中提取某些参数可能需要借助于主动测量。另 第二章时延测量基本理论及经典算法分析 7 外，被动测量是不应该丢失分组的，否则分析的数据将不精确。但随着流量速率 的增加，保证不丢失数据变得几乎不可能，因此目前的网络测量技术大多选择主 动与被动测量相结合的方法。 3 、其他测量方式 从测量点的数量来讲，网络测量分为单点和多点测量。在研究初期，许多工作 都属于单点测量，但因为测量能力有限，搜集的信息不全面。因此分布式多点测 量应运而生。尤其是多点主动测量，利用多个探测点得到的数据，能够综合出大 规模的网络数据和单点所得不到的交叉路由信息。 在拓扑测量方面，多数项目研究的是逻辑拓扑关系图。随着测量范围的扩大， 整张图的规模结构也随之扩大。这时，人们往往希望与实际地域位置相对应，也 就是具有地理信息的拓扑图。s 心t t e r ( c 趾d a ) 针对从几个源点到成千上万个目标 点收集到的路径信息进行拓扑结构和性能属性的可视化，并且开展了地理信息图 方面的研究。 2 1 3 网络测量意义及指标 网络特性的有效测量和准确估计是网络运营和维护的重要因素。由于i n t e r a c t 的分布化、不协作、异质等特点，直接从各种网络设备收集数据，反映网络的实 际运行情况，只局限在可管理的较小范围之内。而掌握更大范围、更具普遍意义 的网络运行参数，对现代网络发展具有很强的现实意义 9 1 。具体来说，研究i p 网 络测量的意义主要表现在以下几个方面： l 、网络性能监控的需要 网络测量为网络开通后提供性能检验、考核指标的手段，为网络工程提供验收 依据，为网络运营提供实时或阶段性性能监控工具，进行网络诊断等。 2 、口网络安全评估、入侵检测与防护的需要 网络安全是用户和i s p ( i n t e m e ts e r v i c ep r o v i d e r ) 、a s p ( a p p l i c a t i o ns e r v i c e p r o v i d e r ) 考虑的首要问题之一，借助于端口扫描等手段对i p 网络进行脆弱性分析 ( v a ，v u l n e r a b i l i t y a n a l y s i s ) ，能使网管人员及时查漏补缺，合理配置防火墙及网 络参数，制定相应的安全策略，在入侵还没有发生前尽量杜绝它。 3 、研究网络新技术的基础 网络测量为q o s ( q u a l i t yo fs e r v i c e ) 控制技术如资源预约协议( r s v p ) 的接 入控制、拥塞控制技术提供了定量选择参数的依据。 4 、网络管理的有力补充 计算机网络的巨大发展，促进了网络管理研究的发展，从而刺激了对网络测量 的需求。过去的集中式网管由于缺乏伸缩性、灵活性，难以适应网络规模和复杂 3 互联网端到端时延测量方法的研究与实现 性的飞速发展，分布式网络管理成为一个重要的研究方向，相应的网络性能则为 网络管理提供了依据。 5 、其他用途 网络测量还有许多其他的用途，例如，用于选择服务器设备，用于验证网络配 置，用于设计因特网的新应用，用于配置网络或服务器，用于广域网中的负载平 衡以及用于计费等方面。 网络测量按照用途的不同，有着不同的指标属性，所需要采集的数据也不尽 相同。目前，i n t e r a c t 工程任务组( m t f ) 的i p p m ( i pp e r f o r m a n c em e t r i c ) i 作组已定 义了一些i n t e m e t 度量的指标，并指出了度量的框架。常用的网络测量指标属性可 以划分为连通性、吞吐量、带宽、信道利用率、丢包率、时延等。其中时延是网 络性能指标中的最重要参数之一，例如在多媒体应用中，报文的传输必须满足严 格的网络时延要求；时延测量还可以为可用带宽、丢包率等其它网络参数的估计 提供极其有用的信息。因此，准确测量网络端到端时延有着重要意义，相应的研 究也比较深入。 2 2 端到端时延的测量理论 2 2 1 时延概述 网络的时延主要分为往返时延( r o u n d - t r i pt i m e ，r t t ) 和单向时g ( a o 端到端时 延，e n d - t o e n dd e l a yo ro n ew a yd e l a y ) 两类。往返时延是指一个固定大小的p 数 据报从源端到目的端又从目的端回到源端往返所需要的时间间隔；端到端时延是 指发送固定大小的m 探测数据报，到达目的端时刻与离开源端时刻之差【1 0 1 。 在实际测量中，由疋报文到达目的端的时间戳减去其从源端发送时的时间戳 就是端到端时延的估计值。但是这两个时间戳必须使用相同的时钟进行记录，否 则不同时钟之间的差异会对时延测量带来严重的误差。影响碑报文网络时延的因 素主要有三大类： 1 、网络本身的性能。即完全独立于网络测量方法，仅与网络本身的硬件特性 相关，包括网络的物理层介质、传输所需的路由转发等分组处理的次数和速度、 网络数据链路层协议的不同实现方式等； 2 、用于测量的数据报文的特性。这与网络测量的具体方式密切相关，主要包 括承载测量报文的协议类型、报文长度、发送频率等； 3 、当前的网络流量。网络负载比较重时，其传输和处理速度就会大大下降， 此时的口数据报文就会经历较长的时延。 根据实际的数据包发送过程，我们可以得出，分组的端到端时延由4 个部分组 第二章时延测量基本理论及经典算法分析 9 成：传播时延、传输时延、处理时延、排队时延。其中传播时延指的是分组的第 一个比特从发送节点到达接收节点在传输链路上经历的时间，主要由电磁波通过 通信链路的物理信道的传播时间所决定；传输时延指的是发送节点在传输链路上 开始发送分组的第一个比特至发送完该分组的最后一个比特所需要的时间，主要 由连接速度或链路容量决定；处理时延指的是分组从一个节点的输入端到达该节 点的输出端所经历的时延，它受每个节点的计算能力和可用的硬件的影响；排队 时延指的是分组在路由器的缓冲区中传输或处理前的等待时间，由路由器中的交 换结构决定。如果数据包在传输过程中遇到了链路上的拥塞，则该数据包就需要 等待路由器等中间节点的处理，由此带来的时延也就是排队时延。 不同的网络环境下，这四种时延所占的比重也各有不同。其中所占比重最大的 排队时延和传播时延，它们是端到端时延的主要构成。 2 2 2 时延测量方法 根据t f 的网络小组发布的r f c 2 5 4 4 1 2 】中提到的测试方法，网络端到端时延 的测量方法有两种： 一种是如图2 1 所示，在测试过程中，数据包带上起始时间戳( s t a r tt i m e ) 从 测试设备的出口流出，从被测系统的一个节点f 进入被测系统，经过中间环节众多 设备的存储转发后，从被测系统的另一个节点f 流出，回到原测试设备的入口，同 时记录下终止时间( e n dt i m e ) 。那么，被测系统两个特定节点间的网络传输延迟 就唯一地确定了。 图2 1 网络传输时延测试原理1 可知，网络传输延迟d 的表达式为： d = e n dt i m e s t a r tt i m e( 2 1 ) 这种网络传输延迟的测量精度很容易就可以达到微秒级别，应该说是一种理想 的网络性能测试。但是在广域网或较大一点的网络中就不适合了，因为单纯一个 1 0 互联网端到端时延测量方法的研究与实现 测试设备在地理位置上必然在一个地方。当数据包从测试设备的一个端口发出， 进入以太网络，传输流通，再路由回来，在实际网络中很少见，除非对网络中的 路由器的配置进行测试环境的重置，使网络的路由处于环路状态。然而这样一来， 网络测试就不是在一个实际运行的环境中进行了，也就失去了测试的现实意义。 另一种方法是数据包从起始点的测试设备出发，带上起始时间戳，在被测系统 的两个节点“，间传输后，到达另一端的终止点测试设备，再盖上终止时间戳， 这样两个时间戳的差值就是网络节点f ，间的传输延迟了，如图2 2 所示。 s t a r tt i m e e n dt i m e 图2 2 网络传输时延测试原理2 这样，被测系统两个特定节点间的网络传输延迟就唯一地确定了。网络传输时 延d 的表达式为： d = e n dt i m e s t a r tt i m e( 2 2 ) 第二种测试在理论上解决了第一种测试的缺陷。当带有s t a r tt i m e 时间戳的数 据包从测试设备s e n d e r 发出，经过网络中各个设备的存储转发，到达目的地的另 一个测试设备r e c e i v e r ，记录下到达的时间。那么，对于这样一个网络来说，两个 特定节点间的实际网络延迟就完全确定了。这样的数据在检测计算机网络中端到 端网络性能是至关重要的。 但是这种测试方式中有个最重要的问题要解决：时间的同步问题。如果在这 样的测试环境中，测试设备s e n d e r 和测试设备r e c e i v e r 在时间上不是同步的，那 么，根据数据包中的出发时间戳和到达时间戳的差值而得出的网络单向延迟就没 有意义了。 2 2 3 时钟同步理论 在介绍网络时钟同步理论之前，先解释几个将会用到的概念【1 4 j 【1 习： l 、标准时钟：即以该时钟的时间和时钟频率为标准； 2 、时钟频差：某一时钟与标准时钟的时钟频率不同，二者的差值称为 时钟频差。举例说明：假设标准时钟频率为1 ，被测时钟频 率为2 。即标准时钟运行1 秒钟的时间内，被测时钟则运行 了2 秒钟，说明被测时钟的时钟频率是标准时钟的2 倍， 二者时钟频差为l ( 标准时钟频率) 。 3 、时间差：与标准时钟的时间差。例如标准时钟当前时刻为5 时1 2 分2 3 秒，而另一时钟当前时间为5 时1 0 分1 2 秒，说明两者的时 第二章时延测量基本理论及经典算法分析 l l 间差是2 分1 1 秒。 4 、时钟同步：两个时钟的时间和时钟频率都相同，称这样的两个时钟是时 钟同步的。 根据2 2 2 的理论可知，真实的网络时延测量和监控需要利用收端接收时间戳 减去发端发送时间戳，而测量两端的机器时间是否同步，将会导致得出的结果可 能会出现较大误差甚至没有任何意义。图2 3 是针对普通网络进行的网络时延测试 结果1 1 3 】。 io o o 一嘲 曹 ；枷 耄枷 室 毒2 0 ： o5 i dl5 0 d2 蛳 图2 3 网络时延测试结果 图像的横轴是测量的时间轴，以s 为单位，每隔1 0 m s 测试一次。纵轴为接收 时间减去发送时间的值。如果当前两端时间是同步的，则每一个测量结果就是当 前的准确时延，图像的整体走势说明当前一段时间网络的时延大小呈上升趋势。 但实际情况是网络上的时钟往往都是不同步的，这就需要我们从以下两个方面考 虑时钟不同步时如何分析图2 3 。 1 、假设收发两端的起始时间是不同的，而时钟频率是相同的。即假设发端在 开始发送时的时间为1 0 1 0 s ，而收端此时的时间是2 0 2 0 s 。假设第一个数据包真实 时延为1 5 0 s ，则接收端接收到的时间是2 1 7 0 s ，收端时间减去发端时间的结果是 1 1 6 0 s ，理论上这时的测量值是两端起始时间差加上真实时延值，而不是真正的网 络时延。 d = r 7 - t 。= a + d( 2 3 ) 其中d 为测量得到的时延，r 7 为接收端接收时间，厂为发送端发送时间，是 两时钟的起始时间差( 因为两时钟的时钟频率是相同的，故在任何发送时刻两者 的时间差都是，不会出现变化) ，d 是数据包的真实传输时间。从式2 3 上也可 以看出，在这种情况下得到的图形是真实的时延和两时钟时间差的和，并不是我 们想要的真实结果。如果起始时间差不确定，就只能通过对多次测量的结果比较， 大体得出当前一段时间的网络时延变化趋势。具体到图2 3 ，该图中的点并不是真 实时延的反映，仅能反映出一段时间内网络时延的变化情况，即网络时延在逐步 增大。 2 、假设测试两端的起始时间是一致的，但两端的时钟频率是不一样的，如图 1 2 互联网端到端时延测量方法的研究与实现 2 4 所示效果： t ，、 t ； 、， 彳 iiii iiliiliii 墨t 1 一 1 图2 4 网络时钟频率不同时的时延测量 图中，f 代表发端发送第f 个数据包时的时间，0 代表接收端接收到第f 个数据 包时的时间，代表当发送端为c 时接收端的时间。假设发端时钟是标准时钟，收 端时钟的频率为a 倍的标准频率，则从图中可以看出，起始时刻的测量传输时延q 的表达式为： q=彳-t；(2-4) 而第一个数据包的真实时延西的表达式为： 4 = 吖- t ；) g ( 2 5 ) 如果说因为a 通常非常接近于标准值，且0 一玎较小，第一个数据包的测量值 日与真实值4 之间的差距微乎其微的话，那么随着时间的推移，t 时间后的第f 个 测量传输时延为： 4 = 彳- t , = ( a - 1 ) t + 4 口 ( 2 - 6 ) 因为a 通常非常接近于标准值，且此时的真实时延值z 也很小，故上式可以简 化为： 口= 彳- t ；= ( a - 1 ) t + 4 ( 2 - 7 ) 根据式2 7 可知，此时测量得到的结果也不是真实的时延值。说明收发时钟存 在频差时，普通方法测量得到的结果并不是我们想要的。 具体分析图2 3 ，图形的波动是由于谚的不同引起的。从图形走势分析来说， 如果a 大于l ，则测试结果会出现如图2 3 所示的向上趋势；但如果这一段时间内 网络真实时延4 也在逐渐增大，也有可能导致测量值口的逐渐增大，这样一来可 能无法清晰的分辨出这种向上的趋势是由a 引起的，还是由真实时延的增加引起 的。所以这种情况下得出的网络时延图不仅不能真实反应具体时延值，甚至于不 能真实反映出当前一段时间的网络时延变化趋势。 考虑到实际环境中，网络时钟通常都是不同步的，既不可能出现零时间差，也 不可能出现零频率差，结合上文的分析介绍，可以知道普通测量方法得到的结果 第二章时延测量基本理论及经典算法分析 1 3 并不是我们需要的。如果想准确测量出网络的时延值，则需要准确掌握当前测试 两端时钟的时间差；如果想准确把握当前一段时间的网络时延变化趋势，则需要 准确掌握当前测试两端的时钟频率差。因此，网络时延测试的关键在于准确掌握 网络时钟的时间差或者频率差，这也是网络时钟同步的核心。 2 3 经典网络时钟同步算法 2 3 1 基于n t p 的网络时钟同步算法 网络时间协n t p ( n e t w o r kt i m ep r o t o c 0 1 ) ，最早由美国特拉华大学( u n i v e r s i t y o f d e l a w a r e ) d a v i dl m i l l s 教授于1 9 8 5 年提出，目的是在分散的、包括很多网关 和不可靠子网的i n t e m e t 环境中，提供精确和健壮的时间服务。n t p 使用层次式时 间分布模型，主要采用客户端服务器模式，由n t p 时间服务器按层次对网络中各 个客户端进行授时，并通过一定的分析计算，同步各个网络时钟。实际应用中， n t p 通过多个时间服务器和t c p i p 网络连接链路的多样性，来保证客户机总能 收到正确的时间信息( 即可靠性) ，通过基于概率论的分析方法和算法，来提高客 户机校正时间的精确度【l5 1 。在i n t e m e t 上，使用网络时间协议可以获得几十毫秒 的精度。在局域网中，使用网络时间协议可以获得小于一个毫秒的精度。 n t p 以客户机和服务器方式进行通信。每次通信包括两个数据包，即客户机 发送一个请求数据包，服务器接收后回送一个应答数据包。两个数据包都带有时 间戳。n t p 根据这两个数据包所携带的时间戳确定时间误差，并通过一系列算法 来消除网络传输的不确定性带来的影响【l6 】。n t p 原理如图2 5 所示： 么 客户机 服务器 图2 5n t p 工作原理 其中，互是客户机发送请求报文时客户机的时钟读数；正是服务器接收到客 户机请求报文时服务器的时钟读数；r 3 是服务器返回响应报文时服务器的时钟读 数； 瓦是客户机接收到服务器的响应报文时的客户机时钟读数。0 为客户机和服 务器之间的时间偏移量，d 是报文在网络的往返传输延时。 五一石= d 2 + o ( 2 - 8 ) 墨一互= 0 一d 2 ( 2 9 ) 所以可以得到 p = 去 ( 五一互) + ( 巧一五) ( 2 1 0 ) 1 4 互联网端到端时延测量方法的研究与实现 d = 五一五) 一( 五一瓦) ( 2 一1 1 ) 式2 1 0 得到了两个时钟的具体时间差，式2 1 1 得到了往返时延。由上文的分 析可知，如果得到了这两个值，就可以准确掌握当前的网络时延状况。 但上述理论中存在一个最大的不准确性，那就是n t p 技术在计算过程中假设 网络中数据包的往返时间是一样的，即发送过程的时延和返回过程的时延均等于 d 2 。而实际上网络中的往返时延通常是不相同的，甚至于有很大差距的。前文介 绍可知，网络时延主要由4 部分组成，即传输时延，传播时延，处理时延，排队 时延。往返链路上，传输时延、处理时延、传播时延差距都不大，可以忽略不计， 主要差别在于排队时延。因为全双工工作方式，两条链路上的网络状况是不确定 的，也是不相关的，可以看成是两条独立的链路，把这样的两条链路上的时延看 成是一致的，在局域网中或许误差不会很大，但在大规模的网络上，就会出现较 大误差。另一方面，在大型网络上，数据包在通信两端之间的往返路由往往是不 同的，这也决定了网络上数据包的往返时延是没有相关性的。这些因素将导致基 于n t p 技术计算出来的两时钟时间差9 和往返时延d 都是不精确的，不足以准确 反映网络时延状况。 尽管如此，考虑到常规应用中对时延的精度要求不高，而且n t p 技术相对成 熟简单，所以n t p 仍然是当前网络中最重要的网络时间同步算法，并大规模普及 应用。下面简单介绍它的具体实现。 n t p 系统采用层次式时间分布模型，其网络结构包括主时间服务器、从时间 服务器及客户与节点间的传输路径。n t p 基本实现模型如图2 6 所示i l 5 1 ， 图2 6 n t p 实现模型 发送进程是由定时器周期性触发的。触发后，发送进程先收集发送目的服务 器的相关数据，并把n t p 报文发送给目的服务器。发送的n t p 报文包括发送报文 时的时间戳、最后一次接收目的服务器的时间戳和其它关于层次和连接的必要信 息。 接收进程负责接收到达的n t p 报文，并可以通过接口直接与其它精确时间源 进行连接。n t p 报文到达后，接收进程就会计算本地时钟和参考时间源之间的时 间偏移量，以及其它用于计算误差和选择时间服务器的信息。 更新进程然后对时钟的时间偏移量进行处理，并从所有的时间参考源中选出 质量最好的时间参考源。 第二章时延测量基本理论及经典算法分析 1 5 本地时钟进程利用更新进程得出的时间偏移量调整本地时钟的频率和相位， 即通过渐进地调整相位把本地时钟的偏移量逐步缩减为零。这样本地时钟也可以 作为其它时钟的稳定时间参考源了。 n t p 协议被广泛的应用于互联网中，很多研究人员致力于n t p 协议的研究： 文献【1 5 】描述了对n t p 版本3 从精度、稳定性和可靠性方面的改进方法；也有很多 类似n 耶的协议出现，如服务器时间协议s t p ( s e r v e r 弧m ep r o t o c 0 1 ) 17 j 是i b m 在 2 0 0 5 年7 月正式推出的，它采用了与n t p 相类似的基于信息的分层机制；文献【墙】 提出了把负载平滑技术用于每个需要同步的节点以获得更高的同步精度；a 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 髓) 方法【聊， 能从连续的同步标准节点故障中迅速恢复，但是同步精度最高也只能达到几十微 秒。 2 3 2 基于g p s 技术的网络时钟同步算法 全球定位系统( g p s ，g l o b a lp o s i t i o n i n gs y s t e m ) 是本世纪7 0 年代由美国陆海空 三军联合研制的新一代空间卫星导航定位系统。其主要目的是为陆、海、空三大 领域提供实时、全天候和全球性的导航服务，并用于情报收集、核爆监测和应急 通讯等一些军事目的，是美国独霸全球战略的重要组成。经过2 0 余年的研究实验， 耗资3 0 0 亿美元，到1 9 9 4 年3 月，全球覆盖率高达9 8 的2 4 颗g p s 卫星星座己 布设完成1 2 0 1 。 g p s 系统包括三大部分：空间部分g p s 卫星星座；地面控制部分地面监 控系统；用户设备部籼p s 信号接收机。 1 、g p s 卫星星座 g p s 工作卫星及其星座由21 颗工作卫星和3 颗在轨备用卫星组成g p s 卫星星 座，记作( 2 1 + 3 ) g p s 星座。2 4 颗卫星均匀分布在6 个轨道平面内，轨道倾角为 5 5 度，各个轨道平面之间相距6 0 度，即轨道的升交点赤经各相差6 0 度。每个轨 道平面内各颗卫星之间的升交角距相差9 0 度，一轨道平面上的卫星比西边相邻轨 道平面上的相应卫星超前3 0 度。 在两万公里高空的g p s 卫星，当地球对恒星来说自转一周时，它们绕地球运 行二周，即绕地球一周的时间为1 2 恒星时。这样，对于地面观测者来说，每天将 提前4 分钟见到同一颗g p s 卫星。位于地平线以上的卫星颗数随着时间和地点的 不同而不同，最少可见到4 颗，最多可见到1 1 颗。在用g p s 信号导航定位时，为 了结算测站的三维坐标，必须观测4 颗g p s