（机械电子工程专业论文）internet链路时延推测的研究.pdf

北京邮i u 人学坝 。学位论文 i n t e r n e t 链路时延推测的研究 摘要 随着因特嘲发展得越来越庞大，越来越复杂，整个网络的稳定运 行对于整个社会有着越来越重要的意义。为了更好地设计、控制和管 理这个动态网络，知道其内部运行参数，如各条链路上丢包率和延时 值，反映其各条链路运行状况是很重要的。由于，只能借助端到端测 量的方法，网络边缘采集的数据是唯一可得到的数据，本论文采用有 别于传统数理统计估算的方法，而是借助各种模型和算法，从而十分 高效准确地推测整个网络内部运行参数。 由于网络上运行的各种不同的网络应用程序会给网络带来不同 流量的负载，对各条链路的影响也呈现不平衡性。基于端到端网络测 量方法是由国际上几个组织提出的 1 】，又称之为网络断层分析。 本论文着重研究链路时延的测量和推测，主要工作包括： 1 利用依赖树模型和上向下向算法，推测链路的时延分布。和 传统的极大似然估计算法不同，该方法利用前面链路的情况推测后面 链路的可能概率。这一过程不断重复，每次都产生可能的估测值，以 适应时延的变化。论文根据多播依赖树这种特殊的依赖树模型，对上 向下向算法进行了优化，减少了一种估算参数。对算法进行了仿真， 通过仿真实验证明了该方法的正确性，能够根据端端测量结果精确 地推算出链路的时延特性。并最终用c c + + 语言编程实现了该算法。 2 在单一路径下采用有限混合模型( m f m m ) 和期望最大化( e m ) 算法，根据测得的端到端的时延数据，推测路径上各链路的时延密度 函数。对算法进行了仿真，分析了算法的有效性。 3 测其它时延推测算法作了简要的介绍，并对各种链路时延算法 作了分析比较。 4 参与了实验网络的搭建。参与了网络测量系统的设计、软件 需求分析、模块设计等工作。完成了依赖树模型和上向一下向算法、 有限混合模型和期望最大化( e m ) 算法的软件实现。 关键词： 网络断层分析依赖树模型上向下向算法高斯混合模型 一! ! 堕i l l ! ! ! 查兰塑一l ：兰竺丝苎 期望最大化算法有限混合模型 北京邮i u 人学倾学位论文 i n t e r n e tl i n kd e l a ye s t i m a t i o n ss t u d y a b s t r a c t i n t e r n e ti si n c r e a s i n gl a r g e ra n dm o r ec o m p l e x i ti si m p o r t a n tf o rt h e s o c i e t yt h a tt h ew h o l en e t w o r ki ss t a b l e t ob e t t e rd e s i g n ，c o n t r o la n d m a n a g ed y n a m i cn e t w o r k s ，i ti se s s e n t i a lt oh a v el i n k - l e v e lp e r f o r m a n c e d a t af o ro u ru n d e r s t a n d i n gi n t e r n a ln e t w o r kc h a r a c t e r i s t i c s s u c ha si i n k l o s sa n dd e l a y d a t ac o l l e c t i n gf r o mt h ee d g eo ft h en e t w o r ki st h eo n l y d a t ab a s e do i le n dt oe n dm e a s u r e m e n t i n s t e a do fc l a s s i c a ls t a t i s t i c s a p p r o a c h ，h e r es e v e r a lm o d e l sa n da l g o r i t h m sa r ep r o p o s e dt oe f f i c i e n t l y a n da c c u r a t e l ya s s u m et h ei n t e m a ld a t ai nn e t w o r k s v a r i o u sn e t w o r ka p p l i c a t i o n si nt h en e t w o r k 1 e a dt od i f f e r e n tt r a 面c l o a d a n du n b a l a n c e d i m p a c t o ne a c hl i n k b a s e do ne n d t o e n d m e a s u r e m e n t ，c a l l e da sn e t w o r kt o m o g r a p h yp r o b l e m ，w a sp r o m p t e db y s e v e r a li n t e r n a t i o n a lo r g a n i z a t i o n s t h i se s s a ye m p h a s i z e so nt h ef o l l o w i n gr e s e a r c h e sa b o u tl i n k l e v e l s d e l a ye s t i m a t i o n 1 al i n kd e l a yd i s t r i b u t i o n a p p r o a c h i s p r o p o s e d b a s e d0 1 3 t h e d e p e n d e n c et r e em o d e la n du p w a r d d o w n w a r da l g o r i t h m c o m p a r i n g w i t hc l a s s i c a im a x i m u m1 i k e l i h o o d e s t i m a t i o n ( m l e ) t h e m a i n d i f f e r e n c ei st h ep o s t e r i o rp r o b a b i l i t yi sa s s u m e db a s e do nt h ep r i o r p r o b a b i l i t y o nt h es a m el i n k t h i sp r o c e s si s r e p e a t e d t o g e n e r a t e e s t i m a t e dn u m b e r st oa d a p tt r a f f i cc h a n g e s f u r t h e r m o r e ，a c c o r d i n gt oa s p e c i a ld e p e n d e n c et r e em o d e l ，m u l t i c a s td e p e n d e n c et r e em o d e l ，t h e u p w a r d d o w n w a r da l g o r i t h mw a so p t i m i z e dt or e d u c et oo n ee s t i m a t e d p a r a m e t e r t h es i m u l a t i o nr e s u l t so ft h ea l g o r i t h mp r o v et h ea c c u r a c yo f t h e u p w a r d d o w n w a r da l g o r i t h m ；m o r e o v e r , d e r i v e t h e d e l a y c h a r a c t e r i s t i ce f f i c i e n t l yb a s e do nt h ee n d t o e n dm e a s u r e m e n td a t a s i m u l a t i o no ft h ea l g o r i t h mw a si m p l e m e n t e du s i n gc c + + 2 b a s e do nm i x e df i n i t em i x t u r em o d e l s ( m f m m ) w i t he x p e c t a t i o n 北京邮i u 人学坝卜学位论文 m a x i m i z a t i o n ( e m ) a l g o r i t h m ，p r o b a b i l i t yd e n s i t ym o d e l sf o rs e v e r a l l i n k s e n d t o e n dd e l a yi sp r o p o s e d t h r o u g ht h es i m u l a t i o n ，t h ea n a l y s i s o fa l g o r i t h me f t i c i e n c yi sg i v e n 3 o t h e ra l g o r i t h m so nl i n kd e l a y sa p p r o a c h e sa r ei n t r o d u c e d a l l k i n d so fa l g o r i t h m sa r ea n a l y z e da n dc o m p a r e dw i t h 4 e n d t o e n dn e t w o r km e a s u r e m e n ts y s t e md e s i g n ，t r i a ln e t w o r ks e t u p ，s o f t w a r er e q u i r e m e n ta n a l y s i sa n dm o d e ld e s i g na r ea l s op a r to fw o r k t h i sw o r kc o v e r st h e i m p l e m e n t a t i o no fd e p e n d e n c yt r e em o d e la n d u p w a r d - d o w n w a r da l g o r i t h m ，m f m ma n de ma l g o r i t h m k e y w o r d s ： n e t w o r kt o m o g r a p h y d e p e n d e n c et r e em o d e l u p w a r d d o w n w a r d a l g o r i t h m g a u s s i a nm i x t u r em o d e l e m ( e s t i m a t e m a x i m i z a t i o n a l g o r i t h m )m f m m ( m i x e df i n i t em i x t u r em o d e l s ) 独创性( 或创新性) 声明 本人声明所呈交的论文是本人在导师指导f 进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果，也不包含为获得北京邮电大学或其他 教育机构的学位或证书而使用过的材料。与我一劂工作的同志对本研究所做的任 何贡献均已在论文中作了明确的说明并表示了谢意。 申清学位论文谈料若有不实之处。本人承担一切相关责任。 本人签名：立齄女=h 期：2 塑：兰； 关于论文使用授权的说明 学位论文作者完全了解北京邮电大学有关保留和使用学位论文的规定，即： 研究生在校攻读学位期间论文工作的知谚 产权单位属北京邮电大学。学校有权保 留并向国家有关部门或机构送交论文的复印件和磁盘，允许学位论文被查阅和借 阅；学校可以公布学位论文的全部或部分内容，可以允许采用影印、缩印或其它 复制手段保存、汇编学位论文。( 保密的学位沦文在解密后遵守此规定) 保密论文注释：本学位论文属于保密在年解密后适用本授权书。非保密论 文注释：本学位论文至属于保密范围，适用本授权书。 本人签名： 逝堑 r _ | 期：洫d ：! 导师签名： 雅担同期：正墨! 堑：三j j 匕束邮电人? 顺l 一一尊化沦文 1 1 课题背景与意义 第一章绪论 近年来，随着计算机的普及，计算机网络也随之迅速发展，其结构越来越庞 大，也越来越复杂。网络也已经不只是为少数用户提供服务，而发展成为一个大 容量、分布式删络。但是多年来，因特嘲一直没有被有效监测和测量，现存随着 因特网规模的迅速扩大，加上因特网本身也出现了重大的变化，使因特网的网络 测量成为迫睁j 需要进行的工作。 但是由于i n t e r n e t 的分布化、不协作性、异质等特点，直接从各种网络设各 收集数据，反映网络的实际运行状况，只局限在可管理的较小范围之内。而掌握 更大范围、更具普遍意义上的网络运行参数，剥现代网络发展具有很强的现实意 义。所以，例络测量受到了国际l 的普遍关注，成为一个新兴的研究领域。 1 2 国内外网络测量方面研究状况 在国外，互联网性能监测这一行业已经非常发达，从事互联网性能监测的知 名企业有许多，如c a 、m e r c u r y i n t e r a c t i v e 、k e y n o t e 、b m c 、f r e s h w a t e r 等。 在我国，由于受刚络带宽、互联嘲普及程度、嘲上交易环境等影响，互联网性能 监测这一行业发展丰h 对较晚。在测量方面，国防利学技术大学，西南交通大学等 单位在基于i c m p 协议的i p 拓扑探测方面的技术比较成熟。目前，哈尔滨工业 大学计算机科学与工程系实现了一个大规模删络拓扑测量的原型系统，能够针对 大规模网络进行路由i p 拓扑结构的自动发现，并进行可视化显示。 网络测量应用范围广泛，通过刘整个网络数据采集、分析、解释为基础和验 证手段，对i 础络流量、耕1 扑、行为建模作出分析。i n t e r n e t 流量的自相似性、i n t e r n e t 拓扑的幂率分布 2 4 1 等重要规律都是通过网络测量发现的：从网络运营、维护和 服务看，网络测量的结果是进行宏观网络控制和管理、业务计费的重要依据。在 月务质量研究领域，q o s 摔制、管理、计费和测量是相互关联的整体。许多q o s 控制机制，如摹于测量的连接接纳控制、q o s 路由、流量工程、拥塞瓶颈检测 等，需通过测量获取网络性能：q o s 管理需监测网络和用户的服务性能，进行动 北京邮电人。学顾土学能沦文 态资源管理、确认服务等级合约、执行入侵和攻击检测等；q o s 计费需要根据用 户实际状得服务质量来收费；它们都需要q o s 测量的大力支持。从应用性能优 化看，多媒体应用需要通过测量了解当前刚络的性能信息来优化编码器解码器， 以获得更好的业务质量。网络测量对于许多i n t e r n e t 应用和西议，特别是涉及大 量数据传输和具有时延限制媒体流的应用至关重要。内容分发嘲络中的请求路由 协议、对等刚络、刚络缓存的位置选择和维护策略、端系统的组播、内容月务器 中的流调度和接纳控制策略、d n s 和w e b 性能检测等都需要嘲络测量的有力支 持。 目前，i n t e r n e t 测量研究工作大致可划分为三部分：( 1 ) 端到端性能测量 ( e n d t o e n d m e a s u r e m e n t ) 。主要包括时钟同步、拓扑推测、时延、丢包率测量、 带宽测量等。( 2 ) 基于路由器的测量( r o u t e r b a s e dm e a s u r e m e n t ) 。它主要是网 络提供商i s p ( n t e r n e ts e r v i c ep r o v i d e r ) 对可摔的内部脚络进行监测。通常利用路 由器中提供的管理软件监测其内部网络的拓扑、流量、时延、丢包率等数据来完 成测量。由于各网络提供商之问的非呐、作性，大量路由器采集的统计性能数据传 递给网管中心系统，大量增加1 叫络负荷，卅i 适合测量因特刚这种庞大的分布式网 络。( 3 ) 路由器协作测量( r o u t e r a i d e dm e a s u r e m e n t ) f w e b 测量、d n s 系统性 能测量等) 。存边缘主机上执行测量，但必须要路由器的配合与支持，这方面近 来提出了一些新协议。同样由于_ i 同刚络提供商之间1 i 咖作的特点，依赖于路由 器配合的测量方法的能力将受到限制。因此如果基于路由器协作的测量需要获 得标准化组织和工业界的各方面的支持。 本课题进行的端到端性能测量现存只是一个新兴的研究领域，国内外的研究 机构对它还停留在理论研究的水平上 2 2 。它利用端到端q o s 测量结果，比如测 量端一端的时延、丢包率，使用统计信号处理技术进行计算，为叫络性能建立模 型，推测删络内部的运行参数，比如各节点间链路的时延、丢包并进行整个删络 拓扑的推测，为因特网的测量和管理提供有力的支持。图1 ，1 表示端到端测量包 括的范围和联系。 端到端性能测量 l 时钟同步单向时延端到端拓扑性能推测带宽推测 时延拓扑推测时延性能推测链路带宽 丢包拓扑推测丢包性能推测瓶颈带宽 可用带宽 图1 一l 网络性能测量的研究范围及其联系 1 3 课题的主要任务 课题主要分二三个部分：搭建嘲络仿真l 台，实现端到端链路时延算法；开发 i 叫络实测软件，采集有关时延统计数据：比较仿真下台数据、推测数据和实测采 集数据进行不i 司算法优劣分析，提出改善方案。 1 建时络仿真j r 台，实现链路时延算法过程。 。 剥r 端到端测量方面的州络仿真平台一般用i i s 一2 这个俐络仿真器来搭建。 n s 一2 x , j 各种网络结构提供，很好的支持。由于它是用c + 上语言编写的，所以可以 方便实现功能的增加。通过编制n s 一2 仿真程序可以构建一个设定好的比较完备的 刚络运行环境。n s 2 n , 3 输出报表，可以得到仿真下各种关于例络性能的数据。 此外，由i 二算法推测涉及许多复杂的数学模型，要利用m a t l a b 进行算法实现。 这本身由于它强大的数学函数库和优越的数学计算处理能力，可以较方便的编制 程序实现算法过程。 当然要编制软件，考虑到运行速度和兼容。l + i0 ：0 题，还要利用c c + + 语言进行 算法实现和仿真。 2 设计、搭建实验酬络，分层软件设计。 按照设计要求搭建网络拓扑结构。课题组按照分工进行分层软件开发，其中 作者负责算法的实现部分。另外参与数据库等方面的工作。 3 比较仿真，f 台数据、推测数据和实测采集数据进行不同算法优劣分析，提 出改善方案。 这是很重要的过程，由于州络推测过程是一个新兴的领域，人们对整个恻络 的规律还没有形成个完备的体系结构。各种各样拙象出来的关于链路时延的算 法可能有一些自身的局限性。通过对仿真i j j 台、算法推测和实际采集得到的数据 进行比较、分析其小同的结果。对相关的算法进行评估，得出结论，进一步提出 改进的方法，这也为实际的例络推测提出依据。 1 4 论文的结构和安排 本文的剩余部分内容安排如下： 第二章概括介绍端到端测量的基础知识。区别于物理拓扑，课题组是在整个 边缘删络对于逻辑拓扑的测量。测量的范围也十分广泛，包括对i 刊络时钟的同 步、整个逻辑拓扑的推测，重点是剥刚络丢包率、时延和网络带宽的推测。接下 来根据各种小同的特点，把端到端测量进行分类。最后，对课题的应用前景和应 北柬邮电人学颂上学位论文 用范围作了整体的介绍。 第三章首先把端到端例络结构，抽象为依赖树模型。并i - i 结合依赖树模型特 点，创造性地提出利用上向一下向算法推测链路时延的统计特征。根据多播依赖 树这个特殊的依赖树模型，作者对算法进行了一些优化，减少了一种情况的估计。 在算法实现的基础上，对理想i 刊络的条件，实现了仿真，并对各项参数指标进行 了不同情况下的比较。接下来，利用r l s 一2 模拟真实刚络情况，处理数据，并进 行了仿真。由于，丢包率测量可以看作时延推测的特殊情况，作者又对基于依赖 树模型的丢包测量，进行了仿真。 第四章理论上介绍了端到端恻络结构，抽象为高斯混合模型用e m 算法估测 一条路径的时延方法和m f m m 模型用e m 算法刘? 多条链路时延的推测方法。完 成m a t l a b 环境下算法的仿真，结合仿真结果得出结论。 第五章介绍了现在关于端到端时延测量的一些其它算法，包括可以估测链路 瓶颈的c g f 算法、信号盲分离算法处理高斯混合模型和蒙特卡罗算法。最后， 各种时延算法的优缺点进行了简短分析。 第六章介绍了课题中实验蚓络的系统设计。从拓扑规划，各个节点的关系到 硬件平台搭建。在软件方面，根据实际测量所需的各利，功能，从项目需求入手到 要求的功能等各个方面进行介绍。最后，给出了课题分层设计中各个模块的关系 和要求，并目，把数据库中的清晰结构洋细列出。 第七章是结束语，对全文进行了总结，并对网络性能测量与推测的作用意义 进行了展望，指出了目前存研究中还存在的一些问题和 i 足，并对下一步的课题 研究提出了一些设想。 第二章端到端网络测量基础 端到端性能测量的研究最初是由m i n c 项目中组播树丢包相关的研究引发， 而后推广到单播网络以及其他性能的研究q 一。其叉称为网络断层成像( i n t e r n e t t o m o g r a p h y ) f l1 。基于端到端测量是指只有边缘主机参与其中，不需路由器提供 配合与支持，莉：尽门j 能减小对嘲络造成负荷的前提下，获取和蚓络性能相关的统 计数据达到网络推测的月的。它总的目标是将i n t e r n e t 网络拓扑、带宽、性能等 映射成随时间空间变化的函数。 矧络的带宽( b a n d w i d t h ) 、时延( d e l a y ) 和丢包( l o s s ) 是最能体现网络行为的三 类性能特征，也是课题进行端到端测量的重点。 在网络拓扑不可知的隋况下，端到端拓扑推测是端到端性能推测的基础。此 外，它还是基于性能角度对复杂物理拓扑进行抽象简化的有效手段；性能( 时延、 丢包、带宽) 的研究主要集中于树型拓扑的性能推测。刘于一般网络，可将其划分 成多个树型拓扑分别进行测量，而后将在这些树型拓扑上获得的性能参数恢复成 整个例络的性能；例络带宽测量的研究包括瓶颈带宽和可用带宽，带宽测量中引 入的一些探针投术( 如包刘) 也被运用在时延、丢包测量中。 2 1 端到端测量网络的构成 通常所说的端到端的测量是建立在逻辑拓扑的基础之上的。逻辑拓扑是区别 于平时所说的物理拓扑。物理拓扑是例络所有节点真实存在的一种物理结构，它 是由网络终端、路由器等一系列网络设备组成的。代表了各种设备之间的一种组 织形式，如图2 一l 所示： 艇比m ? ，- 薹釜 谊收 图2 - 1 ：物理拓扑结构图 收霄t 北京邮电人学颂上学何论文 而逻辑拓扑，是指在实际探测的物理拓扑上，由于每一条物理链路中的节点 只有在存在链路分支的情况下才可以被探测出来( 由于，莉二各个分支中所表现出 来的链路性能刁i 同) 。这样，可以被探测出来的拓扑结构称为逻辑拓扑，如图2 - 2 所示为图2 1 的逻辑拓扑。 收协! 1 图2 - 2( 图2 - i ) 的逻辑拓扑结构 另外，每个网络都由一个网络实体( n e t w o r k e n t i t y ) 组成，恻络实体可以分成 网络节点叫e t w o r kn o d e ) 、网络链路( n e t w o r kl i n k ) 和网络路径( n e t w o r kp a t h ) 。 节点是能使用互联网议来通讯的计算机，包括主机、路由器、交换机、代理等。 链路是由路由器或各种网络设备直接连接的线路。路径是一个节点到另一个节点 的连接，它最少包含一条链路。 端到端测量的范围只分布存整个删络的边缘，可以存边缘主机和边缘路由器 上。对于网络内部的任何信息都是刁；可能状得的，如图2 3 所示： 1 ，7 。j ； 1 。4 。 ：j f i 巫坶恻碡j i 图2 - 3 端到端测量的范围 北柬邮电人学坜上。7 化沦文 2 2 端到端钡0 量包括的内容 2 2l 时间测量 在端到端测量技术中，时间测量是许多测量工作的必要因素，这使得测量主机 间时钟同步成为许多端到端测量技术的重要基础。 传统的时钊，同步技术大都利用g p s 或p s t n 、c d m a 等蚓络借助外部时钟 源来实现测量主机问同步。但高昂的费用使得很多时候不能够采用。为了满足大 规模端到端测量的需要，提出了建立在n t p 7 ，【1 3 协议之上的时间校准算法。 特别是存测量中，时延的推测要求主机时钟的同步。这就要求单向时延的准 确性。端到端双向h , j 延测量可通过环回时延r t t ( r o u n dt r i pt i m e ) 获得，但端到 端是建立存单向时延测量两端主机间时钟同步的基础之上。由于嘲络的路径不对 称性，去的路径和返【主! _ i 的路径，通常是小同的。例如1 i 同嘲络结构，双向链路性 质不刘称，取向拥塞排队不同等，都影1 们实际测量结果。端到端测量依赖于单向 时延，所以把测量获得的单向时延称为测得时延，而实际的时延称为真实时延。 通常情况下，两终端测量主机初始时刻时问1 i 同，并日运行的频率也不同， 称频率之差为刚钟频率偏差。如果两主机的时钟完全唰步，即初始时刻和频率都 相同的情况，测得时延才等j 二真实时延。如果两主机的时钟频率偏差为常量，则 测量时延样点的卜_ 延近似于一条直线d ( t i ) = at + p ，其l 中，b 的含义是两时钟在 测量初始时刻的叫间偏差加上固定的传播和发送时延，o 的含义是两时钟频率偏 差导致测量时延( 下延) 随着测量时间的推移而线性的增加( 或减小) ，测得时延的 抖动是拥塞变化导致排队 | 寸延的卅i 同，如图2 4 ( a ) ： 圈2 4 引丈 14 1 时延仿真结果 实际情况，时钟的行为更加复杂，时钟频率随着时间、温度等条件发生漂移 北京邮电人学顶0 + 学何论文 实际测得时延下沿不再是线性变化，如图2 4 ( b ) 中下沿变成了一条曲线。另外， 网络主机时钟可能由于运行了n t p 协议，周期性地与外部时钟或者其它原因进 行修正。而使测量到的时钟发生突变。所以，单向时延测量的关键任务就是要消 除时钟频率偏差以及外部或本地时钟校准带来的误差，且计算复杂度应足够小。 几种消除时钟对测量影响的算法： 1 ) p a x s o n 提出的中值线适应技术算法：但是，当收集的数据变化区间很大 时，这种算法只能对斜率提供一种很粗略的估计值。 2 ) 线性退化算法：因为网络时延测量自身特性，推算效果也不是a 理想， 仅仅在收集的网络数据非常规的情况下，线性退化算法才能有很好的效果。但是， 实际情况，网络特性本身的变化性根本无法满足这个条件。尤其在突然发生的网 络拥塞状况下，将造成很大的频偏估计误差。 3 ) 分段最小化方法：提出了变频段的概念，但要满足这些频偏段不是一条 直线或者有相同的斜率。显然，真实条件无法满足，因此也一i 会提供正确的剁率 估计。还有把这个问题归纳成线性规划问题并使用线性规划问题的标准算法解 决。 4 ) 凸多边型的计算方法：同线性退化和线性规划算法相比，凸多边型算法 更接近问题的本质，允许存在更多测量误差。存彳i 考虑时钟复位的情况下，在大 量测量点中使用的一种线性算法。 2 2 ，2 网络拓扑探测 为了进行端到端的测量，必须要了解网络的拓扑。这样才能对整个链路情况 有一个准确的判断。传统的拓扑探测方法，是基于路由器或路由器协作的。利用 s n m p ( s i m p l en e t w o r k m a n a g e m e n tp r o t o c o l l 、b g p 协议、m i b ( m a n a g e m e n t i n f o r m a t i o nb a s e ) 、i c m p 等方法获得路由表。这些方法适合于在具有管辖权的网 络范围内进行测量。但它卅i 适合端到端的测量。目前，基于q o s 测量进行刚络 拓扑推测成为新的研究热点，其主要是利用基于点到点流量的端到端测量进行网 络内部特征的推断。 通常的情况下，主要针对一个发送者和多个接收者之间建立的树形结构。利 用发送的多播包或单播包对之问的相关性，推断丢包率和时延的逻辑拓扑。存这 种方法中，网络被建模为个有向逻辑树，树的顶点表示网络的节点如路由器或 终端，树的边则表示捌络的链路。研究表明，通过对多播或单播探测的端点丢包 信息统计分析。利用极大似然估计，可以得到刚络的树型拓扑结构。 北m0 i i j i 乜人学倾j 。学似沦文 2 23 网络丢包率推测 丢包率是丢失的i p 数据包与所有的i p 数据包的比值。许多因素会导致数据 包在l 劂络传输时被玉弁，例如数据包的大小以及数据发送时链路的拥塞状况等。 丢包特征包括单向丢包( o n e - w a y l o s s ) 、双向丢包( r o u n d t r i pl o s s ) 、舌包模式 ( l o s sp a t e r n ) 。 现存，主要利用单播或多播端到端俐络测量来确定内部例络的夏包率。在多 播探测中，用于探测的数据是由一个发送方向许多接收方发送的，但只有部分的 接收方报告多播探测的观测结果。这被用于推测连接发送和接收的每个树形逻辑 链路的丢包特征。存单播探测中，需要建立基于端到端分组测量的网络丢包探测 过程以及推测内部丢包特征的统计建模和计算框架，统计成功通过的探测分组， 并进一步计算出链路的丢包概率。与多播相比，单播推测更易于在多数网络上实 现，目可扩展。但是，由于单播推测的方法，获得的节点相关信息比较少，很难 得到嘲络内部链路的统计特女f 。现存大多利用包对的方法，利用承载相关信息的 包剥，可以获得更多的统计数据。 通常估测恻络端到端丢包率的算法是e m 算法。 2 2 3 网络时延推测 时延是i p 包穿越一个或多个嘲段所经历的时间。概括的说，时延被分为四 个主要部分： 1 ) 处理时延( p r o c e s s i n gd e l a y ) ：指分组到达一个节点的输入端与该分组到 达该节点的输出端之间的时延。它受每个节点的计算能力和可用的硬件的影响， 刁i 受流量的影响。 2 ) 传输时延( t r a n s m i s s i o nd e l a y ) ：指发送节点在传输链路上开始发送分组的 第一个比特至发完该分组的最后一个比特所需的时间。 3 ) 传播州延( p r o p a g a t i o nd e l a y ) ：指发送节点存传输链路上发送第一个比特 时刻至该比特到达接收节点的时间。 4 ) 排队时延( q u e u i “gd e l a y ) ：指分组存路由器的缓冲区中，传输前的等待时 间，由路由器中的交换结构决定。 通常所说f 向吲延包括：单向时延( o n e - w a yd e l a y ) 、政向时延- ( r o u n d t r i p d e l a y ) 。对端到端的h i j 延推测来讲，就是通过对单向时延的路径探测，推测链路 时延。 关于时延的推测，它和丢包推测类似也是主要利用多播和包对的方法。目前 关于链路州延性能推测的研究文献主要有 2 - 8 。 2 2 4 网络带宽推测 带宽一般分为瓶颈带宽和可用带宽。 1 ) 瓶颈带宽是指当一条路径( 通路) 中没有其它背景流量时，网络能够提 供的最大的吞吐量。对瓶颈带宽的测量一般采用包对( p a c k e tp a i r ) 技术，但是由于 交叉流量的存在会出现“时间压缩”或“时间延伸”现象，从而会引起瓶颈带宽的高 估或低估。另外，还有包列等其它测量技术。 2 ) 可用带宽是指在网络路径( 通路) 存在背景流量的情况下，能够提供给 某个业务的最大吞吐量。因为背景流量的出现与否及其占用的带宽都是随机的， 所以可用带宽的测量比较困难。一般采用根据单向时延变化情况，对可用带宽进 行逼近。其基本思想是：当以大于可用带宽的速率发送测量包时，单向时延会呈 现增大趋势，而以小于可用带宽的速率发送测量包时，单向时延不会变化。所以， 发送端可以根据上次发送测量包时单向时延的变化情况动态调整此次发送测 量包的速率，直到单向时延卅i 再发生增大趋势为止，然后用最近两次发送测量包 速率的平均值来估计可用带宽。 瓶颈带宽反映了路径的静态特征，而可用带宽真正反映了存某一段时间内链 路的实际通信能力，所以可用带宽的测量具有更重要的意义。 2 3 端到端测量方式分类 2 3 1 被动测量和主动测量 根据是否发送主动探测包，测量技术可分为被动测量和主动测量技术。 1 ) 被动测量用于观察和记录网上的分组，不注入自身流量，因此被动测量又 称为非侵扰式测量，如t c p d u m p 、n e t r a m e t 等。其原理是通过捕获承载报文的 信息，被动地实现嘲络传输时延的测量，卅i 会对刚络的负荷造成影响。 2 ) 主动测量方法使用测量设备产生的分组对因特网进行探测，并测量出其特 征，因此主动测量又称为侵扰式测量，例如：p i n g 用于估计到因特删特定目的地 的网络时延，t r a c e r o u t e 用于检测因特例中的路径，p a t h c h a r 用于估训沿某路径 的链路容量和时延等。主动测量通过向网络发送探针，并根据探针所携带的信息 来推测网络的情况，主动测量将影响酬络的负荷，产生大量探针的主动测量方法 无法实用。 被动测量不产生探测流量，但缺点是如果网络上没有流量，就无法工作，同 时它还要求特殊的装置或改变协议。而主动测量向网绍中发送测量报文，因此主 动测景会引发性能的失真，即所谓h e i s e n b e r g 效应，这是由于测量报文插入到网 络中的数据包会改变删络的行为，从而使实际测量的结果失真。因此，可结合两 者特性进行测量。 2 3 2i c m p 测量、u d p 测量和t o p 测量 按照其承载的仂、议可以分为如下三类： 1 ) 利用i c m p 协议实现。这是最常用的测量方式，最典型的应用就是操作系 统里自带的“p i n g ”命令。p i n g 是基于i c m p 请求应答( e c h or e q u e s t ) 报文7 1 二发的应 用软件，p i n g 发送i c m p 的e c h o ( 类型0 8 ) 回应请求报文，当接收方收到该报文后， 会马上返回一个e c h or e p l y ( 类型o o ) 1 回应应答报文，这样发送方收到反馈报文后 就可以计算得州列络的性能参数。p i n g 存w i n d o w s “t 台上的默认方式是连续发送 4 次e c h o ! 报文，报文长度为6 0 字节，4 i 过可以根据参数改变测试次数和报文长度。 需要指出的是，p i n g 报文容易造成网络攻击，比较典型的有p i n go f d e a t h 攻击f 利 用大于6 5 5 3 5 字节的非法长度报文去p i n g 主机，使得目标主机没有足够空间组装 该报文而产生死机等现象，对w i n d o w s 系统有效) $ u n e t - p i n g f l o o d i n g 攻击( 利用大 量的p i n g 报文造成d o s 攻击) 。由于其安全性不高，因此现在许多主机和防火墙 开始过滤i c m p i 办议的报文。 2 ) 利用u d p 协议实现。当对方的主机或者中间节点( 包括防火墙) 出于安全等 原因而过滤掉i c m p 报文后，可以使用u d p ：报文来实现恻络的性能参数测量。u d p 报文的实现和i c m p 报文较为相似，都是无连接的。_ i 同的是u d p 协议需要指定 一个端1 ：2 1 ，在实际使用时，可以任选一个端口，当接收方该端口对应的服务不存 在时，会立即返回一个“端口1 i 可到达”的i c m p 报文( 类型0 3 ，码值0 3 ) 。因此，在 使用u d p 报文进行测量时，要注意发送方发送一个u d p 报文，接收方反馈的一i 一 定是u d p 报文，电有可能是i c m p 报文，这两种返回的报文都可以用来计算网络 的性能参数。此外，u d p 议存实现时要注意其最大报文长度与i c m p 报文不同， 通常应小于5 0 0 字节。 3 ) 利用t c p 协议实现。这是钳刑目前防火墙设冠，在业务流测量系统中提 出的一种新方法。该方法的实现比较复杂，但可以适用于测量某些前两种方法不 能工作的特定环境，即l 坊火墙不仅滤掉了i c m p 报文，也滤掉了u d p 报文，只 限制使用某些特定的t c p 协议时。除了选取合适的承载报文，t c p 协议测量刚 络性能参数的难点包括t c p 协议发送机制本身。 t c p 协议为了提高传输效率，往往不是即时发送报文，而要收集足够的数据 后才发送，因此可能会产生发送方记录的发送时间远远早于实际发送时间，而使 北京邮电火学硕 j 学化论文 得测量的结果大于实际值的现象。为了避免这个现象的发生，在主动测量时，不 但要求发送方存承载的t c p 报文中加入p s h 标志( 即用p u s h 操作发送数据报文) ， 此时将立即发送此数据报文而无需等待，同时也要求接收方存反馈该报文时，电 必须带p s h 标志。同理，在被动测量时，要注意承载报文必须是带有p s h 标志 的报文，并日对应的反馈报文也必须同样带有p s h 标志。因此，用t c pt , d 、议实 现网络传输时延的测量时，特别是在被动测量时，必须长时间的等待合适报文的 出现，否则测试的结果都将会有误差。 前面三种方式的比较如表2 1 所示： 衷2 1 网络传输时延测量方式的比较 用i c m p 实现用u d p 实现 用t c p 实现 实现难度容易容易难 可行性容易被滤掉容易被滤掉不容易被滤掉 效率 】司 r 司低 一 安全性低中尚 准确度目较高较高 当然也可以利用其它协议实现网络性能的测量。方法基本和u d p 或t c p 类 似，关键是选取合理的承载报文，即能存发送方立即发送，而接收方收到后又能 立即反馈的报文。在业务流测量系统中，课题组主要采用了基于u d p 协议和t c p 协议的时延测量方法，较好地测得了实时的网络时延，为系统动态选取部件、分 配资源提供了标准。 2 33 多播测量和单播测量 端到端测量的探测方法分为两种方式：多播测量和单播测量。 多播测量：由于在共享链路上，数据包是相同的，在分支前的路由器上进行 数据包的复制，所以只要一个节点能收到数据包就能保证共享链路上的性能，从 而间接判别分支链路上的性能。 单播测量：在多播网络的测量中，可以准确地得到同一个多播包的接收情况， 推测算法也相对准确。但是目前基于流量的考虑，网络上全面支持多播的路由器 较少，多播删络多用于局域l 删和各种测试嘲络中。所以，卅i 得一i 采用单播的方式 进行测量。由于单播不像多播，发送的数据包没有什么相关性。所以，人们采取 了很多方法，其思想尽可能模拟多播方式。现在普遍采用背靠背的包对技沭。其 北柬 | 1 | ；电人学顺r l 学似沦文 摹本思想是这样的：以测量丢包率为例，假设有两个背靠背的包，分别发送到不 同的接收端其th 有一段路径为共享路径，那么如果一个成功接收一个丢掉的话， 就可以推测丢包发生存非共享路径上。列收集到的数据进行处理，就能得到所有 链路的丢包率。这种方法的关键在于包剥可以获得更多的丰目关性信息。与多播相 比，单播推测吏易于在多数嘲络一1 2 实现，i - t 可扩展。 2 4 塥u j 到二而t a j 测, 量目前存在的问题和应用前景 冈特1 列的测量还有相当多的困难。如：测量分组可能丢失，路由随时问变化， 一些路由器关闭i c m p 分组的测试功能等等。网络的拓扑、性能都是时问和空间 的函数，现有的研究工作大都假定性能时空独立来简化问题，【乜使其无法完全解决 列络中实际复杂问题。在这方面有必要迸一步深入地研究。而曰在实测部分， 可能会需要一些服务器和主机的l ! 办作，这也是目前存在的问题之一。 但端到端。睦能测量( 时延和丢包枣的测量) 1 _ - 作的应用前景非常广泛，表2 2 中做j ，一小结。 表2 - 2端到端网络测量工作的应用前号 端端到端时钊，同步存小需要g p s 、p s t n 、c m a 等外部时钊一同 到步机制的条件下，达到消除端到端主机频率偏差 端 的目的。 性端至0 端拓扑 发现与某；f | 1 j 性能d 付延丢包率j 及其敏感参数 能 相关的逻辑拓扑，便于恻络运维和扩容规划。 测 性能推测发现网络中大1 1 4 延高丢失率的区域或链路j 量 接纳控制，流量工程。 网络测量的具体用途可分为以下几大类： f 1 1 故障诊断 某些网络部件的故障会干扰整个网络的运行，例如，广播风暴、非法分组长 度、地址错误、安全性攻击等，需要对这些故障进行诊断。 ( 2 ) 卧议排错 网络的研制者经常要对刚络应用和网络协议“薪的、改进的”版本进行测试。 而例络测最能够为新协议和应用程序的正确运行提供手段，使其和标准保持一致 或使老的版本向后兼容。 ( 3 ) 网络流量特征化 网络测量可使用统计技术来分析经验数据，从而提取网络应用或网络协议的 北京邮电人学领上学位论文 特征。流量特征化使设计的网络协议和网络设备具有更好的特性。 f 4 1 性能评价 网络测量可用来考察某个协议或某个应用存因特嘲中的性能水平。恻络测量 的详细分析能够帮助确定性能“