（计算数学专业论文）端到端路径可用带宽测量方法研究.pdf

端到喘路径可用带宽测量方浊研究 端到端路径可用带宽测量方法研究 专业：计算数学 硕士生：周保良 指导教师：卞静副教授 摘要 可用带宽作为网络最重要的资源之一，是评价网络连接性能的重要度量参 数，和时延、包丢失等其他度量一样直接影响着客户性能，对其准确的估计与测 量是网络运营维护必须解决的问题，而相关测量算法和估计模型的研究一直是网 络测量领域的研究热点和难题。 目前己经有很多可用带宽测量方法被开发并应用于实际，虽然这些测量方法 各不相同，或基于包对，或基于包队列，但绝大多数都是利用网络瓶颈分隔1 6 5 】 原理测量可用带宽的。在实际测量中，现有测量方法存在测量过程复杂，测量精 度不够，应用范围狭小，使用不方便等缺点。 本文对可用带宽测量的模型、现有的测量方法和可用j 特宽测量中需要解决的 关键问题等进行了详细的探讨，并对各种算法的性能与适用性进行了分析和比 较。针对现有测量方法的不足，根据数据包队列延迟趋势模型年n c r u z 流量模型， 本文提出了一种新的可用带宽测量方法p a t h p c o 。p a t h p c o 算法中，接收端每次 接收到1 0 0 个探测数据包，以每个数据包的单向延迟为基准统计其后数据包的连 续进队概率尸s ，。，根据p s ，。大小判断探测数据包的发送速率是否大于当前路径 可用带宽，若朋。大于闽值，则当前发包速率大于路径可用带宽；反之，小于 路径可用带宽。利用参数p s 。计算调整后的发包速率，并把调整后的发包速率 通知发送端。发送端以此速率发送探测数据包。p a t h p c q 不断重复上述过程直到 探测数据包的发送速率非常接近路径可用带宽，算法输出测量到的路径可用带 宽，测量结束。 本文在网络仿真平台n s 一2 2 7 上对参数p s 。和p a t h p c q 算法进行仿真实验， - p 山大学硕士学位论文 端鲥端路径可用带览测量方浊研究 并与当f j 经典的可用带宽测量工具p a t h l o a d 进行了比较。实验结果表明，p a t h p c q 饽法测量精度和测量效率都优于p a t h l o a d 算法。 关键词：可用带宽，单向时延，数据包探测，c r u z 流量模型，n s 2 ，p a t h l o a d i iu 大学删+ 学位论文 端到端路径可用带觉测量方法研究 r e s e a r c ho ne n d t o e n da v a i l a b l eb a n d w i d t he s t i m a t i o nm e t h o d s m a j o r ：c o m p u t a t i o n a lm a t h e m a t i c s n a m e ：z h o ub a o l i a n g s u p e r v i s o r ：a s s o c i a t ep r o f e s s o rb i a nj i n g a b s t r a c t t h en e t w o r ka v a i l a b l eb a n d w i d t hi so n eo ft h em o s tc r u c i a ln e t w o r k r e s o u r c e s i td i r e c t l yi n f l u e n c e su s e r p e r c e i r e dp e r f o r m a n c e t o a c c u r a t e l ym e a s u r ea n de s t i m a t ea v a i f a b l e b a n d w i d t hi sa ne s s e n t i a li s s u e i nt r a f f i ce n g i n e e r i n g ，a sw e lla so t h e rm e t r jc ss u c ha sd e l a ya n dp a c k e t l o s s o nt h ec o n c e p to fp a c k e td i s p e r s i o n ，m a n yp a c k e tp a i r p a c k e tt r a i n t e c h n i q u e sw e r ep r e s e n t e dt oe s t i m a t ea v a i l a b l eb a n d w i d t h m o s to ft h e m a r eb a s e do nt h ep r i n c i p l eo ft h eb o t t l e n e c ks p a c i n ge f f e c t h o w e v e r ， t h e s em e a s u r e m e n tt o o l sh a v es o m ed i s a d v a n t a g e ss u c ha sc o m p l e xt e s t i n g p r o c e d u r e s ，u n s a t i s f y i n gt e s tp r e c i s e n e s s ，c o n s t r i c t e da p p l i c a t i o n r e g i o n sa n dd i f f i c u l tt oa p p y ，e t c i nt h i sp a p e r ，w es t u d yt h ep r e s e n ta v a i l a b l eb a n d w i d t he s t i m a t i o n m e t h o d o l o g y ，a n a l y s et h e i rp e r f o r m a n c e b a s e do nt h ep a c k e t st r a i nd e l a y m o d e la n dc r u zf l u xm o d e l ，w ed e s i g nan e we n d t o e n da v a i l a b l eb a n d w i d t h e s t i m a t i o nm e t h o dc a l l e dp a t h p c q t h ep r o b a b i l i t yo fc o n t i n u o u sp a c k e t s j o i n i n gq u e u eb a s e do no n e w a yd e l a yi sc a l c u l a t e da tt h er e c e i v e ra f t e r r e c e i v i n g1 0 0p r o b ep a c k e t s t h es e n d i n gr a t ei se s t i m a t e dw h e t h e ro rn o t l a r g e rt h a nt h ep r e s e n ta v a il a b l eb a n d w i d t ha c c o r d i n gp s p 二q i f p s p j q i s l a r g e rt h a nt h et h r e s h o l d ，t h es e n d i n gr a t ei sl a r g e rt h a nt h ep r e s e n t a v a i a b l eb a n d w i d t h ，o t h e r w i s et h es e n d i n gr a t ei sl e s st h a nt h ep r e s e n t a v a i l a b l eb a n d w i d t h t h e nt h ea d a p t i v es e n d i n gr a t ec a nb ec a l c u l a t e d 巾山大学硕+ 论文 i i i 端刮端路径n f 用带宽测最办法研咒 b a s e do n p s m 口，a n db es e n t t ot h es e n d e ra st h er a t eo fan e wt r a i no f p a c k e t s 1 1 h ep r o c e s si sc o n t i n u o u st 1t h es e n d i n g p r o b i n gr a t ei sn e a r l y e n o u g ht oa v a i l a b leb a n d w i d t ho ft h ep a t h ， w ev e r i f yt h ep e r f o r m a n c eo fp a t h p c qo nt h es i m u l a t i o np l a t f o r m n s 一2 2 7 w ec o m p a r et h ee s t i m a t i o nr e s u l t so fp a t h p c ow i t hp a t h l o a d f r o mt h ee x p e r i m e n tr e s u ll s ，w ec a ns e ep a t h p c oi sb e t t e rt h a np a t h o a d 0 1 1 p r e c i s i o na n de f f i c i e n c y ， k e y w o r d s ：a v a i l a b l eb a n d w i d t h ，o n ew a yd e l a y ，p r o b ep a c k e t ，c r u zf l u xm o d e l n s 2 ，p a t h l o a d 巾l i 学硕士学位c 文 端到端路径司用带宽测量方法研究 图 图 图 图 图 图 3 1 一1 1 3 - 2 一i ) 3 - 2 2 ) 3 - 3 - 1 ) 3 - 3 2 1 3 - 3 - 3 1 图( 3 6 1 ) 图( 3 6 2 ) 图( 4 1 1 ) 图( 4 1 - 2 1 图( 4 2 1 图f 4 2 2 图( 4 2 3 图( 4 - 2 4 ) 图( 4 2 5 ) 图h 一2 6 ) 图( 4 2 7 ) 图( 4 2 8 ) 图( 4 2 ，9 ) 图( 4 2 1 0 ) 图( 4 2 1 1 ) 图( 4 2 1 2 ) 图名 端到端路径模型 数据包往返时延 瓶颈分隔示意图 探测数据包间插入背景流数据包 a b = 0 7 m b p s ，r = 0 ，5 m b p s 时的数据包单向延迟 a b = o 7 m b p s ，r = o 5 m b p s 时的数据包单向延迟 p a t h l o a d 算法示意图 p a t h o a d 可用带宽测量结果 【j ? ，s ? + 7 _ 】时段内的f i f 0 队列( r 一， a 情形) 数据包单向延迟变化示意图 a b = o 7 m b p s ，r = o 5 m b p s 时的数据包单向延迟 a b = o 7 m b p s ，r = o 7 m b p s 时的数据包单向延迟 a b = 0 7 m b p s ，r = o 9 m b p s 时的数据包单向延迟 a b = 0 7 m b p s ，r = 1 3 m b p s 时的数据包单向延迟 朋。计算方法示意图 朋。值( 可用带宽为0 7 b t b p s ) p a t h p c q 算法流程图 仿真实验中的网络拓扑 p a t h p c q 可用带宽测量结果 p a t h p c o 可用带宽测量误差率 p a t h p c q 与p a t h o a d 测量结果比较 p a t h p c q 与p a t h l o a d 测量时间比较 中山大学硕士论文 i 堪 殂 丝 龙 儿 弛 弘 珀 ” 弘 勰 州 甜 衢 拍 舶 钾 卯 端到端路径司用带宽测量方法研究 1 1 论文的选题背景 第1 章绪论 随着近年i n t e r n e t 持续高速的发展，各种新的网络应用与需求层出不穷， 网络规模不断扩大，带宽不断增加。但由于用户数量迅猛增长，用户对网络连接 速度与服务质量抱怨不断增加，中国互联网络信息中心( c n n i c ) 在2 0 0 6 年1 月发 布的第1 7 次中国互联网络发展状况统计报告l 数据显示：截至2 0 0 5 年年底， 我国网民数量己经达到1 1 1 0 0 万人，上网计算机达到4 9 5 0 万台，网络国际出口 带宽总数达到1 3 6 ，1 0 6 m ，互联网已经发展成为国内增长最快、市场潜力最大的产 业之一，但是用户对当前互联网网络速度的满意程度仅为3 9 8 ，对当前互联网 总体满意度仅为4 7 ，3 ，i p 网络的服务质量( q o s ) 、可靠性和效率成为用户关心 的主要问题。 根据i e t f 的网络小组b m w g 研究的课题：因特网性能度量研究( i s s u e so f i n t e r n e t p r o v i d e rp e r f o r m a n c em e t r i c s ：i p p m ) 而发布的众多r f c 技术文档资 料，网络性能主要由互联性、服务质量、吞吐率、带宽、延迟、丢包率等一系列 参数构成0 2 , 0 4 , 0 5 , 0 6 , 0 7 , 0 8 1 。 带宽作为i p 网络最重要的资源之一，是评价网络连接性能的重要度量参数， 和时延、包丢失等其他度量一样直接影响着客户性能，对其准确的估计与测量是 网络运营维护必须解决的问题之一，而相关测量算法和估计模型的研究一直是网 络测量领域的研究热点和难题。 1 2 可用带宽测量方法的研究意义 近年来，网络中端到端可用带宽的测量越来越被人们所重视，应用也越来越 r 泛。从最早期的k e s h a v 根据数据包对的时间间隔变化来测量可用带宽i l0 j 到现 在各种各样的测量技术、测量工具，部希望在尽可能精确、尽可能快速、尽可能 不影响网络现状的情况下，洲得网络可用带宽的量值。然而由于可用带宽不仅与 路径上链路带宽有关，而且随着背景流量改变而动态变化，这使得对可用带宽的 中山大学硕士学位论文 1 端到端蹿径可用带宽测量方法研亢 测量十分困难，至今为止还没有个公认的可用带宽的测量方法。 1 3 论文的主要贡献 本文刑可用带宽测量的模型、现有的测量方法和可用带宽测量中需要解决的 关键问题等进行了详细的探时，州对各种算法的性能与适用性进行了分析和比 较。钊对现有测量方法的不足，根据数据包队列延迟趋势模型和c r u z 流量模型， 本文提出了一种新的可用带宽测量方法p a t h p c 0 ( 路径上数据包连续进队概率， t h ep r o b a b i1 i t yo fc o n t i n u o u sp a c k e t sj o i n i n gq u e u eo nt h ep a t h ) 。p a t h p c 0 算法中，接收端每接收到1 0 0 个探洲数据包后，以每个数据包的单向延迟为基准 统计其后数据包的连续进队总概率p s 。( 1 h ep r o b a b i l i t yo fc o n t i n u o u s p a c k e t sj o i n i n gq u e u eb u s e do i lo n e w a yd e l a y ) ，根据j d s 大小判断探测数 据包的发送速率是否大于当前路径可用带宽，若j d s 大1 。闽值，则当前发包速 率大于路径叮用带宽；反之，小于路径可用带宽。然后利用参数尸s 根据迭代 公式8 。= 尽。( 1 一q 。) 十r 。巧南或者r o 。= r m i ( 1 一p s 。) + r p s 。计算调整后 的发包速率，并把调整后的发包速率通知发送端。发送端以此速率发送探洲数据 包。不断重复上述过程直到探测数据包的发送速率非常接近路径可川带宽，算法 以此时的发包速率作为测量到的路径可用带宽输出。经仿真实验表明，p a t h p c 0 算法测量精度和测量效率都优于p a t h l o a d 算法。 1 _ 4 论文的内容安排 本文共分为五章： 第一章为全文的绪论部分。该章阐述了本文选题的背景和意义，概述了本文 的主要贡献，描述了本文的内容安排。 第二章详细讨沦厂网络洲量的相关技术。概述了带宽测量方法和带宽测量技 术现状。 第三章详细研究厂可用带宽测量的理论和技术基础，包括可用带宽测量的定 义、各种延迟模型和可用带宽测量方法，并对现有可用带宽测量方法进行分析比 端到喘路径可用带宽测量方法研究 较。 第四章提出了一种新的可用带宽测量方法p a t h p c q 。此章中，我们详细 描述了p a t h p c q 方法的设计目标，p a t h p c q 方法的工作原理，参数p s 。的计算 方法和p a t h p c q 的可用带宽测量机制。通过仿真实验对p a t h p c q 方法进行了验证， 并与当前典型的可用带宽测量工具p a t h l o a d 2 5 1 进行了比较。仿真实验结果表明， p a t h p c q 方法比p a t h l o a d 2 5 1 方法精度高，收敛速度快。 第五章对全文内容进行了总结，并展望了今后的工作。 中山大学硕士学位论文 端到端路径可用带诧测最方法研究 第2 章网络测量技术的研究现状 2 1 网络测量技术 网络测量是获得网络行为指标和参数的最有效手段，是最终建立高效、安全、 可预测和可控制网络的基本环节。网络测量技术研究主要解决以下问题：测量需 求和目的，测量指标，测量方法和测量理论，测量实施时间、地点，测量频度， 测量实施策略，测量精度和可靠性分析，测量对网络影响，测量代价，测量实现 技术等。具体研究领域包括： 1 网络测量指标与算法： 网络测量的主要参数包括站点的连通性，网络延时m ，丢包率”1 、路 由信息、带宽、路径瓶颈、突发业务量的频率、拥塞程度、动态瓶颈、吞吐量、 带宽利用率、服务器和网络设备的响应时间、最大的网络流量、网络服务质量( 包 括图像、数据、语音等服务的质量) 2 0 2 1 1 等。在网络层次的测量中，需要测量的 一类属性是网络固有的，如网络拓扑和相关链路的容量，在较长的时间内稳定， 不会发生较大的变化：而另一类属性反映了网络的当前状态，如排队延迟、连接 可用性、路由的动态性、路径的可用带宽和带宽利用率，与网络路径状况和承载 的网络业务密切相关，随时间不断动态变化。 2 测量结果分析与模型化 分析测量结果，建立模型，找出其中的特征不变量和变化因素，用以预测将 来某个时间的网络行为。 3 网络控制 利用网络测量与模型化知识，对网络资源进行合理配置和优化，实现网络资 源利用最大化和网络总体性能最佳。 目前网络测量技术主要包括基于s n m p ( s i m p l en e t w o r km a n a g e m e n t p r o t o c 0 1 ) 1 1 1 的测最技术、基于流量采集的性能监测技术( 如n e t f l o w 他1 ) 、主动 测最技术和被动测量技术。 中l i i 大学碰! 上学位论文 端士l 批嵩踏径可用带宽测量方法i , j d t 基于简单网络管理协议( s n m p ) 的测量技术通过访问路由器等叫络设备读取 m i b 库，获取网络流量、路由表、接口信息和协议分布等数据信息。但对于跨越 多个网段的大型网络或端到端路径，网络由不同的服务提供商运营，网络管理权 限限制使基于s n m p 的监控与测嚣应用范围狭窄，并且无法提供端到端路径性能参 数和相关的应用层性能指标，加之轮询网络设备的操作需要运行于网络设备中的 s n m p 代理进程1 i 断划请求响应，从而降低了网络设备的转发性能，并带来大量管 理流量负载。 被动测量技术以数据包捕获为基础般需要专用的硬件采集并保存大量的 数据，并提交到上层进行协议解码与分析，可以获得被测网段的详细数据包协议 统计，网元信息与流最分布数据常用的基于被动测量的工具有t c p d u m p ”】， n e t r a m e t 1 4 1 ；d a g il e n ti n t e r n e ta d v i s o r s 1 5 1 等。被动测量不会产生测试流量， 但缺点也很明显：它依赖于网络己有流量，在高速链路需要高性能硬件设备进行 全速捕获和解码分析，可能对网络用户的隐私造成侵犯。 j 卜动测量，即数据包探测的方法则相当灵活。测晕湍按照一定规则向网络发 送探测性流量数据来获得相关的特征参数。土动测昂会在网络巾引入较多的测量 流量，对网络实际性能会造成一定的影响。特别是带宽测量时，产生较好估计的 关键是发送足够的探测数据，随路径氏度的增加，一些测量算法需要的探测数迅 速增加。尽管主动测黾会产生额外的网络测试流量，但它是一种网络级的测量方 法，可以弥 b s n m p 这种网元级的测量方法的不足，又无需特定的装置，通过构造 高效的算法可以以一定的规则定时发出少晕的探测流，沿通路各主要节t i 记录路 由或时间等信息从而达到测试路径相关特征参数的目的，所以在路径性能监测、 h j 户业务仿真和故障链路定位等方面有很大的优势。 与测量技术相关的l e t f ：【：作组主要有专门为制定i n t e r n e t 性能测量标准而 成立的i p p m 工作组( i pp e r f o r m a n c em e t r i c sw o r kin gg r o u p ) ”】，r t f m 3 z 作组 ( r e a lt i m ef 1 0 wm e a s u r e m e n tw o r k ir i gg r o u p ) 1 1 6 1 ，以及t e 工作组( t r a l l f i c e n g i n e e r i n gw o r k i n gg r o u p ) 7 o 在测莓工具的方面，以c a i d a ( c o o p e r a ti r e a s s o e t a t i o nf o ri n t e r n e td a t aa n a l y s i s ) 为代表的研究组织致力于网络测龟 ：l 具的开发和测鼍数据分析方法的研究，己经针对不同的例络性能参数提供了 系列的性能测量工具【1 8 , 1 9 1 。 r j i 山人学埘j 士学位论文 端到端路径可用带觉测量方洼研究 2 2 网络测量技术中的带宽问题 i e t fi p p m 工作组迄今为止已完成了包括i p 网络性能参数框架i i ，和连接 性，单向丢失等系列性能指标标准的制定1 0 6 0 7 0 8 , 0 9 2 2 i ，但对于带宽定义以及测 量的标准化问题一直没有明确提及。一般理解的带宽是指连接到t n t e r n e t 提供 的链路或路径的传输速率或吞吐量。但在实际测量中，网络吞吐量和带宽差异很 大，吞吐量与协议和丢失率相关，而带宽则不受它们的影响。 端到端测量带宽指标通常沿用s t a n f o r d 大学的k e v i nl a i 定义的两个基本 度量参数i ，即瓶颈带宽和可用带宽。瓶颈带宽指给定路径的两端主机之间在不 存在背景流量的情况下可达到的最大数据传输速率，对应于路径中链路传输速率 最低的带宽连接( 瓶颈链路) 所能达到的理想带宽。对大多数网络，只要两端主机 间的路径和节点间的连接保持不变，瓶颈带宽维持不变，瓶颈带宽不受其他的流 量影响。而可用带宽是在某流量负载下路径能提供的稳定可用的最大带宽，随背 景流量改变动态变化。d o v r o l i s 等人1 2 4 2 5 l 则在协议层次上定义路径的瓶颈容量 与可用带宽：路径容量是在没有背景流量的情况下，路径能给予一个流的最大 t p 层吞吐量。可用带宽则是在给定背景流量负载下路径能提供给一个流的最大 i p 层吞吐量。这里给出这两种带宽度量的数学描述： 考虑一条从发送端主机到接收端主机经多个网络节点( 例如路由器) 连接而 成的h l 跳路径，e 为第i 条链路的容量，则该路径的瓶颈带宽，即在没有背 景流量下的最大数据传输速率为c = r r f i nc i ，称瓶颈带宽所在的链路为瓶颈链路 仁i _ h ( b o t t l e n e c kl i n k ) 。由于可用带宽随时间变化，定义第强的可用带宽为【 ，f + 时间内没有利用的部分链路带宽，即a ( ，t + f ) = 吲l 一峨( f ，h f ) ，其中 0 “，( f ，f + f ) l 表示链路f 的利用率。定义时刻f 某一路径端到端的可用带宽为： a ( f ) _ h r a i n c 1 ( f ，h 砷】) 公式( 2 2 1 ) c i u l ( f ，h f ) ，f _ o 对应t 时刻链路i 的背景流量，其大小表明了链路i 的捌塞程 度，把决定端到端可用带宽，即路径中最小可用带宽a 的链路称为紧凑链路 ( t i g h t1 i n k ) 。 叶- 山大学硕士学侍论文7 端到端路径可用带谢删量方法研究 2 3 带宽测量技术研究现状 目前国内外对带宽测量的列 究主要集巾于端到端路径带宽测量和瓶劲! 链路 带宽测量泓乃2 ”。由于不同时刻网络不断发生动态改变，蚓此对带宽的精确测 量是相当棘手的问题。很多实时应用中最为关心的端到端可用带宽依赖于探测流 罩经过的网络路径特征，包括路径各跳链路带宽等静态路径特征和与其他流量的 竞争、非对称路由或路南拓扑的改变等动态路径特征。由于这些限制因素，有关 带宽测量的研究一直进展缓慢，对路径精确的带宽测量很难实现，囚而也一直没 有彤成像p i n g 和t r a e e r o u t e 这样广泛使1 l j 的测量工具。 对于网络层链路带宽和可用带宽，目前已形成如下测量算法： 1 单数据包方法：b e l l o v i n ”i ，j a c o b s o n t 2 ，和d o w n e y t 3 ，使用单数据包 方法，调整探测数据包大小一次只传输一个数据包测量链路带宽。通过向网络发 送不同大小数据包，并统计延迟信息获得链路带宽的估计。k l e i n r o e k l 也使用 厂类似方法。这种方法存在的明碌问题：使用线性i o 归时间开销太大，有些路由 器对产生回应包的速率限制导致响应无法及时传递，逆向路径带来的噪音需要 发送大量的数据。实现的测量工具如p a t h c h a r l 3 2 i ，p c h a r i ”i ，c 1i n k i 朝i 。 2 数据包间隔方法：背靠背发送两个或多个数据包。根据背靠背数据包由 于排队形成的间隔估计瓶颁链路带宽和可用带宽。b o l o t t3 5 l ，c a r t e r 与 g r o v e l l a i “i ，p a x s o n l 2 0 i 以及d o v r o l i se ta l i ”i 等人使用数据包对测量路径的瓶 颈链路带宽，缺点是测量结果易受背景流节影响，难以满足如i p 电话、视频会 议等应用的需要。p a x s o n l 2 ”，s t o i c a ，b a n e r j e e 与a g r a w a l a ，使用的多数 据包方法与前述。法相比，同时考虑了同个流中的其它数据包和端到端延迟。 实现的洲量工具如b p r o b e c p r o b e 侧，p a t h l o a d ”i ，p a t h r a t e l 4 ，和s p r o b e j 等。 3 数据包尾随方法：k e v i nl a i t 4 2 1 对数据包队列排队延迟分析，建立延迟计 算的般方稃，导出新的测量方法。该方法经过两个阶段估计链路带宽，第一阶 段使用单数据包模型和线性回归方法确定与整个路径相关的特征量，第二阶段使 用数据包尾随方法( p a c k e tt a i l g a t i n g ) 推断指定链路的链路带宽。算浊的主要 缺点是：误著滑路径移 累，对于高速链路后的低速链路较难测量。该算法的实现 ：i ：具为n e t t i m e r l 4 ”。 8中i h 大学埘! 十学位1 仑贮 端到端路径可用带宽测量方法研咒 下表中列出的是各种网络带宽测量工具，及其测量最度和应用的技术原理【5 5 测试工具测试领域技术原理 p a t h c h a r 3 2 】单跳容量单数据包、大小变化 ( p e r h o pc a p a c i t y ) ( v a r i a b l ep a c k e ts i z e ) c ii n k l 3 4 i 单跳容量单数据包、大小变化 ( p e r h o pc a p a c i t y ) ( v a r i a b l ep a c k e ts i z e ) p c h a r 3 3 】 单跳容量单数据包、大小变化 ( p e r h o pc a p a c i t y ) ( v a r i a b l ep a c k e ts i z e ) b p r o b e f 3 8 】端到端路径容量数据包对 ( e n d t o e n dc a p a c i t y )( p a c k e tp a i r s ) n e t t i m e r 4 2 】 端到端路径容量数据包对 ( e n d t o e n dc a p a c it y )( p a c k e tp a i r s ) d a t h r a t e 端到端路径容量数据包对和队列 ( e n d t o e n dc a p a cit y )( p a c k e tp a i r sa n dt r a i n s ) s p r o b e l 4 1 i 端到端路径容量数据包对 ( e n d t o e n dc a p a c i t y )( p a c k e tp a i r s ) c p r o b e l 3 8 1端到端路径可用带宽数据包队列 ( e n d t o e n da v a il a b e( p a c k e tt r a i n s ) b a n d w i d t h ) d a t h l o a d 【3 9 端到端路径可用带宽自载周期数据流 ( e n d t o e n da v a il a b l e ( s e l f l o a d i n gp e r i o d i c b a n d w i d t h )s t r e a m s ) i g i 4 5 】 端到端路径可用带宽自载周期数据流 ( e n d t o e n da v a i l a b l e ( s e l f l o a d i n gp e r i o d i c b a n d w i d t h ) s t r e a m s ) p a t h c h a r 3 2 j 端到端路径可用带宽自载周期数据流 ( e n d t o e n da v a i f a b l e ( s e f l o a d i n gp a c k e t b a n d w i d t h )c h i r p s ) t r e n 0 1 4 4 1 批量数据传输容量仿效t c p 吞吐量 ( b u l kt r a n s f e rc a p a c it y ) ( e m u l a t e dt c p t h r o u g h p u t ) c a p 批量数据传输容量标准化t c p 吞吐量 ( b u l kt r a n s f e rc a p a c i t y )( s t a n d a r d iz e dt c p t h r o u g h p u t ) 2 4 带宽测量实现难点及关键问题 现今带宽测量方法虽然很多，但目前仍未形成一种公认的高效精确测量算 法，测量方法很难标准化，并得到广泛使用。而且可用带宽随背景流量动态变化， 中j 大学硕士学位沧文9 端到端路径可用带宽测虽方浊研究 对其测量的精度和实时性难以同时保证，立u 伺设计精确的测嚣算法测量可用带宽 也一直足网络测量领域的技术难点。 由前述带宽测阜：的研究现状和测量： 具描述i j _ 以霜山，带宽测量亟待解决的 关键问题有： 1 带宽定义与分类的标准化，以及带宽测量指标和方法的标准化； 2 开发高效、快速的带宽测最算法，使其在对网络端到端路径进行探测时 能适应不同网络条件的变化，不会向网络产生太多的探测流萤，同时不会影响剑 带宽测_ 晕= 的精度； 3 一些传统的带宽测黾算法在高速网络环境下表现出很大的局限性，测量 结果变得没肯意义，如何同刚改进算法的效率和测最结果的精度以适应新的网络 环境成为网络测量领域新的难点； 4 针对不同网络环境和不同、【k 务或应用的带宽需求，提出相应的带宽测量 以及保讧eq o s 为基f i f | 的带宽分配解决方案。 o1 1 1 人学硼士学位论文 端到端路径可用带宽测量方法研究 第3 章可用带宽测量模型与方法研究 3 1 基本概念 本节综合考虑了各种国际推荐标准和权威论文的讨沦，在通用的网络模型基 础上给出一个普遍适用的网络端到端可用带宽的定义，然后根据相应的定义给出 测量要求。 3 1 1 端到端路径模型 在i n t e r n e t 网络的结构中，星型、树型、三角型等网络结构混杂在一起。 但是，对任意两端点问的网络拓扑结构，我们都可以用如下图( 3 一卜1 ) 所示模型 表示：从发送端s n d 开始，任意一个数据包都会经过网络上若干个节点 ( c 1 、c 2 c h ) ，最终到达接收端r c v 。当然，在网络中，从发送端到接收 端可能存在多条路径或多条随时间变化的路径。但对任意数据包来说，它只能也 必然选择一条，从而符合本节所述的端到端路径模型。 l 1l 2l h 日号皿 芦 j c tc t 图( 3 - 1 一1 ) 端到端路径模型 f i g ( 3l 一1 ) e n d t o e n dp a t hm o d e l 3 1 2 可用带宽测量中的常用概念 圈 本文涉及到许多网络测量的专业术语，有的是直接由i e t f 发布的r f c i ”】阐 明的，有些是本文为了解释作者观点而设定的，都在本节中指出。 1 网络路径( p a t h ) ： 由一系列存储转发节点和链路构成的从发送端到接收端之间传递数据包的 一条逻辑路径。 巾山大学硕士学位论文1 l 端剑端路径可用带盘测量方法研究 an e t w o r kp a t hi sas e q u e n c eo fs t o r e a n d f o r w a r d1 i n k sa n dh o p s t h a tt r a n s f e rp a c k e t sf r o mas e n d e r $ n dt oar e e e i v e rr c v 2 链路( l jn k ：l i ) ： 网络路径上两个= 市点问的连接。 a1 i n ki sc o n n e el i o nf r o mo n eh o pt oa n o t h e rh o p 3 链路容量( c a p a c il y ：e ) ： 在没有背景流量的情况下，链路能给予个流的最大i p 层吞吐最，由设备 性能决定，是一个常量。 4 背景流( c r o s st r a f f i c ：p ) ： 链路上已经存在的数据流，可用带宽测鼍中，探测流要与其共享链路带宽。 5 带宽利川率( b a n d w i d t hu t i l i z a t i o n ：“) ： 某时刻链路上数据流已占用的带宽j j 链路容晕的比值。 6 端到端路径容量( e n d t o e n dc a p a c i t y ：c ) ： 数据包从发送端剑接收端经过的路径 i 各段链路容量的最小值。即： c = r a i n c i 。 卢lh 7 瓶颈链路( b o t t l e n e c kl i n k ) ： 端到端路径的各段链路中容量最小的链路，即满足c2 璺i 2 c 的链路。 t h el i n kw i t ht h es m a l l e s tc a p a c i t ya l o n gap a t h 8 紧凑链路( t i g h tl i n k ) ： 端到端路径的各段链路l pi l j _ 用带宽最小的链路，即满足 4 ( = 。m i n 。 c 1 - - i ( ，h r ) 】) 的链路。 t h e n kw i t hm i n i m u ma v a i l a b leb a n d w i d t ha l o n gap a t h 9 探测数据包( p r o b ep a c k e t s ) ： 在网络测虽= 中从发送端发出，接收端接收用j 数据分析，揭示网络状况的数 据包。 t h ep a c k el st r a n s m it t e d f r o ms e n d e rt or e c e i v e ri nt h et e s t w h i c h a r eu s e dt of i n dt h es t a t u so ft h ep a t h 】山大学碗：卜学位论文 端到端路径可用带宽测量方浊研究 1 0 探测数据包对( p r o b ep a c k e tp a i r ) ： 两个彼此之间有严格延迟限制的探测数据包，两者间延迟的变化表明了网络 路径可用带宽的信息。 t w op r o b ep a c k e t sw i t hd e f i n e dt i m es l o tw h i c hc h a n g ei l l u s t r a t e st h e e n d t o e n da v a i l a b l eb a n d w i d t hi n f o r m a t j o n 1 1 探测数据包间隔( i n t e r p a c k e tg a p ) ： 探测数据包之间的时间间隔。 i n t e r p a c k e tg a ps p e c i f i e st h ep a c k e tt r a n s m i s s i o n si nc o n t i n u o u so r l e n g t ho ft i m eb e t w e e ns u c c e s s i v eb u r s tt r a n s m i tm o d e s 1 2 单向延迟( o n ew a yd e l a y ：o w d ) ： 数据包从发送端到接收端所经历的时间。 t h el e n g t ho ft i m ew i t hw h i c hp a c k e tt r a n s m i t t e df o r ms e n d e rt o r e c e jv e r 3 1 3 可用带宽 3 1 3 1 链路可用带宽 1 定义( a v a i l a b l e8 a n d w i d t h ) ： 链路可用带宽是指链路中未被使用的带宽；一条路径的可用带宽是指路径上 各段链路可用带宽的最小值，即紧凑链路的可用带宽。 2 数学表述： 4 ( t ，t + f ) = c a t ，t + f ) 一只o ，f + f ) 公式( 3 一l 1 ) f _ 0 ，4 ( t ，t + i ) 是链路i 在时间【f ，h 叫的可用带宽，c ( t ，h f ) 是链路i 在 时间【f ，h 纠的容量( c 其实是一个常数，并不随时间变化，这里为了统一表述 也把g 写作时间的函数的形式) ，只( f ，t + f ) 链路i 在时间i t , t + 】背景流占用的带 宽。 设州“+ = 丢鲁等等是链路f 在时i 司 f h z l 的带宽利用率，则 中山大学耐! 士学位论文1 3 端剑端路径几用带宽测量方泄、研究 0 “，( f ，f + f ) i 。 因此链路i 在叫问 ，t + f 】的可用带宽可进一步写作 a t ) = c , l l 一“( f ，t + f ) 】 表示成积分形式为： 舭) = 扩c j l - u 。化m 眦 3 1 3 2 端到端路径可用带宽 公式( 3 一卜2 ) 1 定义： 从发送端s n d 到接收端r c v 的路径是由i l + 1 个节点连接而成，我们假设链 路的拓扑结构在整个测量过稗中是固定不变的链路也不存在珂、结构。相邻两个 节点问的链路( l i n k ) 表示为i ，其间链路容量为c ，背景流山用的带宽为尸， 用带宽为a ，州端点s n d 到端点r c v 的路径在l 时刻的可用带宽为各段链路可用 带宽中| 【f 勺最小值，记作a ( t ) 。 2 数学表述： a ( f ) = ，型2 a ( ，+ f