（计算机科学与技术专业论文）网络路径带宽有效测量方法的研究.pdf

国防科学技术大学研究生院学位论文 摘要 带宽是描述网络状态的重要参数，其在o v e r l a y 网络、无线网络、流量工程与网络安 全等方面都有广泛应用。网络路径的端到端带宽反映了终端用户的网络体验，其准确测量 日益成为研究热点。本文主要研究基于端到端的、无需中间设备协同的路径带宽主动测量。 简要回顾带宽测量的研究现状之后分析了影响端到端带宽测量的主要因素。首先从主 机与网络两个角度较为系统地总结了影响测量的各种因素。然后将测量过程划分为数据收 集、过滤与后处理三个子过程，并分别讨论了每个子过程中各种影响测量的因素。 瓶颈带宽( 或容量) 及可用带宽是描述路径带宽特征的主要参数。通过深入分析报文对 测量及带宽参数本身特征，给出了分别测量可用带宽与瓶颈带宽的有效方法c o p p 与 c a 口e s t 。两种方法均无需路径两端的时钟保持同步，仿真环境中通过与其它类似方法的比 较验证了两种方法的有效性。 c o p p 一次测量过程中包括多组报文对吐卸序列即速率不断增大的报文对序列。其基 本思想是将报文对与自拥塞原则结合，从每组序列中求出所有成为转换点韵报文对，然后 根据这些报文对及其相邻探测报文所受干扰的不同程度赋以它们不同的权重，从而得到一 个可用带宽的部分测量值，然后对部分测量结果求加权和得到最后的测量结果，加权系数 为各部分测量的持续时间与整个测量过程的持续时间的比值。 c a d e s t 一次测量过程中包括多组探测报文对集合，同一集合内报文的大小相同而不同 集合内的探测报文大小不同。其基本思想是将一个报文对集合拆分为两个报文集合，分别 包含报文对的第一与二个报文，并选取各集合中单向延迟最小的报文重构新的报文对进而 得到被测路径的瓶颈带宽。利用t c p 的特殊语义并以报文周转时间i m 代替单向延迟， 可得到仅配置在发送端的娜t ，其灵活性较好但精度明显降低。 报文对在包括c o p p 与c a p e s t 在内的大量带宽测量方法中有广泛应用，因此报文对模 型的研究具有重要意义。本文详细观察了满足b a c k t o b a c k 特征报文对的第一与第二个报 文的相关性与差异性及报文大小、网络负载、背景流的特征、瓶颈带宽及拓扑结构或路径 长度等参数改变时报文对的相关性与差异性的变化趋势。探测报文与背景流报文的交互分 析较好解释了报文对的相关性与差异性。其结果指示了探测信息处理的一个新方向即将对 单个报文的分析与对报文对整体的分析相结合以得到更准确的带宽测量当果。 总之，本文对包括瓶颈带宽与可用带宽在内的带宽的主动测量方法与模型进行了深入 研究。研究结果具有较好的理论与实践价值。 关键词：用络测量，主动测量，带宽测量，瓶颈带宽，可用带宽，擐文对 国防科学技术大学研究生院学位论文 a b s t r a c t c h a r a c t e i i n gt h en e t w o 血s l a u sa sp r e c i s ea sp o s s i b l eb e c o m e si n c r c a s i n g i m p o r t 柚t - w “ht h e e x p l o s i v eg r o w t h0 ft h ea v a i 王a b l er c s o u r c ea n du s 凹sj ni m e m e t a s 锄eo f 耄h ec r 毫l c i a lm e t r i c st o p i c t u r et h en e “，o r kc h 缸a c t e r i s t i c s ，b a i l d w i d t hh a sw i d e - s p r e a da p p l i c a t i o n si nn u m e u sa r e a s s u c ha so v e r l a yn e t w o r k ，d e s i g ha n dm a n a g e m e n ti nw i r c l e s sn e 柳0 r k ，仃a 塌ce n 画n e e r i n 舀 n e t w o r ks e c l l f i t ya n ds o 1 na d 出t i o 】a ，t h ce n d t o - e n db 锄d w i d t ho fn e 细o r kp a t hi s n s i s t e n t w i t ht h ee x p e r i e n c co fc 咖o nu s e r s 7 n 锄0 f b r e ，b a n d w i d t he s t i m a t i o n ，e s p e c i a l l yt l l ee n d t o - e n db 强d w i d t he s t i m a t i o n ，b e c o m e sah o ti 鹦u ei nr c c e n ty e a f s i i lt h i st h e s i s ，w ef o c u sm a i m y 衄t h ee s t i m 鲥o no fe n d t o - e n db 翘d w i d t h0 fp a t hb 卸d w i d t h ( i n d u d i i l gb o 铂c a p a c i t ya n d 鲫a i l a b 重eh 啦d w i d t h ) w i t h o u lc o o p c 船舡o no fl h e 诛婀旧诛i 翦t 啪a l d e v i c e ss u c ha ss w i t ( 出e so r 咖t e f se t c a f t e rr c 、r i e wb r i c n yt h es t a t e _ o f - t h c a ni nb a n d w i d t he s 国n a l i o n ，w e6 格t 和 a l y z et h em a j o r f a c t o 璐a 墙：c t i n gt h eb 姐鼬i d t he s l i m 舭i w ed i s c u s st h e s ef h c l o 糟f 咖n e 脚。咄a sw e l l 鹤 矗o mc n d h o s tc a y i n gt h em e a s t l f e 蛐tp r o c e s s w ef o u n dt h a tt h ed 主v e 牯en e 晰。噍c h a r a c t e f s 蛐c h 够t h ed i 矗b r 曲t 咖t ep o l i c y 蛳dm u n i - c h a h n do fn e m o 出p a t hw i ni 1 1 n u e n c cm ee 幽a 虹o n d 糟s t i c a l l y ka d d i t i o n ，l b ec a p a b i l j t yo fe d - h o s t ，i e t l l ed o c kr e s o l u t i o no rg 蛐u l a r i t y ，m a y l i m “也ee f f e c t i v e n e s so fm e a s u r i ：m e n tt 0 0 1 s 1 ng e n e r a l ，t h em a i nc s t i m a t i n gp r o c e s s e sc a nb ed i v i d e di n t o h r c es t e p s ：出幢ac o l l e c t i n 岛d a t a f i l t e r i n ga n dc o n t i n u o u sp r o c c s s i 昏w ef u r t h e rd i s c u s st h ep o s s i b l ef 她t o r sd e p 佗s s i n go f j m p r o v j n g t h ee x e c u t i o no fe a c hs u b s t 印hm o s tc a s e s ，a c t u a l l y ，e s t i m a 耄i o na c c u r a c y ，d e p l o y - m e n tn “i b i l i t y 锄d0 v e 西d 佃d u d i n gt h ec o s ti nd 印l o y m 髓t ，p f o b i n ga n dc o m p u t i n g ) a r ci n c o n t r a d j d i v e ，t h a ti s ，w ew i l lh a v eb i 曲e rc o s t 曲d1 e s sn e x i b l ed 印l o y m e n ti fw ew i s ht oo b t a i n h i g b e ra c c u n c y t h em a j o r 妣u so ft h et h e s i si st l l ec s t i m a t i o no fb o t ht h ec a p a c i t ) ；，l7 蚰da v a i l a b l c b 锄d w i d 啦a l o 矗ea 昏v c n 撇p a t h w ep r e 越柳os c h e m e s ，e 每0 0 p pa n d q i p 蟊细i n 9 1 f o re s t i l n a t i n g ! c f 诧c i i v e l yl he _ c a p i t y 柏da v a i l a b l eb 柚艄d t ho fp a l l l - 删啦瞄h 哆b o 血 s c h 啪a i n d 印锄d c n to f t l l ea s y c h r o n i z a i 0 ft h et w o s i d ec ! i o c ：l 【so fm e 勰u r c d 尹劬 1 1 l en 棚ec o p p 伽e s 肋mt h ep a n i c u l a rp r o b es c h 锄e ，c h i r p so fp a c k e r l p a i r s ac h i 币o f p a c k e p a i f si sc o m p o s e do fs e v e r a lp a c ：k e tp a i r sw i t hd c c 嗽玎e n t a li n t e r - p a c k e ts p a c i n g a n e r d i s c u 鲒i n g t h e r i g 叫o u sd e f i n i l i o no fa v a i l a b l eb 锄d w i d t h ，t l i en o v e l 咖一s q 塔c s t i m a t i n g m e 山o d o l o g y ，e g p a f c i a la n df i n a ls t e p ，i sp 陀s e n t e d i np a r t i a ls t 印，c o p ps c n d ss e v e r a lc h i r p s o fp a c k e tp a i r s a n e re a c hc h i f pi sr e c e i v e d ，w ef i n do u ta 1 1t u m 抽gp o i n t si nt h ec h i 印，a n dm e n 舀v et h e s ep o i n t sd i s t i n c tw e i g h ta o c o f d i n gt ot h e 曲g r e eo fe x p e r 主e n c e dd i s t o r t i o n t u m i n gp o i n t i ss u c hap a c k e tp a i rt h a ti sd i s t u r b e dm o r e0 b v i o u s l yb yc r o s st r a f ：f i ci nc o n t r a s tt oi t sn e i 曲b o r p a i r s he a c hp a r t i a ls t e p ，a p a r t i a le s t i m a t ec a nb eo b t a i n e da n de q u a lt ot h ew e i g h l e da v e r a g eo f i i 国防科学技术大学研究生院学位论文 a l lt u m i n gb 锄d w i d t hw i t h i nt h ec h 卸i nt h es e c o n ds t 印，t h ef i n a le s t i i n a t e i st h ew e i 曲t e d a m o u n to fa l lp a n i a lr e s u l t so fa l lp a r t i a lr e s u l t si nam e a s u r e m e n te p 王s o d e f i n a l l y ，t 1 1 ev a l i d a t i o n o fc o p pi nv a f i o u ss i m u l a t i 帆ss h o w st h a tc o p pc a np r o v i d ea c c u r a t er e s u l t sw i t hr e l a t i v e l y l e s so v e r h e a dw h i l ea d a p tt on e t w o r kv a r j a t i o n sr a p i d l y a sf b rc a p a d t ye s t i m a t i o n ，p a c k e t p a i rh a sb e e nu s e da s0 n e6 ft h ep r i m a r ym e a n st o m e a s u r en e t w o 址c a p a c i t y y e t ，m o s tp 哟fp r o p o s 蛆t o o l sa r es e n s i t i v et on e 脚d r ks t a t u sa n d p e r f b 瑚p o o d y i nh e a v y l o a d e dn e t w o r k w ep r e s e n tan o v e l 矗l t e f i n gm e c h a n i s m ，i m p l e m e n ti n c a p e s t ，t oa d d r e s st h cn e g a 晰ee f f e c t so fc r o s st m f f i c a f t e rs p l i tt h e 础西ns e to fp r o b ep a i r s i l ot w 0p a c k e ts e t sc o m p o s e do ft t l ef i r s ta n ds e c o n dp a c k e to fa l lp a i r sr e s p e c t i v e l y ，w es e l e c t t h ep a c k c t sw i t hm i l l i m u m 衄e - w a yd e l a yi ne a c hs e ta i l du s et h 锄t or e c o n s t m c tan e w p a i r 丘e e 丘o mi n t e d c r c n c eo fc r o s st r a f f i c ，f r o mw h i c ht h et i n a l c a p a c i t ye s t i m a t e s a r ed e r i v e d p r e l i i l l i n a r yr c s u l t ss h o wt h a tt h ep r o p o s c dm e c h a l l i s mi sf c a s i b l ea n dm b u s tf b rt h eh e a v y l o a d e dn c t w o r k ，w h i c hc a np r o d u c ca c c u r a t ee s t i m a t 宅s 州l l l 犯l 撕v e l yf c 、袱州e h e a d s 咖p 缸e d t 0s 妇i l a rt o o l s i na d d i t i o n ，w i t hl h eh c l po f t l l es p e c i a ls e m a n t j 髂o f t c p ，叻ec a nu s er o u n d 埘pt i m e ( r n ) m s t 髓do f 咖e - w a yd e l a yi ng 哦b s ti no r d e rl or c l e a s et 1 1 ee s t i m a t i r e q u i 掀n e m st od e p l o y s o f t w a r ea ts e n d e r 彻l ya tt h ee x p e n s eo fh i g h e re r r o r s i n al a r g ea m o to fp m p o s e ds c h e m e sc l a i l i n gf b rb 卸d w i d t l ie s t i m a t i o na r eb a s e do n p a c k c t - p a i r t e c h i q u e ，w ef i n a l l yi n s p e c tt h ec o h 己l a t i o 姐dd i f f e r e n c eb e t w e e rt h ef i r s 0a n d s o n dp a c k e to f b a c k t o b a c kp r o b ep a i ri nd e p t h ，a n dt h ee f f c c to fp a c k c ts i z e n e m o r k1 0 a d a n dt o p 0 1 0 9 y ，p a t hc a p a c i t ya i l dc r o s st r a f f i cc h a r a c t e r i s t i c sa n ds oo n n ea n a l y s i so ft h ei n t e r - a c t i o nb e t w e e np r o b ea i l dc r o s sp a c k e t si sc o n s i s t e n c tw i t ht h es i m u l a t j o nr c s u l t s ：跚da 培u e sa n o v e ld i r e c t i o ni np a c k e t p a i rb a s e de s i i m a t i o n ，e g c o m b i n gt h ea n a l y s i so fs i n g kp a c k e ta n d p 卵k e tp a j rt ou t i l i z et h ew h o l ep m b e si n f o r m a t i m o r ce f f c c t i v e l y i ns u m m a r y ，s o m ei n - d e p t l lr e s e a r c hh a sb e e nm a d ei nb a n d w i d t he s t i m a t i o n ，s u c ha st h e a i l a l y s i so ft b e 凸c t o r sa f 6 e c “n ge s t i m a t i o n s ，1 w oe f f i c i e n tm e l l o de s t i i n a t i n g 也ec a p a d t ya 1 1 d a v 胡a b l eb 卸d 丽d t hr e s p e c t i v e i ya l l dt h ei n s p e c l 【；i o n0 ft h ec o 盯e l a t i 衄a i l dd i f 话r e n c ti n s i d e p d d k e tp a j ra n ds 0 恤t h er e s i l l t s 雒eh 亡啦f u 垂f 6 r d e 娼t 姐d i n gt h en e 柳o d 【m o r e d c a n y k e y w o r 葛b ： n e t w o r km e 躯u r e m e n a c t i v ep r o b i n 舀b a n d w i d 出豁6 m a l i 日呜。叩a c j t y ， a v a i l a b l eb a n d w i d t h ，p a d e tp a i r i i i 国防科学技术人学研究生院学位论文 图目录 图2 1 实验拓扑模型( 单位：i b p s ) ，1 3 图3 1n 个报文对组成的探测报文序列2 2 图3 2 转换点k 的分析范围为三个报文对2 4 图3 3 三种不同类型的转换点的p 值分布图2 4 图3 4 可用带宽处于测量边界时c o p p 测量结果偏差较大2 8 图3 5 不同发送速率的大小7 0 0 b y t e s 的报文对s v 值的分布2 8 图3 6 不同发送速率的大小7 0 0 b y t e s 的报文对第二个报文的单向延迟的分布2 8 图3 7 同一测量数据采用不同权重函数的结果比较2 9 图3 8 不同k 值的测量差异( 带宽单位：舳p s ) 3 0 图3 9 仿真实验拓扑结构3 1 图3 1 0 单拥塞情况下c o p p 与p a t h l o a d 、s p r u c e 测量结果的比较3 2 图3 1 1 多拥塞情况下c o p p 与p a t h l o a d 、s p r u c e 测量结果的比较3 2 图3 1 2 三种方法测量导致的最长及晟短持续拥塞时间比较3 3 图3 1 3 三种方法一次测量开销比较( 单位：s ) 一3 3 图4 1 仿真实验拓扑结构3 7 图4 2 当n = 4 时得到无背景流干扰的f p 及s p 报文与整个报文对各需探测报文对数目 ，3 8 图4 3 当n = 1 1 时得到无背景流干扰的f p 及s p 报文与整个报文对各需探测报文对数 目3 8 图4 4c a p e s t 验证实验拓扑结构4 3 图4 5c a p p r o b e 与c a p e s t 测量结果比较4 3 图4 6 误差不超过5 的c a p p r o b e 与c a p e s t 的收敛时间对比4 4 图4 7 仅在发送端部署的c a p e s t 在不同窄链路负载下测量误差累积分布4 4 图5 1 仿真实验拓扑结构。4 7 图5 2 不同大小的报文对f p 与s p 报文的干扰率比较一。一4 9 图5 3 背景流为纯t c p 流时报文对f p 与s p 报文的干扰率比较5 0 图5 4 不同瓶颈带宽下报文对f p 与s p 报文的干扰率比较5 l 图5 5 当n = 1 1 时报文对f p 与s p 报文的干扰率比较。5 1 图5 6 不同大小报文对各报文的所需探测报文对数目5 3 图5 7 不同大小报文对各报文排队延时累积分布5 4 图5 8 纯t c p 流环境下报文对各报文的所需探测报文对数目 圈5 9 纯t c p 流环境下报文对各报文排队延时累积分布 图5 1 0 不同瓶颈带宽下报文对各报文的所需探测报文对数目 图5 1 1 不同瓶颈带宽下报文对各报文的排队延时累积分布 5 5 5 5 5 6 5 7 国防科学技术大学研究生院学位论文 图5 1 2 当n = l l 时报文对各报文的所需探测报文对数目 图5 1 3 当n = 1 1 时报文对各报文排队延时累积分布 图5 1 4 背景流与探测流交互的最简单例子 5 8 5 8 6 0 国防科学技术大学研究生院学位论文 表目录 表1 1 瓶颈带宽( c a p a c i t y ) 测量工具一览表 表1 2 可用带宽( a v a “a b l eb a n d w i d t h ) 测量工具一览表 表2 1 测量结果( 单位：m b p s ) 6 7 1 3 独创性声明 本人声明所呈交的学位论文是我本人在导师指导下进行的研究工作及取得 的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含 其他人已经发表和撰写过的研究成果，也不包含为获得国防科学技术大学或其它 教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任 何贡献均已在论文中作了明确的说明并表示谢意。 学位论文题目：圆终整焦堂室盘煎型量左洼鲍盟窥 学位论文作者签名： 星堡垒 日期： 伽r 年胆月工7 日 学位论文版权使用授权书 本人完全了解国防科学技术大学有关保留、使用学位论文的规定。本人授权 国防科学技术大学可以保留并向国家有关部门或机构送交论文的复印件和电子 文档，允许论文被查阅和借阅；可以将学位论文的全部或部分内容编入有关数据 库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密学位论文在解密后适用本授权书。) 学位论文题目：圆丝整堡鲎童盔煎型量虚洼塑盟窥 学位论文作者签名： 作者指导教师签名： 吕据军谊 陴 日期：k 年，z 月1e 日期：珂年i 乙月刁日 国防科学技术大学研究生院学位论文 第一章绪论 1 1 研究背景 1 1 1 t e m e t 用户及资源的快速增长，使对网络状态的详尽了解变得日益重要。实现灵活的 区分级别的网络服务及网络的改造、升级等也需要准确与实时地获取网络状态。因此设计 获取网络状态参数的方法具有重大现实意义，网络测量作为获取网络状态的有效方法而成 为了许多研究者关注的热点问题。与网络的延迟、抖动等一样，带宽是描述网络状态的关 键参数之一，其在o v e r l a y 网络、无线网络、流量工程与网络安全等方面都有广泛的应用。 网络路径的端到端带宽反映了终端用户的网络体验，其准确测量曰益成为研究热点。本文 主要讨论基于端到端的、无需中间网络设备协同的网络路径带宽的主动测量。 1 1 1 网络状态的刻画与测量 网络技术的迅猛发展，特别是基于t c p i p 协议的国际互联网( i n t e r n e t ) 的广泛应用， 深刻地改变了人们工作、学习和生活的方式。网络从信息传输的基础设施已逐步演变成为 人类社会的基础设施。网络新应用不断涌现，网络的异构性与复杂性不断提高，管理和控 制大型网络变得越来越困难。尽管网络基础设篪的建设取得了长足的进步。但现有的网络 服务和服务质量与用户的需求和期望仍然存在差距。根据第十六次中国互联网络发展状 况统计所作的凋查p 】，截止到2 ( ) 【) 5 年6 月3 0 日，我国上网用户总人数达到了1 0 3 0 0 万 人，上网人数仅次于美国，位居世界第二。国际出口带宽的总量已经达到8 2 6 1 7 m ，网络 容量也成倍增加。网络基础设施取得飞跃的同时，网络总体性能却没有得到大幅度提蔬， 用户对网络使用的总体满意程度仅为4 0 3 ，对网络速度的满意程度更是只有3 7 8 。 i n t e m c t 对信息化的普及和发展起到了巨大推动作用，但是因为i i l t e m 吼缺乏一个正常； 盈利的商业模式，网络缺乏有效的管理和运营手段，面临服务质量、信息安全和网络管理 等饲题一要解决这些难题，非常重要的一点是能够获得网络状态准确、。详尽的了解。 。网络状态的刻画，包括对静态特征和动态特征的描述两方面。静态特征指在运行之前， 就己可确定的网络特征，如核心骨干网的拓扑结构、各链路的最大传输能力：动态特征赠 是只有运行时才可确定的网络特征，如网络路由的选择、路径的瓶颈带宽与可用带宽、报 文的延迟、丢包率、周转时间等。一般地，静态特征具有一定稳定性；而动态特征则往往 随时问而不断变化，并且与网络应用紧密相关。 测量是获取未知特征的重要方法。就测量方式而言分为被动与主动两类，被动方法通 过收集与分析特定节点如路由器的相关信息获得整个网络所感兴趣的状态特征；主动方法 则需要注入一定量探测报文，然后观察它们的特征及特征的变化从而获取网络状念。 被动方法无需额外的探测流，但其依赖于网络的已有应用且需处理的数据量较大，一 第1 页 国防科学技术大学研究生院学位论文 般要求网络设备的访问权，同时信息收集亦需一定的开销；主动方法可控性和灵活性较好， 但探测开销可能阻止其在大规模网络的实时实施。 1 1 2 带宽测量 本节首先给出一些带宽信息重要的应用背景，然后简要讨论带宽测量方式的选择。 夺广泛的应用背景 带宽是网络状态的重要参数，也是许多网络应用所关注与需要的重要信息，其在 o v e r l a y 网络、流媒体点播、端到端访问控制、服务器选择、拥塞控制和网络安全等方面都 有广泛的应用。对具有q o s 要求的应用如视频点播、视频会议等，保证一定的必需带宽是 网络应用平滑执行的重要条件之一。通过测量得到及时准确的掰络带宽、延迟等信息，对 q o s 应用初始启动时的参数配置或执行过程中参数自适应调整，均具有重要的指导意义。 移动和无线网络方便了人们的生活，但面临的一个闯题是必须在多种襁络接入点中做 出选择及适应接入点调整等带来的性能的动态改变，此时迅速得到准确的不同接入点的带 宽具有非常重要的意义。新近兴起的分布式计算、网格计算等需要带宽等信息来指导决策 各节点的任务划分及通信等。此外，就域间流量工程( i n t e r _ d o m a i nt r a f f ce n 百n e e 咖曲或域 内流量工程( i n t r a - d o m a i nt f a 舾ce n 画n e e r i n g ) 而言，带宽是其所依据的基本参数之一。 一个值得注意的新应用方向是网络安全。如在入侵检测领域，判断是否出现异常的重 要依据就是网络状态的变化，而路径带宽作为表征状态的重要参数无疑具有重要的指示作 用，例如路径的带宽发牛的急剧突变可做为判断d o s 、d d o s 类型攻击的重要特征。 夺测量方式选择 尽管带宽信息正日益显示其重要性，但带宽的准确测量却仍是具有挑战性的问题，甚 至关于带宽的定义也在研究者之间未取得统一的认识。如前所述，测量就方式而言，分为 主动与被动测量两类。尽管被动测量具有不产生额外流量的优点，但其存在的缺陷使其并 不非常适合带宽的测量：首先，如果某条链路或路径( 定义见下一节) 没有任何报文通过， 则该链路或路径自甘带宽信息仅通过被动方式是不能或很难得到的；其次0 能调以推断帮宽 信息的报文必须满足。定的条件( 如报文对b a c k 粕h 出特征) ，而这些条件在被动测量中难 以被确保，枞而可能引入测量误差：最后，使用带宽信息的应用均位于应用层 因此带宽 的澳口量主要由普通用户而不是管理员来完成，但网络设备的受限访问限制了被动策略的跨 网络部署及普通用户_ 白勺使用。 主动策略通过控制自身发送的探测报文流，可以较快和方便地得到所需数据。特别是 端到端的主动测量，无需访问中间设各仅通过大量链路或路径的发送端及接收端的协同可 得到网络带宽，从而普通片j 户也可方便地使用。其缺点在于可能造成删络的暂时拥塞，可 扩展性相对相差。另外，测量过程中探测报文与实际应用的报文的网络体验可能存在差异， 此时对测量结果的合理解释将非常重要。 第2 页 国防科学技术大学研究生院学位论文 本文主要关注主动测量。但需要指出是主动与被动的测量在某种程度上是可结合的： 为弥补探测流与应用流的网络体验的差异性，可适当使用被动测量获得的信息对主动测量 结果加权修正。该思想在延迟i 捌 8 3 】与带宽【7 0 】测量中均有讨论。 1 2 带宽测量的研究现状 带宽测量问题自1 9 8 8 年j a c o b o s o 提出【1 5 】，已经成为研究者关注的热点问题。本节首 先给出带宽的一些基本定义与假设，然后从测量方法与测量模型分析两方面总结带宽测量 领域的研究现状。 1 2 1 带宽的基本定义与假设 i n t e l e t 由大量的端主机、路由器及交换机等互连而成。可以直接交换信息的两个设备 间的连接称为一跳或一条链路( h o p ) ；从报文起始传送端到接收端的端到端路径( e n d t o - e d p a t h ) 由一条或多条链路组成。本文仅考虑端到端路径唯一的情况且不存在多通道，第二 章分析了多路径多通道对测量的影响。 带宽包括瓶颈带宽、可用带宽及吞吐量等。瓶颈带宽又称容量。由于吞吐量参数通常 与具体的应用或协议如t c p 相关，此处不作讨论。按照o s i 参考模型既可定义网络层的带 宽，也可定义数据链路层的带宽。早期的研究者未区分不同层的带宽，因而不同测量方法 得到的结果出现不一致的情况。p a s z t o r 等f 3 8 】首先发现这个问题，p r a 鞠d 等栩详细分析了两 种定义的差异和关系并建议采用网络层的带宽定义。本文仅考虑网络层带宽。 定义单条链路的瓶颈带宽c 为它的最大数据传输率；若时刻t 该链路的带宽利用率为 u ，则此时该链路的可用带宽爿o ) 定义为爿o ) t c ( 1 一) 。 对于端到端路径，不妨记从s e n d e r 到r e c c i v e r 的路径p 由n 条链路组成且其瓶颈带宽 分别为c ，c ，e 。路径p 的瓶颈带宽c 为c ；m j i l c 1 ，c ：c 。 ，瓶颈带宽最小的链 路称为窄链路_ 相应坶。如果在b 寸 刻t 名链路的可用带宽为4 ( f ) 4 0 ) ；。魂( f b 娜时刻t 路径p 的可用带宽嘶) 为4 t 珥抽翻。( f ) 4 。( f ) ) ，可用带宽最小的链路称为紧镱 t 毛 路。路径带宽又称为端到端带宽，包括路径瓶颈带宽与路径可用带宽，它反映了位于路径 两端的用户的网络体验，设计其有效的主动测量方法是本文主要的研究内容。 路径带宽测量有两种可选策略即端到端( e n d - t o e n d ) 与逐跳测量( p c r 由o p ) 。前者无需访 问网络中间设备，直接观察探测报文通过整个路径后的特征以得到路径带宽，后者则逐跳 测量每条链路的带宽，然后取各链路带宽的最小值得到路径带宽。早期的测量方法多为逐 跳方法，因其开销较大且存在较大的难以消除的误差，更多研究者转而探讨端到端测量。 本文也将集中于端到端的路径带宽测量，下文无特别沈明或咧确的二下文则带宽测量均指 第3 页 国防科学技术大学研究生院学位论文 端到端的带宽测量。 现在给出带宽泓量对网络的通常假设：网络设备采用f l f o 策略对所蒴习甓文( 不区分 探测报文与背景报交) 提供b e s t e f f o n 服务；背景流满足流模型( f l u i dm o d c l ) ，即背景报 文在大小上可无限细分；报文的传输延迟与报文大小存在正比关系。 该模型显然是一个理想模型，上述假设并不总为1 1 1 t e m e t 所满足。特别是后两条，血t 锄e t 的多样性与多变性特别是背景流的突发性可能破坏其成立。因此测量方法必须处理网络假 设失效引入的误差。 1 ，2 ，2 瓶颈带宽测量 j a c o b o s o n i l 5 】最早提出带宽测量问题，l 沁s h a v i l 6 l 从拥塞控制角度分析了带宽的测量方 法。他们的思想总结起来就是瓶颈带宽测量的两类重要方法，即单报文方法( 亦称为v p s ， v a r i a b l ep a c k c ts i z e ) 及报文对方法( p a c k e tp a 砷。 夺单报文方法( v p s ) 单报文方法的基本思想是报文的单向延迟与报文大小( 记为p ) 存在简单的线性关系， 如( 1 1 ) 式所示。 d 肋| f 一_ f 。2 善( 云+ q 一哟 ( 1 j ) 其中o w d 为报文的单向延迟，n 为路径的链路数目，e 为第i 条链路的瓶颈带宽，玑，曩 分别是第i 条链路的排队延时与传播延时，t ，t o 分别为报文的接收与发送时刻。 传播延时石；是与报文大小无关仅决定于链路本身的量。当排队延时为- o 时就可得到单 向延迟与报文大小的确定性的线性关系，且斜率为链路瓶颈带宽的倒数之和。分别冷= 阼一1 r 叠，即可逐跳测量各链路的瓶颈带宽，进而根据定义可得路径瓶颈带宽。 为谪少误差，知b o s o n 等提出了两金重要的改进措旌：一发送多个根同夹小的报文取 其中单向延迟最小的报文参与计算以最大可能消除排队延时，在测量中使厩多组不同大小 的报文并应用回归分析技术计算瓶颈带宽i 这些措施提高了测量的准确性正但也使开销显 著增大，同时也未克服误差传播的问剧2 2 1 。 报文对方法( p a c k c tp a j r ) 另一种测量路径瓶颈带宽的技术是报文对方法。大小与发送速率均相同的相邻两个探 测撒文称为一个报文对【鄹。按发送时问先后，两个报文分别称为报文对的第一、二个报文， 两个报文问的时间间隔称为报文对内问隔。相应地，两个相邻报文对其前一个报文对的第 二个报文与后个报文对的第一个报文的时刚问隔称为报文对问问隔。报文对的发送速率 第4 页 国防科学技术大学研究生院学位论文 即为其第二个报文的大小与该报文对内间隔的比值。若报文对的发送速率大于路径瓶颈带 宽，则称该报文对满足b a c k t o - b a c k 特征。在瓶颈带宽末知时一般认为测量主机以最大发 送速率发送韵报文对即满足该特征。 发送满足b a c k t o 七a c k 特征的大小为p 的报文对通过测量路径且未受背景流干扰，则 路径瓶颈带宽c 可通过( 1 2 ) 式得到，其中如f e w m ，为在接收端报文对内间隔。 p “亩 ( 1 2 ) 不妨记报文对进入某条链路( 瓶颈带宽为c ) 的报文对内间隔为觑t 们懈z 。则不考虑背景 流干扰时通过该链路后的报文对内问隔满足如f e n f ，一m a x 加f 已九硼，p c ) 。对瓶颈带宽为 c 的路径，若使在发送端的报文对内间隔小于( p c ) ，贝| j 通过窄链路后报文对内问隔将等 于( p c ) ；由于窄链路之后的链路( 如果存在) 的瓶颈带宽大于窄链路瓶颈带宽，因此该问 隔将保持至接收端，利用接收端的报文对内间隔并利用( 1 2 ) 式即可计算路径瓶颈带宽。 报文对方法存在多种扩展，将一一次发送的报文数目由2 增大到n ( n 2 ) 可得报文序列 方法( p a c k e tt r a i n ) 【1 9 】；每次发送3 个报文并视其为两个报文对可得p a c k e tm p l e t s 方法【惦l ： 进一步报文的大小取不同值即得t a i l g a t i n g i2 3 1 、c a n o u c h c l 2 7 】与q u a n e t 方法i 研等。 背景流的干扰可能引入误差，常用的处理方法是统计分析与过滤。该方法认为大量测 量将具有向正确值靠拢的趋势，因此多次测壤之后取其中出现概率最大的值做为测量最终 结果。为提高精度及减少开销，l a i 与m a k e l j 提出了基于潜能带宽过滤、报文窗口等机 制，并引入逐步求精的思想。 统计分析方法的缺陷在于重负载时大多数报文对均受到干扰，此时测量结果分布可能 出现多分形特征( m u l t i - m o d a l ) ，且此时出现概率最大的可能并非真实值。进步研究1 8 】发 现不断增大单个报文序列的报文数目将使多形特征不断减弱直至消失，并且多形特征刚好 消失时的单峰值比瓶颈带宽略小，该值称为渐进离散速率( a d ra s y m p t o 醢cd i s p e r s i o n j r a t e ) ，d o v r o l i s 据此给出了结合报文序列与报文对的澳4 量方法p a n l m t e 嗍。 k a p o o r 等【船l 将单报文方法中基于单向延迟过滤的思想引入报文对方法，瓶颈带宽的计 算仅采用单向延迟之和最小的报文对