（计算机应用技术专业论文）多瓶颈网络拥塞控制若干问题研究.pdf

桂林理工大学硕士学位论文 摘要 近年来 随着i n t e m e t 的飞速发展 网络传输速率不断提高 网络应用和服务变得更 加多样化 除了传统的w e b f t p t e l n e t 等数据流外 还出现了大量新型的网络应 用 如实时多媒体 视频等数据流 由于网络中大量不同的数据流在路由器处交汇 越 来越严重的包丢失和其他的性能恶化问题逐渐暴露出来 其中一个比较严重的现象就是 网络拥塞 主动队列管理是网络拥塞控制中一个比较有效的方法 也是网络拥塞控制中 的研究热点 就目前而言 对主动队列管理算法的研究还不是很完善 其中很重要的一方面体现 在网络拓扑的研究上 现有的对主动队列管理算法的研究绝大多数采用单瓶颈链路拓扑 而对于多瓶颈链路拓扑却少有涉及 相对于单瓶颈链路拓扑而言 多瓶颈链路拓扑是一 种更接近于实际的网络模型 通过在多瓶颈链路条件下对各种主动队列管理算法进行研 究 更能揭露算法在实际网络中可能遇到的问题 因而对多瓶颈链路网络进行深入研究 对于推动主动队列管理算法与实际网络的融合具有重要意义 本文主要包括以下内容 l 基于控制论观点讨论了单瓶颈网络的拥塞机制 从路由器中t c p 流的动力学性质 出发 建立了t c p 流模型的随机微分方程 同时推导出描述a q m 策略和路由器排队过程 的非线性微分方程 并在平衡点附近对微分方程组进行线性化处理 2 建立具有a i m d 参数对 口 的多瓶颈网络流体模型 并基于l y a p u n o v 稳定性 理论 给出多瓶颈网络系统模型渐近稳定的充分条件 分别从无丢包时延和具有反馈时 延两个方面对多瓶颈网络系统的稳定性进行了分析 并以一个具有三瓶颈链路拓朴结构 为例 利用m a t l a b 和n s 分别对其进行了仿真 仿真结果验证了多瓶颈网络系统的渐近 稳定性 3 利用网络处理器的可编程性和可扩展性等特点 设计了一种将缓冲管理和分组调 度相结合的队列管理综合算法 目标是使系统的吞吐量和分组丢失率的综合性能达到最 优 最后对全文进行了概况性总结 并指出了有待进一步研究的问题 关键词 拥塞控制 主动队列管理 多瓶颈 稳定性 网络处理器 桂林理工大学硕士学位论文 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 ft h ei n t e m e tr e c e n t l y t h et r a n s m i s s i o nr a t eo fn e t w o r k si s c o n s t a n t l yi n c r e a s i n g t h ea p p l i c a t i o na n ds e r v i c eo fn e t w o r k sb e c a m em o r ev a r i e t y b e s i d e s t h et r a d i t i o n a ld a t af l o w al a r g en u m b e ro fn e wa p p l i c a t i o na p p e a r s u c ha sr e a lt i m e m u l t i m e d i a v i d e oc o n f e r e n c ee t c d u et ot h ed i f f e r e n td a t af l o wi n t e r s e c t i o na tt h er o u t e r s t h e p a c k e tl o s sr a t ea n do t h e rp e r f o r m a n c ed e t e r i o r a t i o nb e c o m es e r i o u s o n eo ft h ei s s u e si s n e t w o r kc o n g e s t i o n a c t i v eq u e u em a n a g e m e n t a q m i so n ee f f e c t i v em e t h o da n di ti sa l s o ar e s e a r c hf o c u si nc o n g e s t i o nc o n t r o lm e c h a n i s m s a tp r e s e n t t h er e s e a r c hi na q mi sn o tp e r f e c t s i n c em o s ta q m a l g o r i t h m sa r eb a s e do n t h es i n g l eb o t t l e n e c kt o p o l o g i cs t r u c t u r ea n dal i t t l ea b o u tm u l t i p l eb o t t l e n e c kn e t w o r k s c o m p a r e dw i t hs i n g l eb o t t l e n e c k t h em u l t i p l eb o t t l e n e c k sa r em o r ec l o s et ot h ep r a c t i c a l n e t w o r k s or e s e a r c h i n gi nt h ea q mw i t hm u l t i p l eb o t t l e n e c k si sm o r ee f f e c t i v ea n d i m p o r t a n t t h em a i nc o n t e n t sa r el i s tb e l o w 1 w ed i s c u s st h ec o n g e s t i o nm e c h a n i s mo ft h es i n g l eb o t t l e n e c kn e t w o r kf r o mt h ec o n t r o l t h e o r y a c c o r d i n gt ot h ed y n a m i c a lp r o p e r t i e so ft c p f l o w si nr o u t e r s e s t a b l i s ht h es t o c h a s t i c d i f f e r e n t i a le q u a t i o n so ft c p a q ms y s t e m a n dd e r i v et h en o n l i n e a rd i f f e r e n t i a le q u a t i o n s w h i c hd e s c r i b et h ea q m s t r a t e g ya n dc o n g e s t i o nr o u t e r sq u e u i n gp r o c e s s e s f i n a l l yl i n e a r i s m t h en o n l i n e a rd i f f e r e n t i a le q u a t i o n sa to p e r a t i n gp o i n t 2 w ee s t a b l i s ht h ef l o wm o d e lo fm u l t i p l eb o t t l e n e c ks y s t e mw i t ha i m dp a r a m e t e r s q 1 3 a n dt h e na n a l y s i st h es t a b i l i t yo fb o t hd e l a y f r e ea n dd e l a y e ds y s t e m s s u f f i c i e n t c o n d i t i o n sf o rt h ea s y m p t o t i cs t a b i l i t yo fm u l t i p l eb o t t l e n e c ks y s t e ma r ed e r i v e db ya p p e a l i n g t ol y a p u n o vs t a b i l i t yt h e o r yw i t hl y a p u n o v r a z u m i k h i nc o n d i t i o n s n u m e r i c a lr e s u l t sw i t h m a t l a ba n ds i m u l a t i o nw i t hn s 一2a r eg i v e nt ov a l i d a t et h ea n a l y t i c a lr e s u l t s 3 o nt h ef u l lu s eo fn e t w o r kp r o c e s s o rw h i c hh a sh i g hp e r f o r m a n c ea n df l e x i b i l i t y w e d e s i g naq u e u em a n a g e m e n ts y n t h e s i sa l g o r i t h mc o m b i n e dw i t hb u f f e rm a n a g e m e n ta n dp a c k e t s c h e d u l i n g t h i sa l g o r i t h m sg o a li s t o g e tt h eb e s tc o m p r e h e n s i v ep e r f o r m a n c eb e t w e e n t h r o u g h p u ta n dl o s sr a t e f i n a l l y w em a k et h ec o n c l u s i o n sa n ds o m ef u t u r er e s e a r c h e sa r ep r o p o s e d k e yw o r d s c o n g e s t i o nc o n t r o l a c t i v eq u e u em a n a g e m e n t m u l t i p l eb o t t l e n e c k s t a b i l i t y n e t w o r kp r o c e s s o r 研究生学位论文独创性声明和版权使用授权书 独创性声明 本人声明 所呈交的论文是本人在导师指导下进行的研究工作及取得的研究成果 据我所知 除了文中特别加以标注和致谢的地方外 论文中不包含他人已经发表或撰写 过的研究成果 也不包含为获得其它教育机构的学位或证书而使用过的材料 对论文的 完成提供过帮助的有关人员已在论文中作了明确的说明并表示谢意 学位论文作者 签字 随 解醐 芈 学位论文版权使用授权书 本学位论文作者完全了解 学校 有关保留 使用学位论文的规定 有权保留并向国 家有关部门或机构送交论文的印刷本和电子版本 允许论文被查阅和借阅 本人授权 学 校 可以将学位论文的全部或部分内容编入有关数据库进行检索 可以采用影印 缩印或 扫描等复制手段保存 汇编学位论文 同时授权中国科学技术信息研究所将本学位论文 收录到 中国学位论文全文数据库 并通过网络向社会公众提供信息服务 保密的 学位论文在解密后适用本 学位论文作者 签字 签字日期 桂林理工大学硕士学位论文 第1 章绪论 1 1 网络拥塞和拥塞发生的原因 在最近的二十年内i n t e r n e t 取得了突飞猛进的发展 与此同时 用户需求的增长速度 也丝毫不逊色于i n t e r n e t 的发展速度 随着i n t e m e t 的广泛应用 网络己经成为我们日常 生活最为重要的信息交换手段之一 我们也已经越来越依赖于阚络带给我稍的各种信息 通过网络进行数据和信息传输已经成为现代商业社会重要且不可缺少的组成部分和赖以 生存的基础 然恧随着i n t e m e t 本身规模的迅速扩大以及i n t e m e t 用户数量的测增 i n t e m e t 的数据流量也急剧增长 除了传统的w e b f t p t e l n e t 等数据流外 还出现了大量 新型的网络应用 如实时多媒体 视频等数据流 由于网络中不同的数据流在路由器处 交汇 因而给网络的路由节点造成极大的转发负担 很多分组无法在同一时刻被转发出 去 越来越严重的包丢失和其他的性能恶化问题逐渐暴露出来 其中一个比较严重的现 象就是网络誊蔷塞 c o n g e s t i o nc o n t r 0 1 早在1 9 8 6 年1 0 月 计算机网络就遭遇了历史上的第一次拥塞崩溃 v a nj a c o b s o n 在l b l 和u cb e r k e l e y 之闯的链路上观察到了拥塞崩溃的现象 其闯网络链路的吞畦量 从3 2 k b p s 骤然下降到4 0 b p s 下降了将近1 0 0 0 倍 并且网络和协议都处于忙碌状态 通 过截驭网络分组 发现由于网络负载突然增大 造成数据在网络中继或端节点的缓存溢 出 丢失的分组导致数据重新发送 迸一步恶化网络拥塞 从而形成 丢失 重发 的 恶性循环 近年发生拥塞现象的情况还有 2 0 0 1 年2 月和2 0 0 6 年1 2 月由于我国通往美国的海 底光缆发生阻断 我国只能临时利用卫星线路进行网络通讯 由于访问量大而卫星线路 熬带宽远小予原来的海底光缆 造成访翔 艺美国家的速度下降明显 有时甚至无法访闻 因此 网络拥塞导致的直接后果是整个网络的性能下降 包括分组丢失率增加 端 到端延迟增大 网络吞吐量下降 甚至有可能使整个系统发生搠塞崩溃 c o n g e s t i o n c o l l a p s e 当网络处于拥塞崩溃状态时 微小的负载增量都将使网络的有效吞吐量急剧 下降 网络产生拥塞的根本原因在于用户提供给潮络的负载大于网络的资源容量和处理能 力 拥塞产生的直接原因有以下几点 2 1 存储空闻不足 几个输入数据流共同需要同一个输出端翻 在这个端西就会建 立排队 如果没有足够的存储空间存储 数据包就会丢弃 当大量的突发数据流发生时 更是如此 增加存储空间在某种程度上可以缓解这一矛盾 但如果路由器拥有无限存储 桂林理工大学硕士学位论文 量时 拥塞只会变得更坏 而不是更好 因为在网络里数据包经过长时间排队完成转发 时 它们早己超时 源端则认为它们己经被丢弃 而这些数据包还会继续向下一个路由 器转发 从而浪费网络资源 加重网络拥塞 2 带宽容量不足 低速链路对高速数据流的输入也会产生拥塞 根据香农信息理 论 任何信道带宽最大值即信道容量c b x l o g 1 s n n 为信道噪声的平均功率 s 为信源的平均功率 b 为信道带宽 所有信源发送的速率r 必须小于或等于信道容量c 如果r c 则在理论上无差错传输就是不可能的 所以在网络低速链路处就会形成带宽 瓶颈 当其满足不了通过它的所有源端带宽要求时 网络就会发生拥塞 3 处理器处理能力弱 速度慢也能引起拥塞 如果路由器的c p u 在执行排队缓 存 更新路由表等功能时 处理速度跟不上高速链路 也会产生拥塞 同样 低速链路 对高速c p u 也会产生拥塞 4 另外 t c p i p 协议拥塞控制机制中的缺陷 用户的恶意攻击造成的网络拥塞 以及网络系统的混沌 分叉等现象都会导致网络通信系统的崩溃 1 2 网络拥塞控制及其研究意义 从上面我们可以看出 拥塞现象的发生是对网络的需求大于供给 有限的资源由多 个用户使用 没有相应的机制对用户的数量产生控制 不断增长的需求数量 必然会导 致拥塞的发生 拥塞控制本质上是一个如何共享资源的问题 在包交换网络中 所有的 激活终端共享网络资源 这些资源包括节点处理能力 缓存空间和通信链路带宽 在这 三者中的任意一个都可能成为潜在的瓶颈 从而导致网络拥塞 3 在面对网络产生拥塞时发现 上述原因不能单独考虑 因为提高链路速率而不改变 处理器 只会转移网络瓶颈 而不能避免拥塞 增加缓存空间到一定程度时 只会加重 拥塞 而不是减轻拥塞 另外 增加链路带宽及提高处理器能力也不能从根本上解决拥 塞问题 所以上述几点原因需综合考虑 单纯地增加网络资源不能解决拥塞问题 拥塞 本身是一个动态的全局问题 它不可能只靠静态的方案来解决 而需要协议能够在网络 出现拥塞时保护网络的正常运行 在图1 1 中的横坐标是网络负载 o f f e r e dl o a d 代表单位时间内输入给网络的 分组数目 因此网络负载也称为输入负载 纵坐标是吞吐量 t h r o u g h p u t 代表单位 时间内从网络输出的分组数目 具有理想拥塞控制的网络 在吞吐量饱和之前 网络吞 吐量应等于网络负载 故吞吐量曲线是4 5 的斜线 但当网络负载超过某一限度时 由 于网络资源受限 吞吐量不再增长而保持为水平线 即吞吐量达到饱和 这就表明网络 负载中有一部分损失掉了 例如 输入到网络的某些分组被某个结点丢弃了 虽然如 此 在这种理想的拥塞控制作用下 网络的吞吐量仍然维持在其所能达到的最大值 2 桂林理工大学硕士学位论文 吞吐量 轻度拥塞 拥塞输入负载 图1 1 网络拥塞控制作用的曲线图 但是 实际网络的情况就很不相同了 从图1 1 可看出 随着网络负载的增大 网 络吞吐量的增长速率逐渐减小 也就是说 在网络吞吐量还未达到饱和时 就已经有一 部分的输入分组被丢弃了 当网络的吞吐量明显地小于理想的吞吐量时 网络就进入了 轻度拥塞的状态 更值得注意的是 当网络负载达到某一数值时 网络的吞吐量反而随 着网络负载的增大而下降 这时网络就进入了拥塞状态 当网络负载继续增大到某一数 值时 网络的吞吐量就下降到零 网络已无法工作 这就是所谓的死锁 d e a d l o c k 因此 在目前的i n t e m e t 中 既然网络拥塞是无法避免的 就必须采取积极主动的策 略控制和避免拥塞 把拥塞发生的可能性降到最低 即使在发生拥塞后也能及时地恢复 到正常运行状态同时拥塞控制也必须保证网络效率 因此 网络拥塞控制是网络系统改 善性能 提高服务质量的主要手段 网络拥塞控制问题的研究具有重要的理论意义和应 用价值 1 3 拥塞控制研究现状 近年来 国内外关于网络拥塞控制研究方面的成果很多 4 4 3 1 从已经发表的相关文献 来看 研究主要集中在t c p 拥塞控制算法的改进 主动队列管理算法 网络拥塞控制系 统非线性行为和稳定性分析等几个方面 1 3 1t c p 拥塞控制的研究现状 基于窗口的端到端t c p 拥塞控制对i n t e m e t 的稳定性起到了关键作用 t c p 拥塞控 制的基础是加性增加 倍性减 j a i m d a d d i t i v ei n c r e a s em u l t i p l i c a t i v ed e c r e a s e 策略 主 要包括慢启动 拥塞避免 快速重传和快速恢复这四个相关联的算法过程 1 慢启动 s l o ws t a r t 慢启动的原理是 使要发送到网络的新数据包的发送速率等于从接收方返回的确认 3 桂林理工大学硕士学位论文 消息的速率 该算法通常用于连接的开始阶段和超时弓 起的重传丢失包阶段 随往返时间 r t t r o u n d t r i pt i m e 按指数增长拥塞窗口c w n d 慢启动的作用是探测当前网络可提供的容量 避免豳于发送大量突发数据导致网络拥塞 2 拥塞避免 c o n g e s t i o na v o i d a n c e 当c w n d 大于慢启动阀值s s t h r e s h 时 即执行拥塞避免算法 在此阶段 每个r t t 时闻蠹 若发送方接收到对当翦c w n d 对应数据的应答后 c w n d 就比原来增加一个最大 t c p 数据包所对应的字节数 即c w n d 大小以线性方式增长 拥塞避免的馋用是通过减缓c w n d 值的增加速率从焉雄迟网络搁塞的发生 这样可以 使发送端能在较长一段时间内保持较高的数据传输率 3 快速重传 f a s tr e t r a n s m i 0 通常假定 如果发送方连续收到几个 通常为三个 重复a c k a c k n o w l e d g e m e n t 确认 时 即认为有一个数据包丢失 此时 发送方不必等到重传定时器超时就开始重 新传送丢失的数据包 同时t c p 将s s t h r e s h 值设为当前c w n d 僮豹一半 t c p 发送方就 是利用快速重传算法检测和恢复数据包丢失的 4 快速恢复 f a s tr e c o v e r y 在快速重传可能丢失数据包之后 t c p 就执行拥塞避免算法 而不是慢扁动算法 这 就是快速恢复算法 此后 快速恢复算法将控制新数据的传送 直到收到一个非重复的 a c k 为止 快速恢复算法可使在较大窗口下发生中度拥塞时 网络仍具有较高的吞吐量 此算法也可减少快速重发造成的c w n d 急剧振荡 t c p 拥塞控制中比较有代表性的方法有 t c p 嘞o e t c pr e n o l 翻 t c pn e w r e n o f 翻 t c p v e g a s 7 和t c ps a c k f 引 这些控制算法一般都包含以上四个过程 在算法的改进方面主要有知下态容 馒启动方面的改进f 9 l m a s c o l o 等提高的t c p w e s t w o o d t c p w l o p a g a n i n i 等提出的h i g h s p e e dt c p h s t c p 1 l c j i n a n d 等提出的 f a s tt c p d 2 a 3 1 麻省理工大学和柏克利等提出的e x c p e x p l i c i tc o n t r o lp r o t o c 0 1 1 4 1 考虑 t c p 发送窗豳不是以线性增长而是以分段速率递进尝试以寻找最优速率 这是文献中提 到的比较新的值得研究的思想 近年来 国内学者在t c p 拥塞控制算法方面的工作包括 电子科技大学的隆克平教 授 1 5 等提出两种无线t c p 改进机制 即基于重传率调整t c p 段大小的机制和基于吞吐 量估计设置往返时间 0 限检测网络拥塞的机制 北京邮电大学觞纪红教授羹弼等提出一种 适用于无线i n t e m e t 的改进无线t c p 拥塞控制算法 并采用p a d h y e 模型的建模方法 推 导了无线t c p 协议的t c pl d 的稳态流量模型 中国科学院的冯彦君孵1 等提出一种端到 端 肩发式t c p 的改进机制 中国科学院的张国清 l8 等提出一种适用于异构网络的t c p 协议设计等 4 桂林理工大学硕士学位论文 1 3 2 主动队列管理的研究现状 随着应用需求的日益丰富和技术的不断发展 研究者开始认识到如果完全依赖t c p 拥塞控制很难满足诸如服务质量 q o s q u a l i t yo fs e r v i c e 等这样复杂的应用需求 于 是 人们开始将注意力部分转移到对主动队列管理 a q m a c t i v eq u e u em a n a g e m e n t 的研究上来 a q m 机制是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 e 1 9 推荐的基于路由器 拥塞控制的关键技术 对降低丢包率 提高链路利用率 降低队列时延 抑制速率振荡 等方面起到了重要的作用 是解决目前i n t e m e t 拥塞问题的一个主要途径 在i e t f 提出采用r e d 2 0 之前 基于f i f o f i r s ti nf i r s to u t 的丢尾机制是网络中的 唯一队列管理机制 尽管丢尾机制简单并且易于实现 但是它有三个众所周知的缺陷 死锁 满队列 全局同步问题 为了能够克服丢尾机制的这些缺陷 引入随机早期包丢 弃机制以避免满队列现象 r e d 通过在网络中间节点处监视平均队列长度来进行拥塞控 制 其出发点是为了与t c p 拥塞控制进行有效配合 r e d 的意图是在拥塞发生早期 通 过计算平均队列长度检测最初的拥塞 然后用丢弃 或标记 到达的分组的方法向源端 通报拥塞 这意味着路由器以后不必丢弃更多的分组 这样对面向连接的t c p 流来说 r e d 就有可能避免丢弃属于同一连接的连续分组 从而提高连接的吞吐量 r e d 还利用 队列长度的指数加权平均滑动 e w m a e x p o n e n t i a l l yw e i g h t e dm o v i n ga v e r a g e 值度量 拥塞的程度 不仅可以检测即将产生的拥塞 同时还可以消除突发流造成的影响 继r e d 之后 又出现了很多r e d 的变化版本 如 f l o y d 2 l 等提出的a r e d a d a p t i v e r e d 该算法把r e d 算法的控制参数动态化 提高了r e d 算法的鲁棒性 使之更好地 适应网络流量的变化 获得更加稳定的性能 然而另一方面 a r e d 算法增加了算法的 复杂度 除r e d 外 其它比较有代表性的a q m 算法包括 f e n g 等于1 9 9 9 年提出的b l u e 算法 2 2 此算法的主要思想是利用丢包事件和链路 空闲时间动态调整标记 丢弃概率 b l u e 算法的最大贡献在于使用较小的缓存区即可实 现拥塞控制 但一旦发生丢包事件后b l u e 会相对大地增加丢包概率 从而产生连续丢 包 导致t c p 陷入超时 严重时降低链路利用率 另外 b l u e 也存在参数设置问题 h o l l o t 等于2 0 0 1 年提出的p i p r o p o r t i o n a li n t e g r a l 算法 2 3 1 此算法应用控制理论非线性模 型在链路中设置比例积分控制器以增加系统的稳定性与适应能力 w y d r o w s k i 等于2 0 0 2 年提出的g r e e n 算法 2 4 此算法是一个反馈控制机制 根据测量的数据到达速率调整 拥塞通知的速率 国内对a q m 的研究较国外晚一些 但近年来 很多研究人员投入这一新的研究热 点领域 设计了很多新的a q m 机制 西安交通大学的张德运教授 李增智教授分别提出自适应阀值r e d t a t r e d 算 法 2 5 桂林理工大学硕士学位论文 和基于优先级的p r e d 算法 2 6 浙江大学的张顺亮提出根据平均队列长度的变化速率调 整丢弃概率 2 7 上海交通大学的邵惠鹤教授等应用s m i t h 原理结合r e d 提出 p r e d p r e d i c t i v er e d 机制 2 8 1 k a i y u nq i n 等利用控制系统技术设计一个基于可变结构 的控制a q m 机制 2 9 1 孙鹏等提出基于延时反馈的a q m 机制 3 们 1 3 3 拥塞控制稳定性研究现状 近年来 i n t e r n e t 稳定性也获得了很大的关注 尤其是基于窗口的流控制和基于速 率控制的t c p 系统的稳定性受到了更多的研究 很多研究人员利用控制理论分析现有 a q m 机制及拥塞控制的稳定性与动态性能 并设计新的拥塞控制算法 取得了良好的开 端 d i r c e u 等利用控制理论分析s m i t h 预估器的暂态和稳态性能 3 1 1 s r i s a n k a r 等提出设 置a v q 参数的简单规则 3 2 o r h a n 等分析r e m 算法的收敛性质 3 3 m a t t h e w 等分析 t c p a q m 拥塞控制的全局渐近稳定问题 3 4 c v h o l l o t 和l w a n g 等对无丢包时延的单 瓶颈链路的a i m d r e d 系统的稳定性进行了分析 3 5 3 6 c v h o l l o t 等利用单结点的分析 方法 基于一个r e d 网关t c p 连接的线性模型 对系统的边界稳定以及r e d 参数设定进 行了研究 3 7 3 8 在国内 f y r e n 等从非线性控制理论描述了更深层次的t c p r e d 系统中产生冲突 的原因 3 9 l w a n g 等考虑了新的控制机制 可以快速收敛到有效 稳定状态 并且可 以公平的共享带宽以及可以获得较低的丢失率 4 0 东南大学的杨洪勇教授等利用广义 n y q u i s t 判据研究了具有通信时延的a q m 策略的稳定性 4 上海交通大学的蒋凯 汪小 帆教授等基于非线性动态比较分析r e d 和a d a p t i v er e d 的性能 4 2 1 清华大学的任丰原 教授等构造一个新的分析框架 结合现有结果和非线性控制理论中的一些描述函数方法 提出判断t c p r e d 系统是否稳定的标准等 4 3 1 1 4 本文工作 虽然到目前为止 主动队列管理算法的研究取得了不少的成就 然而主动队列管理 算法仍未得到广泛的实际应用 由于算法的分布性 网络的复杂性和对算法的性能要求 使得主动队列管理算法的设计具有很高的难度 另外 目前对主动队列管理算法的研究 还不是很完善 其中很重要的一方面体现在网络拓扑的研究上 现有的对主动队列管理 算法的研究绝大多数采用单瓶颈链路拓扑 而对于多瓶颈链路拓扑却少有涉及 在单瓶 颈链路条件下研究各种主动队列管理算法的理论性能是可行的 然而现实的网络却是更 为复杂的 瓶颈链路之间的相互影响 源端及交叉流量端对瓶颈资源的争夺 交叉流量 对网络的影响等等 这些因素是单瓶颈链路所无法模拟的 而这些却正是影响实际网络 6 桂林理工大学硕士学位论文 性能的重要因素 相对于单瓶颈链路拓扑而言 多瓶颈链路拓扑是一种更接近于实际的 网络模型 通过在多瓶颈链路条件下对各种主动队列管理算法进行研究 更能揭露算法 在实际网络中可能遇到的问题 因而对多瓶颈链路网络进行深入研究对于推动主动队列 管理算法与实际网络的融合也具有重要意义 第一章 作为论文绪论 介绍阐述了本课题的研究背景和意义 网络拥塞控制的相 关概念 以及国内外的研究现状和热点 最后提出本文总体结构 第二章 从网络中支持主动队列管理路由器中t c p 流的动力学性质出发 基于控制 论观点讨论了单瓶颈网络的拥塞机制 将网络中的数据流看做是流体 建立t c p 流模型 的随机微分方程 同时推导出描述a q m 策略和路由器排队过程的非线性微分方程 在 平衡点附近对微分方程组进行线性化处理 得到其线性化微分方程 便于下面章节的分 析研究工作 第三章 根据第二章中讨论的单瓶颈网络流体模型建立了一类具有a i m d 参数对 位 的多瓶颈链路a i m d r e d 系统模型 然后基于l y a p u n o v 稳定性理论 给出具有复 杂多变时滞的多瓶颈网络系统模型渐近稳定的充分条件 并针对无反馈延时和具有反馈 延时两种情况 对多瓶颈网络系统的稳定性进行了分析和研究 最后对一类具有三瓶颈 链路的网络系统进行仿真 m a t l a b 和n s 一2 的仿真结果都验证了多瓶颈网络系统是渐近稳 定的 这些结果对我们以后在多瓶颈网络参数设置时具有很好的指示作用 从而可以保 证网络系统资源的有效利用率 并且减少系统额外的延时抖动 第四章 利用网络处理器的可编程性和可扩展性等特点 设计了一种将缓冲管理和 分组调度相结合的队列管理综合算法 目标是使系统的吞吐量和分组丢失率的综合性能 达到最优 性能仿真结果表明 所设计的综合算法的p o w e r 值总是优于r e d 算法的 第五章 对整个论文的总结和展望 指出我们工作中有待提高和改进的方面 并指 明了下一步的研究方向 7 桂林理工大学硕士学位论文 第2 章单瓶颈网络拥塞模型 网络是一个非常庞大并且复杂的对象 可利用控制理论对拥塞控制机制建模 本章 主要讨论单瓶颈网络拥塞模型 2 1 拥塞机制的控制理分析 从控制论的观点来看 网络的拥塞控制一般有开环控制和闭环控制两种 当流量特 征可以准确规定并且性能要求可以事先获得时 适于使用开环控制 当流量特征不能准 确描述或者当系统不提供资源预留时 适于使用闭环控制 所谓 开环 控制 主要是针对流量控制 即完全不考虑单个用户的流量调节行为 对其它用户造成的影响 发送者以一定参数描述自己即将产生流量的统计特性 然后向 网络提出业务请求 如果许可 网络将预留资源 发送者只需严格遵守自己的业务请求 当然网络也可以进行适当流量检测 从而保证网络不会发生拥塞在具体实现中 开环流 量控制表现为连接接纳控制和流量检测 属于主动拥塞控制机制 它更适合应用在例如 a t m 模型的面向连接的网络体系结构中 由于i n t e m e t 是一个网络业务不断变化的复杂系统 因此一般采用闭环控制 所谓 闭 环 控制就是依据控制论的观点发送方接收反馈信息 并从反馈信息中推断网络状况 确定控制参数并依据一定的控制算法调整发送速率完成对网络拥塞的响应 闭环控制的 基本模式是网络负责探测网络拥塞 拥塞信号如果被接收端系统感知 便会通知源端系 统 从而终端系统会响应拥塞并做出反应 调节进入网络的负载 闭环的拥塞控制可以 动态地适应网络的变化 但它的一个缺陷是算法性能受到反馈延迟的严重影响 当拥塞 发生点和控制点之间的延迟很大时 算法性能会严重下降 由于时延的影响 使得准确 而及时地了解网络拥塞状态进而采取确定的控制措施变得困难 和传统的 队尾丢弃 相比 a q m 在网络设备的缓冲溢出之前就丢弃或标记报文 作为端对端拥塞控制的一种变革和网络拥塞控制机制的有效补充 网络中间节点 路由器 的功能得到加强 在保证较高链路吞吐量的基础上 中间节点上的a q m 策略有效地控 制a q m 根据队列长度变化 在缓存溢出之前对到达的数据包以概率p 进行丢弃 这个 概率经过一些时延后被源端检测到 源端由此判断网络状态 速率控制算法调整发送速 率 从而路由器缓存的队列长度得到控制 从这个角度看 a q m 是网络拥塞系统的控制器 输出p 为系统的控制信号 而源端 的速率控制是系统的执行器 它和路由器的队列长度以及链路延迟一起 成为系统的广 8 桂林理工大学硕士学位论文 义对象p 网络拥塞闭环控制系统如图2 1 所示 l 一一一一一一一 一 一 沪 臣面卜刊丽州络蜮孰列卜 i l 一一一一一一一一一 二 一一一一一一一一 一i 图2 1网络拥塞控制闭环控制模型 2 2 单瓶颈网络拥塞模型 实际的网络是分散的 但是通常把网络抽象成在某时刻t 有n 个数据流通过某一条 路径 路径上有一个瓶颈链路 以瓶颈链路为中心的扩展到整个网络 如下图所示为具 有单瓶颈链路的网络模型 海端速率掩捌缓敞鲻 图2 2 具有单瓶颈链路的网络模型 2 2 1 基于单瓶颈路由器的流体动力学模型 考虑图2 2 所示的单瓶颈链路网络模型 即单拥塞路由器系统 4 5 1 假设该拥塞系统 中的瓶颈链路的传输带宽为c 该路由器的主动队列管理策略由丢包速率尸 x 来表示 路由器中的队列长度以g f 表示 要求t o 丢包速率p 工 采取在r e d 中取的形式 如下 f o o x 面n p x m i n 嚣1 t mt 广广吣鹕一 怵叭 a x l 丢包速率p x 示意图为 9 桂林理工大学硕士学位论文 2 2 1 1 单拥塞路由器的情况 在图2 2 所示的单拥塞路由器网络模型中 令通过单拥塞路由器的t c p 流记为 陀只 i l n 彬 f 及r f 分别表示在t 0 时 t c p i 的窗口大小及往返时延尺刀 r 形 取如下的形式 r q q t c t o 待1 oo n 公式 2 2 其中口 为固定的传播时延 而g 屉表示为路由器中的排队延迟 模型的基本假设为 t c p 流的丢包情况服从p o i s s o n 分布 并由过程 f f 来描述 n i f 按时间的变化率记为乃 f 根据t c p 的a i m d 特性 窗口彬的行为可以由以下 方程描述 删 丽d t 一华哪 公式 2 3 其中第一项代表加乘 a i 部分 第二项代表倍减 部分 在这种模型下 令b f 表示几z 在t 0 时刻的瞬时吞吐量 则瞬时吞吐量b i t 可写 成 黔焉 对方程两边分别取期望值 可得到 删删姐 志 芈 又可简化为 叫赤 2 其中彳 t 为源端收到的丢弃 标识 率 它到达源端的时间大约为丢包后再过一个往返 延迟 取延迟时间f 为下列方程的解 1 0 桂林理工大学硕士学位论文 l t r q t f k t f 在a q m 所使用的按比例丢弃模式中 数据包的分配与流所共享的带宽是成正比例 关系的 因而 如果流的吞吐量在 一f 时是曰o f 则t 时刻源端收到数据包的丢弃率 允 f 为p 何o o b t f 我们记为 兄 f p i f f 彬0 一f r 虿 f f 从而得到期望窗口为 删 兰而d t j w 贼叫 瑞南西 一班 彬彬 一f r 万 2 r 万o f p 2 t r d t 在研厂o 研x 的近似情况下 可得 生d t 志一黑篙 r 贼叫 公加 4 二 一一 一n i r i 一f l l 7 t li 4j r 万 2 r 虿o 一 一 假设平均队列长度的估值是基于角万采样 并且是指数权重移动时的均值 权重系 数为口 0 口 0 因此 可以近似得到研乞 则有 掣一c 姜 南 公式 2 衍 鲁 r 酌 方程组 2 4 2 7 2 9 共有n 2 个耦合的方程及 2 个未知变量 i 虿 矿 该方程组提供了系统的暂态行为时的估计平均值 因此 我们可以直接得到队列长度 队列估计值及窗口大小 而由这些值可以得到r t t 及平均丢包率 2 2 1 2 扩展到整个网络 对于整个网络的情况 设v 为路由器集合 对于每一个路由器v v 都有传输带宽 e 及相应的a q m 丢弃函数p a x v 毛是路由器v 的平均队列长度的估计值 路由器v 的 队列长度为q v r 而2 t 及虿 f 为路由器的平均队列长度及当前队列长度的向量 相应 于每个路由器有不同的采样周期点 及平均权重瓯 考虑 个t c p 流为网络的负载 即 孔z f 1 n 第f 个陀只流的链路集为 1 z 1 z 2 五 n f 其中n 为路径长度 即r c p 流所经过路由器个数 将单路由器的情况推广 则尺z 的 平均尺刀为 r g t o t i q f g v e p 网络中的路由器及t c p 流 可以用矩阵彳来表示 它的不同行代表不同的t c p 流 而不同的列则代表不同的路由器 例如 若4 1 则表示第 个路由器是流r c p 所经 过的路由器 或者表示j 矿 如果p x 表示在每个节点上的丢弃概率 则每个t c p 流的总的丢弃概率为 1 一ii 1 一a p x i 从而 2 4 式可以修改为 1 2 桂林理工大学硕士学位论文 警 而1 而一 器器 一旷删f 一一i 二o 一i i i 一 i i 一月厂 工i i i 衍 足 万 一f 2 r 虿 一f 7 j 1 j i 而1 一 器 a i 一f 一一i 二 二 一i 刀i y f f r 万 f f 2 r 虿 一f 7 1 其中p i 是流陀只在其路径上的丢包概率 另外其队列长度的方程如下 型d t 一 薹南r 狮 7 嚣 万 2 2 1 3 考虑超时的模型 公式 2 1 0 公式 2 1 1 接下来 我们把网络可能会出现的超时情况进行讨论 考虑超时的时候 可以将丢 包分为两种类型 一类是超时 t o t i m e o u t 还有一类是三次重复确认 t d t r i p l e d u p l i c a t ea c k 令q w 表示为t o 的丢包概率 若丢包时的窗1 5 1 大小为 则 q 形 m i n 1 3 此时方程 2 4 可修改为 警 志卅二咖c 一丽w w t 爿 r 雨卜砌 2 蚴 1 一彬 揣q 形 瓦 i f f 2 2 1 4 不同种类流的处理情况 当有完全相同的流出现时 即所有的流具有相同的路由及尺丌时 我们可以用上面 方程来表示平均窗1 5 1 和平均队列长度的行为 但是如果在网络中有f 种不同的t c p 流 时 而第 种流包含以 个完全相同的流 其所经过的路由器为巧 相对应的r 刀为r i q 此时可以用方程 2 9 来表示平均窗1 3 的行为 但是此时平均队列长度的可以修改为 掣一 萎吩南 公加 2 2 2 网络模型在稳定点的线性化处理 由上节 可得到具有单瓶颈路由器的t c p 拥塞控制机制系统非线性微分方程如下 桂林理工大学硕士学位论文 形i 了导 一忑w t w t r t po ro 川2 尺 t r 一 公式 2 1 4 拉等卅c 其中 形为预期的t c p 拥塞窗口值 q 为路由器中预期的队列长度 r 为往返时间 r q c t p c 为链路的可用带宽 乃为传播时延 n 为t c p 连接的数目 p 为数据 包的丢弃 标记 概率 式 2 1 4 所表示的具有单瓶颈路由器的t c p 拥塞控制机制系统非线性微分方程的 窗口变化的结构框图如图 2 4 所示 图2 4t c p 拥暴控制面t 变化结构框图 接下来对式 2 1 4 所表示的非线性方程进行线性化处理 3 7 3 8 1 假定t c p 流的数目n 和往返时间r 为定值 那么我们首先将上述方程的右 边定义为 f w 卯 兰去一1 w o r w 一r g g n 孚w f 一c 在此处 f 圭w t r 记 w 和q 为系统的状态 p 为时延反馈输入 系统的平衡点为 w o q p 使 w 0 q 0 从而 w 0j 眩岛 2 三 o j 百r o c r 圭石q o 乙 对上述方程f w q p g w q 在平衡点 w o q o p o 取偏导 得到 1 4 桂林理工大学硕士学位论文 笪 舞 一瓦wo爵20w 一去 一茄c 一 一 一一一 一一 一一 a 2 r 眩r 劭 却 2 爿击c r 一 w 2 p 2 吾 乃 一去 象一去 斋 o c2 鹾c碍c2 硝c 瑶c 2 塑 一堕 一正n z 一一r o c 2 印2 r o2 r 2 2 堙 为 2 引象 一萄一去 c 乃j 抛一n o w r 从而得到线性化方程 咖 一扣 一一等喇 脚 万衲 芸洲沪万1 洲 在此处 6 w 圭w w o s q 圭q q o s p 圭p p