（通信与信息系统专业论文）ip网络性能测量研究与实现.pdf

摘要 i p 网络性能测量对网络研究与发展十分重要，可以用于分析当前i n t e r n e t 的基 本特性，如网络体系结构和流量模型等。i n t e r n e t 因其异构性、业务类型的多样性 且变化的随机性，使得人们对i n t e m e t 网络体系结构很难准确地把握，数学模型越 来越难以建立，从而导致网络测量成为唯一可行的方法，也是网络发展的一项重 要课题。 本论文来源于国家自然科学基金重点项目：“基于网络探测的i p 网络拓扑 发现和性能分析的研究”。本文主要研究了i p 网络性能测量中最基本的三个指标： 时延、带宽、丢包率的基本概念和测量方法，并采用基于g p s 接收机的时间同步 的方法，设计出了i p 网络性能测量仪，可以测量网络中端到端的时延、丢包率、 瓶颈带宽等网络性能指标，同时进一步为掌握网络真实的行为特征、网络协议和 控制机制等提供了可靠的理论依据。 关键词：网络测量时延 带宽丢包率g p s a b s t r a c t p e r f o r m a n c em e a s u r e m e n to ni pn e t w o r kp l a y sa ni m p o r t a n tr o l ei nr e s e a r c ha n d d e v e l o p m e n to fn e t w o r k ，b e c a u s ei t c a nb eu s e dt oa n a l y z ee s s e n t i a lp e r f o r m a n c eo n i n t e r n e t ，s u c ha si n f r a s t r u c t u r eo fn e t w o r ka n dt r a f f i c ，e t ci n t e m e ti san e t w o r kw h o s e a r c h i t e c t u r e ，p r o t o c o la n da p p l i c a t i o na r ec o m p l i c a t e d ，s oi t st o p o l o g i e sa r ed i f f i c u l tt o b em a s t e r e da n di t sm o d e l sa r ed i f f i c u l tt ob eb u i l t t h u s m e a s u r e m e n tb e c o m e st h e o n l ym e t h o da v a i l a b l et or e s e a r c hi n t e r n e te n d t o e n dd y n a m i c s ，a n di ta l s ob e c o m e s i m p o r t a n t t od e v e l o pi n t e r n e t r e s e a r c hi nt h ep a p e ri sa p a r to fan s f c ( n a t u r a ls c i e n c ef o u n d a t i o no fc h i n a ) k e yp r o j e c tn a m e da s i pn e t w o r kt o p o l o g yd i s c o v e r ya n dp e r f o r m a n c ea n a l y s i sb a s e d o nn e t w o r km e a s u r e m e n t s t h e r ea r et h r e e t h em o s te s s e n t i a l p a r a m e t e r s i n p e r f o r m a n c em e a s u r e m e n to ni pn e t w o r k ，t h e ya r ee n d - t o e n dp a c k e td e l a y ，b a n d w i d t h a n dp a c k e tl o s s p r o b a b i l i t y a f t e ra n a l y z i n gt h eb a s i cc o n c e p ta n dt r a d i t i o n a l t e s t i n g m e t h o do ft h e s et h r e ep a r a m e t e r s ，t h i sp a p e rd e s i g n san e wd e v i c ea n dan e wm e t h o d b a s e do nt h es y n c h r o n o u sm e t h o do fg p sr e c e i v e rt ot e s tt h e s et h r e ep a r a m e t e r sw h i c h f o r mt h ep e r f o r m a n c eo fi pn e t w o r k t h et e s th e l p st o s t u d yt h en e t w o r kp r o t o c o la n d c o n t r o lt h e o r y k e y w o r d ：n e t w o r km e a s u r e m e n t d e l a y b a n d w i d t hl o s sp r o b a b i l i t yg p s 创新性声明 y5 9 3 吣q , n 8 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容p 。t j , ，论文中不 包含其他人已经发表或撰写过的研究成果；也不包含为获得西安电子科技大学或 其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做 的任何贡献均己在论文中做了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名盈叠 日期岔。牛，、5 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究 生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。本人保证毕 业离校后，发表论文或使用论文工作成果时署名单位仍然为西安电子科技大学。 学校有权保留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全 部或部分内容，可以允许采用影印、缩印或其它复制手段保存论文。( 保密的论文 在解密后遵守此规定) 本学位论文属于保密，在一年解密后适用本授权书。 本人签名 导师签名 日期劫口牟，6 日期 一v ，f 第一章绪论 第一章绪论 1 1 i p 网络性能测量技术概述 近年来，随着互联网应用越来越广泛， i p 网络性能测量受到了困际上的普遍 关注。不同的网络使用者如网络管理者、网络研究人员和网络普通用户都需要能 准确、完整、详细地描述互联网及其应用系统的网络性能。 1 1 1 基本概念 网络测量是研究网络行为学( 互联网运行规律的科学) 的重要方法，它是指 遵照一定的方法和技术，利用软件或硬件工具来测量或验证表征网络性能的指标 的一系列活动的总和。网络性能测量是网络测量的主要内容之，主要包含以下 三个要素： ( 1 ) 测量对象：被测量的节点或链路，测量节点、链路或网络的什么特征，如 链路的时延、带宽、丢包率，路由器的路由效率、时延、丢包率，w e b 服务器的 应答延迟、吞吐率、系统容量、最大稳定链接数等： ( 2 ) 测量环境：包括测量点的选取、测量时间的确定、测量设备、通信链路的 类型等； ( 3 ) 测量方法：针对某一具体的网络行为指标，选取合适的测量方法，测量方 法应满足： 稳健性被测网络的轻微变化，不会使测量方法失效： 可重复性同样的网络条件，多次测量结果应一致： 准确性测量结果应能反映网络的真实情况。 1 1 2 测量指标 为了测量网络性能，i p 网络测量指标框架最早由i e t f ，sb m w g ( i n t e m e t e n g i n e e r i n gt a s kf o r c e s b e n c h m a r k i n gm e t h o d o l o g yw o r k i n gg r o u p ) 定义。在 r f c 2 3 3 0 中给出了i p 性能指标的框架“1 。该框架指出，测量的指标必须遵守以f 定义标准： 1 ) 测量指标必须是具体和严格定义的； 2 ) 对该指标的测量方法必须是可重复的，b p 在多个不同时刻、相同的环境下 p 网络性能测量研究与实现 采用相同测量方法可以得到相同的结果； 3 ) 测量指标必须是无偏的，即对相同的i p 技术实现具有相同的测量结果； 4 ) 测量指标必须具有区分性，即对测量结果可以理解和反映出不同的实现技 术； 5 ) 测量指标对端用户和网络运营商了解网络性能必须是有用的； 6 ) 测量指标必须是避免人为影响的性能指标。 对网络性能可靠性指标的研究最先被用来进行协议设计与实现、网络模拟仿 真和分析网络性能等。我们可以利用一些已有的协议工具来进行网络测量，其中 i 劂络测量可用的协议有：s n m p 、r o m n 、c m i p 、i c m p 等，可利用的公开发布的 工具软件有：p i n g ，t c p d u m p ，t e l n e t ，f p i n g ，t r a c e r o u t e r ，l i b p c a p 等。另外，路由器( 如 路由表信息，c i s c o 路由器中的n e t f l o w 模块可以采集网络业务流) 、网管软件的统 计数据电会给网络测量提供有价值的信息。根据实际情况的需要，有时，我们还 要自己编制各种测量工具对某些网络性能指标进行测量。 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 ) 2 1 ，开发用于描述 i n t e r n e t 数据传输服务质量、性能、可靠性的测量指标集和测量框架，目前，i p p m 定义和正在定义的指标和测量方法有：流通性( c o n n e c t i v i t y ) 、单向时延 ( o n e w a y d e l a y ) 、往返时延( r t t , r o u n d t r i pt i m e ) 、丢包率( p a c k e tl o s s l 、吞吐 率( t h r o u g h p u t ) 、瞬时分组延时差、大批传输容量( b u l kt r a n s f e rc a p a c i t y ) 、带宽 利用率( b a n d w i d t h a v a i l a b i l i t y ) 、瓶颈带宽估计( b o t t l e n e c kb a n d w i d t he s t i m a t i o n ) 、 周期流( p e r i o d i cs t r e a m s ) 等。其中，时延、带宽、丢包率被作为网络性能测量中 最基本的三大指标。 在这些测量指标中，已有的定义很大一部分还是草案，应用级的性能指标基 本上还是空白，更谈不上i p p m 和应用级性能指标的关联，离建立性能完备的指标 体系和标准的测试方法还有很大的差距。所以，对于网络性能测量的研究有着很 重要的意义，可以为网络性能指标体系的建立和标准的测试方法的制定提供理论 依据。 1 1 3 主要方法 对于网络性能指标的研究，必须采用一定的测量方法和测量系统得到。根据 i p p m 在r f c 2 3 3 0 中所指的，测量方法必须满足结果重现性和连续性。所谓结果 重现性是指在相同的网络环境下( 相同的网络设施和负载) 不同的时刻采用该测 量方法进行测量，具有一致的测量结果。所谓连续性是指当网络环境具有微小的 变动，采用该测量方法得到的测量结果不应该有很大的变化。 根据测量过程中是否向被测系统中发送主动探针( a c t i v ep r o b e ) ，可将网络性 第一帝绪论 能测量方法分为两种f 3 】：主动测量和被动测量。主动测量是将探测分组注入网络进 行测量，如通过在一端发送探测分组，而在另一端接收该分组，可以观测探测分 组的行为和到达时间，估计端到端的延时、丢包率等网络性能指标，如i e p m 、n i m i 、 n l a n r a m p 、s u r v e y o r 、s k i t t e r 等网络性能测量项目郊采用了主动测量的方法。 被动测量是在网络的某处布置数据采集器，收集流过该处的网络业务流，进彳了分 析、提取业务特征，获得性能数据，如n l a n rp m a 、c o r a l r e e f 等网络测量项目。 c i s c o 公司的n e t f l o w 就是这样的一个被动测试工具，它能让路由器获得大量的流 量统计，包括一个包的源和目的i p 地址及端口号、协议类型等。主动测量的优点 是能够根据不同的应用场景控制探测包，如流量特征、采样频率、调度方法、包 大小和包类型( 以模仿各种应用) 、被监视的路径和函数等。主动测量可以让测量 者按照自己的意图进行，因此容易用于进行场景的模仿，检验网络是否满足 q o s s l a ( 服务质量明臣务等级协议) 等。主动铡量比被动测量能够更有效的测试 网络性能，所以主动测量是处于网络边缘的端用户了解网络状态常用的测量方法， 目前端到端的测量技术都属于主动测量方法。被动测量法可能需要查看网络上的 所有数据包，因此存在如何访问和保护所采集到的数据的保密性和安全的问题， 所以主动网络测量技术被广泛采用和研究。本文也采用主动测量的方法去测量时 延、包丢失率、带宽等。 从测量点的分布，测量方法可分为单点测量和多点测量两种。大部分的嘲络 测量项目都采用分布式多点测量，如：n i m i 、r i p e 、n l a n r a m p 、p m a 、s k i t t e r 、 i e p m 等都是分布式多点测量项目。些测量依赖于在网络的多个点上进行监测， 如要测量个数据包从主机a 到主机b 所需的时间，则需要使用准确同步的时钟 记录数据包离开主机a 和到达主机b 的时间。对于大型网络上通信流量的测量， 可以考虑在多点监测流量，以收集到数据包通过该网络的详细信息。单点测量在 非合作的情形下能发挥巨大的作用，如美国朗讯科技公司b e l l 实验室的单点测量 项目i n t e m e t m a p p i n g 。 网络钡0 量还可以分为单程测试和环回测试两种1 4 3 。单程测试是指探测分组在网 络的源端进入网络，在目的端输出，根据输出参数来评价网络性能。环回测试是 指探测分组在网络一端进入网络，到达目的端后转发回源端输出，根据输出参数 来评估网络性能。环回测试的主要优势是测试配置简单，成本低，但在某些情况 下，进行单程测试更有意义： 在i p 网络里，从源端到目的端的路径可能和目的端回到源端的路径不一 样( 不对称路径) ，有前向和反向的区别；路径所经过的路由也不- 一样， 因此，环回测试其实是将两个不同路径一起测试。每个路径单独测试突出 了两个路径的不同性能，而这两个路径可能是属于不同的网络运营商，或 者根本是不同类型的网络。 ! ! 塑竺堡堂型至翌壅兰壅翌 即使两个路径对称，由于不对称队列，它们也可能有根本不同的性能特征。 一个应用性能可能主要取决于一个方向的性能。例如，使用t c p 的文件 传输可能更取决于数据流动方向的性能，而跟应答传播方向性能无多大关 系。 但是在采用单程测试时，测试点往往位于不同的地点，必须解决测试时钟同 步的问题。本文主要内容就在于利用软件算法和硬件设计实现两种方法，来解决 时钟同步的问题。 按与被测网络的关系网络性能测量可分为：合作测量、非合作测量。合作测 量指需要对方主动配合的测量。对网络运营者来说，合作测量能够掌握网络的运 行状况、找出瓶颈、业务分布情况等，以便有效的管理网络、充分利用网络资源。 非合作测量是指无需对方主动配合的测量，测量目的往往是窥探对方网络的情况， 这在军事上有非常重要的意义。 1 2 目前国内外的研究状况 1 2 1 国外的情况 国外对网络测量进行了大量的研究，已经提出了各种各样的测量体系结构。 典型的如美国国家应用网络研究实验室n l a n r ( n a t i o n a il a b o r a t o r yo fa p p l i e d n e t w o r kr e s e a r c h ) 的测量和运营分析小组m o a t ( m e a s u r e m e n ta n d o p e r a t i o n a n a l y s i st e a m ) 开发的网络分析基础结构n a i ( n e t w o r k a n a l y s i si n f r a s t r u c t u r e ) 睁j ， 目的是建立一个测量体系结构，通过被动采集分组首部、路由和网络管理数据， 并进行主动探测，对获得的原始数据进行分析，并实现可视化。 美国国家科学基金n s f 和d a r p a 资助的国家i n t e r n e t 测量基础框架( n i m i ， n a t i o n a li n t e r n e tm e a s u r e m e n ti n f r a s t r u c t u r e ) 项目【6j ，其目标是要建立一个全球化 的、分布式的、大规模的i n t e r n e t 测量结构，已经设计出了轻负载、可升级、可动 态配置、具有安全验证的测量探针( n p d ，n e t w o r kp r o b ed a e m o n ) ，测量各种性 能参数。i n t e m e t 数据分析合作组织c a i d a ( c o o p e r a t i v e a s s o c i a t i o nf o ri n t e r n e td a t a a n a l y s i s ) 提出并实现了s k i t t e r 和c o r a l ，s k i t t e r 通过几个源向许多其他的地址空间 发送探测包来探测路径和性能；c o r a l 用来测量高速链路的工作流特征。由斯坦福 线性加速器中心( s l a c ，s t a n f o r dl i n e a r a c c e l e r a t o rc e n t e r ) 发起的端到端性能监 控项目p i n g e r ( p i n g e n d - t o e n d r e p o r t i n g ) ，在全世界布有监视点，采用p i n g ( i c m p e c h o r e q u e s t ) 来测量r t t ，p a c k e tl o s s 等，进而推算系统的性能。由b e r k e l e y 第一帝绪论 u n i v e r s i t y 和i b m 开发的s p a n d ( s h a r e d p a s s i v en e t w o r kd i s c o v e r y ) 项目hj ，它 是一个被动共享的测量，通过发送u d p ，t c p 分组让客户机向性能服务器汇报网 络性能，同时在网关处还加了一个性能捕获主机辅助测量。此外，还有 w i s c o n s i n m a d i s o n 大学的p a u lb a r f o r d 提出了g i m i ( g l o b a li n t e r n e tm e a s u r e m e n t i n f r a s t r u c t u r e ) ，m a w i ( m e a s u r e m e n ta n da n a l y s i so fw i d e a r e ai n t e r n e t ，日本) ， p p n c g ( p a r t i c l ep h y s i c sn e t w o r kc o o r d i n a t i n gg r o u p ，欧洲) ，w a n d ( w a i k a t o a p p l i e d n e t w o r kd y n a m i c s ，新西兰) 等都制定相应的性能指标和测量方法的建议。 i 2 i 国内的情况 国内清华大学提出了大规模互联网络性能监控模型l i p m ( l a r g e s c a l e i n t e m e t p e r f o r l n a l l c em o n i t o rm o d e l ) ，借鉴了i s o ( t h ei n t e r n a t i o n a l o r g a n i z a t i o n f o r s t a n d a r d i z a t i o n ) 的层次结构思想，将整个模型分为数据采集、数据管理、数据分 析、数据表示四个层次，融汇了t m n ( t e l e c o m m u n i c a t i o n m a n a g e m e n tn c t w o r k ) 在对象管理方面的方法，易于实现和维护。西安交通大学提出了互联网应用性能 测量系统n a p m ( n e t w o r k a p p l i c a t i o np e r f o r m a n c em e a s u r e m e n t ) ，提出应用探针和 区域探针的分布式体系结构。 1 3 研究的主要意义 i n t e r n e t 已经渗透到社会生活的各个角落。随着i n t e r n e t 的飞速发展，i p 业务量的快速增长和新应用的涌现，人们越来越关注网络的性能，因此对其的测 量和研究也就成为一项具有重要意义的工作。 从服务质量看，q o s 敏感应用越来越成为i n t e m e t 承载的主要业务。传统的 i n t e m e t 提供尽力而为( b e s te f f o r ts e r v i c e ) 的服务，业务流量被网络尽快处理， 没有时间延迟闽值保证机制。随着电子商务、v o i p ( v o i c eo v e ri p ) 、v o d 等业务 的发展，用户需要网络提供时延、丢包率等q o s 保证，i s p 也需要网络提供q o s 保证机制以开展新的增值业务。控制、管理、计费和测量是相互关联的整体，人 们提出了一系列的q o s 保证框架。许多q o s 控制机制隅1 ，如基于测量的连接接纳 控制h 1 、q o s 路由、流量工程【i 、拥塞瓶颈检测等，都需通过测量获取网络性能； q o s 管理需监测网络和用户的服务性能，进行动态资源管理、确认服务等级台约 等；q o si - t 。费需要根据用户实际获得服务质量来收费；不论是在应用层的负绒均 衡或传输层的综合服务和区分服务或网络层的流量工程，各种q o s 保证机制的基 l p 网络性能测量研究与实现 础是为对网络运行状态实时检测并将信息进行有效发布。 因此网络性能测量是 q o s 的基础和重要环节之一。 从网络性能优化看，在稳定运行阶段，网络可能会由于网络设备故障或业务 流量激增导致性能下降，可以通过网络性能测量来定位故障，确定优化方案，改 进协议和应用的设计和实现。网络性能测量对于许多i n t e m e t 应用和协议，特别是 涉及大量数据传输和具有时延限制媒体流的应用至关重要。内容分发网络中的请 求路由协议、对等网络、网络缓存的位置选择和维护策略、端系统的组播、内容 服务器中的流调度和接纳控制策略、d n s 和w e b 性能检测等都需要网络测量的 有力支持。 网络性能测量技术还是传统网络管理系统必要有益的补充，基于s n m p 的网 络管理系统可以通过轮询和接收异常t r a p 消息的方法似乎可以得到设备及其各个 端口运行的状态，但对于详细的协议分析、基于应用的流量特征、端到端的性能 检测及其计费策略等都无能为力。这使得系统地研究网络测量这一基础性课题成 为必然而迫切的需求。 1 4 本文的主要内容 本论文来源于国家自然科学基金重点项目：“基于网络探测的i p 网络拓扑 发现和性能分析的研究”。该项目主要内容为：研究i p 网络探测及性能分析技术， 包括网络性能、拓扑、无线i p 的探测和分析原理及技术、网络性能评价及分析预 测技术，探讨基于网络探测的新技术和新应用，研究从大规模数据中解析网络和 业务特性、网络和信息安全的理论及方法，架构及探测测量监控为一体的综合网 管体系，保证i p 网络安全有效运行，为发展有自主知识产权的网络探测体系及网 络新方法奠定基础。我校负责i p 网络探测的体系结构、i p 网络探测的原理和方法、 i p 网络流及安全性分析、i p 网络拓扑发现、无线i p 探测方法和技术的研究五部分。 本文主要针对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 ) 工作组定义的一些i n t e r a c t 度量的指标中最基本的三大指标：时延、丢包率、带宽，设计了端到端i p 网络性 能测量仪，进行i p 网络性能测量。 本文的创新之处在于：目前我国尚无准确测量和分析网络性能的方法和测量仪 器。我们提出对i p 网络某些行为指标的测量方法，设计实用的测量仪器，能够分 析当前i n t e r n e t 的基本特性，直接为i p 网络的规划、运营管理、网络安全、设备 的开发和网络的发展提供支持。 本文的内容安排如下： 第一章绪论 第二章：对i p 网络性能测量技术进行总体介绍，着重介绍了i p 网络性能测量 中最基本和最重要的三个性能指标：时延、带宽、丢包率的基本概念和测量方法； 第三章：针对三个性能指标，提出了一个基于g p s 接收机时削同步的i p 网络 端到端性能测量仪的方案，着重描述了i p 网络性能测量仪的功能、硬件结构总体 框图以及工作流程。 第四章：介绍了i p 网络性能测量仪的硬件实现，单片机、g p s 接收机、p c i 局部总线接口和网卡等各个部分的接口设计。 最后给出小结，总结全文内容。 p 阿络眭能测量研究与实现 第二章i p 网络性能测量技术综述 在i p 网络性能测量技术中，i e t f 的i p p m 工作组提出并定义的一些i n t e r n e t 度量的指标，时延、带宽、丢包率是其中最基本的三大指标，它们为获得网络性 能数据、掌握网络真实的行为特征，网络协议和控制机制等的改进提供可靠的理 论依据。 2 1 时延 网络的时延主要分为往返时延( r o u n d t r i p t i m e ：r t t ) 和单向时延( 即端到端 时延e n d t o e n dd e l a y ) 两类。往返时延是指一个固定大小的i p 数据包从源端到目 的端往返所需的时间间隔：端到端时延是指发送固定大小的i p 探测数据包，源端 离丌的时标和到达目的端的时标之差。在1 1 节提到的单程测试和环回测试中，我 们已经指出了单程测试的重要性，所以在这里我们所研究的时延主要是指端到端 时延。 端到端时延是评估i n t e r n e t 的网络性能的重要参数之一。在v o l p 【川应用中需要 提供端到端时延的限制( 如当单向时延超过2 5 0 m s ，v o l p 应用的性能将大打折扣) 。 通过对端到端时延的测量，能够分析当前i n t e m e t 的基本特性，可根据i n t e m e t 的 q o s 要求进行网络规划设计，如推测网络的拓扑结构和网络的流量模型等，为网 络技术的改进提供可靠的理论依据。 2 1 1 时延的基本概念 概括的说，端到端时延被分为四个主要部分【1 2 1 ： 处理时延( p r o c e s s i n gd e l a y ，t 。) ：指分组到达一个节点的输入端与该分组到 达该节点的输出端之间的时延。它受每个节点的计算能力和可用的硬件的影响， 不受流量的影响。t 。总体上看是一个随机变化的，每个探测包在路由器中处理 的速度不完全相同，因此，我们分t p 为一个确定部分t p d 和个随机部分b 。，t 。= t p d + t p s 。 传输时延( t r a n s m i s s i o nd e l a y ，t 。) ：指发送节点在传输链路上开始发送分组 的第个比特至发完该分组的最后一个比特所需的时间。t f 主要由连接速度或容 量决定，对于每一个探测包，传输时延被认为是相同的。 第一二章i p 网络性能测量技术综述 传播时延( p r o p a g a t i o nd e l a y ，t 。) ：指发送节点在传输链路上发送第一个比 特时刻至该比特到达接收节点的时间。t 。由电磁波通过通信链路的物理信道的传 输时间所决定。 排队时延( q u e u i n gd e l a y ，t q ) ：指分组在路由器的缓冲区中，传输前的等待 时间，t 。由路由器中的交换结构决定。若节点的传输队列在节点的输出端，则排 队时延是指分组进入传输队列到该分组实际进入传输的时延。若节点的输入端有 一个等待队列，则排队时延是指分组进入等待队列到分组进入节点进行处理的时 延。 令最小要求的数据包的大小为m o 比特( 仅是头字节加上尾字节的大小) ，总的 数据包的大小为m 比特。在第i 个节点，r i 为传输速率，则分别用t 。，t ，t c 。 t q ，。表示处理时延大小，传输时延大小，从节点i 到节点i 的传播时延大小，m 比 特大小的数据包的排队时延大小。r 为总的传输速率( 各个链路传输速率总和) ， l 为传播时延和处理时延的总和，t 。为排队时延的总和，则对于一个k 跳的链路： 女k - 1 上= k - i - 0 ， ( 2 1 ) r = r 一= i m ( 2 2 ) ( 2 3 ) = ， ( 2 4 ) m 比特大小的数据包的端到端时延： 如州蛉( + m o 圯+ 半) ( 2 - 5 ) 式子中第一项( + 警) 是端到端时延的固定部分，它依赖于最初设计的网络 性能( 如数据包的传输速率) 和最短的数据包长 第二项( i + 丝) 是端到端时延的随机部分，它依赖于网络的拥塞程度( 如 钵接利用率) 和数据旬大小m 。 2 1 2 常用的端到端时延的测量方法的局限性 常用的网络端到端时延测量方法是先用p i n g 命令来测出网络的往返时延，然 后除以2 来估算出端到端时延。但是在i p 网络里，从源端到目的端的路径可能和 目的端回到源端的路径不一样( 不对称路径) ，不能简单的用除以2 的方法来获得 端到端时延，加之其性能和t c p 、u d p 或其他i p 协议有一定的出入，所以测得的 数据有一定的局限性，时间精度只能精确到秒。 由于用测往返时延方法来测量端到端时延存在着缺陷，所以在端到端时延测 量中主要是直接测量网络的端到端时延。但是在端到端时延测量配置中，测试点 往往位于不同的地点，如果直接测量网络端到端时延，存在收发主机时钟不同 步的局限性，在i p 数据包中的是各自主机的时钟时间，两个主机时钟的频率和初 始相位不同，如果没有时间同步机制，会造成测量数据的错误。我们发送数据包 来测试端到端时延，发送2 0 0 字节长的1 0 0 0 个数据包，时间间隔是2 0 0 毫秒，用 u d p 协议，从源主机( 西电科大校园网) 到目的主机( 中国电信数据网) 。测试结果 见图2 1 ，横轴为发送分组序列号，纵轴为测得的时延( 单位为微秒h s ) ，收发时 钟分别采用各自的时钟，由于在源主机和目的主机之间时钟不同步( 存在频差) 的影响，测试的结果有一个线性的趋势3 1 。 2 2 蠢2 3 5 裁 2 1 ，一：二毒：彝妒咿 ，r 4 一 口1 2 0 03 0 04 0 0卯0f i 0 07 0 0b f l 09 0 01 0 0 0 分组序列号 图2 1 端到端时延实测结果 本文提出了软件分析和硬件测量两种方法来解决端到端时延测量中的收发时 钟不同步的问题，可以测出网络的前向 是利用线性规划算法来分析端到端时延 反向和往返时延。其中软件分析法主要 硬件测量法是依靠g p s 接收机进行授时 的网络时延测量的方法。本章主要研究软件分析法，硬件测量法将在下一章介绍。 2 1 3 端到端时延的软件分析法 1 测量方法 利用主动探测方法 1 4 】，在互联网上通过在一端发送带有时间戳的i p 探测数据 包，在另一端记录该测量分组的到达时间戳来获得端到端的时延测量值，计算出 第二章l p | 叫络性能测量技术综述 网络链路的前向，反向和往返时延值( 未同步) 。发送端主机a 发送带有时叫戳的 i p 探洲数据包，记录下发送时标t 。o ，同时接收端主机b 在接收到i p 探测数据包 后记录下接收时标t ：另一方面，接收端主机b 回复一个带有时间戳的i p 探测 数据包，并记录回复时标t 啦，原发送端主机a 接收到该回复包记下接收时标t ； 由此可得到在网络上的3 个时延时问( 未同步) ： ( 1 ) 前向时延：t 1 t ，o ； ( 2 ) 反向时延：t 门t 心； ( 3 ) 往返时延：t | 3 t ； 见如图2 2 。 主机b 路由器k 路由器2 路由器1 主机a 数据包i 发送端 。：备兰皇竺竺坠坠= 当： 主机b 路由器k i r _ 弋l i - 4 路由器 + 一路由器 t t 蹈由器 + - 主机a 数据包l 接收端 图注 ：。 丁一， 丁。 7 1 p ，丁 图2 2 数据包在网络中的传输 2 时延测量中时钟不同步影响的消除： s u e b m o o n 提出的线性规划方法 1 5 ，消除了源主机和目的主机之间时钟的频 率差，但没有解决收发时钟的频率差和初始相位差引起的时间偏移的问题。我们 7 ! ! 旦垫堡! ! 型量竺塞兰壅堡 通过对端到端网络时延测量的数据分析，仍在采用线性规划方法基础上进行改进 实现收发时钟的同步，消除收发时钟的频率差和初始相位差，解决了时间偏移的 问题。 利用前向和反向两个单向测量可以估计出消除收发时钟频差和初始偏差的端 到端的时延1 16 1 。对于前向链路： “ 优化目标为m i n f ( 如，掣。一l f m 。+ p ) ( 2 6 ) 约束条件为幽切一l 一手m 。+ 臼0 ，掌，口0 ( 2 7 ) 其中：，孝，口为估计值。出，。为实测到的发送第n 个数据包的时延值， 瓦，= t t ，。 ( 2 8 ) ( c 为发送主机的时钟函数，f 。为发送主机时钟的初始相位) ( 五。为发送端主机的时钟频率) ( m n 数据包的大小，b 。带宽) ( 2 - 9 ) ( 2 1 0 ) p = 妒一t 。 ( 妒= ，。一，为起始时间，l = t 。+ l ) ( 2 1 1 ) 对于反向链路： 优化目标为m 证艺b 出如：。一 ，一l 沈一弘m 。一毋) ( 2 1 2 ) 其中毋= 导o + + ( 2 - l 3 ) 约束条件为考如协：。一( 三一一1 ) 巧一7 7 一- m 。 ( 2 1 4 ) 其中巧为接收主机的时钟函数。 假设被测链路往返方向的传播和处理时延和相等，则= 。设发端初始 相位设为0 ( 如在计算机开机时计为初始时刻0 ) ，即，。= o ，则 多：专p + 季) 连同估计的彦代入式 ( 2 一1 5 ) 导辫 j l = p 手 一笙三主堡塑堑堡壁型堡丝查箜些 一! ! _一_，一 d e l a y j = d e l a y 。一8 ，t 。七( p ( 2 一1 6 ) 即可得时延的估计值，其中d e l a y 。为实测到的时延值。对于这两个目标的优 化，采用线性加权算法，优化目标可写为： r a i n 拐+ ( 1 一丑) f 2 37 ) 其中 2d e l a y 。一乙一f m 。+ 秒 ( 2 1 8 ) = 专d e l a y ；扩协一1 b 一弘m 。一7 7 ( 2 _ 1 9 ) 对于线性规划方法的实现，我们采用线性优化算法 1 编程来求目标函数 m i n 颈+ ( 1 兄) ( 2 - - 2 0 ) 的解。 3 ，端到端时延测量高精度算法的实现： 通过对端到端时延算法的分析我们用c + + 编程实现，具体算法步骤如下： s t e p l ：发送i p 数据包i 前在数据包中记录主机a 的发送时标t i0 ，同时接收 方在接收到i p 数据包i 后则需要记录主机b 的接收时标t ； s t e p 2 ：接收方主机b 收到i p 数据包i 后同样也需要回复一个i p 数据包，其中 记录回复时标t n ，原发送方主机a 接收到该回复包记下回复包的接收时标t i , 3 ； s t e p 3 ：求得在网络上的3 个时延时间( 未同步) ： ( 1 ) 前向时延( d e l a y 。) ：1 1 一i 。： ( 2 ) 反向时延( d e 细，：，) ：t3 - r , 2 ； ( 3 ) 往返时延：z ，一z 。： s t e p 4 ：采用线性优化算法进行时延估计，消除时钟不同步误差，获得端到端 时延的真实值。 算法流程图见图2 3 ： l p 网络性能钡 量研究与实现 ( 开始) 上 读入数据 上 假定给出的初始复形中的第一个顶 点坐标：五m = ( 五o ，五。，五，。) 此顶点坐标满足约束条件 0 f n 维变量窀问中在确定出初始复 形的其余2 n 1 个顶点，利用伪随机 数的方法，按照约束条件产生第1 个 顶点， 。 巧= 0 ，。；托。) 灯= 卜丑h d 习而丽垂_ 砸面而羽藤焉丽 7 7 、z 条件，第j + l 顶点不满足，则作如下 。7 7 检查这业 顶点是 由 。 _ y，yi7 _ 、， 、否满足 岁 7 1 未选蒜：f j，k = l 一 厂 i 计算出各顶点的目标函数值，找 找出最坏点x 的对称点： 出函数值最大的，确定为最坏点 x ( r )x ( r ) = ( 1 + a ) z ( f ) 一口( 月) ，( 工( r ) ) - 。燃一。，i 1 舯x i f 2 啬萎x o ( x ( g ) ) - m m a x l ，) ，# r 口为反射系数口1 3 i 确定一个新项点替代最坏点。如果 厂( 五r ) ) 厂( 墨6 1 ) 则用下式修改 x t ) ，即五n = ( 一+ n ) 2 直至，( 誓，) ) ，( 五) 图2 3 线性优化算法流程图 其中，x o 、z 】、2 、3 、x 4 、x 5 和瓦分别表示式2 - - 1 8 和式2 1 9 中 的多、；、各、肜、五一1 、；。和；，维数行：7 。 4 测试实例及结果分析： 立垦三堡_ 翌! 坐堕! ! ! ! ! 里垫查堡垄 ! ! 我们对西电校园网和中国电信数据网，西电校园网和西安交大校园网问的两 条链路进行了测试，并用线性优化算法对测试结果进行了时延估训。 实例1 ：源主机( 西电校园网) ，目的主机( 中国电信数据网、 钡0 试条件：1 0 0 0 个数据包2 0 0 字节长，时间l 可隔为2 0 0 毫秒，每发送1 0 个数 据包探测数据包长增加5 字节，采用u d p 协议，从源主机( 西电校园网) 到目的 主机( 中国电信数据网) ，测试结果如图2 。 端到端时延实翔些吉呆 。薏妻：宴2 4 端到端时延实测结果中收发时钟分别采用各自的时钟，出于时钟 至! 耋鬈警婴，测试的结果呈现一个线性趋势。同步后的端到端h ；主的i 熹蚤萎 妻量烹彗兰垡兰享法估计参数，去除时钟不同步带来的影响后的时主_ 磊藁薹二 条近似平稳的直线。 一 妇。鼍篓篓竺：! o 暨个数据包1 0 0 - y - 节g ：，时间间隔为2 0 0 毒秒，每发送1 0 个数 篓黑篓竖鬃坳5 黼采用u d p 城从源枷西电磊园高焉；南至 銎鼍黧銮警园里测试结果女口图2 _ 5 0 同样也可以看出，由于时蒜蒿三磊嘉 竺二登翌竺望延实测结果呈现个线性趋势：消除时钟不同步带来的影吾_ 孬 延变化趋于平稳。 ”。 p 网络性能测量研究与实现 1 92 墨 曩1 9 1 bb h d h 州_ ? 蠢分文氍 01 0 口2 0 0：3 0 04 0 05 0 06 0 0 7 0 0b o o9 0 01 0 0 0 持蛆庠列号 端到端时延实测结呆 2 24 嘉2 22 摄 2 2 ，_ _ 【 i ” 1 1 ”下i - 1 ：r o 分组序列号 同步后的瑞到端时延结果 幽2 5 端到端时延测试结果 我们给出了测量网络端到端时延软件分析的方法，根据测得的结果，用线性 规划的方法来消除收发时钟的初始相位差和相对频差等参数，获得端到端时延的 真实值。实例测量结果表明该方法提高了测试结果的精确度，可以应用于互联网 中的端到端时延测量。 2 2 带宽 i n t e r n e t 嗣益广泛的应用，主干带宽不断增加，大量的宽带应用随之出现，例 如视频点播( v o d ，v i d e oo n d e m a n d ) 、v o i p ( v o i c eo v e ri p ) 和实时远程教学等。 尽管网络主干带宽和接入带宽成倍增加，但是网络性能并没有得到成倍的提升。 部分原因是应用