（通信与信息系统专业论文）可用带宽主动测量算法的研究.pdf

北京邮电大学硕士研究生学位论文 可用带宽主动测量算法的研究 摘要 随着网络规模的飞速增长，i n t e m e t 的控制机制和行为特征也日 趋复杂，在认识网络的行为特征和性能表现，辅助网络宏观布局和管 理，优化整体性能，保证和提高网络服务质量，推动信息基础结构健 康发展等方面，网络测量起到至关重要的作用，其中可用带宽作为网 络最基本和最重要的性能指标之一，在网络性能测量中有着举足轻重 的地位。 近年来，国内外在可用带宽算法研究上已经取得了很大成就，通 过理论分析以及大量的仿真模拟试验，提出了许多可用带宽算法。这 些算法主要是主动测量算法，通过发送测试包并在接收端获得测试包 所携带的信息，再由这些信息估计出可用带宽。s p r u c e 算法通过对测 试包在收发两端包间隔进行统计估计，从而估计出可用带宽值；i g i 算法通过不断调整发送间隔直到发送序列与接收序列长度相等，此时 发送速率即可视为可用带宽值；s l o p s 算法根据测试包传输时延的变 化趋势不断调整发送速率直到达到收敛，收敛时的发送速率即为可用 带宽；p a t h c h i r p 算法测试包间隔采用指数分布，使得接收端获得的 时延信息相关性很强，从而能够使用较少的测试包较快的测量出可用 带宽；t r e n o 通过模拟t c p 连接获得b t c ( b u l kt r a a s f e rc a p a c i t y ) ， b t c 在一定程度上反应了可用带宽的变化趋势。 对各算法原理进行研究分析后，编写代码实现各算法，模拟实际 网络负载环境，进行算法仿真试验。然而，通过对比分析各算法试验 结果发现，这些算法都存在各自的缺点：s p r u c e 算法测量结果不稳定； i g i 算法测量精度会随着网络负载突发性的下降而下降；s l o p s 算法 收敛速度慢，测量时间较长；p a t h c h i r p 算法中测试包较大，离开瓶 颈链路后在后续链路中受到影响也较大，从而影响测量精确度；t r e n o 的测量结果反映的只能是t c p 吞吐量而非可用带宽。 最后，研究了一些已有的可用带宽改进算法。通过对这些改进算 法进行经验总结，针对i g i 算法的缺点，提出一种基于i g i 的改进的 可用带宽算法。i g i 算法在负载突发性较高时，测量结果才具有较高 的精确度，因为它仅仅考虑了包对间隔增大的情况，换言之，该算法 忽略了队列长度变化对包对间隔的影响。改进后的算法引入了对队列 长度的递推估计，实现了新的负载流量的计算方法，从而较为有效地 北京邮电大学硕士研究生学位论文 克服了原算法的局限性；此外，改进后的算法还引入对“碰撞现象 的处理，并在测量可用带宽的同时完成了对瓶颈链路带宽的估计，进 一步地提高t n 量精度和测量效率。 关键词：可用带宽瓶颈带宽测试序列网络负载 北京邮电大学硕士研究生学位论文 r e s e a r c ho fa v r a ，a b l eb a n d w i d t h a c t i v e m e 匝a s u r e 正n ta l g o r i t h m a b s t r a c t w i t ht h eu n b e l i e v a b l ed e v e l o p m e n to ft h en e t w o r ks c a l e ，t h ec o n t r o l m e c h a n i s ma n db e h a v i o rc h a r a c t e r i s t i co fi n t e m e tb e c o m em o r ea n d m o r ec o m p l i c a t e d i nt h ea r e ao fr e a l i z i n gt h en e t w o r k sb e h a v i o r c h a r a c t e r i s t i ca n dp e r f o r m a n c ed i s p l a y ，h e l p i n gt h en e t w o r k sm a c r o s c o p ya r r a n g e m e n ta n dm a n a g e m e n t ，o v e r a l lp e r f o r m a n c eo p t i m i z a t i o n ， g u a r a n t e e i n ga n di m p r o v i n gt h en e t w o r ks e r v i c eq u a l i t y , a n dp r o m o t i n g t h ei n f o r m a t i o nb a s i cs t r u c t u r e s h e a l t h yd e v e l o p m e n te t c ，n e t w o r k m e a s u r e m e n ti ss i g n i f i c a n t a so n eo f t h em o s tb a s i ca n dm o s ti m p o r t a n t p e r f o r m a n c ep a r a m e t e r s ，a v a i l a b l eb a n d w i d t ht a k e sa ni m p o r t a n tp a r ti n t h en e t w o r kp e r f o r m a n c em e a s u r e m e n t r e c e n t l y ，t h e r ea r eh u g ea c h i e v e m e n t si nt h er e s e a r c ho fa v a i l a b l e b a n d w i d t ha l g o r i t h ma th o m eo ra b o a r d w i t ht h et h e o r ya n a l y z ea n d m a n ys i m u l a t i o ne x p e r i m e n t s ，t h e yp r o p o s e dm a n ya v a i l a b l eb a n d w i d t h a l g o r i t h m s t h e s ea l g o r i t h m sa r em a i n l ya c t i v em e a s u r e m e n ta l g o r i t h m s b ys e n d i n gp r o b ep a c k e t s ，t h er e c e i v e rc a ng e tm u c hi n f o r m a t i o no ft h e p r o b ep a c k e t s t h e nw ec a ne s t i m a t et h ea v a i l a b l eb a n d w i d t hw i t ht h e i n f o r m a t i o n s p r u c ea l g o r i t h me s t i m a t e st h ea v a i l a b l eb a n d w i d t hb y d o i n gs t a t i s t i c sa n de s t i m a t i n ge a c hp r o b ep a c k e t si n t e r v a li nt h es e n d e r a n dt h er e c e i v e rr e s p e c t i v e i g ia l g o r i t h mr e g a r d st h es e n d i n gr a t ea st h e a v a i l a b l eb a n d w i d t h ，w h e nt h es e n d i n gp a c k e t ss e q u e n c e sl e n g t he q u a l s t h er e c e i v i n gp a c k e t sb ya d j u s t i n gt h es e n d i n gr a t ec o n t i n u a l l y s l o p s a l g o r i t h ma d j u s t st h es e n d i n gr a t ec o n t i n u a l l yb a s e do nt h et r a n s l a t e d e l a y sc h a n g i n gt r e n d ，a n dt h e nt h er a t ew h e nt h ea l g o r i t h mg e t s c o n v e r g e n c ei sr e g a r d e da st h ea v a i l a b l eb a n d w i d t h p a t h c h i r pa l g o r i t h m a d o p t sa l le x p o n e n t i a l l ys p a c e dc h i r pp r o b i n gt r a i n ，w h i c hm a k e st h e d e l a yi n f o r m a t i o nh a v es t r o n gc o r r e l a t i o n ，a n dt h e ni t c a ne s t i m a t e a v a i l a b l eb a n d w i d t hw i t hl e s sp r o b e p a c k e t sr a p i d l y 北京邮电大学硕士研究生学位论文 a f t e rd o i n gr e s e a r c ha n da n a l y z et h ea l g o r i t h m s p r i n c i p l e ，id o c o d i n gt ob r i n go u te a c ha l g o r i t h m ，s i m u l a t et h ec i r c u m s t a n c ew i t ha c t u a l n e t w o r kt r a f f i cp a c k e t s ，t h e nm a k es i m u l a t i o ne x p e r i m e n t s h o w e v e r ，b y a n a l y z i n ga n dc o m p a r i n gt h er e s u l t so fe a c ha l g o r i t h m ，w ef o u n dt h a t e a c ho n eh a sr e s p e c t i v ed e f a u l t s f o re x a m p l e ，s p r u c ea l g o r i t h m s m e a s u r e m e n tr e s u l ti sn o ts t a b l e i g ia l g o r i t h mm e a s u r e m e n ta c c u r a c y w i l ld e c r e a s ew h i l et h en e t w o r kl o a d sr a t ed e c r e a s i n g s l o p sa l g o r i t h m s c o n v e r g e n c er a t ei s t o os l o wa n dm e a s u r e m e n tt i m ei st o ol o n g i n p a t h c h i r pa l g o r i t h m ，p r o b ep a c k e t sa r e s ol a r g et h a tt h em e a s u r e m e n t a c c u r a c yw i l lb ei n f l u e n c e di nt h en e x tl i n kw h i c hi sa f t e rt h eb o t t l e n e c k l i n k t r e n oa l g o r i t h mm e a s u r e m e n tr e s u l tr e f l e c t st h et c pt h r o u g h o u t i n s t e a do ft h ea v a i l a b l eb a n d w i d t h f i n a l l y ，w ed os o m er e s e a r c ho fe x i s t e da v a i l a b l eb a n d w i d t h i m p r o v e da l g o r i t h m w ed r e ws o m ee x p e r i e n c ef r o mt h ea l g o r i t h m s f o u n dt h ed e f a u l t so fi g ia l g o r i t h m ，a n dp r o p o s e di m p r o v e di g i a l g o r i t h m i g ia l g o r i t h mm e a s u r e m e n t i sa c c u r a t ew h e nt h en e t w o r kl o a d i s h i g hb u r s t b e c a u s ei g ia l g o r i t h m sp r i n c i p l ej u s t c o n s i d e r st h e s i t u a t i o nt h a tt h ei n t e r v a l sb e t w e e nt w op r o b ep a c k e t sb e c o m el a r g e r i n o t h e rw o r d ，t h ea l g o r i t h mi g n o r e st h ei n f l u e n c et h a tt h es e q u e n c ec h a n g e b r i n g st ot h ei n t e r v a l s t h ei m p r o v e da l g o r i t h ma d o p t sr e c u r s i o nm e t h o d t oe s t i m a t et h es e q u e n c el e n g t h i ti san e wn e t w o r kl o a de s t i m a t em e t h o d ， w h i c ho v e r c o m e st h el i m i t a t i o no fo r i g i n a l a l g o r i t h me f f e c t i v e l y f u r t h e r m o r e ，t h ei m p r o v e da l g o r i t h ma l s oa d o p t st h ep r o c e s so ft h e h i t t i n gp h e n o m e n o n ，a n di t i sg a u g e da st h ei n v a r i a n tm o d eo fp a c k e t i n t e r v a l sd u r i n gt h ep r o c e s so ft h em e a s u r e m e n t t h e r e f o r e ，t h ep r o p o s e d a l g o r i t h ma l s oi m p r o v e st h ee f f i c i e n c yo ft h em e a s u r e m e n t k e yw o r d s -a v a i l a b l eb a n d w i d t hb o t t l e n e c kb a n d w i d t h p r o b e p a c k e tt r a i n n e t w o r kl o a d 北京邮电大学硕士研究生学位论文 独创性( 或创新性) 声明 本人声明所呈交的论文是本人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果，也不包含为获得北京邮电大学或其他 教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任 何贡献均已在论文中作了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名： 扭虹 日期：竺圣笙至盟! 竺 关于论文使用授权的说明 学位论文作者完全了解北京邮电大学有关保留和使用学位论文的规定，即： 研究生在校攻读学位期间论文工作的知识产权单位属北京邮电大学。学校有权保 留并向国家有关部门或机构送交论文的复印件和磁盘，允许学位论文被查阅和借 阅；学校可以公布学位论文的全部或部分内容，可以允许采用影印、缩印或其它 复制手段保存、汇编学位论文。( 保密的学位论文在解密后遵守此规定) 保密论文注释：本学位论文属于保密在一年解密后适用本授权书。非保密论 文注释：本学位论文不属于保密范围，适用本授权书。 本人签名： 盘! 燃 日期：2 翌垒生! 堕! 望 导师签名： 主受 日期：鲨墨：蔓二：! 北京邮电大学硕上研究生学位论文 1 1 课题背景及研究意义 第一章绪论 随着宽带网络技术以及实时多媒体应用技术( 如流媒体、视频会议等) 的发 展，业务多样化和快速增长已成为一个不争的事实，这对网络提供的“服务 质量 ( q o s ) 提出了更高的要求。传统的“尽力而为”( b e s te f f o r t ) 网络缺乏有效 的q o s 机制，不能保证分组的正确性、有效性及可靠性等因素，因此建立高效、 稳定、可靠、互操作性强、可预测、可控的网络成为网络研究的重点，而网络测 量是获得网络性能指标的有效手段，在测量和测试的基础上建立网络行为模型， 并用仿真模拟的方法搭建理论到实际应用的桥梁是理解网络性能的有效途径。网 络测量与网络性能分析是高性能协议设计、网络规划与建设、网络拥塞控制管理 与操作的基础，同时也是开发宽带网络应用( 如音视频网络应用) 的基础。 网络性能测量技术的研究成果可用于互联网运营商、电信运营商、拥有分组 专用网络的企业、测试服务提供商、测试工具开发商以及政府主管部门等，对于 分析、确定现有分组网络存在的潜在问题，评价和比较网络改造方案，优化网络 性能等方面都有很大帮助。 网络的可用带宽作为网络最基本和最重要的性能指标之一，在网络性能测量 中有着举足轻重的地位，对网络可用带宽的测量是理解网络行为特征和实际应用 状况的有效手段。如何以最快的访问速度获取网络提供的资源和服务，已成为网 络服务提供商和用户越来越感兴趣的事。根据可用带宽的测量结果，可对数据流 速率进行控制，防止拥塞，保证网络的服务质量。 可用带宽测量的结果可用于网络性能监控。为了保证网络以及网络的哥哥部 件能够持续不问断的运行，就需要对网络的可用带宽进行实时监控。可用带宽的 测量还与流量控制有着密不可分的联系。流量控制指的是可以根据网络测量的结 果对网络流量进行一定程度的控制，从而达到提高网络性能的目的。而流量控制 属于流量工程的一部分，流量工程涉及网络工程中与互联网的设计、供应和调整 有关的各个方面。它将商业目标、技术上和科学上的原则应用于互联网流量的测 量、建模、描述和控制，并依靠这些知识和技术达到特定的服务和性能上的目标， 包括流量在网络资源的有效利用，以及网络容量的合理规划。 因此，研究可用带宽测量算法具有重要的现实意义，通过相关技术的产业化， 能够产生良好的经济效益和积极的社会效益。 1 2 相关领域的研究现状及发展趋势 北京邮电火学硕士研究生学位论文 目前，对于网络性能测量技术的研究越来越受重视，可用带宽算法测量的研 究也越来越多，国际上相关团体对于带宽和流量己经作了大量工作，与测量技术 相关的组织有很多。从1 9 0 0 年开始，i e t f 即开始对流量工程有关的领域进行跟 踪，相关的工作组也成立很多，例如：i p f i x ( i pf l o wi n f o r m a t i o ne x p o r t ) ， c c a m p ( c o m m o nc o n t r o la n dm e a s u r e m e n tp l a n e ) ，m p l s ( m u l t i p r o t o c o ll a b e l s w i t c h i n g ) ，t e w g ( i n t e r n e t t r a f f i c e n g i n e e r i n g ) ， b m w g ( b e n c h r n a r k i n g m e t h o d o l o g y ) ，i p p m ( i pp e r f o r m a n c em e t r i c s ) 。这些组织都致力于网络带宽测量 算法研究，并取得了不少成果。 但是就整体研究水平来讲，这些研究还处于处级阶段，测试理论的研究还有 待深入。大多数可用带宽算法都只考虑了简单的单跳网络实验环境，且假设紧张 链路即为瓶颈链路，这在实际网络中都是不合理的。带宽测量有待解决的关键问 题有： 1 带宽定义与分类的标准化，以及带宽测量指标和方法的标准化； 2 开发高效、快速的带宽测量算法，使其在对网络端到端路径进行探测时 能适应不同网络条件的变化，不会向网络产生太多的探测流量，同时不 会影响到带宽测量的精度； 3 一些传统的带宽测量算法在高速网络环境下表现出很大的局限性，测量 结果变得没有意义，如何同时改进算法的效率和测量结果的精度以适应 新的网络环境成为网络测量领域新的难点； 4 针对不同网络环境和不同业务或应用的带宽需求，提出相应的带宽测量 以及保证q o s 为基础的带宽分配解决方案。 从长远来看，网络性能测量还应该与对网络性能的控制与调整相结合，在这 方面，以后的目标是： 1 提供主动的控制功能，不仅仅在于对网络性能状况的获得，还能够设计 实现业界标准的流控算法进行灵活的流量控制，改进网络服务质量。 2 满足重点监控需要，提供丰富的特征参数监控，可以进行灵活的复合设 定，全面满足运营商的需要，也可以通过定制来实现特定要求。 3 降低互联互通成本，获得重点出口中继链路的利用率，用户和协议分布， 源和目的网段间的流量分布和趋势，提供运营和互联成本分析。 4 实现区分服务，保证服务质量，性能监控获得的数据，可进行高低优先 级客户的网络资源占用率分析、服务质量的测量。通过资费政策的调节、 业务等级的区分，在中继线路上实施流量控制，优先保证高优先客户的 服务质量。 5 网络安全和抵御d o s 攻击，通过连接会话数的跟踪，源目的地址对的 北京邮电大学硕士研究生学位论文 分析，t c p 流的分析，能够及时发现网络中的异常流量和异常连接，监 测和定位网络潜在的安全问题和攻击行为，保障网络安全。 建立完善的监控系统，支持同时从多个网关获取流量数据，实现分布式流量 监控系统，便于在未来建立完善的网络性能监控网，保护前期投资。对外提供标 准接口，与其他运营支撑系统共享数据。 1 3 论文内容安排 本文主要介绍了几种可用带宽测量算法，通过n s 仿真平台模拟实际网络环 境，实现各算法并对测量结果进行对比分析，总结出各算法的局限性；针对i g i 算法的缺点，提出了一种基于i g i 的改进的可用带宽算法，改进后的算法考虑了 队列长度以及负载突变对包间隔的影响，有效减小了测量偏差；此外，提出了一 种简便的瓶颈带宽的计算方法，测量可用带宽的同时也可测量出瓶颈带宽；最后， 分析了包列长度和包的大小对测量结果的影响。通过仿真试验证明，改进后的算 法缩短了测量时问，提高了测量效率和测量精度。 本文章节安排如下：第二章对网络性能评估指标和现有网络可用带宽的测量 方法进行综述；第三章详细介绍网络模拟软件n s ；第四章建立实际网络负载流 的模型，搭建网络拓扑，仿真实现各可用带宽算法，并对各可用带宽算法测量结 果进行对比分析，包括误差分析和收敛时间分析：第五章介绍现有改进的可用带 宽算法，并详细介绍一种基于i g i 的改进算法，最后进行仿真试验；第六章总结 全文，展望下一步研究内容。 北京邮电大学硕士研究生学位论文 2 1网络性能评估指标 第二章综述 网络性能测量是指遵照一定的方法和技术，利用软件和硬件工具来测试或验 证表征网络性能的指标的一系列活动的总和，可以借鉴物理学中测量物理量的方 法。带宽测量的方法主要分成两大类，被动测量和主动测量。本文研究主动测量 方法。 被动测量方法主要是通过对网络流量及状态参数的监视和收集来完成测量 任务，其测量尽量避免干涉网络的正常运行，对网络性能的影响很小。但是，被 动测量采集所需要的数据不能达到实时性，不能迅速满足了解网络现状的要求： 而且被动测量一般只能用于单点监测，难以进行端到端的行为分析。因此，这里 主要讨论主动测量方法。 主动测量方法通过向网络发送测试数据包，并根据测试包所携带的信息来推 测网络的情况。测量工具在测试主机上测量，不需要路由器增加其他的网络协议 来配合，属于端到端测量主动测量具有主动性强、灵活、方便等优点，能以更直 接的方式来分析网络。 网络性能指标是描述网络性能的有效参数，比较常用的评价网络性能的主动 测量的测量指标【l 】有：分组差错率和丢失率；延迟，包括单向延迟，往返延迟和 时延抖动；带宽，包括容量，瓶颈带宽，链路利用率，可用带宽，吞吐量等；系 统可用性，可靠性。 本文主要介绍几种基本指标：吞吐量( t h r o u g h p u t ) 、时延( d e l a y ) 、丢包率( l o s s g a t e ) 、时延抖动( d e l a yv a r i a t i o n ) 、带宽( b a n d w i d t h ) 等。 吞吐量：测量交换设备的数据包转发能力，通常指在不丢包的情况下每秒转 发数据包的数量。 时延：数据包的发送时刻t l 与数据包接收时刻t 2 的时间间隔t 2 t l 。时延 的测量往往经过多次测试采样后取平均值。 时延抖动：数据流中，数据包之间时延的变化。在测试数据包大小相等的前 提下，若第i 1 个数据包的延时为d i - i ，第i 个数据包的延时为d i ，则延时抖动定 义为d 广d i 1 的绝对值。 丢包率：某一段时间内网络传输及处理中丢失或出错数据包个数占传输包总 数的比例。 带宽：单位时间内物理通路理论上所能传送的最大比特数。 另外，网络性能描述中还包括可用带宽这一重要的指标，顾名思义，该指标 4 北京邮电大学硕士研究生学位论文 是用于描述当前网络环境中剩余的带宽量。具体定义如下： 假设传输通路p 由1 1 条链路构成，每条链路k ( i _ l ，2 ，n ) 的最大传输能 力为c i b p s 。对于传输通路p ，其最大传输能力定义为： 一沪e n d2m i n ( c , ，g ，e ) 式( 2 1 ) 假设负载流量在短时间t 内恒定不变，肛表示链络l i 在t 时间段内的利用 率，链路的可用带宽为a i - - c i ( 1 u 0 。在时间t 内，通路p 上的可用带宽定义如 下： 一细一耐= m i ( 4 ，4 9 - - 0 94 1 ) 虽然本论文着重研究可用带宽，但是网络性能指标中其它参数的具体概念也 需要掌握。 2 2 网络可用带宽测量算法 近年来，国内外进行了许多关于网络可用带宽测量算法的研究，并提出了相 关算法原理，归纳起来分为探测间隔模型( p r o b eg a pm o d e l ，简称p g m ) 和探测 速率模型( p r o b er a t em o d e l ，简称p r m ) 两种【2 1 。p g m 方法( 以分析测试序列 中包间隔的变化为基础，典型的算法包括s p r u c e t 到、i g i 3 】等；p r m 方法以调节 测试序列的数据速率为基础，典型的算法包括s l o p s ( s e l fl o a d i n gp e r i o d i c s t r e a m s ) 4 1 ，p a t h c h i r p t 5 】等。然而，这些经典算法都存在各自的缺点和不足：s p r u c e 算法测量结果不稳定；i g i 算法测量精度会随着网络负载突发性的下降而下降； s l o p s 算法收敛速度慢，测量时间较长；p a t h c h i r p 算法中测试包较大，离开瓶颈 链路后在后续链路中受到影响也较大，从而影响测量精确度。除了这些方法以外， 还可以通过模拟t c p 连接获得b t c ( b u l kt r a n s f e rc a p a c i t y ) 6 1 ，t r i o 算法就是其 中的一种，虽然该测量结果反映的只能是t c p 吞吐量而非可用带宽，但是两者 的变化趋势是一致的。 2 2 1 s p r u c e 算法原理 图2 - 1 测试包通过瓶颈带宽后的间隔变化 s p r u c e 是基于p g m 的，它假设紧张链路与瓶颈链路为同一条链路，通过在 5 北京邮电大学硕士研究生学位论文 接收端的测试包获得发送间隔和接收间隔的信息，并对这些信息进行处理，从而 统计估计出可用带宽。 发送端向接收端以间隔i n 发送数据包对，测试包符合p o s s i o n 分布，调整 包对间隔，使得前一个测试包离开路由器，之后一个测试包到达路由器这段 时间内队列非空。在接收端接收到测试包对，测得包对间隔为a 呲。从图2 1 可 以看出，呲是后一个测试包和在缸时间内进入队列中的负载流通过该瓶颈链 路所用的时间之和。所以，包对之间插入的负载流本身所用的时间则为o l n i n 。 假设瓶颈带宽c 是已知的，则由式( 2 3 ) 计算出可用带宽。 彳：c fl 一垒l 凸加 式( 2 3 ) 这是发送一个包对的情况，为了提高测量的准确度，发送端向接收端以 p o i s s o n 分布发送多个包对，包对间隔为i n ，而两相邻包对之间的间隔为t ，为 避免产生相邻包对间的影响，t 应该远大于i n 。这样，通过发送多个包对可以得 到多个可用带宽a 的值，通过重复测量，求统计平均值，从而得到一个较为准 确的可用带宽估计值。 s p r u c e 算法测量时间短，可调的经验参数较少，具有良好的测量性能；但是， 它以瓶颈链路与紧张链路是同一链路为前提条件，可操作性较差，且测量结果不 稳定。 2 2 2i g i 算法原理 i g i 算法的测试序列由k 个大小为l 的数据包构成，包间隔为g i 在传输过程 中，测试序列与网络负载统计复用，测试包的间隔发生变化。因此，目的端测试 包间隔与负载的平均速率有关，据此可估计出负载水平，进而计算出可用带宽。 皇2 p 2p ii 广 踟 趁兹茏b c 励爿竺! 卜弦狃霉翟至g o 驷 图2 - 2 负载与测试序列问的相互影响 图2 2 记录了k = 2 时，测试序列和负载通过瓶颈节点时，两者相互影响的结 果。p 1 和p 2 为两个测试包，g i 是测试包的发送间隔，g b 是单个包通过瓶颈链路所 用的时间，g o 是测试包的输出间隔，b c 表示g l 时间内负载的平均速率。如果式 ( 2 4 ) 成立，则队列在p 1 离开路由器至p 2 至l j 达路由器这段时间内非空。 毋+ 丝 易 g ， 式( 2 4 ) 6 北京邮电大学硕士研究生学位论文 式( 2 - 4 ) 中，b o 是瓶颈带宽的大小，l 是测试包的大小，q 为p 1 n 达路由器 时队列的大小。此时，输出间隔9 0 由两部分组成，r o p l 通过路由器的时间g b 和p 1 与p 2 之间的负载通过路由器的时间b c * g i b o g o2 9 口+ & g t 式( 2 5 ) 式( 2 5 ) 表明负载的平均速率b c 可以通过g l 、g o 和g a 来估计。 由于网络负载具有突发性，为了提高测量的准确程度，测试序列长度通常远 远大于2 ，r p k 2 。在整个测试过程中，发送端不断增大测试包的发送间隔g i ， 即调节测试序列的发送长度。当测试序列在收发两端长度相等时，达到所谓的拐 点。由于经过拐点后，测试序列的输出间隔独立于网络负载，即输出间隔不随发 送间隔的增大而变化。所以，拐点为最佳测量点，此时测试流与负载速率之和近 似为瓶颈带宽b o 。 达到拐点时，输出测试序列中，间隔增大的包对一定受到了负载的影响，必 然满足式( 2 - 4 ) ，从而可由式( 2 5 ) 求出g i 时间内的负载的平均速率。由于i g i 算法默认网络负载具有较强的突发性，故认定间隔不变或减小的测试包对没有受 到负载的影响，所以在计算负载流量时，忽略了上述两类包对。i g i 给出的网络 负载平均速率计算公式如下： j i i ， b o ) - ：( g ：- g 口) 也= 百专矿 酊+ 酊+ g i = li = ii m l 其中，矿、百和旷分别表示增加、减小和不变的包对间隔， 应于测试序列中间隔增大、减小和不变的包对个数。 式( 2 6 ) m 、n 和k 则对 最后，由公式a b w = b o b c 即可求出可用带宽。 i g i 算法收敛时间短，测量效率较高；但是，测量精度会随着网络负载突发 性的下降而下降。 2 2 3p a t h l o a d 算法原理 基于s l o p s 的测量工具p a t h l o a d 7 】在2 0 0 1 年提出，此工具用于测量通路的可 用带宽。所谓s l o p s ，即是发送一系列等长等速率的数据包。p a t h l o a d 采用u d p 包作为测量包，并要保持一个t c p 控制通道以传递一些控制信息。它的原理是： 源端先以一定的速率r 发送一列由k 个测试包组成的测试序列，在目的端根据接 收到的测试包观察整条通路的单向延迟状况，并绘出一条延迟曲线，若r 大于链 路可利用带宽b w ，测试包就会造成链路的短时拥塞，则目的端的延迟曲线会反 7 北京邮电人学硕十研究生学位论文 映出明显上升的趋势。目的端将此信息反馈至源端，源端即可根据一定的策略调 整发包的速率r ，重复此测量过程，直至通路中没有发生拥塞时，目的端的延迟 曲线会比较平稳，没有明显的波动趋势。此时既可认为r 近似等于通路可用带宽， 那么也就可以推断出可用带宽b w 值。具体测量过程如下： 在发送端以速率r 发送一组数据包，设相邻数据包的间隔为，则r = l a 。 根据接收端数据包的间隔变化趋势来判断发送速率r 是大于或是小于通路可用 带宽a ，从而对发送速率r 进行调整，来逼近a 。p a t h l o a d 的参数示意图如图 2 3 所示： g 怂 图2 - 3p a t h l o a d 参数示意图 g 黧x 间隔变化趋势可由p c t 和p d t 两个参数来判断，p e t 和p d t 的定义如式( 2 7 ) 和式( 2 - 8 ) ： e l ( d d 扣1 ) = 丝t 丁一 式( 2 7 ) c ， d r d 1 荟i l j ) 一上) 一1 i j ( 2 8 ) i=2彳r(7r) 其中，r - i ，k 为一条流所包含的包的个数，_ r 0 p c t i ，i 0 4 时，认为间隔为递增趋势。 再通过间隔趋势来相应调整第n 条流的发送速率r ( n ) ，一般取r 咖_ 0 ， r r 眦- a 。 1 ) 如果间隔呈递增趋势，说1 日f j r ( n ) a ，则r m l = r ( n ) ，并令r ( n + i ) = ( r m a x + r m l ) 2 ； 北京邮电大学硕士研究生学位论文 2 ) 如果间隔保持不变，说明r ( n ) s a ，则胆r ( n ) ，并令r ( n + 1 ) = ( r 。嗽 + r 衄) 2 。 但是，在整个流中，根据间隔变化趋势来决定r 与a 的关系并不严格，因为 可用带宽a 可能在r 附近发生变化，使得间隔无明确的变化趋势，此时则说明速 率r 处于所谓的灰色区域( g r e y - r e g i o n ) ，可通过下列方法来调整速率： 设g r e y - r e g i o n 范围为 g 咖，g 皿1 】， 1 )如果g 一 r ( n ) r i 椒，令g 眦x - r ( n ) ，并令r ( n + 1 ) = ( r 一+ g 一) 2 ； 2 ) 如果r 衄 r ( n ) g 咖，令g m m _ - r ( n ) ，并令r ( n + 1 ) = ( r l 咖+ g 帅) 2 。 直到条件r i 嘲- r 衄如，r 一- g 蚴 ) 威g 咖- r 衄甄( 与) c 由测量结果的精度 要求所决定) 中任意一个成立，则得到最终的测量结果，并输出a 的范围r i 呶和 r m i 。 p a t h l o a d 算法具有良好的测量性能；但是，收敛速度慢，测量时间较长。 2 2 4 p a t h c h i r p 算法原理 p a t h c h i r p 是基于s e l f - i n d u c e dc o n g e s t i o n 的。若发送速率大于可用带宽，则 测试包处于排队状态，从而增加传输时延；反之，则没有排队时延。所以，可用 带宽可以用测试速率代替，由拥塞状况来估计。p a t h c h i r p 的测试包间隔采用指 数分布( 如图2 - 4 ) ，获得的时延信息相关性很强，从而能够使用较少的测试包 较快的测量出可用带宽。 吵宁慨 l2n - 4n - 3n 2 矗ln l 。且m 口 口口口 而了歹亓广1 订t i m e 图2 4 包间隔为指数分布的c h i r p 测试包 p a t h c h i r p 发送1 1 1 个测试包，计算出每个测试包的相对时延，从而估计出可 用带宽，具体算法步骤如下： 1 ) 找出第一个满足q i ( m ) i 且j 剑，则e x c u r s i o n e 【i , j l 】，f o r ( s = it o j - 1 ) e s = 凡； b ) 若j = n + l ，则e x c u r s i o n i , n l 】，f o r ( s - - - it on 1 ) e s = r i ，l - - - i ： c ) 其他情况：若q i ( m ) l 满足 ，、，、m a x l _ 出j g ( 尼) 一g ( ，) g - ，) 一g ( 脉型严 式( 2 9 ) 则e j = r i 。 4 ) 求出各测试包的e k ( 叫，代入公式d m ) _ ：磁a k e 7 2 a 。，最后求出某一 时间段内的统计平均值。计算流程如下： b e t k b 【t i ( 川，t n ( m ) 】 b t t ，t 】 要选择的参数：包的大小p ，指数分布的参数( 包间隔分布) t 、减小因子f 、 忙碌区间( b u s y p e r i o d ) l 、测量d ( m ) 的时间间隔百。 p a t h c h i r p 算法具有良好的测量性能，且不需要向发送端返回信息，从而避 免了返回的数据包对链路造成干扰；但是，测试包较大时，离开瓶颈链路后在后 续链路中受到影响也较大，从而影响测量精确度。 2 2 5t r e n o 算法原理 该方法属于端到端的测量方法，从层次上看属于传输层。其基本思想是建立 一个t c p 会话连接，通过该会话连接获得一些参数，再利用这些参数求出通路 的可用带宽。该连接必须和已有的负载流量1 0 0 地占有链路的全部带宽，同时 在测量时还要求采用类似于t c p 连接的拥塞控制算法，而且为了能够达到t c p 拥塞控制过程中的均衡速率( 均衡速率指的是拥塞避免过程中的速率) ，t c p 的会 话时间必须达到1 0 秒以上( 稳定过程的建立需要一定的时间) ，这样测量获得的参 数才能真实地反映出可用带宽的大小。但在实际应用中，因为基于这种方法的测 量是与t c p 层的协议密切相关的，并且应用了t c p 拥塞控制算法，所以测量结 果反映出的只能是t c p 吞吐量而非可用带宽。 t r e n o 实际上就是t c p 的一个用于测量的简单的实现版本，它的提出是为了 解决不同t c p 版本问的实现差异而产生的测量中的兼容性问题。它在一定程度 上反映了可用带宽的变化趋势，但不能直接作为可用带宽测量值。 l o 北京邮电大学硕士研究生学位论文 第三章网络模拟软件n s 概述 n s 作为一个事件驱动的网络仿真平刽引，是美国南加州大学，施乐p a r c 实验室和加州大学伯克利共同合作的一个项目。它是源代码开放的，目前还在不 断的充实、