（模式识别与智能系统专业论文）端到端的有效带宽的测量方法.pdf

大连理工大学硕士学位论文 摘要 随着i n t e m e t 技术的高速发展，人们对其服务质量( q o s ) 、可靠性的要求也越来越高， 因而在网络运行过程中，通过网络测量发现网络异常，进行故障诊断变得尤为重要。而 有效带宽的测量是网络测量中一个重要环节，因此，端到端的有效带宽的测量成为网络 理论和应用研究的重要方面。根据端到端的有效带宽测量的各种理论、方法及其工作原 理，已经有很多测试软件工具被开发并应用于实际。但是由于测量方法的建模的简化或 者测量方法的片面及测量硬件设施的局限，这些测量软件工具在实际的测量中存在测试 过程复杂、测试精度不够，应用范围小等缺点。 本文在查阅大量国内外文献的基础上，介绍了有效带宽测量方法研究的发展现状及 存在问题，在此基础上介绍了带宽测量的相关概念及仿真工具n s 2 。以数据包对为代表 的测量方法作为种经典的有效带宽的测量方法，能够比较准确的测量网络的有效带 宽，但是，很多的测量方法中存在测量包的排队失败、探测列丢失、多重路由选择和背 景流量干扰等问题，由于这些闯题的存在，影响了很多测量方法的实用性。针对包对算 法的一些不足，提出了改进的数据包对测量方法和指数间隔的数据包列测量方法。最后 利用l i u n x 环境下的n s 2 仿真平台，对提出的两种测量方法进行了深入系统的仿真研究。 仿真结果表明，本文提出的方法在一定程度上改进了现有测量方法的不足，减小了对网 络背景流的影响，并且能在较短的时间得到更准确的有效带宽的值。 关键词：有效带宽；改进包对方法；指数间隔数据包方法 大连理工人学硕士学位论文 m e a s u r e m e n to fe n d t o e n da v a i l a b l eb a n d w i d t h a b s t r a c t w i t l lt h er a p i dd e v e l o p m e n to fi n t e r a c t t h ed e m a n d so fq u a l i t yo fs e r v i c ea n dr e l i a b i l i t y b e c o m es t r i c t e r , s ow h e nt h ei pn e t w o r ki sr u n n i n g i ti si m p o r t a n tt of i n dn e t w o r ka b n o r m i t y a n dd i a g n o s en e t w o r ke r r o r a v a i l a b l eb a n d w i d t hm e a s u r e m e n ti so n ei m p o r t a n tp a r to f n e t w o r km e a s u r e m e n t s ot h em e a s u r e m e n to fe n d t o e n da v a i l a b l eb a n d w i d t hi nt h en e t w o r k h a sd r a w ni n t e r e s to fr e s e a r c h e r s i na d d i t i o nt ot h eg r e a te f f e c to nt h ea p p l i c a t i o no fn e t w o r k a u d i oa n dv i d e oc u mn e t w o r ko p t i m i z a t i o n ，i td r i v e st h ed e v e l o p m e n to fi n t e l l i g e n ta g e n ti n t h ec o m p u t i n g 蛳d t e c h n o l o g y o fn e x t g e n e r a t i o n b a s e do n av a r i e t yo ft h e o r i e s ， m e t h o d o l o g i e sa n dp r i n c i p l eo ft h ee n d t o e n d a v a i l a b l eb a n d w i d t h ，al a r g en u m b e ro f s o f t w a r e ，d u et oo v e rs i m p l i f i e dm o d e l ，t h ei n c o m p l e t e n e s so ft h em e a s u r e m e n tm e t h o d sa n d t h ec o n s t r a i n sf r o mt h eh a r d w a r eo ft h et e s t i n ge q u i p m e n t ，t h e s em e a s u r e m e n tt o o l sh a v et h e d i s a d v a n t a g e ss u c h 弱c o m p l e xt e s t i n gp m e e d u r e s u n s a t i s f y i n gt e s t i n gp r e c i s e n e s sa n d c o n s t r i c t e da p p l i c a t i o nr e g i o n se t c b a s e do ns m d # n gm a n yd a t u m t h i st h e s i sa n a l y s e st h ee x i s t e da v a i l a b l eb a n d w i d t h m e a s u r e m e n tm e t h o d sa n dp r e s e n t st h ed e f i n i t i o no fb a n d w i d t ha n da v a i l a b l eb a n d w i d t ha t f i r s t n l em e a s u r e m e n to fu s i n gd a t ap a c k e tp a i r s p r o b i n gt r a i ni sac l a s s i c a la v a i l a b l e b a n d w i d t hm e a s u r e m e n tm e t h o d i tc a nc o m p a r a t i v e l y e x a c t l ym e a s u r e s t h ea v a i l a b l e b a n d w i d t ho ft h en e t w o r k ，w h e r e a se x p e r i m e n ti n d i c a t e s ，d u et ot h ee x i t i n go fq u e u ef a i l u r e ， p r o b i n gt r a i nd r o p ，m u l t i l ：l l er o u t e rs e l e c t i o na n dc r o s st r a f f i c ，m a n ym e a s u r e m e n tm e t h o d s l o s ec u r r e n c y b a s e do nt h e s e ，w ea n a l y s e st h ed i s a d v a n t a g e so ft h ep a c k e tp a i r sm e t h o d ， p r e s e n ti m p r o v e dp a c k e tp a i r sm e t h o da n de x p o n e n ts p a c i n gp r o b i n gt r a i nm e t h o d f i n a l l yt h e p e r f o r m a n c e so fd i f f e r e n ta l g o r i t h ma r ev e r i f i e da n dc o m p a r e di nt h en s 2p l a t f o r mw h i c h r u n su n d e rl i n u xs y s t e m ，1 1 l es i m u l a t i o nr e s u l t ss h o wt h a tt h em e a s u r e m e n tm e t h o d si m p r o v e t h et r a n s i e n tp e r f o r m a n c e ，d e c r e a s et h ed i s t u r b a n c eo ft h ec r o s st r a f f i c ，a n dc a no b t a i nm o r e e x a c tv a l u eo f a v a i l a b l eb a n d w i d t hi ns h o r t e ri n t e r v a l k e yw o r d s ：a v a i l a b l eb a n d w i d t h ；i m p r o v e dd a t ap a c k e tm e t h o d ；e x p o n e n ts p a c e d d a t ap a c k e tm e t h o d 独创性说明 作者郑重声明：本硕士学位论文是我个人在导师指导下进行的研究工 作及取得研究成果。尽我所知，除了文中特别加以标注和致谢的地方外， 论文中不包含其他人已经发表或撰写的研究成果，也不包含为获得大连理 工大学或者其他单位的学位或证书所使用过的材料。与我一同工作的同志 对本研究所做的贡献均已在论文中做了明确的说明并表示了谢意。 作者签名：趟 日期：! ! ! ：! ! ：2 大连理工大学硕士研究生学位论文 大连理工大学学位论文版权使用授权书 本学位论文作者及指导教师完全了解“大连理工大学硕士、博士学位论文版权使用 规定”，同意大连理工大学保留并向国家有关部门或机构送交学位论文的复印件和电子 版，允许论文被查阅和借阅。本人授权大连理工大学可以将本学位论文的全部或部分内 容编入有关数据库进行检索，也可采用影印、缩印或扫描等复制手段保存和汇编学位论 文。 作者签名 导师签名 秘 之! 1 6 年2 月上旦_ 日 大连理工大学硕士学位论文 引言 随着网络技术的迅速发展和各种新型业务的涌现，大量的视频点播、流媒体、网络 游戏等实时业务以及p 2 p 类型业务广泛应用于宽带网络，这些新业务对网络传输能力和 服务质量提出了更高的要求。网络运营商需要了解网络带宽情况来指导网络运维、网络 规划、瓶颈故障检测、拥塞控制、接纳控制以及异构无线网络的切换、性能优化等；个 人用户则希望通过简单的有效带宽测量工具了解当前网络的带宽状况，考察s l a 的执 行状况。有效带宽( a v a i l a b l eb a n d w i d t h ) 在整个报文网络历史中都起着核心的作用，在传 输协议中有效带宽的充分利用一直是主要的问题。 在数字网络中带宽描述的是网络链路或者网络路径数据的传输速率。数字通信中带 宽的概念，特别是数据包网络中，是指在单位时间内网络链路或者网络路径能够传输的 数据的数量。对于数据密集型的应用，比如文件传输或者多媒体流，能够应用的有效带 宽直接影响着应用的质量；而对于交互式的应用，它对于等待时间比对吞吐量更加敏感。 考虑到有效带宽对各种网络应用的重要作用，在端到端的路径中对有效带宽的了解能够 增强基于速率流的利用，端到端的认证控制，服务选择，网络覆盖技术中的最优路径选 择，拥塞控制和服务层的协议验证等技术的应用。然而由于不同的技术、保密事件、不 足的测量辨析度和准确性水平等的影响，从路由器获得有用的有效带宽的估计经常是不 可能的。因此，通过有源的或者无源的测量方案从网络的端点处推断需要的信息变的十 分必要。理想的探测方案应该能够在相对短的时间内提供路径的准确的有效带宽的估 计，特别的，能在几个往返时f 日q ( r t t ) 内并且对网络施加较轻的负载。 精确的网络端到端带宽测量在实际网络应用中有着非常重要的实际意义首先，当 前骨干网基本上采用大容量的d w d mi s d h 传输系统，骨干链路和接入链路的带宽成 倍的增长，网络应用性能依然是人们关注的主要问题。影响网络应用性能的原因包括终 端系统、网络应用与协议特性、网络容量、资源调度策略等，其中链路宽度是最重要的 网络资源，是决定传输路径性能的主要因素之一。网络路径与整体性能分析、容量规划 以及链路有效带宽测量必须依靠链路带宽的精确测量。其次，许多网络协议和应用需要 知道有效带宽以判断协议和应用运行的效率。许多对服务质量较为敏感的业务需要在进 行业务传输之前先了解网络路径的瓶颈带宽和有效带宽，再选择不同的服务质量和有效 带宽的路由，如客户程序在了解了各个不同服务器所在的路径的瓶颈的有效带宽之后可 以动态选择瓶颈的有效带宽最大的那台计算机作为访问服务器。最后，有效带宽是网络 的重要技术指标。许多网络资源监控系统根据网络带宽进行全网络范围的网络规划，减 少网络瓶颈，分析网络性能。网络供应商( i s p ) g 以根据检测到的网络有效带宽的参数进 端到端的有效带宽的测量方法 行有效的s l a 确认和验证，协助进行业务规划和运行维护，实现负载均衡和路由等性 能保障。许多网络协议和应用需要知道瓶颈带宽以判断协议和应用的效率。然而想要准 确的测量是很困难的，网络状况千变万化，例如从源端到目的端的跳数的多少，空载和 饱和的链路，链接存在多少通道的情况，各种无线和有线技术的，采用的排队原则以及 不同的路由算法等等，而且有些测量工具需要严格的时间同步或源宿端协同工作，所有 这些都直接影响着最终测量精度。为了能更好的洞察网络有效带宽的特性，显著改善网 络接入能力和服务质量等级，必须有高效的测量技术支持。们需要让自己的算法适用不 同的网络环境，也需要对网络施加尽可能小的负载，以避免测量造成的通信量对应数据 通信的影响。本文的工作重点来说，主要集中于网络有效带宽的测量。 大连理工大学硕士学位论文 1 有效带宽测量的目的意义及发展现状 随着计算机技术和网络通信技术的不断发展，人们越来越多的依靠计算机网络完成 信息交换工作，并期望计算机网络所提供的服务具有多样化的内容、形式和可调整性， 以满足不同应用的要求。在目前的因特网中，用户通过从网络服务供应商p ) 预定服务 来访问因特网。然而，狭窄的访问链路变成网络的瓶颈阻止用户良好的应用网络。对于 家庭预定者，后台的h t r p 下载传输能够导致烦人的交互的远程登录应用的延迟。对于 小型的办公室、家庭办公室( s o h o ) 、中小型商业( s m b ) 和企业预定商，后台的f 1 哼部 分可能阻碍要求严格的传输，比如v o i p 和企业资源计划传输。这种情况下需要在网络 的链路之间配置带宽管理器来给交互式的或者延迟敏感的应用在链路中分配带宽。在另 一方面，一个网络供应商( i s p ) 和它的预定用户共享主干资源。有些预定者有可能超预定 访问链路因此导致影响其他用户的运行，因次，i s p 需要在路由器和转换器之间安装带 宽管理器来公平的在预定者之间分配资源。 1 1 网络测量技术 网络测量技术源于上世纪7 0 年代，并在上世纪末期随着计算机网络的发展得到迅 猛发展。在网络测量方法、测量工具和网络中流量模型构建等各个方面都在不断的探索 并取得了一定的成果。由于国内计算机网络技术起步较晚，网络测量技术的研究是在上 世纪9 0 年代末期随i n t e r a c t 网络在中国的迅猛发展而逐步发展起来。由于近年来的发展， 我国己成为世界上i n t e r a c t 用户数量第二的国家【1 1 ，网络流量迅速增大，迫切要求网络 服务提供商( i s p ) 在网络规划和设计时对现有网络进行测量。网络流量测量，网络流行为 的研究以及网络设备的性能分析，都可以为下一步网络的发展提供依据。从研究手段和 方法上看，网络数据的采集、分析是网络测量技术的基础研究方法。网络流量、网络拓 扑和网络行为的建模分析研究是在此基础上的升华。从网络测量技术的数学分析看，网 络测量技术就是要将网络的拓扑结构、带宽、性能等参数映射成一个随时空变化的函数。 但是，由于网络的分布化，不协作性和异质性，再加上网络流量的复杂特性，使得网络 测量技术研究工作极具挑战性1 2 】根据测量方法所获得的节点支持以及数据采集点的位 置，可以将测量方法划分为基于路由器测量，基于路由器协作测量，端到端测量三种【3 1 。 基于路由器的测量主要由路由器中的管理软件来完成测量，一般用于来监测网络内部网 络的拓扑、流量、时延、丢包率等。基于路由器协作测量是在边缘主机上执行测量，但 需要路由器的配合，在路由器增加新的功能或协议。基于路由器测量和基于路由器协作 测量一般都需要i s p 的支持，同时需要各个i s p 之间的协作。端到端测量的目标是在只 端到端的有效带宽的测量方法 有边缘主机参与下，无需路由器的配合，在现有的网络协议和网络资源配合的情况下获 取网络性能统计结果，并且尽可能减小对网络造成的负荷。由于端到端测量不需要i s p 支持，因此成为近期网络带宽测量方法研究的重点领域。 1 ，2 有效带宽测量的目的及意义 随着i n t e r n e t 持续高速的发展，特别是电信市场服务水平协议s l a 的实施，人们开 始对其服务质量( q o s ) 【4 】、可靠性和效率进行重新思考并提出多种解决方案，以全面提高 p 网络性能。有效带宽是网络的重要资源，对其准确的估计与测量是流量工程必须解决 的问题。同时，有效带宽也是评价网络连接性能的重要参数，它和延时、包丢失等其他 度量一样直接影响着客户端的性能。特别是随着区分服务( d i f f s e r v ) 的提出，网络服务提 供商需要对带宽资源的占用情况做出较为准确的估计并实施调整，同时在规划网络扩容 时找到网络瓶颈；而用户也关心当前提供的有效带宽是否与服务水平协议规定的一致。 可以说，有效带宽测量为网络的性能测评与指导流量工程中路径状况的调整提供直接的 定量依据，并为最终探寻高效的服务质量解决方案提供了有力的支持【5 1 。 ( 1 ) 有效带宽测量是了解网络健康状态、实现网络资源控制的关键技术。 近年来，以国际电信联盟( i t u ) 提出的通用电信服务评估标准为基础，s l a 作为服 务提供商与用户签署的法律文件保证服务质量，在业界得到广泛的关注。随着关键的商 业活动对服务应用的依赖程度的不断增加，s l a 已逐渐成为服务系统中不可分割的一部 分，s l a 的实施无疑对传统的服务理念和管理方式提出了新的挑战。以口业务为核心 的新一代的电信网管理变得更加复杂，更加强调应用层服务的可用性和网络性能的确定 性。有效带宽作为i s p 与用户共同关心的网络资源，直接反映了网络的性能状况和业务 保证能力。有效带宽测量成为了解连接性能状况，发现网络瓶颈，网络资源分配和负载 均衡的重要手段【6 1 。有效带宽测量技术成为实现网络运行状态监控，网络问题检测等网 络管理功能和拥塞控制等网络控制机制的关键技术。 ( 2 ) 高速网络中有效带宽测量技术本身极具研究价值。 在高速带宽的网络环境中，网络连接容量不再是问题，而系统的服务质量，特别是 关键业务的性能成为衡量服务水平的重要的指标，如何采用有效的有效带宽算法，充分 利用有效带宽，保证较高水平的用户端数据吞吐量，做到按需求分配带宽，这些问题都 极具研究价值【7 8 】。特别是在高速网络环境下，一些传统的有效带宽测量算法表现出很 大的局限性，如何同时改进算法的效率和测量结果的精度都是很有挑战性的问题。因此， 有效带宽的准确测量对于提高网络应用程序的性能和网络本身的利用率都具有十分重 要的意义。 r 4 一 大连理工大学硕士学位论文 1 3 有效带宽测量方法的研究现状 根据测量工具是否向网络发送测量分组可以分为主动测量工具和被动测量工具。 1 3 1 主动测量方法 主动测量：网络的主动测量工具通过向网络发送测量分组，并根据测量分组所携带 的信息来推测网络的情况。测量工具是在测试主机上测量，不需要路由器增加其他的网 络协议来配合，属于端到端的测量工具。主动测量具有主动性强、灵活、方便等优点， 测量工具能以更直接的方式来分析网络。 根据发送测量分组的类型，主动测量方法还可以划分为组播，单播两种方式。根据 测量分组结构的差异，常用的测量分组可分为：单测量分组，等长测量分组和非等长测 量分组或测量分组列等。 端到端的有效带宽的测量工具中，绝大多数都是主动测量工具，其采用的测量方法 一般是向网络发送测量分组链或测量分组对，然后测量分组在网络运行后携带的信息参 数，用这些测量值参与带宽和有效带宽的计算，信息参数一般有下面几种： ( 1 ) 测量分组在网络中的运行时间础盯( r o u n d - t r i p t i m e ) 值； ( 2 ) 测量分组时间间隔在发送端和接收端的变化值； ( 3 ) 测量分组发送速率在发送端和接收端的变化值。 主动测量方法的不足：由于需要向网络发送测量分组，会增加网络的负担，对网络 性能产生影响。大量的测量流量可能会在瓶颈处产生拥塞，从而使测量结果偏离实际值， 产生系统误差i 1 3 2 被动测量方法 被动测量工具并不向网络发送任何测量分组，而是监听网络中的分组所携带的状态 信息参数来推测网络的情况，其测量机制尽量避免干涉网络的正常运行，采用监听方法， 例如在h u b 上，或者用探测针的形式读取网络中流过的流量，所以不会对网络造成影响。 被动测量工具从收到的所有分组中挑选出对测量有帮助的分组，读取他们的状态信息参 数用于计算。被动测量工具由于不向网络发送测量分组，不注入新的流量增加网络流量 成为它最主要的优点。但是测量采集所需要的数据不能达到实时性，即收敛性差，不能 满足迅速了解网络现状的要求。同时，由于被动测量一般只能用于单点监测，难以进行 端到端的行为分析，如路由分析等。测量工具捕获得到的分组信息中，难以甚至不可能 获得我们想要的某些信息。这些导致测量的范围较小，难以把握整个网络的状况，因此 难以实现有效的端到端的有效带宽的测量。 端到端的有效带宽的测量方法 1 3 3 有效带宽的测量方法的研究现状 c a r t e r 和c r o v e l l a 提出了一种测量有效带宽的方法叫c - p r o b e t l 2 】，它是测量有效带 宽的先驱。它通过传输较短的i c m p 数据包列来估计有效带宽。有效带宽测量值为探测 通信被最后一个i c m p 到达回复和第一个i c m p 到达回复分成的间隔。p i p e c h a r l l 0 】也用 了相同的方法，然而，d o v r o l i s u 】证明这种方法测量的并不是有效带宽，这种长数据包 列的分散情况的是吞吐量的一个衡量标准，目前称为a d r ( a s y m p t o t i cd i s p e r s i o nr a t e ) 。 另一个测量方法是d e l p h i 1 4 1 ，d e l p h i 的主要思想是假设在探测包到达链路时链路不 是空的，就能根据接收端的两个探测包的间隔估计链路通信量。d e l p h i 假设路径能够由 单独的队列来模拟。这个模型有很大的局限性，首先不能用于窄链路和紧链路不同的路 径中，其次它认为任何的队列延迟都是路径中的紧链路上的队列延迟。 s p r u c e 是紧链路和窄链路是同一个链路的假设下成立的一种方法【1 5 l ，在第一个测量 数据包离开瓶颈队列之前发送第二个数据来采样瓶颈链路数据包的到达速率，然后计算 接收端两个探测包在探测期间到达的字节数，最后用链路容量减去瓶颈链路到达速率来 计算有效带宽。基本算法为：利用两个连续的探测包到达在发送端的间隔和接收端的间 隔之间的关系来计算有效带宽，设c 为路径容量，探测包以。的间隔发送，到达的时 间间隔为。假设只有一个瓶颈链路并且第一个数据包和第二个数据包之间的时间间 隔期间队列不能为空，则。，就是瓶颈链路传输第二个包和在。时间内到达的背景流量 的和，那么传输背景流量的时间为。一m ，背景流量的速率为： 挚c ( 1 1 ) 凸h 则有效带宽为： 一 一警) z ， 上述几种方法都是在瓶颈链路已知的假设下建立模型，但是在实际的网络中，瓶颈 链路却是未知的，为了解决隐藏瓶颈问题提出了t o p p ( t r a i no fp a c k e t sp a i r s ) 方法。 m e l a n d e r m 1 提出了t o p p 的测量方法，它是包对测量方法的一种延伸。t o p p 方法分为 两个阶段，首先是主动测量阶段，在这个阶段中向网络发送成对的测量数据包，接下来 是分析阶段，这时根据探测包的接受时间估计带宽。 t o p p 测量阶段需要尽量避免给网络增加的负载，这样在探测路径中存在的通信量 受到较小的影响，这样就能降低由探测数据包引起的暂时的重负载或者造成网络拥塞， 大连理工大学硕士学位论文 从而使测量时间滞后的危险减小。为了实现这个目标，测量数据包由下列的方式产生： 开始以o r a i n 速率将n 个间隔时间相同的包对发送到目的主机，在这组包对被发送之后， 数据包的速率o 晌会增加d 得到新的发送速率o ，并且以这个速率发送另一组测量数据 包。然后o 再次增加( 以相同的数量d ) 并且以变化后的速率发送另一组的测量数据包， r i n b 1 l 血 这个过程持续到速率增加到标注在测量阶段最后的d “为止，这样就有= l 三二三一l 。l 。 j 个速率变化阶次。两个测量数据包对的时间间隔为a t p ，a t p 是根据使两个探测包在同 一个节点排队的可能性尽量小来选择的。这样的时间间隔使探测包有很好的网络友好 性，使路径中的节点不会遇到长的突发的测量数据包。在接收端按照接收时间给数据包 加上时间戳。一旦所有的包都被接收到( 或者处理丢失包超时) ，这些时间戳送往测量主 机。为了仅仅得到一个方向的估计并且避免路径不对称的问题，在测量过程中所有的测 量包都是单向的。 分析阶段是根据瓶颈间隔作用原理，也就是当两个包的间隔a s 在链路上传输的服 务时间q a s ，那么包离开链路时间隔变为a r = q 。利用包的大小b 和间隔r ，通 过链路的经验带宽可以估计为： 于= 去 ( 1 3 ) 如果q a s ，那么a r = a s ，表示链路能够以包到达的速率来传输。测量阶段的 输出是一系列的接收的测量包的时间戳。对每组数据包对都有月个时间戳，计算这n 个 值的平均值得到一个值。因此相应于每个提供的速率o 都会有一个a r 值与之对应。现, 在利用r 和包长b 和上述估计公式( 1 3 ) ，能够计算每个珥提供速率的带宽估计尹。建 立这样的网络模型：在路径中按比例分享链路，可以得到按下面的比率分享有效带宽o ，n 跃距i 是接收端，当发送端提供负载是o ，o o = o ，并且跃距i 的背景流量为m ，那么 q = 嚣 ( 1 4 ) 端到端的有效带宽的测量方法 对每个i = l 2 一n l ，带宽估计厂和提供带宽口之间的关系可f h ( 1 4 ) 给出。提供速率的 测量数据包只能使有效带宽s d 1 的跃距产生拥塞。既然提供速率列ld l ，, o n ll 是增长的， lj 那么发生拥塞的跃距可以通过探测序列l 广1 ，pi 来得到。 lj t o p p 方法有很多的优点，能够估计隐藏瓶颈的有效带宽( 也就是瓶颈有效带宽和瓶 颈链路不是同一个链路) ，能计算链路瓶颈带宽和有效带宽并且在一定的假设下还能估 计多跃距的带宽和有效带宽。然而，t o p p 方法在执行时计算过于密集，这样就延长了 估计的时间。最近，j a i n 和d o v r o l i s 又提出了p a t h l o a d 测量工具【l ”。p a t h l o a d 包含在源 端运行的程序和在接收端运行的程序。测量包流用的是u d p 协议，而两个端点之间用 的是t c p 协议来控制测量的。 源端在每个数据包之前加一个时间戳，因此接收端能够计算出测量包k 的相对单向 时间延迟d ，它和实际的单向时间延迟相比有一定的偏移量，这个偏移量是由于两个 主机端的时钟不同步引起的。由于计算中只对单向时间延迟之间的差值感兴趣，因此测 量单向时间延迟中存在着常量的偏移量不会对分析的结果造成影响。 一个测量列包含长度为工字节的k 个数据包，以恒定的速率震发送。在运行期间对 每个测量列的流速r 进行调节。数据包的间隔r 一般设为乙。，它一般是主机端能够实 现的最小的间隔。给定r 和r ，包长可以由l = r t 计算，然而，包长必须比路径的 m t u z p 小( 为了避免分片) ，比最小的长度严= 2 0 0 b 大。引入上唧的原因是限制第二 层包头对流速率的影响。如果r 0 4 则为增长趋势。 p a t h l o a d 并不是根据一个流来判断是否是r a ，而是发送一个包含个数据流的 列，从而连续采样次来决定是否r a 。这个列中的所有的数据流以相同的速率r 发 送。为了避免路径中出现等待处理的流的情况，每个数据流都要在前一个流确认之后再 发送，所以在流之间要有空闲间隔，它要比路径的肿大。一个列的持续时间 u = n ( v + a ) = n ( k t + a ) 给定y 和，则就决定了列的持续时间，它和p a t h l o a d 的测量等待时间相关。的默认值为1 2 个流，列速率r 的平均速率为 丽n k ly 5 r 矗为了把测量列的平均速率限制在，j 、于r 的1 0 ，最近的p a t h l o a d 矿 版本中设定的流内的空闲间隔为= m a x r t t ，9 v 。如果遇到太多的丢失( 1 0 ) 或者 是很多的流遇到一定量的丢失( 3 ) ，那么整个列被丢弃，并且下一个列的速率会减小。 一个速率为r ( n ) 的y , j n 结束后，p a t l d o a d 就会决定是r ( n ) 一，是r ( n ) - ，还是 r ( n ) o c a 。这种迭代确定下一个列速率r ( n + 1 ) 的算法和二分检查法很相似。但是除了 保存有效带宽的上下界r 一和r ”外，p a t h l o a d 算法中还保存灰度区域的范围，也就是 g 一和g “。当r ( n ) * a 时，这两个范围依据，如果g “ r “( 更新g “) 来更新。如果没有检测到灰度区域，r ( n + 1 ) 这样选 择： i fr ( n ) a ，r 一= r ( n ) i f 胄0 ) s a ，r “= r ( n )( 1 7 ) r ( n + 1 ) = ( r + r 劬) 2 如果检测到灰度区域，当r ( n ) = g “，r ( n + 1 ) 要在g “和r 一之间取值；当 r ( n 1 = g ，r ( n + 1 1 要在g 劬和r “之间取值。只要有效带宽的范围严格的包含在 r 劬，r l 内，二分检查法就能成功的找到有效带宽。p a t h l o a d 计算的截止条件有两个， 一个是当有效带宽的检测在一定的范围时，也就是r “一只“g o ；另外一个就是当 r 一g 一z 或者g ”一r s z 时，也就是两个有效带宽的边界都在相应的灰度区域 的边界范围z 内。p a t h l o a d 最后得到有效带宽的一个范围lr “，r i 。p a t h l o a d 是基于 迭代算法的，因此很难判断测量需要的时间。对一个路径默认的工具参数为a z l o o m b s 和a = l o o m s ，大约需要1 5 s 来完成最终的估计。只要有效带宽的绝对量增加或者是灰度 区域的范围增加，测量的等待时间都会增加，并且等待时间还依赖于终止参数国和z 。 s l o p s 测量方法是在p a t h l o a d 上运行的一种方法【1 8 】。t o p p 和s l o p s 都是基于当探 测包的速率大于路径的有效带宽时，连续的周期探测包队列延迟是增加的，但是这两种 方法又有不同之处。s l o p s 中的周期流包含长度为三的置个数据包，用恒定的速率r 发 送。设从发送端s n d 到接收端r c v 的路径包含日个链路。每个链路的容量是e ，链路 f 的有效带宽是4 ，那么利用率为u l = ( c j 一4 ) q ，在时间段f 内有q g f 个字节的背景 流量到达或离开链路i 。假设链路服从先到先服务的规则，并有足够的缓冲器保证不会 有数据包的丢失。忽略路径中的传播延迟和固定延迟，因为它们不会引起数据包之间延 迟的变化，路径的有效带宽彳由紧链路f 1 9 o o i h 决定，4 = 鹏42 乎：5 g ( 1 一嘶) 2 a 。 设发送端在任意时间以速率r 向接收端发送五个数据包的周期流，数据包的长度为工， 则数据包的传输时间为t = 叫。数据包k 从发送端到接收端的单向延迟d 为： ：兰f 軎4 - 譬1 ：兰f 吾4 - 钟1 ( - 8 ) i - i o fo f i = i o i 其中矿是链路i 数据包k ( 不包含七) 之前的队列的长度，钟= 计c 是数据包k 在链 路i 处的队列延迟。连续包列k 和k + 1 之间的单向延迟的误差为： 大连理工大学硕士学位论文 d t ；d “t 一：艺譬：羔耐 ( 1 9 ) i s lo fi - i 其中矿；矿“- q ：，耐；甜g 。能够证明如果r a ，那么k 个周期数据包流将会 以增长的单向延迟速率到达接收端；如果rs a ，包列流将会遇到相等的单向延迟。也 就是：如果r a ，那么a d 0 ，k = 1 ，；如果r 蔓a ，那么d = 0 ，k = l ，置。 基于上面的结论构造了如下测量端到端的有效带宽的迭代算法。设源端向接收端以速率 r ( n 1 发送周期流行，则 矿r ( n ) a ，r “= r ( n ) i fr ( n ) a ，r m = r ( n )( 1 1 0 ) 胄( 矩+ 1 ) = ( r 眦+ r m h ) 2 其中r “和r m 分别是周期流再之后的有效带宽的上界和下界，其初始值为 r “= 0 ，月“应该设置为足够高的值，一般设为8 a 3 。当r 一一月曲时，迭代 截止，c o 为用户设定的截至参数。如果有效带宽不随时间的变化而改变，前面提出的算 法将会变成一个包含一范围lr 曲，胄i 。 lj i g i ( i n i t i a lg a pi n c r e a s i n g ) 钡l j 量方法和p t r0 a c k c tt r a n s m i s s i o nr a t e ) 测量方法是根据 单跃距l s q 隔模型，它是一个三维图，分别为输出间隔值、队列大小q 和竞争通信吞 吐量毋，路由器用先进先出队列处理机制并且探测包的长度相等。一个队列周期是这 样定义的，在整个时间段内队列不是空的，也就是，两个连续的队列周期被一个队列为 空的时间段分开。根据队列周期的定义就可以把上述模型分为两个区域：不连续的队列 区域( d q r ) 和连续的队列区域( j q r ) 【1 9 1 。 i g i 和p t r 测量算法是从源端向目的端发送一系列的初始间隔不断增长的包对。监 测器比较源端和目的端的平均间隔的差，当两者之差等于零时终止。这个点是包列执行 的转换点，然后利用i g i 和p t r 的公式计算最后的测量。i g i 和p t r 是用瓶颈链路容量 减去竞争通信的吞吐量来计算有效带宽的。瓶颈链路的带宽可以用b p r o b c ，n e t t i m e r 或 者是p a t h r a t e 等工具来获得。瓶颈链路带宽的测量的误差会影响有效带宽估计的准确性， 但是上述提到的方法能够比较准确的测量瓶颈链路的容量，因此在i g i 和p t r 方法中忽 略了这个因素的影响。i g i 和p t r 算法不同之处是，i g i 是利用测量包列间隔值变化的 信息来估计路径中紧链路的有效带宽，而p t r 则是利用包列的平均速率来估计有效带 宽。 端到端的有效带宽的测量方法 i g i 和p t r 方法比p a t h l o a d 方法相比有更快的估计速度。在紧链路和瓶颈链路不是 同一个链路时或者紧链路中没有显著的竞争通信时，i g i 方法就失去了准确性。而p t r 不利用探测包列间隔变化，因而在紧链路上是否有背景流量对有效带宽的测量影响很 小。 1 4 本文的研究工作 在查阅了国内外大量的相关文献的基础上，本文认为，自从互联网私有化以后，呈 现出两大特点：无政府状态的联合和异构性。无政府状态的联合默许了不同的网络服务 提供商在竞争中只关注自己的网络的构建，使得网络服务供应商间的全局性能问题、网 络的发展预测与评估一度处于停顿状态【2 0 】。t p c i p 把不同性质的网络连接在一起，但 其本质并没有改变网络的异构性。这两个特点以及其庞大的规模所带来的复杂性，随着 客户的快速膨胀、对性能和服务质量的要求日益提高的期望，更雪上加霜的加剧了单纯 的增加容量、内容和服务的扩张模式与网络效率之间的矛盾。于是，人们开始从盲目的 竞争中回到理性的合作中来。网络测量作为网络性能优化和安全状态分析的利器才又一 次得到人们的重视。因此，本文认为，有效带宽的测量是优化网络服务性能的重要手段。 本文的具体研究内容如下： ( 1 ) 从网络测量技术和网络应用中提供服务质量的要去出发，给出网络测量技术的 介绍，分析测量有效带宽的必要性和重要性，介绍有效带宽的发展现状，概述本文的主 要工作。 ( 2 ) 给出有效带宽的定义，提出了本文有效带宽算法的设计要求，详细介绍了本文 应用的仿真工具n s 2 ，并给出了编写t c l 脚本的具体的流程。 ( 3 ) 在分析了已有的有效带宽的测量方法的基础上，提出了有效带宽的改进包对的 测量方法。 ( 4 ) 在改进包对算法的基础上，提出了有效带宽的指数间隔数据包测量方法。 ( 5 ) 对本文提出的端到端的有效带宽的测量方法做了总结和展望。 大连理工大学硕士学位论文 2 有效带宽的基本概念及仿真软件 2 1 带宽、瓶颈带宽与有效带宽 端到端的有效带宽测量的模型，如图2 1 所示，网络中存在测量数据包及背景流， 若采用的被动测量则不需要探测报文。网络对测量数据包及背景数据包采用相同的处理 策略；中间的网络拓扑结构，设备的服务策略及路径的负载等未知。 e n d t o e n d p a t h 图2 1 有效带宽测量模型 f i g 2 1a v a i l a b l eb a n d w i d t hm e a s u r cm o d e l 国际工程任务( i e t f ) i p p m 工作组迄今为止已完成了包括p 网络性能参数框架和连 接性，单向延时、单向丢失等一系列性能指标标准的制定，但对于带宽、有效带宽的定 义以及测量的标准化问题一直没有明确提及。端到端带宽测量指标通常沿用s t a n f o r d 大 学的k e v i nl a i 定义的两个基本度量参数捌：即瓶颈带宽和有效带宽。 端到端的有效带宽的测量方法 2 1 1 带宽与瓶颈带宽 一般理解的带宽是指连接到i n t e r a c t 时，网络提供的链路或路径的传输速率或吞吐 量，以 ：酬j 或女吖j 为单位。但在实际测量中，网络吞吐量和带宽差异很大，在第二层 链路中通常只能传输常字节( c b r ) ，它是分段的传输速率。分段的传输速率受到下属传 播介质的物理带宽和它的电子和光电发送器和接受器硬件的限制。由于第二层封装和组 帧的系统开销，口层传输的速率一般低于名义上的传输速率。m 层的容量依赖于p 包 的大小相对于第二层的系统开销【2 3 1 。端到端的路径是发送主机和接受主机之间一系列存 储转发节点和链路所构成的一条逻辑线路，用于在主机之间发送和接受数据。端到端的 路径的容量是口层发送端到接受端路径能够传输的最大速率。也就是，路径的容量确 定了用户期望从路径得到口层吞吐