（计算机应用技术专业论文）基于回归模型的ip网络可用带宽测量研究.pdf

重庆邮i 乜学院倾i 论文 摘要 准确获取一条路径上的可用带宽对于l p 网络有效地实旌q o s 服务至天重 要 如端到端的接入控制 服务器选择 路由选择 拥塞控制 验证s l a 等 目前可用带宽的测量多采用主动测量方式 由于现有测量工具几乎都以i c m p 或者u d p 协议承载探测包 冈此无法获得精确的时削戳及路径等信息 此外当 前的可用带宽测最主要依赖于测量主机的系统性能 如系统i o 带宽 系统定 h j 器的分辨率等 然而相比于i 酬络带宽的飞速增长 测量主机系统性能的提高 显得十分缓慢 特别是其系统i o 带宽已经远远落后于网络带宽 存测量时会 产 生 潜在带宽 p o t e n t i a l b a n d w i d t h 的问题 这就导致许多现有的模型难以 适成面向高速网络的可用带宽测量应用 本论文的工作是以高速i p 网络的 u 用带宽测量为研究对象 研究网络上一 条确定路径的可用带宽测量问题 研究方法是以排队论和回归分析法为王甲论基 础 建立测量模型 利用i p 测量协泌 i p m p 承载探测包 通过获取探测包 经过的一条确定路径的时延信息 预测出该路径上的町用带宽 论文首先分析了当前两个 i 要的可用带宽测量模型 p g m 模型和p r m 模 型 及相关的算法 讨论了模型中存在的问题及其发展趋势 然后提出了一种 面向高速i p 网络的基十回归分析的t l j 用带宽测量模型 该模型能够在网络边界 处获取对应丁 条确定路径的时延信息 并根据该测量信息 计算出测量周期 内垓路径上的流量 运用川归分析法 对不同流量条件下的测茸结果进行拟合 得出被测路径上流量与时延的叫归方程 并掘此方程预测被洲路径上的可用带 宽 由十接收到的探测包所携带的时i r j 戳是由该路径上的路山器提供的 凶此 可以在一定程度上解决单纯依赖测黾主机性能而产生的 潜在带宽 问题 使 得模型具有测量代价和开销都较小 同时又能保证测量精度的优点 模掣的测 量过程具有单向性 计算过程所用的时延信息是时问差 因而无需时钟同步 仿真结果显示存满足测量模型假没条件的情况下 模型是有效的 论文还在 w i n d o w s2 0 0 0 环境中设计了个基十本义测量模型的 能够运行于操作系统内 核的测量系统 实现了测量模型中接收和发送探测包 提取测量数据等基本功 能 经测试达到了测量模型的性能要求 理论 i 可以满足带宽为8 0 0 m b s 瓶颈 链路可用带宽的洲量要求 关键词 可用带宽 主动测量 i p 测量协议 测量模型 回归分析法 重庆邮l 学院坝i 论土 a b s t r a c 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 a b m i sc r i t i c a l it oe f f e c t i v e l yi m p l e m e n t q o ss e r v i c ei nn e t w o r kb a s e di e e g e n d t o e n da d m i s s i o nc o n t r 0 1 s e r v e r ss e l e c t i o n r o u t es e l e c t i o n c o n g e s t i o na v o i d a n c ea n ds l av e r i f i c a t i o n n o w a d a y sa c t i v e m e a s u r e m e n ti st h em a i nm e t h o df o ra b m b u ta l m o s ta l lt h ee x i s t i n gm e a s u r e m e n t t o o l st a k et h ei c m po ru d pa st h ec a r r i e rp r o t o c o lo fp r o b i n gp a c k e t s s ot h a tt h e y c a n to b t a i nt h en e c e s s a r yi n f o r m a t i o ns u c ha sa c c u r a t et i m e s t a m p sa n d r o u t i n g f u r t h e r m o r e t h ee x i s t i n ga b m m o d e l s 柚l yd e p e n do ns y s t e mp e r f o r m a n c eo f m e a s u r e m e n th o s t e g t i m e rr e s o l u t i o n i ob a n d w i d t h w h i c hr e s u l t si nt h e s e m o d e l sc a n tb ea p p l i e dt oh i g h s p e e di pn e t w o r k a n ds e r i o u sr e s t r i c t st ot h e d e v e l o p m e n to f a b m t h em a i na i mo ft h i sa r t i c l ei st h a tm e a s u r e m e n ta v a i l a b l eb a n d w i d t ho fa n a p p o i n t e dp a t hb ym e a s u r i n gt h ed e l a yo fp r o b i n gp a c k e t sw h o s ec a r r i e rp r o t o c o li s i p m p s ow ec a np r e d i c tt h ea v a i l a b l eb a n d w i d t h t h e s ed a t u mc a nb eu s e dt o c o n t r o lt r a f f i ca n dl a y o u tn e t w o r ke f f i c i e n t l yb yt h en e t w o r ka d m i n i s t r a t o r a tf i r s t w ea n a l y z et w om a i na b em o d e ln a m e l yp g ma n dp r m w h i c h e x a m p l e db yt w or e p r e s e n t a t i v ea b ma l g o r i t h m s c o n c l u d et h ee x i s t e n tp r o b l e mi n t h ea b mm o d e l sa n di n d i c a t e st h ed i r e c t i o no ft h ef u t u r er e s e a r c h t h e nw ep u t f o r w a r da l la b mm o d e lb a s e do nr e g r e s s i o na n a l y s i st h a tc a nb eu s e dt oh i g h s p e e d i pn e t w o r k t h i sm o d e lc a no b t a i nt h ep r o b i n gp a c k e t s d e l a y c a l c u l a t et r a 币c a c c o r d i n gt ot h em e a s u r e m e n tr e s u l t a n d f i tt h er e s u l ti no r d e rt h a td e d u c et h e r e g r e s s i o nf u n c t i o no nt r a f f i ca n dd e l a y f i n a l l yw ec a nu s e t h er e g r e s s i o nf u n c t i o nt o p r e d i c ta v a i l a b l eb a n d w i d t hi nt h ea p p o i n t e dp a t h n l ea d v a n t a g e so fo u rm o d e la r e t h el o w e rc o s ta n d o v e r h e a d h i g h e r a c c u r a t e r e s u l t i n d e p e n d e n t c l o c k s y n c h r o n i z a t i o n t h em o d e li sv a l i db ys i m u l a t i o nv e r i f i c a t i o n a t1 a s tw ei m p l e m e n t t h ef u n c t i o no f p r o b i n gh o s ti na b m s y s t e mb a s e do no u rm o d e li nw i n d o w s2 0 0 0 k e yw o r d s a v a i l a b l eb a n d w i d t h a c t i v em e a s u r e m e n t i pm e a s u r e m e n t p r o t o c o l m e a s u r e m e n tm o d e l r e g r e s s i o na n a l y s i s i i 幂庆邮i 乜学院坝i 一论殳 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果 据我所知 除了文中特别加以标注和致谢的地 方外 论文中不包含其他人已经发表或撰写过的研究成果 也不包含 为获得重麽宦g 电堂暄或其他教育机构的学位或证书而使用过的材 料 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了 明确的说明并表示谢意 学位论文作者签名 鸽灵 签字日期 卫肼年厂月幻日 学位论文版权使用授权书 本学位论文作者完全了解重迭自e 虫堂瞳有关保留 使用学 位论文的规定 有权保留并向国家有关部门或机构送交论文的复印件 和磁盘 允许论文被查阅和借阅 本人授权重麽由e 曳堂喧可以 将学位论文的全部或部分内容编入有关数据库进行检索 可以采用影 印 缩印或扫描等复制手段保存 汇编学位论文 保密的学位论文在解密后适用本授权书 学位论文作者签名 伯灵 导师签名 7 t 签字日期 厶j o q 年厂月2 0 日签字目期 加l p 年9 月埤曰 晕庆邮1 u 学院顷 论文 1 1 选题背景 第一章绪论 近年来 随着i p i n t e m e t p r o t o c 0 1 网络的进一步发展 i n t e r n e t 的规模大 幅度地增加 传统电信网络正逐渐演变成为以i p 技术为基础 综合话音 数据 图像 视频的多媒体业务网络 由于各种新的应用带来了新的业务模式 因此 需要动态配置网络设备以便适应不断增长的业务需求 并且对不同的业务需求 提供相应的q o s q u a l i t y o fs e r v i c e 服务保证 因此理解i n t e m e t 业务的动态 性质特别是其流量 i r a f f i c 对于网络管理至关重要 但是由于i p 网络的规模 不断扩大 流量迅速增加 以及采用分布式管理模式 使得对i n t e m e t 流量的观 测变得越来越困难 对网络管理和控制来说 网络测量十分重要 用户需要对其应用 a p p l i c a t i o n 的性能进行监测 以检验服务等级是否得到保涯i 运管商需要监 测当前业务的级别 以便执行与用户达成的协定 以及实施网络规划 控制措 施等 都需要先期进行准确的网络测量 i e t f i n t e m e te n g i n e e r i n gt a s kf o r c e 的i p p m i p p e r f o r m a n c em o n i t o r 工作组已经定义了一些q o s 测度 m e t r i c 如i p 性能测度框架 r f c2 3 3 0 连通性 r f c2 6 7 8 单向延迟 r f c2 6 7 9 单向分组丢失 r f c2 6 8 0 往返延迟 r f c2 6 8 1 单向丢包模式抽样 r f c 3 3 5 7 等 其中一些测度可在网络核心处进行测量 另一些可在网络的边缘处 进行测量 在各种反映网络状态的测度中 一个与流量密切相关的测度 可 用带宽 a v a i l a b l eb a n d w i d t h 是最能体现网络性能好坏的测度之一 根据需求的不同 可用带宽有两种定义 一种指单条链路上的可用带宽 用于拥塞避免和选路 另一种指一条路径上的可用带宽 它反映了网络中一条 路径上最拥挤链路的带宽利用状况 准确地了解一条端到端 e n d t o e n d 路径 上的可用带宽 对于许多网络应用来说很有帮助 如接入控制 a d m i s s i o n c o n t r 0 1 2 服务器选择网 网络路由优化踟 拥塞控制 5 以及s l a s e r v i c el e v e l a g r e e m e n t 验证f 6 j 等 在m p l s m u l t i p r o t o c o ll a b e ls w i t c h 网络中 利用可 用带宽信息有助于建立l s p l a b e ls w i t c hp a t h 选路 最短最宽路径 最宽 最短路径 以及l s p 抢占1 w 等 由此可见 可用带宽的测量对于在网络中实 施流量工程 t r a 币ce n g i n e e r i n g 简称t e 十分有用f i j j 因此 近年来对可 用带宽测量的研究引起了人们浓厚的兴趣 l 且前 可用带宽测量主要基于主动 a c t i v e 和被动 p a s s i v e 测量的方式 利用被动测量方式 如基于s n m p s i m p l en e t w o r km a n a g e m e n tp r o t o c 0 1 机 制只需对链路上的数据包进行采集 就可以提供诸如物理带宽 容量 和利用 重庆邮m 学院硕士论文 率等有关网络单元 路由器和交换机 的详尽统计数据 不会引起链路带宽的 消耗 且测量的准确性较高 但该方法存在以下缺陷 需在被监测的网络中布置数据采集卡 增加了测量成本 在网络中的每个路由器处进行测量 势必增加网络的负担 占用许多的网络 资源 利用s n m p 对大量的测量结果进行传送时 也会造成较大的网络开销 需要有对路由器以及被查询网络设备的m i b r m o n 进行特定访问的权限 因此不便于实施 也缺乏灵活性 被动方式的可用带宽测量工具的主要代表是a b e s t 主动测量方式需要在发送端向网络中注入探测数据包 p r o b i n gp a c k e t s 这会消耗一定的链路带宽 甚至会干扰网络中的正常流量 但相比于被动测量 方式 该方式便于实施 只需要在测量主机 发送主机和接收主机 上安装相 应的测量工具 使它们相互配合工作 即可完成测量 这样测量仅需要在网络 边缘进行 避免了在网络核心处各路由器上实施测量时的困难及其给路由器带 来的开销 对于普通用户来说 用主动测量的方法便于估算网络可用带宽 因 为它无需访问路由器 且可以在网络的边缘进行测量 对于i s p i n t e r n e ts e r v i c e p r o v i d e r 来说 也需要方便快捷的工具对网络的可用带宽进行监测 以便于网 络故障的查找和网络规划的实施 特别是当一条路径跨越若干个网络时 端到 端的测量方式是唯一可行的方法 因此当前基于主动测量的可用带宽测量研究 迅速发展起来 设计高效 精确 快速 消耗带宽小的可用带宽测量模型和算 法成为该领域的研究热点 1 9 1 1 0 1 58 1 目前大多数主动测量工具如t r a c e r o u t e p i n g 等都是利用i c m p 或者u d p 协议来承载探测包 1 0 1 由于这些协议在最初设计时都不是用于网络测量的目的 的 因此不能提供测量者所需要的一些重要信息 如时间戳 路径等信息 而 且其基于这些协议的测量结果的精度和可信度都得不到保证 导致许多主动测 量的工具无法适应日益复杂的网络环境 严重制约了可用带宽测量的发展 目 前i e t f 正在着手研究和制定专用的主动测量协议一i p m p i pm e a s u r e m e n t p r o t o c o l i p 测量协议 5 7 到2 0 0 4 年2 月已经推出了第四个版本的草案 本文的研究工作得到重庆市科委科技攻关项目 7 2 2 0 1 3 2 0 和教育部春晖 计划的资助 1 2 本论文的主要工作和组织结构 本论文的工作是以高速i p 网络的可用带宽测量为研究对象向 研究网络上 一条确定路径的可用带宽测量问题 目的是利用i p 测量协议 i p m p 承载探 蓐庆邮i u 学院坝1 论文 测包 通过获取探测包经过的一条确定路径的时延信息 预测出浚路径上的可 用带宽 所做的主要工作如 f 提出了一种面向高速i p 网络的基于回归分析的可用带宽测量模型 通过在o p x e t 中建立仿真拓扑 设计仿真方案 在模型要求的假设条件 下对测量模型进行了仿真澳 试 并对仿真结果进行了分析和比较 设计了一个基于本文测量模型的测量系统 它能够运行于w i n d o w s2 0 0 0 操作系统内核环境中 实现了接收和发送探测包 提取测量数据等基本功能 并进行了测试 论文的后续组织如下 第二章介绍目前可用带宽测量的现状和基本测量模型 着重分析了两种可 用带宽测量模型的原理及其应用 并指出了其不足和发展趋势 第三章提出了一种面向高速i p 网络的基于回归分析的可用带宽测量模型 利用排队论和回归分析法 r e g r e s s i o n 的相关数学理论 推导出时延与背景流 量的相关公式及回归方程 应用这些公式 可以计算得知测量周期内一条指定 路径上的可用带宽 通过对不同网络负载条件下的测量结果进行拟合 f i t t i n g 最终得到被测路径上可用带宽与时延的回归方程 第四章根据回归模型的假设条件建立了的仿真拓扑 设计了仿真方案 在 不同的网络负载条件下对回归模型进行了仿真测试 对仿真结果的分析显示回 归模型是有效的 通过与i g i 算法测量结果的比较 指出了回归模型的优点和 不足 第五章介绍了本论文中回归模型所用探测包的承载协议 i p 测量协议 以及基于回归模型的测量系统的基本结构 第六章着重阐述了测量系统的系统架构 设计方案及其实现方法 即如何 构建一个运行于操作系统内核的 测量系统专用的协议栈 并通过实际测试说 明了测量系统可以满足测量模型的性能要求 第七章对论文做出总结 并且对需要进行的后续工作做了说明 重庆邮l 也学院硕 j 沦文 第二章可用带宽测量的研究现状 2 1 主动测量简介 在第一章中已经提到了主动测量是铡量可用带宽的重要方法 本节简要介 绍主动测量的基本思想及其特点 s 憾臻am s 静i 鼢 捌a 蝴礴 i l 瓢麓懒 翻w 黼 图2 1主动测量f i 勺基本思想示意图 如图2 1 所示 主动测量的基本思想是将被测网络看成一个 黑箱 通过 向被测网络发送精心设计的探测包 获得感兴趣的测量参数 从而推断被测网 络的特定部分的行为 测量者可以根据测量的需要 灵活地设计具有不同属性 的探测包组成的探铡流 把它们当作输入信号 从发送端开始穿越被测网络 最终到达接收端 通过该方法不但可以测量简单的网络性能指标如一条路径上 的平均延迟和丢包率 而且可以测量诸如链路带宽 可用带宽及背景流量 c r o s s 廿a i s l e 等更高级的网络性能指标 与被动测量不同的是 主动测量不涉及大量 数据包的处理 也不会侵犯用户的通信隐私 2 2 与可用带宽相关的概念 由于目前i e t f 尚未对可用带宽及其相关概念进行明确的定义 为了讨论方 便 参照文献 9 中的相关描述 作出如下定义 设端到端 e n d t o e n d 的路径p 包括n 条链路厶 l 1 l 它们的容量 c a p a c i t y 分别为c 1 c e 它们负载的流量分别为 五 矗 单位为 b i t s 定义一 链路容量c 称为链路带宽 b a n d w i d t h 晕庆邮电学院硕1 j 论文 定义二 若链路厶 1 s 6 2 的带宽g f i n n c c c 则称厶为路径p 的 瓶颈链路 b o t t l e n e c kl i n k 定义三 若链路厶 1 b 中 c 2 m i n c 一 q 一五 e 一以 则 称厶为路径p 的t i g h t 链路 定义四 称链路 上的未用带宽c 一五为该链路的可用带宽4 若 4 c f 一再 m i n a a a 则称4 为路径p 的可用带宽 以上定义的逻辑表示如图2 2 所示 圈2 2可用带宽定义的示意图 显然 链路带宽和可用带宽既有区别又密切相关 链路带宽是一个静态的 概念 对某一链路而言 只要硬件不发生改变 其带宽值就是恒定的 而可用 带宽是一个动态的概念 其值随链路上流量的变化而变化 且始终小于或等于 相应链路的带宽 由于可用带宽的动态性质 使得要准确测量它变得很困难 目前可用带宽的测量模型和算法几乎都是在链路带宽测量模型和算法的基础上 产生的 2 3 链路带宽测量模型及算法 目前用于测量网络中链路带宽的算法和工具很多 但归纳起来都可以用两 种测量模型来描述 即单包模型 o n e p a c k e tm o d e 和包对模型 p a c k e tp a i r m o d e 1 2 2 3 1 单包模型 单包模型用于测量网络中一条路径上各链路的带宽 其基本思想是 假设 路由器是存储转发 s t o r e a n d f o r w a r d 方式并采用f i f o 排队策略的 被测链路 是单通道 s i n g l e c h a n n e l 的 且不考虑探测包在路由器上的排队延迟和处理 延迟 从而近似地得到探测包的传输延迟与探测包长度之间存在线性关系 设 重庆邮电学院硎l 论文 s 表示探测包的长度 表示探测包在第i 条链路上的累计延迟 a l 表示探测包 在第i 条链路上的传播延迟 鱼表示第i 条链路的带宽 则单包模型可用下式表 示 l a 1 2 1 i o 叶 j a c o b s o n 根据该模型于1 9 9 7 年提出了p a t h c h a r 0 3 1 算法 该算法通过向被测 网络发送大小不同的探测包 并在发送端测量出各探测包的r t t 往返延迟 从而根据探测包大小和r t t 值变化的规律 采用数理统计的方法逐跳 h o p b y h o p 地估算出探测包所经路径上各链路的带宽 由于算法中使用了 r t t 因此还要进一步假设网络中路径是 对称 的 尽管测量精度不高 且不适用于高速网络 但p a t h c h a r 算法最大的特点在 于它的实现较为简单 只需要在一台测量主机上安装相应的测量工具 口可 无 需时钟同步 该算法还奠定了带宽测量的基础 由此派生出来的链路带宽测量 算法和工具有 c l i n k l l 4 1 和p e h a r 1 4 等 2 3 2 包对模型 为了测量网络中一条路径上的瓶颈链路带宽而提出的包对模型 其基本思 想是 发送两个大小相等且背靠背 b a c k t o b a c k 的探测包 使它们在瓶颈链 路中一同排队 两个探测包到达接收端的时间间隔就会发生变化 由于瓶颈链 路后的各链路带宽都比瓶颈链路带宽高 因此探测包对到达接收端的时间间隔 就和它们在瓶颈链路中的排队间隔相同 设6 f 表示瓶颈链路的带宽 砖和t 分 别表示两个探测包到达接收端的时间 砰和t 分别表示两个探测包离开发送端 的时间 则包怼模型可用下式表示 1 f 一r m a f j t o 2 2 0 t 包对模型假设 两个探测包在瓶颈链路中排队时 它们之间没有背景流量 c r o s st r a f f i c 探测包对发送的时间间隔 一譬 足够小 对路由器和链路的假 设与单包模型相同 根据以上假设 l a i 和b a k e r 证明了模型的正确性 1 2 1 并由 包对模型推出了多包模型 m u l t i p a c k e tm o d e 当测量满足假设条件时 根据 2 2 式可以很容易地计算出被测瓶颈链路的带宽 6 重庆邮l u 学院颁 论文 岛2 蠢 汜 2 3 式假设两个探测包在瓶颈链路中排队 它们之间没有背景流量的干 扰 若有背景流量插入到两个探测包之间 或在第一个探测包之前排队 则等 式不成立 显然 实际存在的背景流量成了 噪声 必须予以 滤除 以保证测量 的精度 由包对模型派生出来的算法有 t o p p t r a i no f p a c k e tp a i r 算法 p b m p a c k e t b u n c hm o d e s 1 6 算法和t a i l g a t i n g 1 2 j 算法等 相应的测量工具有 p a t h r a t e 1 w n e t t i m e r 1 8 和b p r o b e 2 5 1 等 它们都对包对模型进行了不同程度的改 进 其中t o p p 算法也可以用来测量可用带宽 2 4 可用带宽测量模型及算法 由于单包模型在实现测量的过程中 发送的数据量大 测量耗时长 且不 具备单向性 导致测量结果精确度较低 因此在研究可用带宽测量时 多以包 对模型和多包模型为基础的 目前对可用带宽测量的研究都是指测量瓶颈链路 的可用带宽 即一条路径的可用带宽 与链路带宽测量相比 可用带宽的测量 更加困难 更具挑战性 k e s h a v l l 9 1 最早尝试将包对方法用于在终端主机上测量可用带宽 但由于在 他所用的方法中假设了路由器使用公平排队 f a i rq u e u i n g 的方式 而路由器 在设计时多采用f i f o 排队方式 因此该方法无法应用于当今的网络环境中测 量可用带宽 c a r t e r 等人提出的c p r o b e 2 0 1 算法第一次以端到端的方式测量可用带宽 方 法是通过发送 n 由i c m p 包组成的探测包序列 p a c k e tt r a i n 然后计算探测 包的流量与最后一个i c m pe c h o 包和第一个i c m pe c h o 包到达的时间间隔的比 值 从而得到可用带宽的值 该方法被用于服务器选择 其实质就是多包模型 的应用 不过d o v r o l i s 等人的研究指出c p r o b e 所测的结果是 渐进离差率 a s y m p t o t i cd i s p e r s i o nr a t e 与可用带宽相关 但并非可用带宽 他们还进 一步提出和分析了探测包间隔的多态分布 m u l t i m o d a ld i s t f i b u t i o n 属性 近年来的研究进一步促进了可用带宽测量技术的发展 出现了一些新的算 法和工具 归纳起来基本上也可以用两种模型来描述 即p g m p r o b eg a p m o d e l 模型和p r m p r o b er a t em o d e l 这两种模型都基于以下假设 被测路径上的路由器都采用f i f o 排队方式 在一次测量其间 背景流量的变化率很小 称为 平滑 另外 p g m 模型还进一步假设被测路径上的瓶颈链路就是t i g h t 链路 这些 重庆邮i 乜学院顺i 论史 假设对模型的分析和测量结果十分重要 但文献 9 的研究指出在实际测量环境 中 即使某些假设不能满足 相应的测量工具仍可能 f 常运行 2 4 1p g m 模型 p g m 模型是在包对模型基础上发展而来的 也是利用两个探测包到达接收 端的时间间隔值来估算瓶颈链路的可用带宽 根据可用带宽的定义可知 要计 算可用带宽 必须先获得瓶颈链路上的背景流量 因此如何测量背景流量成了 p g m 模型的核心问题 p g m 模型的原理如图2 3 所示 p 2p 一 c r o s st r 赢i 3 1 c k 卜 c t r a r l lc n e 一 卜 a t一7 五p 图2 3p g m 模型原理图 顾名思义 p o m 模型的目的就是要找出探测包对之间的间隔与背景流量间 的关系 从而计算出可用带宽值 设探测包对p 1 和p 2 的发送时间间隔为 z 到达接收端时的输出时间间隔是 如果探测包p 1 离开瓶颈链路和探测包 p 2 到达瓶颈链路期间队列不为空 即有背景流量插入到两个探测包之间 则 6 r o 即为传输p 2 的时间与传输在 巧期间流经瓶颈链路的背景流量的时间之 和 因此 传输背景流量的时间为a r o 一 l 背景流量为 五 6 r o a r i 重庆f l n 学院硕f 论文 圈2 4 可用带宽与流量的荚系 a i f t r 亭r c 一删 a t 2 6 2 6 式中 彳 f t f 表示在时间间隔t 内链路i 上可用的带宽的平均 值 c 表示链路i 的带宽 是一个常数 五 f 表示时刻t 时链路i 上的流量a 由 此不难看出 链路流量与可用带宽紧密相关 只要获得了链路流量即可算出相 应链路上的可用带宽 反之亦然 p g m 模型的典型应用是d e l p h i 2 h 算法和i g i i n i t i a lg a pi n c r e a s i n g p t r p a c k e tt r a n s m i s s i o nr a t e 算法吼 i g i 算法通过构造一个简单的 间隔模型 来解释在一个单跳 s i n g l e h o p 网络中背景流量是如何影响探测包对之间的间隔的 对该模型的分析表明 包 的初始间隔是影响可用带宽测量精度的关键参数 如果包p 2 到达路由器队列 时 包p 1 已经离开 则输出间隔将落入模型中的d q r d i s j o i n t q u e u i n g r e g i o n 区域 这意味着包的间隔没有改变或是减小了 此时将无法对背景流量进行计 算 反之 输出间隔将落入模型中的j q r j o i n tq u e u i n gr e g i o n 区域 且随 着背景流量的增大而线性增加 此时就能利用 2 4 式计算背景流量 因此 算法的核心就是找到合适的探测包初始间隔 使测量能够在j q r 区域中运行 由于模型假设在测量期间背景流量是一个 平滑 的数据包流 而实际上 是存在突发性的 所以必须发送一组探测包对来测量背景流量的平均值 据此 提出了i g i 公式 皖 k 一g 五 2 7 其中分母表示总的测量时间 包括探测包间隔增加 不变和减小的时间总和 分子表示测量期间总的背景流量大小 b i t s 该算法使用了三个参数 包数量 包大小和包对的初始间隔 算法的流程是 首先初始化三个参数 获得探测包在瓶颈链路上的传输时 g g m 晕庆邮1 乜学院倾 论文 延 接着不断调整探测包的初始间隔以寻找合适的值 使之与输出间隔相等 确保测量在j q r 区域进行 然后根据i g i 公式计算出背景流量及可用带宽 最 后进行误差分析 2 4 2p r m 模型 p p j v l 模型是由所谓 主动诱发拥塞 s e l f i n d u c e dc o n g e s t i o n 概念发展而 来的 该模型是基于以下简单的启发式的基本原理 如果发送探测包流的速率 r 低于被测路径上的可用带宽a 则在接收端探测包的到达速率将与发送端的 相匹配 反之 如果发送探测包流的速率r 高于可用带宽a 则在网络中的瓶 颈链路上会出现排队现象 且探测包流会被延迟 最终导致探测包在接收端的 速率低于发送端的速率 换句话说 如果探测速率小于可用带宽 则探测包的 延迟不会增加 如果探测速率大于可用带宽 则探测包的延迟会增加 因此 用该模型实现可用带宽测量的关键在于通过不断调节发送探测包流的速率来寻 找发送速率与接收速率开始匹配的转折点 p r m 模型的典型应用是p a t h l o a d 2 习和p a 廿l c h 卸 2 3 算法 p 1 r 算法在初始 化时也使用了该模型 n 1 o h op a c k e l s j 蠢j l n n 3 冰 毽冰 j 举 0 n 0 0 0 0 业皿 了i 了可 了r 再 f t 汛e 图2 5p a t h c h i r p 算法发送探测包示意图 p a t h c h i r p 算法该算法对p r m 模型中探测包的发送做了改进 通过发 送一列称为 c h i r pp r o b i n gt r a i n 的探测包 所谓的c h i r p 来进行溅量 各探 测包的间隔是按指数规律变化的 且各包的大小相同 如图2 5 所示 这样做 的优点是 若发送的探测包数为n 则得到的包间隔数为n 一1 而发送包对则 需要2 n 一2 个包 探测包间隔按指数规律变化可以使测量带宽范围为 k c 2 m b p s 的网络仅用l g c 2 l g q 个探测包 此外还能捕获关键的延迟相 关的信息 这些都使得该算法能用较小的代价快速地获得可用带宽信息 该算 法使用了四个参数 包大小p 扩散因子y 忙周期阀值l 和缩减因子f 算法的流程是 首先设置各个参数 通过发送探测包列来获得所谓 排队 延迟签名 q u e u i n gd e l a ys i g n a t u r e 点 即转折点 从而计算出对应于每个 c h i r p 的可用带宽e 的加权平均值d 如 2 8 式所示 式中 气表示包k 和包k l 之间的间隔 重庆邮电学院硕士论史 e t a t 专f 姑 在测量的过程中 需要调节好算法的四个参数 以适应不同的测试环境 获得较为准确的结果 但探测包的发送量也会相应地增加 2 5 测量模型的相关问题及其发展趋势 当前有许多算法和工具在端到端的网络路径带宽测量上取得了不少成果 其中包括 p a t h c h a r 它使用可变包长 v a r i a b l e p a c k e ts i z e v p s 算法逐跳地 估算一条路径上各链路的物理带宽 c l i n k 2 6 和p c h a r 2 7 1 是p a t h c h a r 的不同实现 版本 n e t t i m e r 使用被动测量的算法测量一条路径上瓶颈链路的容量 但该算 法要求在瓶颈链路后的所有网络单元中无排队发生 因此只能应用于非常理想 的链路上 为了消除逐跳测量造成的误差累积和背景流量的影响而产生了改进 的链路带宽测量算法 如e p a t h c h a r 2 8 和p t v s p a c k e t1 协nw i t h 耐a b l es i z e 2 9 1 还有一些工具如b p r o b e c p r o b e r c p 30 1 c a p t 3 1 1 等 可以用来测量t c p 吞 吐量 t h r o u g h p u t 文献 3 2 还提出了测量子路径带宽的算法 这些算法和工具 都为可用带宽测量模型的发展奠定了坚实的理论基础 但总的来说 它们应用 于高速网络时几乎都无法得到令人满意的结果 可用带宽测量模型建立的基本思想简单明确 当假设条件满足时 其测量 精度是很高的 但实际测量环境往往很难满足假设条件 因此如何提高测量精 度始终都是研究的核心问题 不论是链路带宽测量还是可用带宽测量 在实现 的过程中 由于存在背景流量的干扰 如突发性的背景流量 为了提高测量精 度 几乎都采用了发送探测包 对 来得到多个测量样本值 并且都不同程度 地采用了数学方法来尽可能的消除干扰 如t o p p 算法使用的线性回归法计算 带宽 l d e l p h i 算法使用了多分形 m u l t i f r a c t a l 的方法来计算背景流量 2 l p a t h c h i r o 算法则使用了加权平均的方法 此外 gh e 和j c h o u 刀 还使用了 长相关 l o n g r a n g ed e p e n d e n c y 的分形方法来测量端到端的背景流量 在理论上 其精度是相当高的 但目前可用带宽测量工具的实际测量结果并不尽如人意 表现为链路带宽越高 误差越大 第二 干扰性小 n o n i n t r u s i v e 也是可用带宽测量模型设计的一个重要目 标 因为在测量过程中必然要向网络中注入探测包 如果数据量过大 就会对 网络正常流量造成干扰 根据p r m 模型的原理 在实现测量的过程中 必须经 过多次尝试来调节探测包流的发送速率r 用类似二分检索的方法 因此在这 个过程中需要发送大量的探测包 而p g m 模型发送的探测包则少得多 如 重庆 j f 乜学院硕 论文 p a t h l o a d 在一次测量期间会产生2 5 m b 至1 0 m b 的探测流量 p a t h c h i r p 是3 0 0 k b 至l m b 而i g i 则是1 3 0 k b 左右 从这一点上看p g m 模型要优于p r m 模型 第三 需要考虑网络路径发生变化的可能 由于测量模型仅在发送端或接 收端记录测量信息 不具备记录所测路径拓扑信息的能力 而测量过程中被测 路径一旦发生变化 测量结果就没有意义 不过p a x s o n 2 4 的研究表明 在网络 中 主机之间的路由通常能在数小时至数天内保持稳定 这个结论非常重要 这意味着可以在短时间内重复进行可用带宽的测量 并能得到期望的结果 在测量可用带宽的两个基本模型中 都要测量探测包间隔 而i n t e m e t 带宽 越来越高 传输单个包的时间越来越短 使得测量主机成为 瓶颈 表现为 时钟分辨率 r e s o l u t i o n 低 时间戳不准确 探测包发送速率受p c i 总线带宽 限制 操作系统执行系统调用以及上下文切换 c o n t e x ts w i t c h 增力 发送时间 间隔等实际问题 如果不能得到切实的解决 将会造成测量精度下降 甚至使 测量失去意义 因此 开发新的专用测量协议 让路由器分担测量主机的部分 功能 并记录所经路径的拓扑信息 设计适用于高速网络的新的测量模型 编 写运行在操作系统内核态的测量软件以减小数据包拷贝和上下文切换带来的开 销 都是可用带宽测量研究发展的趋势 通过上述分析可知 由p g m 模型和p r m 模型得到的可用带宽测量算法都 是以端到端 e n d t o e n d 的方式对被测路径上的可用带宽进行实时溅基 能够 在一定的误差范围内快速地获得当前网络所处的状态及网络性能信息 锄璧是由 于端到端方式固有的限制 例如主要依赖于测量主机的性能 路由器不参与测 量等 使得测量结果的精度受到较大的影响 并且由于主要依赖于测量主机的 性能 特别是网卡的吞吐量和p c i 总线带宽的限制 会产生 潜在带宽 p o t e m i a l b a n d w i d t h 的问题 3 4 脚 往往当被测链路带宽超过1 0 0 m b s 时 测量结果的失 真会越来越大 这说明当前的可用带宽测量模型及算法已经不能适应高速网络 针对这些问题 本文将提出一种面向高速网络的测量模型 并根据此模型设计 一个可以运行于操作系统内核的测量系统 对这些问题进行不同程度的改进 2 6 本童小结 本章重点介绍了可用带宽测量的研究现状 首先给出了与可用带宽相关的 定义 然后从测量模型的角度简单介绍了可用带宽测量模型的基础 即链路带 宽测量模型 接着分析了两种有代表性的可用带宽测量模型即p g m 和p r m 及 其相关算法 最后讨论了模型中存在的问题 提出了进一步研究的趋势 晕庆邮叱学院硕 j 论立 第三章基于回归分析的可用带宽测量模型 本章将提出一种可用带宽测量方法 基于回归分析的可用带宽测量模型 以下称为回归模型 对第二章所分析的当前可用带宽测量模型中存在的问题 进行改进 如前所述 由于i p 测量协议只是作为探测包的承载协议 不影响对 模型的建立 因此对该协议的说明将在第五章中进行 以下将以排队论 3 6 埽口回 归分析法 4 8 1 为理论基础建立回归模型 并对它进行详细描述 3 1 排队论基础 在网络性能的理论分析中 应用排队论 q u e u i n gt h e o r y 的数学知识是最 基本的方法 在排队论中 用形式a b m k m 表示一个排队系统 3 刀 其中 一 间隔到达时间分布 卜服务时间分布 卜系统中服务员的数目 一队列长度分布 彳一顾客数 当芷和m 没有列出时 表示这两个参数取值为无穷大 当对分组网络的性能进行分析时 通常选择m m 1 排队模型 3 8 3 9 1 其含义 是分组到达间隔时间和服务时间服从指数分布 即m a r k o v i a n 马尔可夫链 过程 且系统是单个服务员 一般情况下 也将m a r k o v i a n 到达过程称为p o i s s o n 泊松 到达过程 即对分组到达过程有 a x 2 e 7 3 1 其中九表示分组平均到达速率 对分组服务过程有 b x p 叫 3 2 其中1 助表示分组的平均服务时间 排队模型具有如下重要性质 性质1 分组到达过程与服务过程相互独立 性质2 具有无记忆性 即已知系统现在的状态 系统将来的状态如何与系统 过去的状态无关 性质3 泊松过程的合成定理 对多个相互独立的泊松过程 其和仍然是一 霞庆 i j 巳学院顺i 论文 个泊松过程 即对 有 a 4 3 3 五 以 3 4 k 其中丸表示泊松过程4 的平均到达率 流 爹 哑寸 图3 1f i f o 队捌模型 在分组网络中 当分组到达一个节点后 在该分组结束服务之前 通常需 要在缓存中先进行排队 根据排队应用缓存策略的不同 一般可以分为输出排 队 输入排队和共享缓存三种方式 4 叫 通常 路由器中使用的最普通的排队方 式是先进先出f i f o f i r s ti nf i r s to u t 队列 也即先到先服务f c f s f i r s tc o m e f i r