（无线电物理专业论文）网络可用带宽测量关键技术研究.pdf

摘要 摘要 可用带宽测量对于网络行为分析 刚络业务质量保证 网络负载均衡 流媒 体的速率控制 服务器的动态选择 覆盖网络 o v e r l a yn e t w o r k 的路由选择 拥 塞摔制等网络应用有很重要的意义 现有的可用带宽测量方法主要对端到端路径 进行测量 实际给出的是路径上承压链路 具有最小可用带宽 的信息 而没有提 供其余关键链路的信息 现有的瓶颈链路定位工具只能定位路径上承压链路的位 置 由于网络总可用带宽不能由路径的可用带宽简单相加获得 而且路径上的瓶 颈链路不一定是网络的瓶颈链路 所以我们需要研究一些新的可用带宽测量技 术 以克服现有技术的不足 本文的工作包括 改进了现有的一种可用带宽测量 方法 提出了两种链路可用带宽测量方法 首次提出了两种网络总可用带宽测量 方法 本文提出的链路可用带宽测量算法包括l i n k p p q 和p q l i n k 它们能够测量 路径上任意链路的可用带宽和跟踪链路上背景流的变化 l i n k p p q 部署在路径的 两端 不需要中间路由器提供除存储转发之外的功能 p q l i n k 则只需要部署在 路径的一个端点 不需要访问路径的另外一个端点 所以便于在实际网络中广泛 应用 本文在仿真环境下 通过重放实际环境中的背景流与构造不同的流量场景 研究了这两种算法的性能与参数的关系 实验结果表明l i n k p p q 和p q l i n k 能够 比较准确且平稳地对两条典型路径上每条链路的可用带宽进行测量 在实验网 上 本文验证了l i n k p p q 在三种典型场景下的性能 测量紧邻狭窄链路之后的 大容量链路 测量背景流变化的狭窄链路前面的大容量链路 测量给定路径上多 条狭窄链路 这三种情况都是现有路径可用带宽测量算法所无法测量的 此外 l i n k p p q 和p q l i n k 可以估计路径的可用带宽 并且在测量具有多条狭窄链路的 路径的可用带宽时 性能比现有的方法更好 本文所提出的一种网络总可用带宽测量算法首先通过全网链路可用带宽测 量 运用最大流算法定位网络最小可用带宽割集实现网络真实瓶颈链路集位置的 估计 然后通过对该割集的链路进行测量实现网络总可用带宽的估计 此方法保 证了测量的准确性 降低了测量的负载 提高了跟踪背景流变化的能力 仿真实 验表明 无论是恒定的或变化的背景流 单次全网链路测量就能比较准确地定位 i i i 摘要 网络瓶颈链路 此方法能够准确地估计网络的总可用带宽 迅速跟踪网络的背景 流的变化 本文所提出的另一种网络总可用带宽估计方法利用现有的路径瓶颈链路定 位方法定位网络中各路径的瓶颈链路 根据瓶颈链路被共享的程度 从中选出对 网络性能影响较大的链路作为网络的关键链路集 然后利用现有的路径可用带宽 测量工具估计关键链路的可用带宽 进一步估计全网的可用带宽 这种方法扩展 了路径可用带宽测量方法和瓶颈链路定位方法的功能 仿真实验表明 此方法能 近似地估计出网络总可用带宽 i v 关键词 主动测量 可用带宽测量 瓶颈链路定位 a b s t r a c t a b s t r a c t a v a i l a b l eb a n d w i d t h a b m e a s u r e m e n ti s i m p o r t a n tf o rm a n y i n t e r n e t a p p l i c a t i o n s s u c ha sn e t w o r kb e h a v i o ra n a l y s i s n e t w o r kq u a l i t yo fs e r v i c e q o s g u a r a n t e e n e t w o r kl o a db a l a n c i n g s t r e a m i n gm e d i ar a t ec o n t r o l s e r v e rd y n a m i c s e l e c t i o n r o u t i n gi no v e r l a yn e t w o r k c o n g e s t i o nc o n t r o l a n ds oo n e x i s t i n ga b m e a s u r e m e n tt o o l sm a i n l ym e a s u r ea bf o raw h o l ee n d t o e n dp a t ho ft h en e t w o r k a n dp r o v i d ei n f o r m a t i o na b o u tt h et i g h tl i n k s o t h e rt h a nv i t a ll i n k s e x i s t i n g b o t t l e n e c kl i n kl o c a t i o nt o o l sc a no n l yl o c a t et h et i g h tl i n kw h o s ea bi sm i n i m a lo n a p a t h b e c a u s et h et o t a la b o fan e t w o r kc a l ln o tb eo b t a i n e db ys i m p l ea d d i t i o no ft h e e s t i m a t e da bo fi t sp a t h s a n dt h eb o t t l e n e c kl i n k so nt h ep a t h sa r en o ta l w a y st h e b o t t l e n e c kl i n k so ft h en e t w o r k w en e e dt od e v e l o pn e w t e c h n i q u e sf o ro v e r c o m i n g t h el i m i t a t i o no ft h ee x i s t i n ga bm e a s u r e n e tm e t h o d s t h ec o n t r i b u t i o no ft h i sp a p e r i n c l u d e s i m p r o v i n ga ne x i s t i n ga bm e a s u r e m e n tt o o l p r o p o s i n gt w oa be s t i m a t i o n m e t h o d sf o ra r b i t r a r yl i n k s a n df i r s tp r e s e n t i n gt w oa l g o r i t h m sf o rm e a s u r i n gt h et o t a l a bo f an e t w o r k t h i sp a p e rp r e s e n t st w oa l g o r i t h m sl i n k p p qa n dp q l i n k b o t ho fw h i c hc a n m e a s u r et h ea bo fa n yl i n ka l o n gap a t h a n dt r a c kt h ev a r i e t yo ft h ec r o s s t r a f f i co n t h el i n k l i n k p p qi sd e p l o y e do nt w oe n d p o i n t so fap a t h b u td o e sn o tn e e dt h e m i d d l er o u t e r st op r o v i d ee x t r af u n c t i o n so t h e rt h a nt h eb a s i cf u n c t i o no fs t o r ea n d f o r w a r d p q l i n ki si n s t a l l e do n o n ee n d p o i n to fap a t ha n dd o e sn o tn e e dt ov i s i tt h e o t h e re n d p o i n t a n ds oi ti ss u i t a b l et ob ee x t e n s i v e l ya p p l i e di nr e a ln e t w o r k s i n s i m u l a t i o nc i r c u m s t a n c e s t h i sp a p e rp r o d u c e sd i f f e r e n tc r o s s t r a f f i cs c e n a r i o sb y r e p l a y i n gt r a c e sc o l l e c t e df r o mr e a ln e t w o r k s a n ds t u d i e st h er e l a t i o n s h i pb e t w e e nt h e p e r f o r m a n c eo ft h e s et w oa l g o r i t h m sa n dt h e i rp a r a m e t e r s s i m u l a t i o nr e s u l t ss h o w t h a tl i n k p p qa n dp q l i n kc a r lq u i t ea c c u r a t e l ya n ds t a b l ym e a s u r ea bo fe a c hl i n ko n t w ot y p i c a lp a t h s t h el a b o r a t o r i a le x p e r i m e n t ss h o wt h a tl i n k p p qc a na c c u r a t e l y m e a s u r et h ea bu n d e rt h ef o l l o w i n gs i t u a t i o n s a m e a s u r i n gal i n kw i t l ll a r g e c a p a c i t yb e l l i n dt h en a l t o wl i n k b 1m e a s u r i n gal i n k 嘶ml a r g ec a p a c i t y b e f o r et h e n a r r o wl i n ko nw h i c ht h ec r o s s t r a f f i cc h a n g e s c e s t i m a t i n gt h ea bo ft h en a r r o w v a b s t r a c t l i n k so nap a t hh a v i n gm u l t i p l en a r r o wl i n k s t h ee x i s t i n ga bm e a s u r e m e n tm e t h o d s f o rp a t h sa r eu n a b l et o c o m p l e t et h e s em e a s u r e m e n t su n d e rt h ea b o v es i t u a t i o n s l i n k p p qa n dp q l i n kc a nf u r t h e r m o r eb eu s e dt oe s t i m a t et h ea bo fap a t h a n d o b t a i nb e t t e rm e a s u r e m e n tr e s u l t st h a no t h e ra bm e a s u r e m e n tt o o l sf o rp a t h sw h e n m e a s u r i n gt h ea bo fp a t h st h a th a v em u l t i p l en a r r o wl i n k s t h i sp a p e ri n t r o d u c e san o v e lm e t h o df o rm e a s u r i n gt h et o t a la bo fan e t w o r k a tf i r s t i tm e a s u r e sa l ll i n k so n an e t w o r k t h e nm a k e su s eo fm a x f l o wa l g o r i t h m st o f i n dt h em i n a b c u ta sa 1 1e s t i m a t i o no ft h el o c a t i o no ft h et r u eb o a l e n e c kl i n k si nt h e n e t w o r k a n df i n a l l yc o m p u t e st h et o t a la bo ft h en e t w o r kb ya d d i n gt h ea b so fa l l t h el i n k si nt h em i n a b c u t t h i sm e t h o dc a ne n s u r et h em e a s u r e m e n tv e r a c i t y d e c r e a s et h ep r o b i n gl o a d a n db o o s tu pt h ec a p a b i l i t yo ft r a c i n gt h ev a r i e t yo f c r o s s t r a f f i c s i m u l a t i o n ss h o wt h a t n om a t t e rt h et r a f f i cs c e n a r i o sk e e pc o n s t a n to r c h a n g ed u r i n gt h em e a s u r i n gp r o c e s s t h eb o t t l e n e c kl i n k so ft h en e t w o r kc a nb e e x a c t l yl o c a t e db ym a k i n gas i n g l em e a s u r e m e n to fe a c hl i n ko nt h en e t w o r k t h i s m e t h o dc a na c c u r a t e l ye s t i m a t et h et o t a la bo fan e t w o r k a n dc a nq u i c k l yt r a c et h e c r o s s t r a f i l e t h i sp a p e ra l s op r e s e n t sa n o t h e rt o t a la be s t i m a t i o nm e t h o df o ran e t w o r k i t u s e st h ee x i s t i n gb o t t l e n e c kl i n kl o c a t i o nm e t h o d st of i n dt h eb o t t l e n e c kl i n k s o n e a c hp a t h c h o o s e st h ep i v o t a ll i n k sf r o mt h eb o t t l e n e c kl i n k sb a s e do nt h e i r f r e q u e n c e ss h a r e db ya l lp a t h s e s t i m a t e st h ea bo nt h e s ep i v o t a ll i n k su s i n gt h e e x i s t i n ga bm e a s u r e m e n tm e t h o d sf o rp a t h s a n df u r t h e re s t i m a t e st h et o t a la bo ft h e n e t w o r k t h i sm e t h o de x t e n d st h ef u n c t i o n so ft h ee x i s t i n ga bm e a s u r e m e n tt o o l sf o r p a t h sa n db o t t l e n e c kl i n kl o c a t i o nm e t h o d s s i m u l a t i o n ss h o wt h a tt h i sm e t h o dc a n a p p r o x i m a t e l yo b t a i nt h et o t a la b o ft h em e a s u r e dn e t w o r k k e y w o r d s a c t i v em e a s u r e m e n t 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 t b o t t l e n e c k l i n kl o c a t i o n v i 原创性声明 原创性声明 本人郑重声明 所呈交的学位论文是本人在导师指导下进行的研究工作以及 取得的研究成果 除了文中已经注明引用的内容外 论文1 i 包含其他个人或集体 已经发表或撰写过的作品成果 对本文的研究作出重要贡献的个人和集体 均已 在文中以明确的方式标明 本人完全意识到本声明的法律结果由本人承担 学位论文作者签名 何耗 日期 一以年1 2 月岁日 学位论文使用授权声明 本学位论文作者完全了解中山大学有关保留 使用学位论文的规定 即学校 有权保留学位论文并向国家主管部门或其指定机构送交论文的电子版和纸质版 有权将学位论文用于非赢利目的的少量复制并允许论文进入学校图书馆 院系资 料室被查阅 有权将学位论文的内容编入有关数据库进行检索 可以采用复印 缩印或其他方法保存学位论文 学位论文作者签名 何朽 导师签名 日期 矽9 9 年fz 月7 日 日期 力疹子年f 二月3 日 第一章绪论 第一章绪论 1 1 可用带宽测量研究意义 i n t e r n e t 的发展过程中 网络测量起到很重要的作用 虽然目前i n t e m e t 能够 正常工作 但网络的性能还可以进一步地提高 网络测量帮助我们通过研究网络 的运行方式了解网络的设计 并理解它为什么以目前这样的方式运行 1 2 帮助 我们诊断已经出现的网络问题 并找出问题的解决办法 帮助我们设计新的网络 体系结构以满足下一代网络应用的需求 网络测量所面对的主要问题包括 如何 有效狭得数据 3 1 以及数据的后期处理 4 1 下面这些因素不利于进行网络测量 网 络核心设计得比较简单 连接和流都是与状态无关的 t c p i p 网络的分层体系 结构屏蔽了低层的信息 网络中存在许多看不到的设备 比如防火墙 流量整形 器 代理和n a t n e t w o r ka d d r e s st r a n s l a t i o n j 曼务器等 由于竞争的需要 因特 网服务提供商 i n t e m e ts e r v i c ep r o v i d e r i s p 不会公布涉及自身利益的网络拓扑 和流量的信息 即使公布拓扑信息 也主要是自治域 a u t o n o m o u ss y s t e m a s 级 的宏观拓扑 而不是路由器级的拓扑 目前国外研究机构进行网络测量的组织主要有c a i d a 5 1 i e p m t 6 1 i n t e m e t 2 a b i l e n e 7 1 m a w i i s n i m i 9 n p a c in w s 1 0 p p n c g t l1 r i p e r i s 1 2 r i p e t t m 13 1 s u r v e y o r t l 4 t r i u m f 15 1 u o r e g o n r o u t ev i e w s v r o j e c t 1 6 1 w a n d 1 7 等 其中c a i d a 开展的研究包括网络拓扑测量 叫络安全 流量分析 路由和地址信息分析 d n s 监控与保护 网络政策与经济 可视化等项目 国 内的有清华大学的大规模互联网络性能监控模型l i p m 1 8 中科院计算所的分布 式大型网络性能监测与在线分析系统n i p m a s 1 9 哈尔滨大学的大规模网络拓 扑测量原型系统 能够对i n t e r n e t 路由器级拓扑自动发现 2 0 等研究成果 网络测量包括主动测量和被动测量 1 1 可用带宽测量研究意义 主动测量一般在网络的边缘引入探测分组 端主机在网络边缘分析穿过网络 的探测分组所携带的信息从而获得网络的内部状况 主动探测的优点是不需要网 络中问路由器提供特殊的权限 在网络的边缘就获取网络内部的信息 尤其适合 于在异构的网络环境中观察端到端数据传输的q o s q u a l i t yo f s e r v i c e 另外不涉 及用户的网络信息 对用户是安全的 但是 设计主动测量工具时需考虑主动探 测引入的探测流对网络中应用的影响 以避免引起网络拥塞 主动测量广泛应用 于网络层析成像 2 1 1 和网络性能参数的测量 2 2 1 被动测量一般在网络中设置监测点 捕捉流经监测点的网络背景流 或者查 询网络设备的管理信息库 m a n a g e m e n ti n f o r m a t i o nb a s e m i b 获得网络各接 口的状态信息 2 3 1 被动测量在测量时不增加网络负载 对监测点的网络行为进行 详尽的记录 然而 下面几个原因影响了通过被动测量获得可用带宽以及瓶颈链 路的位置 不断增长的 分布化 不协作 异构的i n t e m e t 不利于网络状态信息 的共享 在高速发展的互联网上存储流量数据需要巨大的存储空间 并且不便于 管理数据 由于企业竞争和保密的需要 i s p 一般不会向公众提供查询路由器上 流量信息的权限以及不会公布获得的流量和路由级的网络拓扑信息 也不允许在 网络内部随便设置监测点 威胁到用户的隐私和信息安全 如果核心路由器提供 额外的查询服务 很可能影响路由器转发数据分组的功能 探测点只能收集到局 部信息 无法了解网络端到端的行为和网络整体的行为 可用带宽测量和瓶颈链路定位一般属于主动测量 主动测量的对象包括单向 时延 o n e w a yd e l a y 时延抖动 d e l a yv a r i a t i o n 来回时间 r o u n d t r i pt i m e 分组 丢失 p a c k e tl o s s 分组重新排序 p a c k e tr e o r d i n g 路由和带爿2 2 1 主动测量还包 括拓扑测量和瓶颈链路定位等 可用带宽测量一般假设网络的拓扑已知或可以通过现有的拓扑测量方法 2 0 2 1 2 禾3 3 1 等测量获得 而且一般假设链路的容量已知或可以通过现有的链路容量测 量工具 3 4 4 1 等测量获得 可用带宽测量除了具有网络测量的研究意义外 还具有下面几个方面的研究 意义 1 网络安全方面 2 第一章绪论 网络安全领域中现有的流量异常检测和网络行为分析系统 比如a r b o r n e t w o r k s t 4 2 1 l a n c o p e l 4 3 1 m a z un e t w o r k s l 4 4 1 n i t r o v i e w t 4 5 1 等 一般部署在企业内部 互联网中 通过s f l o w t 4 6 1 c f l o w l 4 7 1 n e t f l o w t 4 8 等工具获得网络中各条链路的流量 信息 然后采用特征检测和异常检测机制 4 9 规1 从网络流量数据中识别感兴趣的网 络行为 比如流量异常 然而要在i n t e r a c t 上进行网络行为分析 需要用可用带 宽测量等主动测量方式收集数据 网络攻击通过消耗受害节点的计算资源以及其周边网络有限的带宽资源 使 得网络和节点不能提供正常服务 一般网络攻击向受害节点发送大量请求或者伪 造的数据分组 然而存在一种更加隐秘的攻击方式 即通过抬高服务节点周围网 络的背景流强度来达到攻击的目的 服务器周围网络中存在三种类型的流 一是 端主机向服务器发送的请求 二是服务器对请求的响应 三是穿过服务器周围网 络的背景流 在服务器前端可以检测流向服务器的攻击流和服务器被动响应的攻 击流 然而对于不经过服务器前端的攻击流却无法检测出来 因此 对这种流的 检测有着重要的意义 由于这种攻击影响了服务器周围网络的总可用带宽 通过 测量网络总可用带宽的变化 可以间接检测这类攻击 2 网络服务质量方面 链路带宽和节点缓存区资源是保证网络q o s 的决定性因素 影响网络吞吐 量 时延 分组丢失率等性能指标 随着q o s 问题研究的深入 i e t f 提出两种 不同的q o s 体系结构 分别是综合服务 i n t e g r a t e ds e r v i c e s i n t s e r v s 3 和区分服务 d i f f e r e n t i a t e ds e r v i c e s d i f f s e r v 5 4 1 i n t s e r v 依据资源预留协议r s v p t 5 5 实现q o s 的协商机制 为每个流逐节点保留流的路径状态和资源预留状态 通过接纳控制 a d m i s s i o nc o n t r 0 1 决定链路或节点是否有足够的资源满足流的资源预留要求 通 过传输控s 0 t r a f f i cc o n t r 0 1 对i p 分组进行分类 调度和路由 然而 网络系统状 态和链路容量 可用带宽变化的不确定 使得端到端带宽预留缺乏保障 5 6 1 端到 端可用带宽测量结果体现在不影响现有网络应用的前提下路径上路由器能够接 纳的最大的流量 如果用户请求的带宽不超过这个上限 那么路径两端节点可以 缩短q o s 协商的时间 在数据传输过程中 对各链路容量和可用带宽的测量有 助于及时了解网络的状态以及进行传输控制 区别于i m s e r v 对网络资源的集中 控制方式 d i f 奄e r v 在网络的内部节点只进行简单的调度转发 边缘节点负责保 3 1 2 论文的研究内容和创新点 存流的状态信息以及进行流的传输分类与调节 由于d i f f s e r 矿的资源控制方式是 分布式的 需要在边界节点控制进入网络的总流量 以避免内部节点和链路产生 拥塞 网络总可用带宽测量的结果反映了网络还能够容纳的流量 边缘节点可根 据带宽测量结果调整进入网络的流量 3 网络可用带宽测量还应用于网络负载均衡 流媒体的速率控制 端到端 的接入控制 服务器的动态选择 覆盖网络 o v e r l a yn e t w o r k 中的路由选择 拥 塞控制等网络应用 与可用带宽测量对应的瓶颈链路的定位不仅帮助动态选择服 务器和覆盖网络中的路由 而且能够帮助检查网络故障 找到网络拥塞产生的原 因 以及建议采取合理的措施来避免拥塞 从而提高网络的性能 1 2 论文的研究内容和创新点 在国家自然科学基金刚络与信息安全重大研究计划项目 网络时空行为与 2 0 0 8 奥运会网络安全关键技术研究 项目号 9 0 3 0 4 0 11 国家自然科学基金 广 东联合基金重点项目 下一代互联网 i p v 6 应用核心技术分类控制方法研究 项 目号 u 0 7 3 5 0 0 2 国家高技术研究发展计翅j 8 6 3 项目 基于应用行为规范的网 络主动实时防护系统 项目号 2 0 0 7 a a 0 1 2 4 4 9 等项目的资助下 本文深入研 究了网络测量领域中现有的路径可用带宽测量技术和路径瓶颈链路测量技术 指 出现有研究的不足之处 对现有的路径可用带宽测量算法 p t r l 5 7 1 进行了改进 并根据应用的需求 把可用带宽测量的研究从路径层次扩展到网络中的任意链路 和网络的整体 并且我们揭示了网络总可用带宽与网络瓶颈链路之间的内在联 系 在解决网络总可用带宽测量问题的同时也解决网络的瓶颈链路的定位问题 论文的创新点具体来说主要体现在下面几个方面 1 分析了现有端到端路径可用带宽测量中广泛使用的等长分组对或分组链 不适用于测量路径中的任意链路的原因 在此基础上 提出了一种新颖的非协作 的链路可用带宽测量算法l i n k p p q t r a i n so fp a i r so fp a c k e t q u a r t e t su s e dt o m e a s u r ea v a i l a b l eb a n d w i d t ho f a r b i t r a r yl i n k s 它部署在路径的两个端点 能够测 量路径上任意链路的可用带宽 这克服了现有可用带宽测量方法只适合于测量整 4 第一章绪论 条路径可用带宽的局限性 在仿真环境下 通过重放实际环境的背景流构造不同 的流量场景 仿真结果表明该算法对两条典型路径上每条链路的可用带宽进行准 确且平稳地测量 实验网的实验验证了该算法适用于以下三种特殊场景的可用带 宽测量 测量紧邻狭窄链路之后的大容量链路 测量变化背景流下狭窄链路前面 的大容量链路 测量给定路径上多条狭窄链路 这三种情况都是现有路径可用带 宽测量算法所无泫测量的 此外 该算法在估计具有多瓶颈链路的路径可用带宽 时 准确度优于著名的i g i p t r 5 7 和s p r u c e l 58 1 其中p t r s p r u c e 通常低估了路 径可用带宽 而i g i 不能跟踪路径上背景流的变化 2 提出一种新颖的链路可用带宽测量方法p q l i n k 它能够从网络中的单一 节点测量网络中任意链路的可用带宽 不仅能够提供网络路径上瓶颈链路的信 息 还能监测其余链路的状况 与现有的路径可用带宽测量方法有很大的不同 该算法只需要部署在网络中的一个节点 从而更容易应用 仿真实验表明该算法 能够准确和平稳地测量给定两条典型路径上各链路的可用带宽 测量具有单瓶颈 链路的路径的可用带宽时取得和s p r u c e 近似的测量性能 而测量具有多瓶颈链 路的路径的可用带宽时 该算法的性能优于s p r u c e 3 首次提出网络总可用带宽测量方法 首先 本文基于链路可用带宽测量方法和成熟的网络流理谢5 9 1 提出一种网 络总可用带宽测量算法 这种方法首先依次对网络中每条链路的可用带宽进行测 量 再运用最大流算法定位最小可用带宽割集 然后通过对最小可用带宽割集中 每条链路的可用带宽进行测量 获得网络总可用带宽的估计值 该算法交替进行 全网链路测量和最小可用带宽割集测量的方式既保证了测量的准确度 又降低了 测量负载以及增强了算法跟随背景流变化的能力 仿真表明 当网络处于不同的 流量场景时 链路可用带宽测量算法p q l i n k 都具有良好的性能 在测量过程中 无论网络的流量场景恒定或变化 单次全网链路测量可以比较准确地定位网络的 瓶颈链路 在网络中流量场景变化的情况下 该算法结合全网链路测量和最小可 用带宽割集测量 能够准确地估计网络的总可用带宽 迅速跟踪网络的背景流的 变化 其次 本文提出一种基于路径测量的网络总可用带宽近似估计方法 它利用 现有的路径瓶颈链路定位方法定位网络中各路径的瓶颈链路 然后根据瓶颈链路 5 1 3 论文结构 被共享的程度 从中选出对网络性能影响较大的链路作为网络的关键链路集 再 利用现有的路径可用带宽测量工具估计关键链路的可用带宽 进一步估计全网的 可用带宽 仿真实验表明 此方法能近似地估计出全网总可用带宽 1 3 论文结构 后续的章节的内容安排如下 第二章介绍与本论文相关的基本理论和技术 内容包括 网络流理论 基本 的网络性能度量 可用带宽测量和瓶颈链路定位的研究现状 现有研究的不足 本文对路径可用带宽测量算法p t r 进行的改进 第三章提出一种非协作的链路可用带宽测量技术l i n k p p q 第四章提出一种单端链路可用带宽测量技术p q l i n k 第五章提出两种网络总可用带宽测量方法 第六章对本文的可用带宽测量算法进行实验验证 第七章总结全文 并给出研究展望 6 第二章基本理论与技术 第二章基本理论与技术 本章2 1 节介绍网络流理论 2 2 节介绍与可用带宽测量相关的几个网络性 能度量 2 3 节和2 4 节分别介绍可用带宽测量和瓶颈链路定位的研究现状 2 5 节指出现有研究的不足之处 2 6 节对路径可用带宽测量算法p t r 进行改进 2 7 节总结本章 2 1 网络流理论 网络流理论 5 9 6 0 1 是 1 7 传统的学科 植根于机械制造学 工程学 应用数学 计算机科学和运筹学等学科 其应用已遍及通讯 运输 电力 工程规划 任务 分派 设备更新以及计算机辅助设计等众多领域 网络流理论中有三个基本的问 题 最短路径问题 最大流问题和最小费用流问题 我们重点介绍与最大流问题 相关的网络流理论 有向网络g k 日由节点集合矿和弧集合e 构成 集合v 包括n l a q 个节点 弧集合e 包括m l g l 条弧 这里用弧表示有向边或不同节点的有序对 弧l i 力 连接节点勘和x j 其容量用c f 力 简写为嘞表示 是非负的 令u m a x c v c i 1 构成的路径p u 称为p 的局部路径 c f u 和a f i j 分别表示 前向局部路径尸f 旷 厶 l f 件1 l f j 的容量和可用带宽 相应地 用c s j 和a b i j 分别表示后向局部路径p b f 广 b f l b w i 三彤 的容量和可用带宽 下面我们介绍几个与可用带宽测量紧密相关的几个度量 度量的定义与 2 2 和 7 3 一致 1 容量 1 0 第二章基本理论与技术 从节点x 净0 x g 之间的链路l i 的容量c f 是该链路上在i p 层能够传输的 最大可能的吞吐量 路径尸的容量a 尸 是路径两个端节点之间在i p 层能够传输 的最大可能的吞吐量 数值上等于路径所有链路的容量的最小值 即 c p 2 m i n l 班p c i 力 容量最小的链路称为狭窄链路 n a r r o wl i n k 目前在链路容量测量的典型方法有p a t h c h a r 36 1 b i n g 38 1 c l i n k 35 1 p c h a r 3 9 1 p a c k e tt a i l g a t i n g 4 0 1 p a c k e tq u a r t e t s 3 4 1 以及针对非对称链路测量的 4 1 7 4 1 路径 容量测量的工作有b p r o b e 7 5 1 p a t h r a t e 7 6 1 n e t t i m e r 7 7 s p r o b e t 7 8 和1 7 9 等 删可以对 路径中的任意局部路径进行测量 2 可用带宽 不同于几乎不随时间变化的容量 可用带宽具有时变性质 这使得可用带宽 测量难于容量测量 链路l i 力在一段长为耐间区间 t o t o r 的平均利用率为 甜 f 力 0 s 甜 f 力 1 相应地链路 f 力的背景流的平均强度为 坝f 炉 f 力 c f 力 此链路的可用带宽定义为 a i 力 c f 力一似f 力 而路径尸的可用带宽定义为 彳 尸 2 m i n l o 力e e a i 力 可用带宽最小的链路称为承压链路 t i g h tl i n k 直觉上 狭窄链路与承压链 路不总是在同一位置 一条网络路径上存在多条狭窄链路或多条承压链路也是可 能的 我们用 b 尸 a r g m i 妒n c f 肼 代表路径尸的狭窄链路的集合 一条路径上的承压链路是对端到端应用影响最大的链路 所以也称为路径的 瓶颈链路 网络中最影响网络性能的链路称为网络的瓶颈链路 3 时延 时延分为链路时延和路径时延 2 2 相关度量 我们先介绍分组在路径上的传输过程 一个分组p 从发送端出发 经过一系 列路由器 到达接收端 分组p 经过一条链路 f 经受了几种类型的时延 首 先 节点x 将分组p 送到一个输出缓冲区队列 等待通过链路上 f 力发送到节点 x j 设在 口 f 时刻分组p 的最后一个比特进入此队列 排队等待向该物理链路 传输 为叙述方便 简称乙 f 为分组p 到达链路上 f 的时刻 分组p 在经过排 队时延以f 力以后开始被传输 经过s p c f 其中s 是分组p 的长度 的传输 时延 分组的所有比特都被传输到物理链路三以 之上 一旦其比特出现在物理 链路上 立即向x j 传播 每个比特从该物理链路的起点到x j 的时间称为传播时延 4 f 力 取决于该物理链路的长度与所采用的媒介 x j 在接收完分组p 的所有比 特后 检查p 的首部 并决定向哪条输出链路转发 然后将p 转移到通往此输出 链路的缓冲队列中 这部分时间称为处理时延 f 刀 分组p 的最后一个比特 进入此队列的时刻是f f 力 简称为离开链路上 f 力的时刻 至此 分组完成了 在一条链路上的传输 注意 分组在一条链路上的传输不仅包括了在物理链路上 的传输过程 而且包括节点对分组的处理以及分组的排队等待等过程 因此 分 组p 经过一条链路三 力的总时延为 d i 歹 t t i 歹 一t o i 歹 c o i 歹 s p c i 歹 d p r o p i j d 孟 f 2 3 其中 传播时延研唧 f 力和处理时延c g i d 与分组的长度没有关系 可认为 是经过 亿 移的每个分组都需要经过的恒定时延 路径尸的时延是路径上各链路的时延的累加 即 舀 p d i 2 4 l 巧 e 尸 在路径上没有背景流或背景流可以忽略时 链路时延与容量成反比的性质广 泛应用于链路容量的测量 3 1 1 在分组大小和链路容量一定时 路径时延中可变 部分是分组排队时延 反映网络的拥塞情况 s l l 提出的可用带宽测量工具 p a t h l o a d 通过分析分组的端到端时延的变化来判断探测流的速率是否与路径可用 带宽匹配 o w a m p 8 2 1 和q o s m e t l 8 3 1 b a d a b i n g s s l 都能够测量网络中两个节 点之间路径的时延 4 1 时延抖动 时延抖动定义为前后两个分组经过端到端路径的时延差 高时延抖动将损害 实时多媒体在网络中的传输 q o s m e t 8 3 8 4 1 汞 i p e r d 8 6 1 可以测量路径的时延抖动 1 2 第二章基本理论与技术 5 丢失率 分组丢失率定义为没有被接收的分组数量与发送的分组的总数量的比值 路 径的丢失率是链路丢失率的乘积 取对数后 路径的对数丢失率是各链路对数丢 失率的和 在上面的性能指标中 时延和丢失率 取对数后 具有累加的性质 所以从端 到端路径的时延和丢失率可以推测网络中链路的时延和丢失率 8 7 8 引 2 3 可用带宽测量 现有可用带宽测量工作主要是对端到端路径进行测量 可用带宽测量工作可 以追溯到1 9 9 1 年 k e s h a v e 8 9 1 根据分组对的间隔反比于可用带宽的现象 提出了 一种分组对速率探测算法和一种基于速率的流控机制 能够应用于路由器采取公 平调度机制的网络中 这不适合于路由器普遍采取先进先出队列机制的现代网 络 c a r t e r 等 7 5 1 设计的c p r o b e 工具不局限在采用公平调度队列机制的网络环境 中 c p r o b e 的发送端向接收端以超过路径容量的速率发送一串i c m p 回显请求 分组 然后统计i c m p 回显应答分组平均到达速率作为对路径可用带宽的估计 类似的技术应用于p i p e c h a r t 蚓 c p r o b e 和p i p e c h a r 的潜在假设是分组串在路径上 扩散的间隔与路径可用带宽成反比 然而 p l 指出分组串的扩散间隔测量的是一 个称为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 的度量 它低于路径的容量 但不是路 径可用带宽 背景流分组 囵 r 探测分组 二卫o 图2 2 探测速率模型p r m 1 3 2 3 可用带宽测量 根据可用带宽的估计方法 可用带宽测量模型分为探测速率模型 p r m p r o b er a t em o d e l 5 7 8 1 9 2 9 7 1 和探测间隔模型 p g m p r o b eg a p m o d e l 5 7 5 8 9 8 1 p r m 基于自诱导拥塞 s e l f i n d u c e dc o n g e s t i o n 的概念 如图2 2 所示 探测 分组以一定的速率尺从发送端向接收端传输 当探测速率达到一定程度 大于可 用带宽彳 时 将造成网络瞬时拥塞 从而使探测分组的排队时延瞬问增加 使 网络路径从不拥塞状态转移到拥塞状态的临界点 对应的探测分组发送速率被认 为等于路径的可用带宽 m e l a n d e r 等 9 3 j 设计的t o p p t r a i n so f p a c k e tp a i r s 以逐 渐增大的速率向接收端发送分组对链 采用线性回归的方法分析发送速率与到达 接收端的速率的分段线性关系曲线 获得对承压链路的容量和可用带宽的估计 t o p p 也可用于测量路径上多条拥塞链路 但这些链路的可用带宽需满足a a j f 删的条件 然而即使获得测量结果也难以与具体链路对应起来 j a i n 等 8 u 提出s l o p s s e l f l o a d i n gp e r i o ds t