（通信与信息系统专业论文）ip网络带宽测量技术研究.pdf

西南科技大学硕士研究生学位论文 第1 页 摘要 随着i n t e r n e t 持续高速的发展，人们开始对其服务质量、可靠性和效率 进行重新思考并提出解决方案，网络测量技术提供反映i p 网络运行状况指 标，并能及时发现网络异常，为网络故障发现和定位提供依据。无线网络应 用的发展很快，对无线网络带宽测量研究文献很少，无线网络带宽测量技术 研究更具挑战性，具有重要理论意义和实际应用价值。 本文首先讨论了i p 网络瓶颈带宽的包对和包列间隔算法，深入分析了 不同测量样本与瓶颈带宽的关系。在对传统测量样本过滤算法研究的基础 上，提出一种动态窗宽瓶颈带宽过滤算法，该算法根据初始探测的带宽范围 和测量样本的波动值确定核估计的窗宽，测量样本越分散窗宽越大，保证了 计算精度，减小了估计时间。 现有的测量有线可用带宽的方法主要有探测单向延迟变化和包间隔变 化两种方法。本文对包间隔递增搜索平衡点的算法进行了改进，采用双向搜 索的方式，这样测得平衡点更加准确。 比较了有线网络与无线网络传输模型的区别，分析了有线可用带宽模型 在无线传输模型下的不适用性。进一步通过仿真研究，说明了在无线网络中 探测包包长对无线信道的最大吞吐量的影响很大。发展了一种累积分布统计 测量无线带宽的方法，研究结果表明中等背景流量下测量是精确的，但是小 部分探测包有可能在连续的背景流量中插入，导致单向延迟样本变小和高估 可用带宽，背景流量越大发生的机率越大。对比分析了泊松分布和均匀分布 作为探测包发送时间间隔的测量结果，用泊松分布发包更附合实际网络背景 流量发送时间，真实地反映出可用带宽。 关键词：可用带宽瓶颈带宽核估计累积分布 西南科技大学硕士研究生学位论文第页 a b s t r a c t w i t ht h er a p i dd e v e l o p m e n to fi n t e r n e t ，i t sq u a l i t yo fs e r v i c e ，r e l i a b i l i t y a n de f f i c i e n c ya r et a k e ni n t oa c c o u n to v e ra g a i n ，a n dl o t so fs o l u t i o n sa r e b r o u g h tf o r w a r d o n eo ft h e mi sn e t w o r km e a s u r e m e n t ，w h i c hc a ng i v em a n y q u a n t i t a t i v em e t r i c sr e f l e c t i n go p e r a t i n gs t a t u so fi pn e t w o r k ，a n dd i s c o v e r i n g n e t w o r ko u t l i e ri nt i m e t h ew i r e l e s sn e t w o r ka p p l i c a t i o ni sr a p i d l yd e v e l o p e d ， b u t t h er e s e a r c hp a p e r sa b o u tw i r e l e s sb a n d w i d t hm e a s u r e m e n ta r ef e w , t h e r e s e a r c ho nw i r e l e s sb a n d w i d t hm e a s u r ei sm o r ec h a l l e n g e ，i ti ss i g n i f i c a n tf o r t h e o r e t i ca n da c t u a la p p l i c a t i o n f o rb o t t l e n e c kb a n d w i d t hm e a s u r e m e n to fi pn e t w o r k ，t h i sp a p e rf o c u so n p a c k e tp a i ra n dp a c k e tt r a i na r i t h m e t i c ，d e t a i l e d l ya n a l y z i n gr e l a t i o nb e t w e e n m e a s u r e m e n ts a m p l ea n db o t t l e n e c kb a n d w i d t h b a s eo r r e s e a r c h i n go n c o n v e n t i o n a lf i l t r a t i n ga r i t h m e t i c ，t h i sp a p e rp r e s e n td y n a m i cw i n d o wf i l t r a t i n g a r i t h m e t i c t h i sf i l t r a t i n ga r i t h m e t i cc a l c u l a t ew i d o ww i d t hb yi n i t i a lp r o b i n g b a n d w i d t hb o u n da n dr a n g eo fb a n d w i d t hm e a s u r e m e n ts a m p l ef l u c t u a t i o n ，t h e m e a s u r e m e n ts a m p l em o r ed i s p e r s i v e ，t h ew i d o ww i d t hm o r ew i d e r ，i te u s u r e p r e c i s i o no fs a m p l ef i l t r a t i n ga n da p p r o p r i a t ec a l c u l a t i n gs p e n d i n g a tp r e s e n t ，t h em a i n l ym e a s u r e m e n ta r i t h m e t i ca b o u tw i r e dn e t w o r ki s d e t e c t i n gc h a n g e so fo n ew a yd e l a ya n di n t e r v a lo fp a c k e t t h ea r i t h m e t i ca b o u t s e a r c h i n gb a l a n c ep o i n tb yi n c r e a s i n gp a c k e ti n t e r v a li si m p r o v e di nt h i sp a p e r , w eu s eb i d i r e c t i o n a ls e a r c h i n ga r i t h m e t i cw h a ti sm o r ee x a c t b yc o m p a r i n g w i r e dn e t w o r ka n dw i r e l e s s n e t w o r k ，t h ec o n v e n t i o n a lw i r e d a 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 o d e lb ef i n dn o ta p p l y i n gf o rm e a s u r i n gw i r e l e s s a v a i l a b l eb a n d w i d t h b ys i m u l a t i n g ，w ef i n dt h a tp a c k e ts i z eh a v er e m a r k a b l e i n f l u e n c eo nm a xt h r o u g h p u ti nw i r e l e s sn e t w o r k b ys i m u l a t i n gc u m u l a t i v e d i s t r i b u t i o na r i t h m e t i cw h a ti sb eu s e df o rm e a s u r i n ga v a i l a b l eb a n d w i d t h ，w e f i n di ti sp r e c i s i o ni nm o d e r a t eb a c k g r o u n dt r a f f i c ，b u tas m a l lp a r to fp r o b i n g p a c k e tw i l la r r i v ee x a c t l yd u r i n gt h ei d l ep e r i o db e t w e e ns u c c e s s i v ec r o s s t r a f f i c p a c k e t s ，w h a tr e s u l t i no n ew a yd e l a ys a m p l ed i m i n i s h i n ga n do v e r r a t i n g a v a i l a b l eb a n d w i d t h ，t h em o r eb a c k g r o u n dt r a f f i ct h em o r er a t i o w ea d o p t p o i s s o nd i s t r i b u t i o na n de v e nd i s t r i b u t i o na ss e n d i n gt i m ei n t e r v a lo fp r o b i n g p a c k e t i n s i m u l a t i o n ，b e c a u s es e n d i n gt i m ei n t e r v a lo fa c t u a ln e t w o r k b a c k g r o u n dt r a f f i ci sp o i s s o nd i s t r i b u t i o n ，s oa d o p tp o i s s o nd i s t r i b u t i o nf u r t h e r 西南科技大学硕士研究生学位论文第1 i l 页 p o s s i b l er e f l e c ta c t u a la v a i l a b l eb a n d w i d t h k e yw o r d s ：a 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 kb a n d w i d t h ； k e r n e ld e n s i t ye s t i m a t i o n ；c u m u l a t i v ed i s t r i b u t i o n 独创性声明 本人声明所呈交的论文是我个人在导师指导下( 或我个人) 进行的研究 工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外， 论文中不包含其他入已经发表或撰写过的研究成果，也不包含为获得西南科技大 学或其它教育机构的学位或证零而使用过的材料。与我一同工作的同志对本研究 所做的任何贡献均已在论文中作了明确的说明并表示了谢意。 一研彳嗍 ) 9 1 厂、7 关于论文使用和授权的说明 本人完全了解西南科技大学有关保留、使用学位论文的规定，即：学校有权 保留学位论文的复印件，允许该论文被查阅和借阅；学校可以公布该论文的全部 或部分内容，可以采用影印、缩印或其他复制手段保存论文。 ( 保密的学位论文在解密后应遵守此规定) 龇桐彳一各嘲帆z 卯 西南科技大学硕士研究生学位论文第1 页 1 绪论 网络技术的出现对现代科技与世界经济的发展以及人类生活产生了巨 大而深刻的影响，其发展之迅猛是其他科学技术所不能及的。计算机网络是 一些互相连接的、自治的计算机的集合。在所有计算机网络中，i p 网络占主 导地位，9 0 以上计算机网络运行i p 协议。 i p 网络性能测量技术对网络技术的发展和应用起着十分重要的作用，对 网络进行研究的最终目的是为了建立商效、稳定、安全、互操作性强、可预 测以及可控制的网络，网络测量是获得第一手网络行为指标和参数的最有效 的手段。在对网络进行测量和测试的基础上建立网络行为模型，并用模拟仿 真方法搭建从理论到实践的桥梁，是理解网络行为的十分有效的途径。 由于i p 网络在计算机网络中占主导地位，i p 网络带宽测量是网络测量 领域中的研究热点，因此i p 网络测量具有重要的理论意义与实际应用价值。 1 1i p 网络性能测量技术 1 1 1i p 网络性能测量技术概述 网络测量是指遵照一定的方法和技术，利用软件和硬件工具来测试或验 证表征网络性能的指标的一系列活动的总和。网络测量根据内容的不同主要 分为网络拓扑测量( 主要是了解网络拓扑结构，用以指导资源调节和流量分 配) ，网络性能测量( 主要是通过监测网络的端到端的时延、抖动、丢包率 等特性，了解网络的可达性、利用率以及网络负荷等) ，网络流量测量( 主 要是对网络数据流的特性进行监测和分析，以掌握网络的流量特性，如协议 的使用情况、应用的使用情况、用户的行为特征等) 。 按测量点的分布可分为：单点测量、多点测量，大部分的网络都采用分 布式多点测量。按与被测网络的关系可分为：合作测量、非合作测量。合作 测量对网络运营者来说，能够掌握网络的运行状况、找出瓶颈、业务分布情 况等，以便有效地管理网络、充分利用网络资源。非合作测量是指被测网络 不乐意被别人测量，测量目的是窥探对方网络的情况，这在军事上有非常重 要的意义。 网络测量的方法有两种：主动测量、被动测量。主动测量是将探溺分组 注入网络进行测量，如通过一端发送u d p 分组，而在另一端接收该分组， 可以测量端到端的延时、丢包率；被动测量是在网络的某处布置数据采集器， 收集流过该处的网络业务流，进行分析、提取业务特征，获得性能数据。 西南科技大学硕士研究生学位论文第2 页 i p 网络指在网络层上运行i p 协议的网络，如果在传输层主要运行t c p 和u d p 协议，一般称t c p i p 网络。 无线局域网的室内i p 接入方案，指在网络层上运行i p 协议，传输层主 要运行t c p 和l i d p 协议，链路层采用8 0 2 1 1 协议。这样的网络称为无线i p 网络。 无线i p 网络系统将是一个集成广播电视网络、无线蜂窝网络、无绳网 络、无线局域网( w l a n ) 、短距离应用的蓝牙等系统和固定的有线网络为一 体的结构，各种类型的接入网都能无缝的接入基于l p 的核心网。 无线i p 网络发展的最重要的、目前发展最快的技术就是无线局域网技 术，无线局域网提供了室内i p 接入的方案。无线局域网是指采用无线传输 媒体的计算机局域网，链路层采用的标准是i e e e 8 0 2 1 1 。1 9 9 0 年i e e e 8 0 2 标准化委员会成立8 0 2 1 1 无线局域网( w l a n ) 标准工作组，并于1 9 9 7 年 6 月公布了i e e e 8 0 2 1 1 标准，定义了物理层和媒体访问控制( m a c ) 规范， 允许无线局域网及无线设备制造上建立互操作网络设备。无线局域网与有线 局域网的主要区别在于传输媒体与m a c 协议，它可以与有线网络互连使用 或单独使用。 i p 网络性能测量就是对i p 有线和无线网络的各项性能指标进行测量， i p 网络性能指标主要有时延、时延抖动、丢包率、瓶颈带宽、可用带宽、吞 吐量等 1 1 2l p 网络性能指标的定义 链路带宽：链路带宽指的是端主机可通过一条链路传送的最大数据传输 速率。链路带宽可能受到它所连接的路由器的限制，因此不是链路本身的固 有属性，而是由链路和连接的路由器共同决定的。链路带宽受下层的物理介 质实现技术、链路层头部开销和介质访问控制协议以及路由器转发能力等因 素影响。 瓶颈带宽：假设一条h 跳的路径，链路带宽可以表示为b = c o ，c 1 ，c h 。 其中c i ( i = 0 。h ) 是每一跳的链路带宽。这条路径中的最小的链路带宽 c b 。= m i n c i ，i = l 2 n ) 即为瓶颈带宽。只要网络中端到端路径的路由不变， 瓶颈链路带宽也保持不变，与网络中的背景流量无关。 可用带宽：可用带宽是在不影响现有背景流量的数据传输速率前提下， 端到端路径可提供最大数据传输速率，即未被背景流量占用的剩余带宽。对 于一条包含n 条链路的路径，c i 表示链路i 的物理带宽，u i 表示链路i 的利 西南科技大学硕士研究生学位论文第3 页 用率，刚可用带宽为c o v = m i n c i ( 1 - u i ) ，i = 1 ，2 ，n 。 单向延迟：假设数据包源地址s r c 和目标地址d s t ，在t 时刻在源地址 发送数据包p ，在t + a t 时刻d s t 收到该数据包的最后一个b i t ，则单向延 迟为a t 。延迟直接影响应用的性能，当端到端的延迟大于某个阈值时，应 用往往会因为超时而失效。并且延迟抖动的不确定使得实时应用动行根本不 可能。延迟一般由三部分组成：传输延迟、传播延迟以及排队等待时间，因 此测量得到最小延迟的值一般仅仅包含传输延迟和传播延迟。只有在背景流 量非常小的测量环境下才能得到最小延迟。延迟越大越说明数据包在路径上 的排队等待时间越长，路径上拥塞越大。测量单向延迟因为存在两端时间同 步的问题而难度远大于测量双向延迟。测量单向延迟的意义在于：i n t e r n e t 中路径往往是不对称的，或者即使路由是对称的但双向具有不同的性能特 征，或者有此应用的性能只依赖于单向延迟( 使用t c p 进行文件传输) 。相 应地，单向延迟指标可分为单次测量单向延迟指标和多次采样统计测量延迟 指标两种。 单向丢包：网络发生拥塞使得路由器缓存溢出或数据包延迟过大而数据 包丢失。丢包进一步造成数据包在网络中重传，网络负载增大，性能恶化。 和单向延迟与双向延迟比较相同的原因，双向丢包率并不能代替单向丢包率 测量。 双向延迟：网络应用往往需要客户机和服务器之间发送请求和应答，以 完成信息传递。网络中路由不对称性的存在，使得只有测量双向延迟才能得 到完成一次握手不同路径的总延迟。 在i p 网络性能测量中，网络带宽测量是很重要的部分，主要测量的指 标包括网络瓶颈带宽和可用带宽。瓶颈带宽反映了路径的静态特征，而可用 带宽真正反映了在某一段时间内链路的实际通信能力。因为网络运营商需要 了解网络带宽情况来指导网络运维、网络规划、瓶颈故障检测、拥塞控制、 接纳控制以及异构无线网络的切换、性能优化等；个人用户则希望了解当前 网络的带宽状况，因此对网络带宽测量的研究有着重要的意义 1 2i p 网络带宽测量技术的研究现状 随着i n t e r n e t 的应用日益广泛，虽然主干带宽不断增加，但是网络性能并 没得到成倍的提升。虽然一部分原因是因为应用业务量也在不断增加，但是 更重要的是网络容量设计、网络资源分配管理和应用设计的问题。因此优化 西南科技大学硕士研究生学位论文第4 页 带宽使用和分配是提升网络性能首要解决的闯题。许多网络资源监控系统利 用网络带宽进行全网范围的网络容量和业务规划，减少网络瓶颈、均衡业务 流量配置，提升网络性能，因此带宽测量是很重要的。 近年来，以i t u t ( 国际电信联盟远程通信标准化组) 提出的通用电信服 务评估标准为基础，s l a ( 服务等级协议) 作为服务提供商与用户签署的法律 文件保证服务质量，在业界得到广泛的关注。随着关键的商业活动对服务应 用的依赖程度的不断增加，s l a 已逐渐成为服务系统中不可分割的一部分， s l a 的实施无疑对传统的服务理念和管理方式提出了新的挑战。以i p 业务 为核心的新一代的电信网管理变得更加复杂，更加强调应用层服务的可用性 和网络性能的确定性。带宽作为i s p 与用户共同关心的网络资源，直接反映 了网络的性能状况和业务保证能力。带宽测量成为了解连接性能状况，发现 网络瓶颈，网络资源分配和负载均衡的重要手段。带宽测量技术成为实现网 络运行状态监控，网络问题检测等网络管理功能和拥塞控制等网络控制机制 的关键技术。 关于瓶颈带宽测量方法主要分为单数据包方法、包对和包列方法、数据 包尾随方法。其中单数据方法对网络注入流量多、干扰大、测量结果不准确； 数据包对方法实现上存在的问题是很难控制背靠背数据包发送的时间精度， 而由于背景流量的存在，必须使用优良的过滤算法，否则很难保证对由不同 网络连接构成路径估计的健壮性。 目前国内外研究带宽主要集中在有线的i n t e r n e t 网络，对无线网络研究 相对不多。2 0 0 0 年k l a i 提出了n e t t i m e r t l 】测量算法，这种算法主要采用包对 模型，提出了一种优良的核密度过滤算法，可把大部分受背景流量干扰得到 的测量数据给滤除。美国学者v a nj a c o b s o n 于1 9 9 7 年提出了p a t h c h a r ! ”】算 法，这种算法容易受背景流量干扰，向网络注入的包多，好处是只用一端安 装此软件便可以测量。2 0 0 1 年c d o v r o l i s 提出了p a t h r a t e 2 8 】测量算法，这种 算法是基于对于网络瓶颈带宽的一种统计分布模型，能在背景流量较大的情 况下准确地测出瓶颈带宽。 在可用带宽方面文献【2 】中所提到的c p r o b e 可以说是第1 个用于测量可 用带宽的工具。c p r o b e 用包队列代替了包对，通过一组首尾相连的包队列中 第1 个和最后一个报文的到达时间以及报文长度来计算可用带宽。文献【3 j 中 所提到的p i p e c h a r 采用的也是相似的方法。然而，文献【4 】中的研究表明， c p r o b e 测量的并不是可用带宽，而是另外一种完全不同的参数。目前称为 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 ) 。文献【5 i 中提出的t o p p ( t r a i n so f p a c k e tp a i r s ) 西南科技大学硕士研究生学位论文第5 页 的基本思想是：以递增的速率向目的节点发送包对组成的队列，根据不同包 对的输入输出速率之间的关系来判断可用带宽。文献 6 1 中所提到的 s l o p s ( s e l fl o a d i n gp e r i o d i cs t r e a m s ) 基于的原理是：当发送速率高于可用带宽 时，报文的单向延迟会有上升的趋势。基于s l o p s 的思想实现了可用带宽 测量工具p a t h l o a d 。虽然t o p p 和p a t h l o a d 可以测出相对比较准确的可用带 宽，但是它们都需要发送大量的探测报文。在无线网络等带宽非常有限的网 络环境中，这么多的探测报文完全可能造成网络的阻塞。另外文献中的研 究表明，p a t h l o a d 会高估可用带宽。文献1 7 】中提出的i g l ( i n i t i a lg a pi n c r e a s i n 曲 和p t r ( p a c k e tt r a n s m i s s i o nr a t e ) 通过发送一系列报文间隔逐渐增大的包队 列，并探测输出间隔和初始间隔的差别来确定可以用来计算可用带宽的包队 列。然而文献【8 1 中的研究表明，该算法在网络的利用率较大时对带宽变化的 反应非常迟钝，提出的s p r u c e 和i g i 一样，都是基于探测间隔模型的，但其 测量所需的探测流量要高于i g i 。 当宽带主干网建成之后，再通过城域网或局域网向社区和用户延伸，由 于用有线网络接入成本高、施工复杂。无线局域网成本低、施工方便，得到 运营商广泛青睐，而且大多数都集中于商务客人经常出入的热点地区，如机 场、商务酒店、会展中心、写字楼等地。无线局域网是以后接入网发展的重 点，所以对无线局域网带宽进行测量，以满足用户的服务质量要求非常重要。 随着现代通信技术的进步，人们对移动通信需求的不断增加，移动通信 系统，如个人笔记本计算机，掌上型p d a 设备等得到了迅速普及。在接入 网中运营商需要知道无线可用带宽是否可以满足用户上网要求。战场上部队 快速展开和推进、发生地震或水灾后的营救。这些场合的通信不能依赖于任 何预先架设的网络设施，需要高可靠性的无线通信。无线通信受电磁干扰， 地形干扰或天气影响较大，特别是在a d h o c 网络中，网络带宽非常有限，需 要合性地利用带宽。 无线网络传输不是先进先出的包转发模式，而是分布式竞争机制。无线 网络接入协议的特点还体现在网络吞吐量上，由于无线网络数据帧的碰撞会 导致所有的发送方都要退避一段时间，然后重新发送数据，这就必然对系统 的吞吐量产生影响。 由于无线网络的复杂性，目前国内外对无线可用带宽的研究很少，研究 如何减小环景干扰、符合无线传输模型的可用带宽测量方法有重要意义。 西南科技大学硕士研究生学位论文第6 页 1 3网络带宽测量技术的关键问题 对于带宽测量方法而言，主要可以分为主动测量和被动测量。主动测量 是将探测分组注入网络进行测量，如通过在一端发送u d p 分组，而在别一 端接收该分组。被动测量是在网络的某处布置数据采集器，收集流过该处的 网络业务流，进行分析、提取业务特征、获得性能数据。 目前的带宽测量方法仍未形成一个公认的高效精确的测量算法，这在一 定程度上也导致了带宽测量本身很难标准化，并得到广泛应用。带宽测量亟 待解决的关键问题有： 1 1 带宽定义与分类的标准化，以及带宽测量指标和方法的标准化； 2 1 能够动态实时地对网络端到端路径进行探测，适应不同的网络，不会 向网络注入太多的测试流量，同时不会影响到带宽估计的精度。 3 1 对于可用带宽来说，因为是随时间动态变化的，能够实时灵敏地跟踪 到可用带宽变化。 4 ) 因为现在网络接入点已经向无线发展，传统的有线带宽测量算法有很 大的局限性，所以如何提高在无线网络下的抗噪声能力，精确测量带宽成为 难点。 1 4 课题研究内容及章节安排 本文即重点研究l p 网络瓶颈带宽与可用带宽的测量方法。 对现有的包对和包列算法进行了深入分析，在此基础上改进了包对和包 列算法的过滤算法，经n s 2 仿真【4 5 】分析，比起原p a t h r a t e 算法中采用直方图统 计的方法提高了精度，同时由于采用动态可变窗宽，使计算量更加合理。改 进了可用带宽i g i 算法中的搜索平衡点的方式，使其按正反向搜索，提高了精 度。讨论了无线网络与有线网络的传输模型区别，仿真了最新的单向时延统 计测无线带宽算法，对其探测包的大小和发包时间分布进行了深入分析，得 出用小的包并且发送时间服从泊松分布时更能精确测量出可用带宽。 本文结构组织如下： 第一章：介绍课题的研究背景以及i p 网络性能测试的研究意义与现状， 并对i p 网络带宽测量进行概述。 第二章：深入分析瓶颈带宽的包对和包列算法在各种情况下的测量样本 西南科技大学硕士研究生学位论文第7 页 分布，并在此基础上提出了对于包对和包列算法新的过滤模型。 第三章：针对可用带宽的测量方法进行了分析，对i g i 算法提出了正反 向搜索平衡点的改进。 第四章：分析了无线网络与有线网络的区别，对无线情况下载荷用不同 大小包长时的最大吞吐量进行了仿真分析，发现随着载荷包长的增大，其最 大吞吐量也增大。 第五章：编程实现了瓶颈带宽测量软件和网络评估软件。 结论部分总结本文工作，并展望将来进一步的研究工作。 西南科技大学硕士研究生学位论文第8 页 2 网络瓶颈带宽测量算法研究 本章主要针对i p 网络瓶颈带宽的包对和包列测量模型，分析了测量样本 在各种不同测量包长、不同背景流量下的分布情况。在对现有的瓶颈带宽过 滤算法研究的基础上，提出了一种基于动态窗宽的核估计瓶颈带宽测量算 法。 2 1 单数据包模型 单数据包模型假设没有其它流量引起的与负载相关的延时( 排队延时) 。 单数据包模型的局限性在于将数据包的传输延时和固有延时的决定因素归 结到链路而不是路由器，但实际上路由器和链路都会带来延时。 p a t h c h a r 算法【1 3 1 是一种单数据包算法，由美国学者v a nj a c o b s o n 于1 9 9 7 年4 月提出的，该算法通过向网络发送不同大小的测量分组，在发送端测量 该分组的r t t ( 往返时延) ，根据分组大小与r 盯时延变化的规律来推算出分 组所通过链路的带宽。p a t h c h a r 算法只需在一个终端主机中安装一些测量软 件就能够测量出一条路由中各段链路带宽的算法。 2 1 1算法原理 p a t h c h a r 算法是一种单数据包方法，它向路径逐跳的发送不同大小的 i c m p 数据包，利用t t l 测量其往还时间并计算每跳带宽。 用乃表示分组到第i 个节点的l 唧时延，s 表示测量分组的大小，k 表 示每一跳的链路带宽，那么当i = 2 时，有 。笙+ 笙+ c 删( 2 1 ) k 上式中，c o n s t 是一个依赖于i 的常量，它是传播时延和排队时延的总和。 在假设模型中我们假定测量时链路中无其他流存在，因此排队时延为零。于 是有 l 套瞢一骞号+ 一 亿2 ， 上式中，对于特定的k ，可视乃为s 的线性函数，设岛表示线性函数 乃佃) 的斜率，那么 t 。荟毒4 甸一k 。青 西南科技大学硕士研究生学位论文第9 页 所以 k = 去 s ， 从式( 2 3 ) 中可知，要想得到雎，首先必须求得岛。为得到岛需要不断地 向网络发送大小不同的测量分组，在发送端测量每个分组的r t t 时延死。 这样，我们就得到了一系列的样本点( s ，t i ) ，通过s 与乃的线性关系，我们 就可以根据这些样本点绘出一条直线，直线的斜率就是所求的岛，从而可以 进一步算出被测链路的带宽k 。 我们在模型中已假定，测量时被测链路中无其他的流存在。这种假设在 实际中并不总是存在的，即使是在网络轻载的情况下，测量也会受到一些干 扰流的影响。因此，该算法需要向网络发送大量的测量分组以取得尽可能多 的( s ，t i ) 样本点来保证岛的准确性，从而保证被测链路带宽k 的精确度。所 以，p a t h c h a r 算法在测量链路f f 的带宽时，首先发送p 次大小为6 4 字节的分 组，然后再发送p 次大小为( 6 4 + 3 2 ) 个字节的测量分组。如些反复，每种大 小的测量分组以3 2 个字节递增，直到测量分组的大小超过该路由的最大传 输包长为止，并在发送下一个测量分组之前必须收到前一个测量分组的应 答。 每跳对应不同大小数据包中分别选择最小的往返时间值( 最小往返时间 过滤1 ，进行最小二乘拟合，如图2 1 所示： p a c k e ts i z e 图2 - 1最小二乘拟合求k i f i g 2 1 l e a s ts q u a r e se s t i m a t ef o rk l 西南科技大学硕士研究生学位论文第1 0 页 2 1 2 性能分析 从上一节所描述的算法可知，p a t h c h a r 算法需要发送不同大小测量分组 的种类数是： i ，。m 一1 3 2 对以太网来说，m ( 最大传输包长) 是1 5 0 0 字节，于是需发送分组的种类 数w 为4 5 。此外，对于每一跳不同大小的测量分组每一次要发送p 次，p 是测量精度因子。显然，p 越大，测量结果就越精确，但相应的测量时间和 所耗费网络资源就越多，默认配置下p = 3 2 。因此运用p a t h c h a r 算法测量一 条路由上所有链路的带宽所需的总时间为： n + l f p w r , 钉 假定任何一个节点收到测量分组后能够立刻发出响应，且发送端收到响 应后立刻发送下一个测量分组。那么对以太网中的一条路由，若网络跳数 n = 9 ，则平均r t t 时延为l o r e s ，则使用p a t h c h a r 测量算法完成每段链路带 宽的测量将耗时1 4 4 s ，这显然是太慢了。当然可以通过减少每种大小分组的 发送次数来提高测量速度，但这是以牺牲精确度为代价的。 而且，p a t h e h a r 算法将会消耗大量的网络带宽。设在测量某一段链路带 宽时的平均分组大小为p 。i ：。： h。64+(64+32)+(64+32x2)+(64+32(w-1)x8 3 2 xvk 。包8 所消耗的平均带宽为： 平均数据包大小 ( 。2 4 ) 连接往返传输延时正 对于一个路由器节点的以太网，若l u t 时延为1 m s ，则消耗网络带宽 为6 1 4 4 m b i t s ，这对一个l o m b i t s 的以太网来说影响是巨大的。而且p a t h c h a r 算法为测量每条链路带宽总要向网络发送的测量包为 p o + 嚼【6 4 + 3 狮一1 ) 】1 1 咖o + 项w + 3 ) 2 - 5 西南科技大学硕士研究生学位论文第1 1 页 对于一个网络跳数n = 9 的以太网来说，p a t h c h a r 总共要向网络注入约 l o m b 的数据量，而不管链路带宽是多少。因为它的大小只与节点数、m 最 大传输包长和p 有关。如果最大传输包长非常大并且第一跳为低带宽链路， 那么p a t h c h a r 将会耗尽该链路的带宽。 通过上面的分析，p a t h c h a r 算法虽然是现在唯一的一种只需在一个终端 主机中安装测量软件就能够精确测量出一条路由中各段链路带宽的算法，但 是它却有着测量速度慢、耗费网络带宽大的缺点。尤其是p a t h c h a r 的运行时 间正比于网络的r ，丌时延，并且不管网络的实际带宽是多少，p a t h c h a r 总是 向网络发送固定的测量报文。如果网络中同时有多个主机在运行p a t h c h a r ， 那么他们所发出的测量报文对网络来说将是一个巨大的负担。甚至对于低带 宽连接的几个主机，p a t h c h a r 仍要消耗大量的带宽资源，以至于p a t h c h a r 算 法不能正常运行。 2 2包对测量模型分析 包对是指发送连续的背靠背数据包，背靠背指的是这两个包之间的时间 间隔非常的小，理论上应该为零。 假设一条h 跳的路径，链路带宽可以表示为b = c o ，c l ，c h 。其中c i ( i = 0 一h ) 是第i 跳的链路带宽。发送2 个长度为s 的背靠背的包，用于探 测包对之间的时问间隙。由于操作系统的实时性，无法实现前一数据包包尾 和后一数据包包头间隙为0 ，我们通过在包中打上发送时间戳来测量时间间 隙。定义包对之问的时间间隔i 为第二个包的最后一位被完全传到某条链 路的时间减去第一个包的最后一位被完全传到某条链路的时间，如图2 2 所 示。 评一妇 图2 2包对模型测量瓶颈带宽 f i g 2 1 p a c k e tp a i rm o d e lf o rb o t t l e n e c kb a n d w i d t hm e a s u r e m e n t 西南科技大学硕士研究生学位论文第1 2 页 如采该条链路上没有其它流量。即在该链路上两个连续的数据分组等待 传输，那么这两个分组在该链路传输后的时间问隔为： a i = s | b i 从而，可以看出，这两个分组的传输时间间隔随链路带宽变化呈反比变 化。假设经过链路c i - l 的时间间隔为i ，那么两个分组在经过链路c i 传输 后的时间间隔为： a l m a x f 1 ，s i b t ) 假设源端发送的时间间隔。足够小，那么可以很容易的用数学归纳法证 明，这对分组经过整个路径后的时间间隔为： f - m a x o ，玩。 - s l 既。 其中刀h - m i n 马，f l 2 ，n ) 。 可以得到在无背景流量情况下，基于包对的算法来测量瓶颈链路带宽： 氏- s a 。 ( 2 - 6 ) 数据包对方法实现上存在的问题是很难控制背靠背数据包发送的时间 精度，而由于背景流量的存在，必须使用优良的过滤算法，否则很难保证对 由不同网络连接构成路径估计的健壮性，特别在高速的网络环境下，要控制 使测量数据包对在瓶颈链路排队更是困难。 在有背景流量的情况下，用包对探测瓶颈带宽会产生两种误差，从图二 我们可以看出，情况a 为无背景的情况下，测量值真实反映了瓶颈带宽。情 况b 为背景流量插入到包对之间，导致测量时间间隔增大，瓶颈带宽测量值 比真实值小；情况c 为背景流量在第一个包之前，导致测量时间间隔减少， 瓶颈带宽测量值比真实值大。 a ) ：卜- 卜卜 砖= 告= 告 b ) 。卜。日- 。一 咭 告 告 c ) i _ 、i _ - 一口卜- 一 告 = 告 告 告 图2 3背景流量导致的误差 f i g 2 - 3 e r r o lr e s u l tf r o mb a c k g r o u n di r a f f i c 西南科技大学硕士研究生学位论文第1 3 页 针对这种干扰，有两种办法，一种是滤波的办法，最大限度地滤除受干 扰流量影响的样本，第二种是采用统计模型对样本的各个峰值进行分析。 2 2 1不同流量背景下测量样本分布 为了分析不同大小流量背景下测量样本的分布情况，用n s 2 搭建一个6 跳的路径b = c o ，c 1 ，c 5 = 1 0 0 m ，7 5 m ，5 5 m ，4 0 m ，6 0 m ，8 0 m ，在源节点发送 大小为1 5 0 0 b y t e 的包对，在路径的每一跳产生不同的背景流量，分析在随 机背景流量轻载和重载时对包对测量样本的干扰情况。包转发服从f c f s ( 先 到先出1 的机制，这种机制是现在i n t e r n e t 路由中占主流的转发机制，如图 2 - 4 所示： p a t hp a t h 8 0 鞫簿吲埘烈参 略净咯净吲 c r o s st r a f f i c c r o s st r a f f i c s o u r c e ss i n k 图2 4多跳网络仿真模型 f i g 2 4 m u l t i p l eh o pn e t w o r ks i m u l a t i o nm o d e l 在源节点发送5 0 0 个包长为1 5 0 0 b y t e 的包对，背景流量用泊松分布的 流量发生器来产生，分别使每跳的带宽利用率u 为2 0 和8 0 ，得到测量 样本的直方图如图2 5 所示： 2 0 0 测 量 次1 0 0 数 o 弼量带宽( k b p s ) ( a ) 1 1 = 2 嘣 带宽( g b p s ) ( b ) u - - 8 暇 图2 5背景流量对测量样本的影响 f i g 2 5 m e a s u r e m e n ts a m p l er e s u l tf r o mb a c k g r o u n dt r a f f i c 萨 _ | 西南科技大学硕士研究生学位论文第1 4 页 从图中我们可以看出，在带宽利用率为2 0 的时候，瓶颈带宽测量样本 受干扰较小，可以从测量样本直接得到瓶颈带宽。当带宽利用率为8 0 的时 候，瓶颈带宽样本受到很大的干扰，真实瓶颈带宽只是局部峰值。 2 2 2 测量包长对测量样本分布的影响 在这一节将分析探测包长对测量样本的影响，现在大部分观点认为包长 越长越好，最佳的包长度应该是以太网容许的最大包长( m t u ) ，因为大的包 长产生较宽的时间间隔，抗背影流量干扰好，而且可以减轻由于c p u 本身 计算时间带来的影响。 为了验证这种思想，用图2 4 的网络模型做不同探测包长的仿真，在使 每跳带宽利用率为4 0 的情况下，使包长l 分别为1 0 0 b y t e 和1 5 0 0 b y t e ，得 到样本分布直方图如图2 6 所示。 由于大的包长产生宽的时间间隔，所以背景流量容易插入到包对中间， 假设当包对到达链路带宽为c i 的链路i 时，正好有背景流量在包对之间插 入，将会增大包对之间的时间间隔。包对的包长越大，背景流量插入到包对 之间的可能性越大，因为包对在传输过程中，越长的包长产生越宽的时间问 隔，使背景流量插入更容易。从图2 6 可以看到在包对取1 0 0 b y t e s 包长时， 大于真实瓶颈带宽的测量样本占主要地位，当包对取1 0 0 0 b y t e s 包长时，小 于瓶颈带宽的测量样本占主要地位。 2 0 0 测 量 次l o o 数 0 2 04 06 08 0 测量带宽( k b p s ) ( l = 1 0 0 0 b y t e st = 5 0 2 0 0 测 量 次1 0 0 数 0 2 04 0 6 08 0 测量带宽( k b p s ) ( b ，l ：6 0 0 - 1 0 0 0 b y t e su - - 5 0 图2 - 6测量包长对测量样本的影响 f i g 2 6 m e a s u r e m e n ts a m p l er e s u l tf r o mp a c k e ts i z e 西南科技大学硕士研究生学位论文第1 5 页 2 2 3 背景流量包长对测量样本的影响 在这一节分析背景流量的包长分布对测量样本的影响，利用图2 4 的网 络模型，使背景流量包长k 为固定值1 0 0 0 b y t e s 和【4 0 ，1 0 0 0 l 做仿真