（通信与信息系统专业论文）基于主动探测的可用带宽测量方法在无线环境中的应用测试分析.pdf

中文摘要 摘要：随着网络应用的逐渐多样化，以及对q o s 的要求逐渐增加，可用带宽测量 特别是端到端主动可用带宽测量逐渐成为了一个研究热点。同时随着无线网络的 广泛应用，现有的针对有线网络的测量工具和方法是否依旧适用于无线也成为了 一个热点话题，本文针对现有的基于主动探测的可用带宽测量方法在无线环境下 的应用这一问题进行了较为详细的理论研究，并通过详尽的实际测试证明了理论 分析的正确性。 端到端的主动带宽测量是一种通过向网络发送测量分组，并根据测量分组所 携带的信息( 延迟、速率) 来推测网络的情况的测试方法。现有的主动带宽测量 方法大都基于固定速率背景流假设下的包间隔曲线，或其变形形式速率响应曲线， 如果我们能够掌握其在无线链路中的演变形式就可以得到这些可用带宽测量方法 在无线链路中的测量特性。以此为出发点，本文依据i e e e 8 0 2 1 1 d c f 机制下的时 间传输特性，建立了一种i e e e 8 0 2 1 l 无线局域网环境中的速率响应曲线的理论模 型，并由此推导出了在无线环境下使用端到端主动可用带宽测量方法测量的理论 结果。经过对这一理论模型的m a t l a b 分析可知，在单跳无线网络中，可用带宽的 测值将和探测包的大小以及网络中的接入点个数有关，随着探测包的逐渐增大， 无线网络的可用带宽测值将逐渐增大，此外，接入点的增加将直接导致碰撞的增 加从而使得传送过程中由于碰撞导致的时间占用增加，最终使得可用带宽减少。 最后本文按照理论模型的特性依据窄链路是否处于无线链路将使用无线接入的网 络分为两类，分别以探测包大小、背景流大小以及无线接入点个数为参量进行了 详细的实际测量，并将测量结果进行了一定的分析处理并和理论值相比较，这些 测试表明我们提出的理论模型以及其分析结果能够很好的解释实际测试中获得的 结果。图3 8 幅，表2 个，参考文献2 8 篇。 关键词：可用带宽测量；主动测量；8 0 2 1 1 ；无线局域网；d c f ；速率响应曲线， 瓶颈带宽；包间隔 分类号：t p 3 9 3 e 塞窑逼太堂亟堂焦途塞垦sib g 至 a bs t r a c t a b s t r a c t ：a st h eg r o w i n gv a r i e t yo ft h en e t w o r ka p p l i c a t i o n ，t o g e t h e rw i t ht h e r e q u e s t f o rq o s ，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 th a v ea t t r a c t e dm o r ea n dm o r e a t t e n t i o n ，g i v e nt h es i t u a t i o nt h a tt h ew i r e l e s sa p p l i c a t i o nh a sb e e nw e l ld e v e l o p e da n d w i d e l yu s e d i nn o w a d a y s ，w eh a v et oc o n s i d e rt h a tw h e t h e rt h o s eo l dn e t w o r k m e a s u r e m e n tm e t h o d sa n dt e c h n o l o g i e sb a s e do nw i r e dn e t w o r kc a ns t i l lb ea d o p t e di n w i r e l e s sn e t w o r k i nt h i sp a p e r , t h ea u t h o rt o o kad e e pa n a l y s i so nt h ea p p l i c a t i o no ft h e p r o b i n g b a s e da 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 ni e e e 8 0 2 11w i r e l e s se n v i r o n m e n t ， w i t ht h o r o u g he x p e r i m e n t s ，w h o s er e s u l tt e s t i f i e st h ep r o p o s e dt h e o r e t i cm o d e lw e l l ；h e m a n a g e d t os h o wt h a tt h ea n a l y s i sr e s u l ta p p r o p r i a t e l ye x p l a i n e dt h en e wc h a r a c t e r i s t i c o ft h o s em e a s u r e m e n tm e t h o d su n d e rw i r e l e s sc o n d i t i o n m o s to ft h ec u r r e n ta c t i v ee n d t o e n da 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 sb a s e do nt h e i n t e r - p a c k e tg a pr e s p o n s ec u r v eo ri t sv a r i a n t - t h er a t er e s p o n s ec u r v e ，s oi t i s q u i t e e s s e n t i a lt ot a k et h ei n f l u e n c eo ft h ew i r e l e s se n v i r o n m e n to nt h i sg a p ( r a t e ) r e s p o n s e c u r v ei n t oc o n s i d e r a t i o n a f t e rad e t a i l e da n a l y s i so ft h et r a n s m i s s i o nt i m eo f i e e e 8 0 2 11d c fm e c h a n i s m ，t h ea u t h o rm a n a g e dt od e r i v et h ee x p r e s s i o no ft h e a f o r e m e n t i o n e dg a p ( r a t e ) r e s p o n s er a t em o d e li n8 0 2 11w i r e l e s se n v i r o n m e n t s ，t h u s s f i c c e s s f u l l yo b t a i n e dt h et h e o r e t i c a lp r o p e r t i e so ft h em e a s u r e m e n tm e t h o di nw i r e l e s s c a s eb yu s i n ga n a l y s i st o o lo fm a t l a b t ot e s t i f yh i sa n a l y s i s ，t h ea u t h o rd i v i d e dt h er e a l c a s ei n t ot w oc l a s s e sa c c o r d i n gt ot h ep o s i t i o no ft h et i g h tl i n k ，a n dc a r r i e do u tas e r i e s o fe x p e r i m e n tw h i c hi n c l u d eas e to ft e s tb e dt e s ta n das e to fr e a li n t e r n e tt e s tf o re a c h c l a s s a se x p e c t e d ，t h ee x p e r i m e n tr e s u l t sc o i n c i d ew i t ht h ea n a l y t i c a lr e s u l tv e r yw e l l k e y w o r d s ：a v a i l a b l e b a n d w i d t h ；a c t i v em e a s u r e m e n t ；8 0 2 1l ；w i r e l e s sl a n ；d c f ； r a t er e s p o n s ec u r v e ；b o t t l e n e c kb a n d w i d t h ；i n t e r - p a c k e td i s p e r s i o n c i a s s n o ：t p 3 9 3 i v 图表目录 图1 主动带宽测试示意图5 图2 窄链路和瓶颈链路8 图3 链路利用率9 图4 包间隔响应1 0 图5 速率响应曲线示意图一1 1 图6 多跳情况下的速率响应曲线1 3 图7p a t h c h i r p 的一个c h i r p 中的包间隔示意图1 4 图8 时延图样1 4 图9d c f 的b a s i c 模式示意图1 9 图1 0d c f 的l 玎s c t s 模式2 0 图1 l 随机过程f b ( t ) ，s ( t ) ) 的马尔科夫链表示2 6 一2 1 图12 信道占用时问2 4 图13 碰撞概率和发送概率( a ) 2 7 图1 4 碰撞概率和发送概率( b ) 2 8 图1 5 碰撞概率与接入点个数2 8 图16 发送概率与接入点个数2 9 图1 7 接入点个数对传输时间的影响( a ) 刀2 ，2 0 1 一3 0 图1 8 接入点个数对传输时间的影响( b ) 刀2 ，1 0 0 0 1 一3 0 图1 9 平均分组大小和传输时间( a ) 3 l 图2 0 平均分组大小和分组传输时间( b ) 一3 2 图2 1 平均分组大小和分组实际传输效率3 3 图2 2 包间隔响应曲线( a ) n = 3 一3 4 图2 3 包间隔响应曲线( b ) n = 1 0 3 5 图2 4 不同接入点个数时的速率响应曲线3 6 图2 5 可用带宽测量理论值( a ) n = 2 3 8 图2 6 可用带宽测量理论值( b ) n = 5 3 8 图2 7 可用带宽测量理论值( c ) n = 2 0 一3 9 图2 8 试验床拓扑结构：4 1 图2 9 测试一4 3 图3 0 测试二4 4 图3l 测试三4 5 图3 2 测试四 4 7 图3 3 测试五4 8 图3 4 测试六：4 9 图3 5 一次完整的测试数据5 0 图3 6 互联网测试网络拓扑结构5 1 图3 7 互联网测试n = 2 5 2 图3 8 互联网测试n = 4 5 2 v l l 学位论文版权使用授权书 本学位论文作者完全了解北京交通大学有关保留、使用学位论文的规定。特 授权北京交通大学可以将学位论文的全部或部分内容编入有关数据库进行检索， 并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校向国 家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文萜者签名：办咙1 1 1 签字日期： 眇方年月7 日 导师签名： 签字日期： d 艿年多月8 日 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的研 究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表或 撰写过的研究成果，也不包含为获得北京交通大学或其他教育机构的学位或证书 而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作 了明确的说明并表示了谢意。 学位论文作者签名：多每唆71 签字日期： 5 9 。穷年月7 日 致谢 本论文的工作是在我的导师陈常嘉教授的悉心指导下完成的，陈常嘉教授严 谨的治学态度和科学的工作方法给了我极大的帮助和影响。在此衷心感谢三年来 陈常嘉老师对我的关心和指导。 胡师舜教授悉心指导我们完成了实验室的科研工作，在学习上和生活上都给 予了我很大的关心和帮助，在此向胡师舜老师表示衷心的谢意。 郭宇春、张立军、赵永祥教授对于我的科研工作和论文都提出了许多的宝贵 意见，在此表示衷心的感谢。 感谢我的家人，特别是我的父亲，感谢他能够在百忙之中抽出时间配合协助 我完成实验的互联网测试部分。 感谢我的同学，特别是在测试时慷慨的提供他们私人计算机的那些同学，没 有他们的热情帮助，我就无法按照我的设想搭建试验床，我的测试也不可能完成。 1 引言 针对某一网络通路的端到端主动可用带宽测量作为一种有效的测量方式在音 视频流传输、视屏会议、交互式i p t v 、v o i p 、o v e r l a yr o u t i n g 、服务器选择、拥 塞控制以及网络问题诊断和网络性能优化等领域都有非常广泛的应用，因而对其 测量方法的研究在近年来逐渐成为一个热点，在过去的几年里，人们提出了很多 方法，其中最具代表性的有t o p p l 、p a t h l o a d 2 、p a t h c h i r p 3 、i g i p t r 4 、s p r u c e 5 ， 绝大多数的方法是基于包对( p a c k e t p a i r ) 或包序列( p a c k e t t r a m ) 探测的，当 然对于某一确定路径，其可用带宽可以通过每一节点的路由器直接获得，但是这 种相对被动的方式需要对每一个节点的路由器的相应访问权限，也就是说当被测 的网络延伸至两个或多个控制域( a d m i n i s t r a t i v er e g i o n ) 时，就只能使用上述的“主 动”测量方式了，因此基于主动探测的端到端可用带宽测量显得更加具有实用价 值。 无线网络，包括用于提供与有线网络接入的无线接入以及通过a d h o c 模式连 接各个无线节点的无线网络应用，在当今的网络应用中变得越来越重要，随着无 线网络的广泛应用，以及人们对无线网络依赖性的逐渐增加，人们越来越关注是 否当前的网络测量方法和工具依旧可以适用于这些无线环境中。在这篇文章里， 我们将会对端到端的可用带宽测量这一技术在无线接入这一无线应用环境中的应 用作为重点进行分析研究。 目前流行的基于主动包探测的网络带宽测量技术具有一个共同点，这就是， 它们都使用了一系列的探测包从网络路径的一端发送出去，然后在另一端通过对 这些包的接收得到其时延的变化，或者得到探测速率和实际发包速率之间的关系 ( 速率响应曲线) ，然后通过对时延变化，或对速率响应曲线的特性分析，即可得 到网络的即时可用带宽信息。对于这一原理我们将在后文中进行详细地说明，通 过分析可以看出这些方法其实本质上有很大的共同点。 在这篇文章中，我们将通过理论分析和实际测试来研究分析i e e e 8 0 2 1 1 无线 网络的特性是怎样影响到实际的网络带宽测量结果的，通过对理论模型的分析， 我们得到了测量过程的理论期望值，同时为了证实分析结果，我们搭建了针对这 一测试的试验床，通过人为的调整一些网络参数来获得这些可用带宽测量方法在 无线网络应用中的一些特点，同时为了获得更具说服力的结果，我们对其在实际 的互联网中的应用也进行了测试，这些实验结果验证了之前分析的正确性。 测试使用了目前较为完善的端到端网络可用带宽测量软件p a t h c h i r p 作为主要 的测试工具，为了涵盖这应用的不同情况，分别对瓶颈链路在无线连路和有线 链路两种情况分别进行了测试分析和研究，针对这两种情况使用不同的背景流以 及探测包大小设计进行了不同的测试，最终得到非常全面的测量数据。截至完成 这篇文章之时，据我们了解，还没有人对这问题进行过如此全面的分析测量， 因此这一测量分析是非常具有参考价值的。 为了能够更好地说明测试结果，我们提出了无线网络中的速率响应模型，这 一模型是以有线情况下的模型为基础，引入了i e e e8 0 2 1 1 网络环境的一些特性参 数，通过对实际测试结果的分析，可以看到，无线速率响应模型在很大的程度上都 对测试数据进行了很好的阐释。 测试所使用的试验床包括一个使用无线接入的测试端以及若干跳使用有线的 局域网路径，局域网的理论带宽为1 0 0 m b p s ，无线链路理论传输速率为11 m b p s 同 时根据不同的测试情形，采用了1 2 台使用和测量机处于同一信道的无线终端作为 背景流生成器，这一拓扑结构比较符合当前流行的无线接入方式。测试时使用 e t h e r e a l 记录下背景流，同时使用t c p r e p l a y 2 7 】来产生相同的背景流以便加以比较。 对于实际互联网路径的测试，测试路径为北京交通大学学苑公寓宿舍至甘肃电信 提供的a d s l 接入的一个普通用户之间的网络通路。路径基本涵盖中国东西之间 的互联网主干道，比较真实地反映了我国当前的互联网状况，较具代表性。 在对相关领域的大量文献进行研究整理后，我们找出了一些相关的研究，在【6 1 中作者使用了d i e t t o p 。7 】对无线链路为瓶颈时的情形进行了分析并提出了扩展 t o p p 模型来说明他的测试结果，他的结论是，在引入无线末端后测量的结果将会受 到探测包大小的影响，但由于其仪仅从实验的观测数据来推断出上述的结论，并没 有经过实际的理论推倒和证明，而且它并没有能对结果提出解析性的表达式，因 此其结论的可信度大大降低。在 8 】中，作者详尽的论述了主动带宽测量这一方法 的理论基础，他从排队论的角度出发，对当前的主动测量方式提供了一整套的数 学模型基础。【9 】一文中，作者对无线a d h o c 环境下的可用带宽测量做了较为详细 的研究，并提出了一套适用于无线a d h o c 环境的可用带宽测量方法，当然，他所 提供的方法是基于被动侦测的，这一点，对于无线a d h o c 来说是非常有益的，因 为如果在a d h o c 中使用主动探测，那这些探测包的发送将会给整个网络带来很大 的丌销负担。在 1 0 】中，作者对当前流行的几种主动可用带宽测量技术进行了详细 的比较分析，他们使用了一套可以控制各种参数的实验床来说明他们测试的准确 性，这一点对于这些测量方法的比较是非常重要的，但是对于实际的情况则不能 准确的反映出来，因为实际的网络状况和人为生成的网络状况具有很大的差距的。 在 2 6 】中，作者对i e e e 8 0 2 1 l 无线局域进行了非常详尽的性能分析，通过建模， 他构造了以碰撞阶段为状态所构成的随机过程的马尔科夫链，通过分析获得了系 统的吞吐量，其分析过程非常有启发性，其结果也非常具有参考价值。 总的来说我们的研究以理论为基础立足实际，对于含有无线接入的端到端可 用带宽测量进行了较为详实的理论分析，填补了这一领域的空缺，为了验证理论 的正确性，对许多不_ j 的情况都进行了测试比较，而这种比较在之前都足从未有 过的，在具体的测试时，我们使用了各种流行的网络测试工具，通过巧妙的设计， 达到了较为满意的测试效果，所有的测试都竞可能的使用实际的网络链路，从而 使得到的结果非常真实的反映了实际的网络状况，大大提高了研究的适用性以及 学术价值。 本文之后的章节是这样安排的，在第二章我们将会对可用带宽测量方法进行 简单介绍并对主动带宽测量方法进行一定的分析说明：第三章我们将对无线局域 网中的分组传输时间加以分析；在第四章中我们以之前的分析为基础，推导出无 线环境下可用带宽测量模型，并针对这一模型使用m a t l a b 进行详细的分析比较； 之后，我们在第五章中将会通过实际测试对我们的理论模型进行对比验证；在文 章结尾的结论部分，我们将会对本文的工作加以小结，并对未能解决的一些问题 提出具有可行性的建议。 2 基于主动探测的可用带宽测量技术 2 1 常见可用带宽测量方法简介 带宽测量可分为单跳链路( s i n g l e h o p ) 的带宽测量以及对整条网络路径的端 到端( m u l t i h o p ) 的网络带宽测量，而后者更加具备实际意义，当前大多数此类 研究都是针对端到端的网络带宽测量展开的。 目前，端到端路径可用带宽测量的研究还处于起步阶段，其主要目标是在不 干扰或者不影响路径原有业务的情况下准确快速地测量可用带宽。由于i n t e m e t 上 流量的动态性，路径上可用带宽会随时间不断变化，如果测量时间过长，路径的 可用带宽可能会变化较大，从而测量结果也将大打折扣，以致失去意义，因此， 一个好的端到端可用带宽测量方法应具有很快的响应时问，且对路径上可用带宽 的变化较为敏感。 2 1 1分类 随着人们对可用带宽测量的速度以及精确度需求的逐渐增加，新的带宽测量 方法层出不穷，不断涌现，不过根据这些方法的基本原理划分，当前流行的带宽 测最方法主要分为主动( a c t i v e ) 测量和被动( p a s s i v e ) 测量两类，有人称之为侵 入式( i n t r u s i v e ) 和非侵入式( n o n i n t r u s i v e ) 测量 9 1 ，这种分类的依据则是探测时 是否需要向待测链路发送额外的探测包，如果需要则称其为主动测量或侵入式测 量，否则称其为被动测量或非侵入式测量。 2 1 2主动测量 在i p 层使用主动包探测的方法始于2 0 世纪8 0 年代末到9 0 年代初b o l o t ， j a c o b s o n 1 2 】，k e s h a v l l 3 】的研究，最初的研究主要是在拥塞控制方面，当时只是提出 了“通过主动探测包可以获得可用带宽”这一概念，而对这一方法并没有非常的 重视，不过随着对q o s 的要求逐渐提高，人们开始逐渐注意到这一方法，随之而 来的测量方法和工具也接踵而山，而近来涌现出的各种各样的带宽测量方法大都 借鉴于基于固定比特率( f l u i dc r o s s t r a f f i cm o d e l ) 的瓶颈带宽测量研究【1 ， 2 】。 主动测量：网络可用带宽的主动测量工具通过向网络发送测量分组 4 ( p a c k e t p a i r 、p a c k e t t r a m ) ，并根据测量分组所携带的信息( 延迟、速率) 来推测 网络的情况。测量工具在网络两端的测试主机上测量，不需要路由器增加其他的 网络协议来配合，属于端到端的测量工具。主动测量具有主动性强、灵活、方便 等优点，能够以更直接的方式来分析网络。 i n p u t 饼獬铲 t t a f t i e - - - 啼 i n l 弧a 阳翩 u a f f i 窑 o u p u t f 锄蟹 钧瀚c 约让l 豺掰e 籀鑫相y - o u l p l u 毯囝嗡 暂黝霉 图1 主动带宽钡4 试示意图 f i g 1a c t i v eb a n d w i d t hm e a s u r e m e n t 一般主动测量会通过以下的信息来确定待测链路的可用带宽： 1 ) 测量分组在整个待测路径上的r t t ( r o u n d t r i pt i m e ) ； 2 ) 相继分组之间的间隔在经过整条路径后的变化( i n t e r - p a c k e td i s p e r s i o n d i f f e r e n c e ) 或者分组经过整条路径后的速率变化，实际上分组的速率是使 用分组的大小除以分组的问隔来定义的，所以两者直接并没有本质的不 同。 3 ) 分组经过整条路径后的时延的变化趋势。 主动测量方法的不足：由于需要向网络发送大量的测量分组，这样便会增加 网络的负担，对网络性能产生影响。大量的测量开销流量很有可能在瓶颈处导致 拥塞，使测量结果偏离实际值，产生系统误差。 目前流行的主动带宽测量方法种类繁多，对其分类的方式也众说纷纭，在 1 0 】 中将其分为基于p g m ( p r o b eg a pm o d e l ) 和基于s e l f - i n d u c e dc o n g e s t i o n 两类，而 实际在我们后面的分析后可以看出，他们实际上都是使用了相同的基本模型，只 不过在模型的具体实现卜有些差异罢了，为了避免混乱所以在这里我们使用一种 相对更加准确的分类方法【8 】来对目前流行的测量方法分类简述。按照这种分类方 泼，它们可以分为d i r e c t 和i t e r a t i v e 两类。 2 1 3d i r e c t 类测量方法 这类方法可以简单概括为：当探测包的速率大于可用带宽时，就可以用探测 响应曲线( r e s p o n s ec u r v e ) 上的一点来确定当前的可用带宽，这种方法一开始就 以较快的速率发包并且假设一开始就知道或者可以探测到这条路径的容量，即总 带宽( 比如使用p a t h r a t e 等软件事先测得路径的容量) ，因此每一个p a c k e t t r a i n 的 样本都可以产生一个测量结果，探测使用了多次平均来获得最终的结果，通过多 次平均可以解决由突发背景流对f l u i dm o d e l 带来的影响，这一点会在之后对f l u i d m o d e l 详述时具体说明。使用了这种方法的代表性测量工具有： d e l p h i 1 4 】d e l p h i 的主要思想是，当链路非空，而且当探测包的速率大于链路 的可用带宽时，依据包之间的间隔就可以计算得到当前的可用带宽，这一方法是 基于单一队列模型的，这一模型的局限性在于他所模拟的环境必须是瓶颈链路必 须足窄链路1 ( t i g h tl i n k ) 的情况。如果将这一方法用于不符合其模型要求的网络 路径中，那么将会对测量结果造成一定的影响，这样一来这一方法的适用性就大 为降低了。 i g i 1 5 】，p t r ，i g i 和p t r 都是基于p r o b eg a pm o d e l 的，为了能够更好的使用 这一模型，他们引入了j q r ( j o i n tq u e u i n gr e g i o n ) 和d q r ( d i s j o i n tq u e u i n gr e g i o n ) ， 通过这一划分，将那些非空队列排除掉使得待考察的p a c k e tp a i r 都处在同一个 j q r 中，这样就可以用它们离开待测路径后的间隔计算出带测毒路径的带宽，p t r 的不同在于它使用测试速率来代替了包间隔，但实际上也是和i g i 基于同一模型 的。 s p r u c e 1 6 】，s p r u c e 使用通过网络后包间隔的变化来确定当前链路的可用带宽。 实际上他首先通过相继包的间隔扩展获得了当前背景流的速率，然后用网络路径 的容量减去背景流速率从而推知了链路带宽。 2 1 4i t e r a t i v e 类测量方法 这类方法首先向网络发送一系列的不同速率的探测包序列，然后通过接收端 的接收和处理分析判断寻找出这一链路的可用带宽。 p a t h l o a d 2 1 ，p a t h l o a d 通过向网络发送含有k 个探测包的p r o b et r a i n 来获得k 个单向延迟，通过对这些单向延迟的分析可以得到响应的延迟变化趋势，然后通 过这些变化趋势的统计来确定导致网络饱和时的探测速率，从而得到当前的可用 带宽，p a t h l o a d 的一个显著特点就是它使用一个范围来表示测得的可用带宽的，同 时他对于在一个t r a i n 内背景流所导致的时延波动用g r e yr e g i o n 来表示。 t o p p 1 1 t o p p 可以同时测量网络的容量和可用带宽，它基于对速率响应曲线 ( r e s p o n s e c l l r v e ) 拟合的原理，通过对速率响应曲线的线性部分做线性回归，得 对于瓶颈链路和窄链路的定义请参考2 2 1 节中的相关说明 6 到该曲线，从而得到相应的网络容量和可用带宽。理论上通过这种方法可以依次 测得路径上的每一条窄链路的可用带宽，但实际上如果探测包的速率远大于瓶颈 链路的可用带宽时，将导致丢包，从而使得测量产生严重的误差。 p a t h c h i r p ，p a t h c h i r p 使用了不等间隔的p a c k e tt r a i n ，通过以指数形式分布的包 阳j 隔来加快了对带宽饱和点的搜索，它可以非常迅速的得到即时带宽，同时可以 手动调整探测包的大小和速率范围等一些重要参数，在当前的网络测试中被广泛 使用，因此我们也以其作为主要测量工具，对这一方法的具体介绍请参见2 3 节。 2 1 5被动测量 被动( 或非侵入式) 测量最显著的特点就是它们都使用了包含带宽利用率的 本地信息，比如各个路由器的即时带宽统计信息，或者在无线环境中通过对无线 信道的侦测而计算出的信道利用率，通过对网络路径上的各个路由器或a d h o e 节 点的信息的统一收集，即可完成整条链路的可用怡宽计算，通常，这类信息可以 通过广播的方式传播，大多数的协议都是使用h e l l o 报文来广播发送这一信息的。 在有线环境中，我们可以通过路径上每一个路由器所提供的带宽监测信息来 得到整条路径的可用带宽，不过前提是能够获得这些信息，也就足说这些信息的 获得必须以对路径中所有路由器的访问管理权限为前提，普通的用户是无法获得 这些信息的，凶此在真正的应用中，人们都会使用主动探测的方法，主动探测并 不需要对每一个路由器都有完全的控制权，换句话说就是主动探测对待测路径的 控制需求为零。 无线a d h o e 一般会采用被动方式的带宽测量，因为主动测量所发出的探测包 在a d h o e 环境下经过多跳之后对整个网络造成的负担之大是难以想象的。这种应 用一般会通过使用一些协议来达到可用带宽信息的获得，这类应用中比较具有代 表性的有b r u i t 1 7 1 、c a c p 1 引、q o s a o d v 1 9 1 、x a 、c 幢0 1 ，这类方法并不是本文研 究的重点，在此不再赘述。 2 2主动带宽测量的基本原理 2 2 1可用带宽的定义 目前由于对带宽以及相关概念的说明并没有达到统一，因此在不同的文献中， 可能用到了不同的名称来表示同一概念，因此非常有必要在此将这些概念加以澄 清。 在数字通信中对带宽的定义是链路可以传送数据的最大速率，这一速率也被 称为链路的容量。不过更为普遍的一种说法是：网络提供的链路或路径的传输速 率或吞吐量，一般情况下，吞吐量的概念受到了协议的影响，不同的封包或组帧 方式，将带来不同的开销，以致实际的数据吞吐量小于网络所能提供的最大带宽， 因此，d o v r o l i s 等人在协议层次上定义路径的容量与可用带宽： 路径容量：路径容量是在没有背景流量的情况下，路径能给予一个流的最大 i p 层吞吐量。 可用带宽：在给定背景流量负载下路径能提供给一个流的最大i p 层吞吐量。 在我们以下的分析中，我们采取了如下的定义： 链路带宽( l i n kb a n d w i d t h ) ：即链路容量，指的是链路在物理设计上能够达 到的最大数据传输速率，一般足一个固定值。通常我们用c 来表示。 链路可用带宽( 1 i n ka v a i l a b l eb a n d w i d t h ) ：链路上未被背景流量占用的剩余带 宽。 瓶颈链路( b o t t l e n e c kl i n k ) ：两个节点之问路径上拥有最小的链路带宽的链路， 它表示一条路径的最大传输速率。 瓶颈链路带宽( b o t t l e n e c kc a p a c i t y ) ：瓶颈链路的带宽。 窄链路( t i g h tl i n k ) ：在有背景流的情况下，路径中具有实际最小可用带宽的 链路。 根据上述的说明我们可以看出，当链路有背景流时，链路的瓶颈带宽就不一 定是链路的可用带宽了，因为有可能在某一非瓶颈链路上因为有更大的背景流从 而使得该处的可用带宽成为了路径中的最小值，从而使窄链路成为了非瓶颈链路， 也就是说一条网络路径的瓶颈链路和窄链路实际上是没有关系的。瓶颈带宽反映 的是路径的静态特征，而可用带宽带宽则真正反映了在某时段链路的实际通信能 力，请参考下图，图中瓶颈链路为1 l ，而窄链路则为1 3 。其瓶颈带宽为b l - ，而可用 带宽为a 1 。 a 3 a 2 a 1b 2 b 3 b l l ， 1 1 2 图2 窄链路和瓶颈链路 f i g 2t i g h tl i n ka n db o t t l e n e c kl i n k 8 上述分析定义都是基于流体模型的，也就是将链路看成了管道，而其中的数 据流则当做了水流，而在实际中，网络中所传播的是一系列的二进制比特流，下 面我们将从链路利用率出发推导出实际情况下的链路带宽表示。 链路利用率：在网络端到端路径中，在任意时刻t ，任何一条链路要么处于忙状 态，正在以最大速率转发数据包，要么处于空闲状态，设链路状态定义如下【8 1 ： “( ，) ：e ；窭要烈篓璧篓 ( 2 2 1 )“2t 1 ；该时刻链路空【2 2 1 j 那么在一段l , - i f f ，t + r 内，链路的利用率为【8 】： u ( t ，t + f ) = 二iu ( x ) d x ( 2 2 2 ) 下图直观的表示了这一过程： 图3 链路利用率 f i g 3l i n ku t il i z a t i o n 链路利用率定义了一段时间内链路处于转发数据包状态的平均比例，表征了 链路的被占用程度。 由此可得链路的可用带宽，即在一定时间间隔p ，t + f 】内链路i 总容量被占用 的平均值即： e ( f ) = c ( 1 - u ( t ，t + f ) )( 2 2 3 ) 而一条网络路径的可用带宽按我们之前的定义，为该路径中所有链路的可用 带宽的最小值，即( 设路径有n 条链路) ： a ，( f ) = m i n b ：( f ) )( 2 2 4 ) 需要注意的是a ，( f ) 随着时间t 以及观测问隔f 的变化而变化，这使得测量变 得非常复杂，为了克服这一问题，目前的大多数的测量都使用了一种固定比特率 背景流的f l u i d 2 1 1c r o s s t r a f f i cm o d e l 来解决这一问题，在固定比特率背景流的前提 下，上述的4 ( t ) 将与时间以及测量问隔无关而成为一个定值，从而使得探测输入 与输出的关系易于确定。 。 2 2 2f l u i dc r o s s t r a f f i cm o d e l 假设在上述的f l u i dc r o s s t r a f f i c 的情况下，我们来考察一条链路的情形，设该 链路的容量为c ，背景流是以固定的速率旯 s ( c c ；g - i 2 训) c 一兄) ( 2 2 5 ) 我们通过p a c k e tp a i r ( n _ 2 时) 来说明上式的意义，当有两个包p 1 和p 2 先后 经过链路，在经过链路之前p 1 和p 2 之间的距离为g i 当第一个包p l 开始传送时， p 2 包需要等待p 1 包本身的传输时间以及p 2 和p 1 的间隔时间内到达的背景流的 传输时间，也就是说p 1 和p 2 之间要传送的总的数据为p l 本身的长度s 加上p 1 与p 2 间隔时间g ，内到达的背景流五g ，传送这些数据需要的时间为0 + 2 9 j ) c ， 如果这个时间小于g ，那么最终还的间隔还是g ，否则就是o + 2 9 ：) c 。 盂船= 唑：严口口婴四g b 衄 b c g o 图4 包间隔响应 f i g 4g a pr e s p o n s e 而式( 2 2 5 ) 被称为s i n g l e h o pf l u i dg a pr e s p o n s ec u r v e 【8 】，这一模型有许多变种， 其中有一种直接和带宽相联系，描述如下： 如果用乞表示输出端的测得探测序列的速率，则名= s g 。，同样，进入链路之 前的速率，；= s g ，那么式( 2 2 5 ) 可以变形为【8 1 ： 名= 州，是) = 强他删霪g 二三 ( 2 2 6 ) 上式并不是线性的，因此m e l a n d e r 在 1 lr f | 提出了一种对其线性化的变换： i r i x ( 1 ，字) = 训c 霪g 二孟 ( 2 2 7 ) 式( 2 2 7 ) 被称为速率响应曲线，它包含平行于横坐标的一段以及线性增长的一 段，是一个分段函数。 上述各式具有一个共同点，就是当曲线发生转折时，那一点的带宽即为可用 带宽，而当探测包传输速率在a ，0 0 1 时也可以通过以上各式得到信道的容量c 以及 背景流的速率彳从而间接的得到可用带宽。容易看出在我们上一节中所叙述的几种 模型要么使用了速率的转折点，要么就使用曲线的特点得到c 和彳从而间接的得 到a ，但他们都基于上述的带宽基本模型，其本质是相同的。 l o 2 2 3速率响应曲线 下面我们来看看前面提到过的速率响应曲线，它具有线性的部分： y = 口，：+ p ；，；【彳，】 ( 2 2 8 ) 其中口= 1 c ，= a c ，那么我们可以通过斜率口得到链路容量c ，而通过 i l i a 得到链路的背景流速率名，从而根据a = c 一五得到链路的可用带宽。下图为 一条速率响应曲线的示意图： 图5 速率响应曲线示意图 f i g 5r e s p o n s ec u r v e 实际上，我们直接可以得到可用带宽，因为，可用带宽a 正好是曲线发生转 折时的横坐标，：的值。可以看出，在f l u i dc r o s s t r a f f i c 的情况下，通过上述的速率 响应曲线就可以得到我们想要的结果，不过实际的网络很少会像上述的情况一样 具有固定不变速率的背景流，恰恰相反，实际的网络中的背景流往往具有一定的 突发性，甚至在有些时候具有非常强的突发性。对于这问题的处理我们将在下 一节中详细叙述。 2 2 4 b u r s t yc r o s s - t r a f f i cm o d e l 如果我们把一次测量时的背景流的突发性考虑在内，那么上述的模型就可能 无法正确得到测量结果了，上述的响应曲线在这种情况下将会和图5 中所示有一 些偏差f 2 2 】，但足在统计上来说，测量的期望是符合这一曲线的，在【2 3 中作者将这 种突发性背景流带来的偏差当作噪声来处理，也就是说，经过多次的测量得出的结 果的平均值将会很大程度上符合上述的规律，这一假设可以用下式表示8 1 ： e g 。】= m a x g f ，竿)( 2 2 9 ) l 一 在上式中，e g 。】表示输出包间隔的统计期望( 多次测量的平均值) ，而在这 里的见表示了在很长一段时间内的背景流平均速率，因为较长的探测序列将会把观 测期拖得很长【8 j o 当前的主动测量方式都是建立在这一假设之上的，虽然没有严密的理论验证 这一假设的正确性，但是就实际测试来看，测量的结果在很大的程度上是比较合 理的，从而间接的说明了这种假设的正确性。 对于当前流行的主动测量方法，它们都假设突发性的背景流对整个测量的影 响莫过于一定程度的偏差，通过多次的测量就可以将这种偏差降低到需要的程度， 它们经过测量得到的每一个结果实际上都是测试的每一次观测期之间的平均值。 所以当经过大量的测量( 多次的重复试验) ，使用大量的探测序列样本的情况下， 基于上述的f l u i dm o d e l 的测量结果将成为实际情况的很好近似。 2 2 5多跳链路的可用带宽 假设路径上存在1 3 条链路，链路带宽为g ，可用带宽为4 ，且4 递增，艺。为 探测流通过第l 条链路后的带宽。当逐渐增大发送速率i ，直到i a 时，第1 条 链路发生拥塞，如前所述，：r o = 喁+ 屈i ，这时探测流以的速率到达接收端， 当继续增大，直到r o 。4 时，第2 条链路也会发生拥塞，此