（计算机应用技术专业论文）ip网络的带宽测量技术的研究.pdf

摘要 随着计算机互联网技术的不断发展，网络规模不断扩大，网络流 量爆炸增长，网络性能检测在当今的网络中变得日益重要。而作为网 络性能定量描述中的一个基本参数链路带宽，是网络规划、管理 和性能优化的基本指标，因此构建较完善的端到端链路带宽测量模型 和设计合理的基于带宽测量模型的应用框架具有重要的意义。国外的 c a i d a ( c o o p e r a t ea s s o c i a t i o nf o ri n t e m e td a t aa n a l y s i s ) 和s t a n f o r d 大学在从事这方面的研究，而国内的研究仅仅处于起步阶段。到目前 为止，国际上仍没有公认的带宽测量的标准，不能很好地为用户准确 地提供网络运行的相关参数。本论文的探讨与研究内容为链路带宽测 量提供了一种新的思路和途径，因此该项目的研究具有较高的社会和 经济效益 本文从近年来链路带宽测量的发展方向着手，首先介绍了该领域 研究的进展情况，比较了一些具有代表性的链路带宽测量模型及其应 用，分析了现有测量技术存在的问题及其原因，在此过程中修正了 p a t h c h a r 算法中对链路带宽消耗的一个公式。这对掌握国际上有关此 方面的最新网络带宽测量技术以及网络带宽测量建模方法具有重要 的指导意义。 接下来着重剖析了基于多分组延迟模型( m u l t i p a c k e td e l a y ) 的 追尾( p a c k e t t a i l g a t i n g ) 算法。追尾算法针对链路带宽测量提出了一 种比较完善的解决方法和崭新的思路，但是它的测量公式相当复杂并 t 且存在着一些问题。因而在这基础上，本文构建了新的基于多分组延 迟的确定性模型( d e t e r m i n i s t i cm o d e l s ) ，推导出适用于链路带宽测 量的一个新的简洁公式，并通过分析研究这类确定性模型的本质来证 明我们新模型的正确性。 最后，基于新模型设计了一个用于链路带宽测量的工具d p r o b e ， 它可以测量一条路径上的瓶颈链路带宽和所有链路带宽。 我们还对链路带宽测量过程中的过滤干扰数据流等问题进行了 讨论，并对链路带宽测量的发展趋势进行探讨和预测。 关键词：链路带宽测量，端到端，确定性模型，瓶颈链路，数据包对 算法，核心密度估计 a b s t r a c t w i t ht h ed e v e l o p m e n to fi n t e r n e tt e c h n o l o g i e s ，t h es c a l eo fn e t w o r k e x t e n d sc o n t i n u o u s l y , t h eq u a n t i t yo f n e t w o r ki n c r e a s e ss t u p e n d o u s l y , a n d d o i n ge f f i c i e n tm e a s u r e m e n to fp e r f o r m a n c eb e c o m e sm o r ea n dm o r e i m p o r t a n t i nn e t w o r kn o w a st h eb a s i cp a r a m e t e ro fn e t w o r kt e s t i n g ，l i n k b a n d w i d t hm e t r i c sa r en e c e s s a r yf o rn e t w o r kp l a n ，m a n a g e m e n ta n d p e r f o r m a n c eo p t i m i z a t i o n , s oi t i sh i g hs i g n i f i c a n tt ob u i l dt h eb e t t e r m o d e lt om e a s u r eb a n d w i d t ho fe n d 4 0 - e n dn e t w o r k , a n dt od e s i g na n r e a s o n a b l ea p p l i c a t i o nf r a m e w o r kb a s e do nt h em o d e lo fm e a s u r i n g b a n d w i d t h c a i d aa n ds t a n f o r du n i v e r s i t ya r es t u d y i n gi nt h i sf i e l d ，b u t i no u rc o u n t r y , t h i si sj u s tb e g i n n i n g u pt on o w , t h e r ei sn os t a n d a r do f m e a s u r i n gb a n d w i d t hi nt h ew o d da n di tc a n n o ts u p p l yt h ed a t ao f o p e r a t i o ns t a t u st ou s e re x a c t l y t h ed i s c u s sa n dt h es t u d yo nt h i sp a p e r c o u l do f f e ran e ww a yt om e a s u r i n gb a n d w i d t h ，s ot h ep a p e rh a v eg o o d s o c i e t a la n de c o n o m i c a lb e n e f i t t h ep a p e ra l o n gt h ew a yo ft h ed e v e l o p m e n to fl i n kb a n d w i d t h m e a s u r e m e n ti nr e c e n ty e a r s ，f i r s ti n t r o d u c e st h er e l a t e dr e s e a r c hw o r k s ， a n dc o m p a r es e v e r a lt y p i c a lm o d e l sa n da p p l i c a t i o no fm e a s u r i n gl i n k b a n d w i d t h ，t h e na n a l y z et h em a i np r o b l e m sa b o u tt h ee x i s t e n tt e c h n i q u e s ， a n dm o d i f yt h ef o r m u l af o rt h ec o s to fa v e r a g eb a n d w i d t hu s e df o r - 玎i p r o b i n gap a r t i c u l a rh o pa b o u tp a t h e h a r i t i si m p o r t a n tt om a s t e rt h e n e w e s tt e c h n i q u ea n dm e t h o do f m o d e l i n ga b o u tm e a s u r i n g b a n d w i d t h n e x ts t r e s s i n go na n a l y z i n gt h ep a c k e tt a i l g a t i n gw h i c hd 印铋d c d o nt h em u l t i p a c k e td e l a ym o d e l t h ep a c k e tt a i l g a t i n gb r i n g sf o r w a r da b e t t e rw a ya n dan e wi d e a , b u ti t sf o r m u l ai sq u i t ec o m p l e xa n dt h e r ea r e s o m eq u e s t i o n s t h u so nt h eb a s i so ft h e s ew o r k s ，w e b u i l da d e t e r m i n i s t i cm o d e lb a s e do nt h em u l t i - p a c k e td e l a ym o d e l ，a n dd e d u c ea n e wc o n c i s i o nf o r m u l a ，a n dp r o v e dt h er e l i a b i l i t yo f o u rn e wm o d e lb y a n a l y z i n gt h ee s s e n c eo f t h e s ed e t e r m i n i s t i c m o d e l s a tl a s t ，0 nt h eb a s i so ft h en e wm o d e l ，w et r yt od e v e l o pap r o b i n g t o o ln a m e dd p r o b ew h i c hc o u l db eu s e dt om e a s u r et h eb o t t l e n e c k b a n d w i d t ho fap a t ha n dt h eb a n d w i d t ho fe a c hl i n ko ni t b yt h ew a y , t h i sp a p e ra l s od i s c u s s e ss o m eq u e s t i o n sa b o u tf i l t e r i n g o u tt h ee f f e c to fc r o s st r a f f i cd u r i n gm e a s u r i n gl i n kb a n d w i d t h ，a n d p r o p o s e ss o m es u g g e s t i o n sa n d f u r t h e rr e s e a r c hd i r e c t o r k e yw o r d s ：l i n kb a n d w i d t hm e a s u r e m e n t ，e n d t o 。e n d , d e t e r m i n i s t i c m o d e l s ，b o t t l e n e c kl i n k , p a c k e tp a i r , k e r n e l d e n s i t y e s t i m a t i o n 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定， 同意学校保留并向国家有关部门或机构送交论文的复印件和电子版， 允许论文被查阅和借阅。本人授权江苏大学可以将本学位论文的全部 内容或部分内容编入有关数据库进行检索，可咀采用影印、缩印或扫 描等复制手段保存和汇编本学位论文。 保密口，在年解密后适用本授权书。 本学位论文属于， 不保密u 。 学位论文作者签名丁昌苛 签字日期：沁哆年6 月l f 日 学位论文作者毕业后去向： 工作单位： 通讯地址： 导师签名：专概导师签名：一v 叶幢_ b l 签字日期：如以年6 月心e t 电话： 邮编： 独创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进 行研究工作所取得的成果。除文中已经注明引用的内容以外，本论文 不包含任何其他个人或集体已经发表或撰写过的作品成果。对本文的 研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本人 完全意识到本声明的法律结果由本人承担。 学位论文作者签名：丁曷许 日期：徊唯年6 月j f 日 第1 章绪论 随着i n t e m e t 技术的迅猛发展，网络规模不断扩大，网络流量爆炸增长但 在这个发展过程中，人们对于i n t e r n e t 的流量模型、网络行为、性能指标等都缺 乏深入的了解和精确的描述，尤其对网络测量这方面的技术研究更是显得明显滞 后并且i n t e m e t 在全球范围的急剧膨胀导致了传输带宽资源的紧缺，这成为限 制网络发展的主要因素，而实时业务和多媒体业务等新业务的增加，又对网络的 应用性能提出了更高的要求一般说来，影响应用性能的原因包括链路带宽、链 路瓶颈、应用与协议的设计、主机系统等，而其中的链路带宽，由于是最重要的 网络资源，也是传输路径性能的主要决定因素，并且网络瓶颈与整体性能分析、 容量规划都密切相关，因此精确地测量链路带宽就成为网络研究中的一个首要问 题 然而，精确地测量链路带宽却显得异常棘手在i n t e m e t 发展初期，并没有 考虑到对网络的带宽测量需求，所以现有的带宽测量只是在利用现有网络提供的 可能性来进行i n t e m e t 的庞大结构和异构特征，以及测量费用和网络安全等因 素，使得单纯地在i n t e m e t 上配置测量硬件的做法不太现实；而由于网络是分散 管理的，从终端主机上着手测量也是困难重重良好的测量算法必须要适应复杂 的网络环境，可是现存的一些链路带宽测量算法在实际的网络环境测试中，均存 在着各自的不足 本文承继近年来链路带宽测量技术的研究，在对追尾( p a c k e tt a i l g a t i n g ，p t ) 模型做出深刻剖析的基础上，提出修正的带宽测量模型n p t ( n e wp a c k e t t a i l g a t i n g ) ，它比现存的类似技术对网络造成的影响更小，所消耗的带宽更少， 测量结果更精确。一般来讲，如果需要在待测链路两端进行配置的话，因为它不 依赖于路由器返回的i c m p 报文，因而测量结果会更加稳定；如果只需在某一端 进行配置，相对于在两端配置软件进行测量来说，测量精度会有所降低。因为我 们的模型不对应用和传输协议或传输的数据量做假定，所以它适用于更加广泛变 化的带宽测量应用需求。 1 1研究背景和动机 由于采用了d w d m ( 波分多路复用) 技术，近年来，网络上链路带宽的增 长速度一度超越了通信量的增长速度，于是，有些人就认为链路带宽会变得越来 越富余，带宽测量便显得不再有必要了可是尽管在时间、空间上链路带宽是相 对富裕的，并且带宽的增长和应用需求的增加一直在试图寻求一种平衡，但是不 富裕、不平衡的状况却是绝对存在的，链路带宽以稳定的增长率持续增长直至超 越应用所需的带宽是不太可能的下面我们略加说明 假如用户对带宽的需求猛增，网络上就会发生拥塞，网络上的应用性能必然 会大打折扣，而应用性能的降低肯定会使用户减少对带宽的需求，所以带宽需求 不可能极大地超越供给：同样，由于提高链路带宽耗费巨大，只有当公司相信有 足够的需求和效益时才会对此投入资金，所以带宽供给也不可能极大地超越需 求。当链路带宽增长时，现有的应用性能将会得到提高，于是需求随之增长，相 应会出现许多新的应用，继而带来更多的需求，这必然会导致新一轮的网络拥塞， 表现为一个螺旋发展上升的过程。 历史上，1 9 9 5 1 9 9 6 的i n t e r n e t 拥塞的巨幅增长正是由于w w w 应用的流 行造成的，这使得各大公司迅速投资增加链路容量，从而导致了目前i n t e r a c t 核 心链路容量的供过于求但是总的说来，由于i n t e m e t 用户的急剧增多和服务功 能的日臻完善，链路带宽的增长将超越通信量的增长以至于没有必要再进行链路 带宽测量，这是不可能的 狭义地说，由于链路带宽是网络最基本、最重要的性能指标之一f i l ，精确地 测量链路带宽也很有意义i s p 在进行网络规划、运行维护、负载均衡和采用 q o s 性能保障等技术时，链路带宽是一项重要的参考因数；用户也可能会把链路 带宽的相关参数用来作为服务性能的指标之一；研究人员则会利用链路带宽的相 关参数对协议和应用进行改进和测试，例如可以用来改进协议的实现。提高拥塞 控制技术，为网络管理和网络升级提供依据等 然而，i n t e r a c t 的异构性和网络环境的复杂性使精确地测量链路带宽面临着 巨大的困难。比如说，在网络上链路带宽的数值已经跨越了5 个数量级，网络环 境一直在不断地变化，因此在测量的过程中会有许多难以预料和难以避免的因素 相互纠结，它们都在不同程度上影响着链路带宽测量的最终结果。同时，在链路 带宽的测量中，并不是每个i s p 都支持对自己网络的性能和负载进行测试，这使 得某些依赖于相关参数的测量变得不再可行对于个人用户来说，他们则希望有 简便易用的软件测量工具，以了解自己所用网络的状况，而有些测量工具却并不 容易配置和实现 1 2 带宽测量术语和路由 1 2 1 带宽测量术语 不同的应用和需求关心着带宽的不同指标。i e t f 的i p p m ( i n t e m e tp r o t o c o l p e r f o r m a n c em e t r i c s ) 发布了不同的r f c 。定义了单向延迟、延迟抖动、丢包率 等网络性能的指标和测量方法【2 】【3 1 ，但至今没有一个r f c 对链路带宽的相关指标 进行定义本节中，我们给出如下的链路带宽的相关定义【4 】【s 】嘲，为后面的研究 工作做铺垫 链路带宽：数据在连接两个节点的某条链路上的传输速率因为链路带宽在很大 程度上影响着应用性能，所以本概念并不关心它是链路本身的属性还是链路与相 邻路由器的结合属性，我们所关一t l , 的只是忽略其他因素以后，从端到端所透视定 义的链路带宽。 瓶颈链路带宽：在一条路径中，所有链路的链路带宽的最小值也就是说，设p 为节点s 、t 间的一条路径，每条链路厶的链路带宽为且，则p 的瓶颈链路带宽 为口i = m i n b ，f = 1 , 2 ，仃 ，( h 为链路的数目) 瓶颈链路带宽限制了发 送节点沿着一条路径发送数据的速率。只要端到端路径的路由不变，瓶颈链路 带宽也就保持不变，与网络中的背景流量无关 可用带宽：在不影响现有背景流量的数据传输率的前提下，端到端的路径可以达 到的最大数据传输率也就是说，曰。m = m i n ( b l ( 1u a ) ) ，f = 1 , 2 ， ，( 厅为 链路的数目，“，为链路f 的带宽利用率) ，即；未被背景流量占用的剩余带宽 对可用带宽来说，它依赖于许多因素，包括应用、协议、干扰数据流( c r o s st r a f f i c ) 的特征和路由等。 1 2 2 路由问题 路由的很多特征要求能够频繁地、方便地和在每个方向上独立地测量网络的 链路带宽路由包含着两个基本的动作：确定最佳路径和传输数据。假定某条链 路因故中断，很多路由算法将迅速地选择次佳的路径来传递数据，这会导致沿着 一条路径的链路发生改变，从而使得链路带宽也随之改变另一种路由改变是由 于移动主机的存在，它们可能一天移动很多次位置，而每次移动后与i n t e r a c t 其 他节点之闻的路由可能就会发生变化。一项研究表明，路由的改变可能频繁到每 几分钟就发生一次p 】由于频繁发生着路由改变，在节点和网络资源上，链路带 宽的测量必须足够方便以使得可以反复地进行测量另一个问题是存在不对称路 由，例如数据在往返方向上传输时选择了不同的路径，这样，就需要在两个方向 上单独地测量链路带宽 1 3 研究方法 针对以上描述的问题，我们使用如下方法来测量链路带宽： ( 1 ) 沿着一条路径测量每一条链路的链路带宽和测量瓶颈链路带宽； ( 2 ) 从终端主机着手来测量； ( 3 ) 尽可能被动地测量链路带宽，只是在不可能进行被动测量的情况下，再 选择主动测量。 1 3 1 测量链路带宽 我们将在网络层上测量链路带宽，这样做的优点是，不依赖于某个具体的高 层协议( 例如h t t p ) 就可以进行链路带宽的铡量事实上，在i n t e r n e t 历史上， 许多高层协议和相关内容大幅度地改变过很多次例如，最流行的应用协议一度 是文件传输协议( f t p ) 川，后来则变成了超文本传输协议( h t t p ) i s 现在， g n u t c u a 的端到端文件共享协议( p 2 p ) 9 1 j e 在蓬勃地发展。 因为i n t e r a c t 的分层体系结构【m 】和t c p i p 协议本身优良的特性，使i n t e r a c t 在网络层一直使用口协议，但是在具体执行和下层的接口上却可能有多样的变 化。如果低于网络层测量链路带宽的话，就需要理解目前各种复杂的链路特性， 这会使测量工作变得相当繁琐，而且也降低了通用性。 测量链路带宽的最终原因，是为将来测量可用链路带宽做准备可用带宽给 出了一个更好的对实际应用性能的预测，但是，如1 2 1 节中可用带宽定义所述， 它涉及的因素太多，相关模型和实际测量也就显得更加复杂化因此在本文研究 中，我们选择了测量链路带宽而不是测量可用带宽，具体原因如下：1 ) 链路带 宽参数的利用率比可用带宽参数的利用率高；2 ) 可用带宽的可变性极大，难以 验证测量结果的正确性，相对来说，链路带宽测量的结果在i n t e m e t 上是比较容 易验证的；3 ) 测量链路带宽有助于测量可用带宽，因为可用带宽既依赖于干扰 数据流的行为，更依赖于链路带宽 针对某些应用需要知道沿着一条路径的瓶颈链路在哪里和需要理解延迟的 全部来源的特征，我们选择测量沿着一条路径所有链路的链路带宽针对在1 1 节中描述的许多应用，它们只关心从一个主机到另一个主机发送数据包能够达到 的最大速率，我们选择测量瓶颈链路带宽此外，比较测量沿着一条路径的所有 链路带宽与测量瓶颈链路带宽的工作量，后者花费的时间和数据包均较少，却可 以达到更高的精确度 1 3 2 端到端测量 所谓端到端测量 4 1 ，意味着我们在测量链路带宽的时候，不可以依赖来自网 络的某些特殊信息和特殊传输协议。也就是说，要求只在一条路径的两端安装好 测试程序后就可以进行测量，因此测量的过程应当不依赖任何特定的网络设备， 而能够适用于多种现有的网络环境。所以说，从终端主机出发的测量比依赖于路 由器帮助的测量所面临的挑战更大。但是，依赖于路由器帮助的测量不仅难于部 署，而且在不同的管理区域面前，也显得相当不切实际 依赖于路由器帮助的测量之所以很难布署，是因为这需要修正沿着一条路径 的所有路由，而i n t e m e t 并不广泛地支持这种从路由器出发来着手探查链路性能的 方式虽然在一些公共的标准中提供了对链路带宽查询的支持，例如：i c m p 的 r f d l l l 中说明了路由器应当支持t r a c e r o u t e 这个口选项，提供其出口链路的带宽 和m t u ，但由于多种原因，并非所有的路由器都提供这些信息。此外，由于网 络设备形态多样和数量庞大，使得几乎不可能在它们上面统一安装特定的监视程 序，而由于i n t e m e t 管理区域的异构性，未来也不太可能做到这一点 1 3 3 圭，被动测量、测量节点 主动测量、被动测量 顾名思义。主动测量技术是指主动地发送在测量过程中所需要的数据包，而 被动测量技术就只依赖于其他应用发送的数据包。因为往网络中注入的数据流不 仅会影响到我们自己的测量精度，也会对网络中其他用户的应用造成影响，所以 链路带宽测量的理想方法是：通过侦昕现有的通信来被动地测量；在这一方法不 可行的情形下，通过发送自己的探测数据包来主动地进行测量。主动测量技术可 以进一步定量地计算，为了测量带宽而发送了多少数据包到网络中去；至于其他 缘故( 例如铡量结果的分布或者时间同步) 而发送的数据包，由于依赖于一个特 殊的测量运算法则的执行，般并不做计算。 主动测量技术对网络有巨大的影响。为了过滤噪声，例如网络拥塞或者测量 主机的进程时序安排之类因素的影响，从而获得一个相对稳定的带宽测量值，一 些主动测量技术发送巨量的数据包到网络中去。大量探测数据包的注入可能会使 一个低带宽链路饱和，且拒绝为其他运行在同一主机上( 或是同一网络上的其他 主机上) 的应用去服务由于探测数据流将消耗大量i n t e m e t 链路带宽，因此这种 往网络中发送大量数据包的技术不可能被广泛地采用 主动测量技术与被动测量技术相比，前者的另一个优势是可以更快地提供更 精确的带宽测量结果假设两种技术同时需要n 个包来计算链路带宽。前者只需 要简单地发送n 个包，而后者则不得不被动地去等待，1 个包的产生如果被动测量 技术需要等待如此长时间，以至于一个或多个瞬时的网络状态已经改变了，那么 它的结果与主动测量方法的结果相比，精确度就会降低而且，如果被动技术持 续地发现无效数据流，并且网络条件在不断变化，那么它将永远不能收敛为一个 较精确的值。 此外，主动测量技术可以产生精确地测量链路带宽所需要的某种特殊类型的 数据流，例如，在2 3 节和第3 章中描述的技术需要一种背靠背( b a c k - t o - b a c k ) 【3 】 的数据包，而如果利用现存的数据流，这几乎不可能办到进一步研究的话，我 们可以发现，即使能够使用被动测量技术，因为必须捧除大小不合适的包和不响 应的包，所以往往也只能用到可用数据包的一个子集。这样，就不能再利用往返 时间进行测量了( 如果需要利用往返时间来代替单向延迟的话) 组播通信就是 常常不被响应的数据流( 确认将导致确认风暴) 即使数据包满足了大多数的要 求，对于理论模型来讲，可能很多性质也不是最理想的 测量节点 实际测试中，我们必须具体地在路径的某些节点上来测量信息( 例如；包的 源、目的、传输时间、抵达时间、大小等等) ，被测量节点就会与从源端到目的 端传输的某些数据流密切关联。譬如，我们可以在发送节点上，在接收节点上， 既在发送节点又在接收节点上，或者在沿着一条路径的所有节点上进行测量测 量节点的设置常常影响软件配置的难易和测量精确度的高低 显而易见，测量软件所需节点越少越容易配置例如，假设某种技术需要测 量i n t e m e t 上沿着一条路径的每一个路由器的一些数据包，这可能相当困难。退一 步说，就算实现了，配置过程也必定相当棘手即使不同的管理区域合作，也必 须要通过许多不同种类的路由器，那么，与不需要实现这些功能时相比较，路由 器的速度可能就会变慢。比较起来，仅仅在末端配置测量软件就比较容易实现， 而只需要在一个末端上配置就更加容易实现了 但是，当只在末端测量时，即使多次反复测量，与依赖于路由器的测量相比， 它的精确度也会降低例如，干扰数据流会干涉沿着一条路径的每一条链路带宽 的测量，而对末端来说，它们可能没有有效的信息去过滤噪声。 另一个局限性是，如果只能在一个末端上配置软件，这就决定了只能测量某 一个方向上的带宽比如说，存在a 、b 两个节点，只有a 这个末端能够被测量， 那么如果使用依赖于发送数据包的测量技术，就只能测量a b 这个方向上的链 路带宽；如果使用依赖于接收数据包的测量技术，就只能测量b a 这个方向上 的带宽。对于存在不对称路由或者不对称链路的路径，这个问题就显得很突出 1 4 面临问题 在链路带宽的测量中，我们面l | 缶着巨大的挑战闱： 1 ) 链路的异构性i n t e r n e t 上链路技术的异构性，意味着只能对即将进行的带宽 测量做最少的假定表1 1 中简单地说明了一些有关带宽和链路层协议的情 况从表中可以清晰地看到，带宽的变化达到了5 个数量级( 从1 4 k b s 到 i g b s ) ，因此，算法就不可以简单地假定带宽估计值会落入某个限定的区间 里( 例如1 - 1 0 0 m b s ) ，而链路的不对称性意味着我们必须在一条链路的两个方 向上独立地进行测量 名称带宽对称性无线链路层协议 以太网l g 龇对称 否髓e 8 0 2 3 z 8 0 2 3 a b 以太网 1 0 0 m b s 对称否 m e e 8 0 2 3 u 以太网 l o m b ，s对称否 e e 8 0 2 3 8 0 2 1 l bl l m b s对称是疆e 8 0 2 1 i b w a v e l a n2 m b s 对称是腑p e l a n a d s l 1 5 m b s ；1 2 8 k b s不对称 否a n 江p p p o e m o d e m5 6 k b ，s ：3 3 3 k b s对称否 v 9 0 p p p c d m a1 4 4 k b s 不对称 是 c d n 【a ，p p p 表1 1i n t e m e t 上的链路技术 2 ) 通信量的异构性既然链路带宽在很大幅度上变化着，那么链路上的通信量 也必然如此这就增加了另一个可能高度变化的延迟来源，它当然也会干扰 链路带宽的测量 3 ) 无路由器帮助。因为将要采取的这种从客户端出发来进行带宽测量的方法 ( 1 3 2 节) ，我们并不清楚沿着一条路径上的链路到底发生了什么情况，所 以只能够从观察出发进行推断，当通信到达客户端时是如何被扰乱的。然而， 在这条路径上的其他通信，虽然不在我们所期望测量的链路上，但也可能会 干扰测量，因此必须处理这些噪声。 4 ) 在发送方和接收方配置的困难。用户和机构可以轻而易举地在属于自己的客 户机上配置新软件，但是一旦涉及到需要在与他们通讯的另一端的客户机上 配置软件，因为另一端的客户机不一定也落入管理者的控制范畴，操作就会 很复杂。因此，链路带宽测量技术必须考虑到测量节点配置的问题。 5 ) 需要最小化测量探测包。往链路中发送大量的探测数据流，这首先就违背了 测量的意图通过链路更加有效地传输数据。在许多网络及其应用中，使 用被动测量技术或是发送少量探测数据流的主动测量技术，效果都会更好一 些然而，现存数据流的模式可能使测量变得困难或者几乎就不可能了，而 且只使用较少数量的探测数据包，不一定能够有效地过滤干扰数据流 6 ) 路由和链路改变i n t c m e t 上路由和链路的改变可能导致链路带宽测量变得无 效，而且路由和链路的改变，也违背了需要“最小化探测数据包”这个基本 出发点。例如，路由和链路在频繁改变，为了获得稳定精确的测量结果，就 必须更加频繁地测量，这肯定会导致探测数据流数量的大幅增长，而愈发无 法得到精确的测量结果 1 5 论文的框架 正是由于链路带宽测量在整个网络测试中的重要地位。也因为现有链路带宽 测量算法的种种问题，本课题对带宽测量进行了深入的研究 1 、现有的链路带宽测量技术，主要通过发送大量不同大小的数据包或者数 据包对，通过测量传输延迟来逐跳类推链路带宽，可以称之为变包测量 ( v a r i a b l ep a c k e ts i z e ，v p s ) d 2 本文在第2 章中对v p s 进行理论分析， 指出影响v p s 测量精度和有效性的主要因素是误差累积和干扰数据流的 影响，误差累积使得v p s 不适合多跳链路的测量；干扰数据流使得数据 包传输延迟增加，测量带宽值较实际链路带宽值偏大或偏小在此过程 中，修正了p a t h c h a r 算法所消耗链路带宽的一个公式。第2 章是对带宽 测量模型和各种技术的全面回顾与评价，详细地讨论了各种模型、技术 的优缺点以及数据过滤问题，并对单包技术和包对技术、包对技术之间 做了比较，这是我们进一步研究的基础。 2 、针对v p s 上述问题，相对有较大本质改善的基于多分组延迟模型的追尾 算法( p a c k e tt a i l g a t i n g ) 【l3 1 ，第3 章探讨了它的算法推导过程中的一个 有疑问的步骤基于消除这个有疑问步骤的想法，文中从两种链路带宽 测量思路出发，在第2 章对链路带宽测量的模型及其应用进行全面分析 和比较的基础上，构建了一个新的基于多分组延迟( m u l t i p a c k e td e l a y ) 的确定性模型n p t ( n e wp a c k e tt a i l g a t i n g ) 。新模型采用了差值思想，不 仅在理论上消除了追尾模型的那个有疑问的步骤，而且在实际应用中， 也可以抵消干扰数据流的影响。通过进一步研究，我们找出了此类方法 的本质，从而证明了新模型的正确性n f r 不需要对现存的路由器做修 正，在面临同样的问题时，也比现存的主动测量技术需要较少的探测数 据包，它适用于每个包交换，存储转发，f c f s ( f i r s t - c o m e ，f i r s t - s e r v e d ) 队列的网络第3 章是我们论文的理论核心部分 3 、在第3 章对新模型进行定性分析的基础上，第4 章中描述了链路带宽测 量工具d p r o b e 的实现细节，该工具可以测量一条路径上的瓶颈链路带宽 和所有链路带宽最后。使用d p r o b e 进行测试。这一章是我们的实现应 用部分 4 、第5 章中对全论文作出总结，并简明指出未来的研究方向 通过本课题的研究，我们所提出一种相对较为完善且占用较少网络资源的测 量链路带宽的新方法，相信这是一个具有稳固理论基础的、简洁的测量链路带宽 的新选择。 第2 章链路带宽测量技术回顾与评价 本章中，我们全面地讨论带宽测量的不同网络模型和各种实现工具。稍后我 们将要使用确定性模型( d e t e r m i n i s t i cm o d e l ) 来推论第3 章中的网络性质，接 着再使用这些性质，作为下一步测量的基础。 2 1网络模型 h l t c m c t 的不确定因素很多，影响带宽测量的因素也非常多要想对网络进行 精确的测量就必须先建立模型，虽然对不确定环境建立确定模型。这本身就是误 差源，但是只有建立了确定模型才能进行分析和设计参数。确定性模型是用数学 方程建立性能参数与设计变量的关系，用离散值表示各个设计变量，用给定的数 学函数计算单个给定值的结果，与之相对的是随机模型。现有的链路带宽测量方 法基本都是基于确定性模型。确定性模型从数学上来说比较容易处理，使得我们 能够找到一个解析解( a n a l y t i c a ls o l u t i o n ) 而不是一个数字解( n u m e r i c a l s o l u t i o n ) ，但是在确定性模型中，要求所有事件的发生必须是确定的，就不能考 虑到变数的影响，两在实际情况中，这个条件却很难被满足。i n t e m e t 上的很多因 素。例如路由器错误、路由切换、干扰数据流的影响、暂时的链路失效，都是很 难用确定性模型去描述的。常用的一种技术是；假定所有的设计变量取其极限值， 再由此获得性能参数值。如果我们从某些角度出发，加上某些限制条件或者假定， 依然可以使用确定性模型来描述和解决带宽测量中的这些问题。 下面，我们将要讨论单包( s i n g l ep a c k e t ) 模型( 2 1 1 节) ，包对( p a c k e tp a i r ) 模型( 2 1 2 节) 和多分组( m u l t i - p a c k e t ) 模型( 2 1 3 节) 所有这些模型均基 于以下假定： 1 ) 包交换网络包交换网络中的交换模式决定了每个数据包如何区别于其他包进 行传递，与此相对的是流交换网络即使h 她m 赜局部上在运行着流交换网络( 例 如电话网) ，整体看来，它仍然是一个包交换网络。 2 ) 存储转发交换存储转发( s t o r e - a n d - f o r w a r d ) 交换意味着在转发每个包的第 一个比特( b i t ) 前必须接收到包的最后一个比特，与此相对的是直通式 ( c u t - t h r o u g h ) 交换存储转发交换比直通式交换引入了更多的延迟，但是却更 易于实现，这也是i n t e r n e t 应用最为广泛的方式 3 ) f c f s 和丢尾捧队策略捧队策略控制着数据包如何在队列中移动和被丢弃。 最普通的服务策略是先来先服务( f i r s t - c o m e f i r s t - s e r v e d ，f ( 、f s ) ，即路由器将根 据发送包抵达的次序工作最普通的丢弃策略是丢弃尾部，即队列大小超过极限 时，最后抵达的数据包将被丢弃 4 ) 无于扰数据流干扰数据流会导致测量数据包以不可预测的方式排队本节中 我们描述的模型均假设不存在干扰数据流。然后，通过过滤适用于模型的数据和 模型产生的结果( 2 3 节和第3 章、第4 章) 再来排除干扰数据流的影响在这些 理论模型里，均假定了网络中其他数据流的分发方式：特别的按照抵达时间和包 大小进行排队然而，这样的分发方式在i n t e m e ti - 不可能总是有效的。 5 ) 在网络层上为单信道链路数据包经过一条单信道链路时，传输延迟等于包的 大小除以该链路的带宽相应的，在一条多信道链路上，因为每条信道都有一个 独立的带宽，则链路的总带宽是每条信道的带宽之和，所以，数据包通过一条多 信道链路时的传输延迟，等于包的大小除以包通过的那条信道的带宽( 而不是链 路总计带宽) 。这个假定只涉及链路在网络层的表现形式，而不涉及它在低层的 实现方式 多信道链路的例子是b r ii s d n ( 基础速率综合业务数字网) 链路( 由两个 并行的6 4 k b s 的信道组成) 【h 1 和c i s c o 的e t h e r c h a n n e l ( 由任何数量的以太信道组 成) 【搭】，这些链路可能把数据包重新排序。因此导致不必要的t c p 重传和t c p 吞 吐量的降低。 本节中的模型使用图2 1 中所示的术语。链路有西的带宽和d ，的延迟。存在 九条链路。包肽小为s 且存在p 个包。 包 主机 图2 1 网络模型 1 2 路由器 以下为论文中用到的变量定义： m 路径的跃点长度； k ：瓶颈链路； 西( s ) ：链路哟固定延迟； d ( s ) ：包括链路埴到链路，的固定延迟的和： 岛c o p s ) ：链路啪带宽； ，( b i o ：包厢q 大小； 露( s ) ：第豇个包完全到达第，条链路之前的那个路由器的时间； 苏( s ) ：第蠡个包离开节点满时刻； a f ：。( s ) ：包脐毗：艺间的间距； 计( s ) ：第七个包在第，条链路之前的那个路由器上的排队时间 2 1 1 单包模型( s i n g l ep a c k e tm o d e l ) b e l l o v i n 1 6 1 ，j a c o b s o np ：q 和d o w n e y 1 3 1 使用蚴p 融的包延迟模型来计算 链路带宽我们称之为“s i n g l e p a c k e t ”，是因为它假设从源端到目的端只有一个 简单的数据包在传输。这种技术的出发点是：通过观察发现，慢链路比快链路传 输数据包的时间长它的基本思想是：当数据包在路径上传输时，所耗费的时间 由包在路由器上的排队时间、包的传输延迟( t r a n s m i s s i o nd e l a y ) 以及包在所有 链路上的等待时问( 1 a t e n c y ) 三个部分组成f 1 9 】。包的传输延迟由路由器在缓冲区 中复制分组和从链路把分组发送出去这两部分时间组成。等待时间是由信号在线 路上以光速传输所消耗的时间、路由器进行路由选择的时间以及路由器处理每个 分组所需要花费的固定时间这三块开销组成。单包模型需要一些假定 单包模型等式 单包模型使用如下等式( 变量在表2 1 节中已定义) ： 疗= 露+ i 芝- o ( k 善+ d 0 | ( 2 1 ) 这里，是包在第阶节点前通过第卜l 条链路所需的时间。它与本章后面的模 ，j 型类似，均假定传输延迟与包大小成线性正比，而与链路带宽【6 ，) 成线性反比， 实际情况可能并不是这样的，比如路由器处理1 2 8 字节的包的时间与处理1 2 9 字节 的包的时间与字节大小不一定具有线性关系，当然这种影响微乎其微而常常可以 被忽略它还假定没有负载相关延迟。即只存在负载独立延迟。负载相关延迟是 由其他流中通信量所引起的延迟，也就是假设包经过另外一个无负载网络时所花 费的最小时间( 或最佳情形延迟) 。负载独立延迟则是由每条链路上的传输延迟 陛1 和固定延迟0 ，) 两部分组成。前者传输延迟是随包的大小而变化的延迟成分， l 刈 包括数据包通过链路的传输时间和路由器可能引起的任何与包长相关的延迟时 间；而后者固定延迟对一条链路来说则是常数，是包延迟的一个组成成分固定 延迟的来源之一是电磁波沿着媒介传播的速度而导致的( 光) 传播延迟 图2 2 详细地表明了单包模型中的时间情况。 图2 2s i n g l ep a c k e t 模型时间图引自【1 3 】 单包模型本身有相当多的局限性。这个模型将传输延迟和固定延迟均归因于 链路而不是路由器。如上描述，路由器和链路它们都会产生延迟结果，当使用 单包模型来模拟一个低效率的路由时，路由器的延迟就被归因于前面的链路和紧 跟路由器后面的链路了。本章中后面所提及的模型也有这个限制。 另一个局限性是假设负载独立的延迟要么与包大小线性相关，要么是固定 的，丽通过一个无负载路由器的延迟可能会以其他的方式变化比如说，路由查 找时间可能不是常数，它依赖于数据结构和存储技术；经过内部交换结构的时间 可能是不确定的，它依赖于仲裁方案；因为分割的复杂性、内存刷新时间、内部 处理的原理，缓冲时间也可能与包大小是非线性相关的 此外，存在非对称链路的问题，也就是i c m p 包返回的路径和测量数据包发 出的路径不同，这个时候的测量结果就会有问题，此问题在参考文献 2 0 】中被部 分的解决了 有关误差传递问题，也就是前一条链路的测量误差会