（信息与通信工程专业论文）ip网络中的qos问题研究.pdf

摘要 摘要 近年来，随着互联网应用的普及以及迅猛发展，网络业务也得到了快速的 增长和多样化，兴起了多种的多媒体业务。但是现有的网络是基于i p v 4 网络协 议，这种i p 网络提供的是“尽力而为( b e s t - e 舫n ) ”的质量保障。在加上基于 “公平性”的网络结构以及网络的异质性等原因，网络无法向用户提供有效的 服务质量保障，也不能实现网络资源的有效监控和管理，服务质量( q o s ) 始终 是下一代网络发展技术的“瓶颈”。因此如何提供有效措施以及机制来保证服务 质量具有非常重要的意义。 本文基于服务质量( q o s ) 这个研究点，首先介绍了q o s 的研究背景，以 及q o s 的主要研究内容。然后从网络分层模型的角度出发，分别介绍了基于传 输层的网络拥塞控制问题，以及基于数据链路层的最新的无线城域网协议 i e e e 8 0 2 1 6 的m a c 层的o o s 问题。 第二章针对o o s 研究中具有重要地位的网络拥塞问题，详细探讨了网络拥 塞控制的概念和本质，介绍了网络拥塞控制中的常用队列管理算法，并针对其 中的b l u e 算法存在的缺点，提出了一种改进的自适应的a b l u e 拥塞控制算法。 并在n s 中实现仿真，证明该算法具有更好自适应性，能更有效的改善搠塞。 第三章针对最新的无线接入协议i e e e8 0 2 1 6 ，首先概述了i e e e s 0 2 1 6 ，介 绍了p m p 和m e s h 模式的主要特点，然后针对m e s h 模式详细研究其q o s 机制。 并在n s 仿真软件中实现了m e s h 模式f 的m a c 层的基本过程，提出了一种基于 优先权的分组调度算法，实现了m a c 层的q o s 保证。 最后对全文进行了总结，并对进一步的研究进行了展望。 关键词：服务质量，拥塞控制，i e e e8 0 2 1 6 ，调度机制 a b s t r a c t a b s t r a c t r e c e n t l y , w i t ht h er a p i dd e v e l o p m e n to f i n t e r n e ta p p l i c a t i o n ，i n t e r n e ts e r v i c e s h a v es e e nar a p i dg r o w na n db e c o m em o r ea n dm o r ed i v e r s i f i c a t i o n t h ec u r r e n t s e r v i c em o d e l ，w h i c hi sb a s e do nt h e “i p v 4 ”p r o t o c o l ，p r o v i d e st h e “b e s te f f o r t s e r v i c e s oa l o n gw i t ht h e f a i r n e s s ”n e t w o r ks t r u c t u r ea n dt h eh e t e r o g e n e i t y ，t h e n e t w o r kc o u l dn o to n l ym e e tt h e s u b s c r i b e r s r e q u i r e m e n t s ，b u t a l s oc o u l dn o t c o m p l e t et h en e t w o r kr e s o u r c es u r v e i l l a n c e a n dm a n a g e m e n t t h eq o sh a sb e e n b e i n gt h e b o t t l e n e c k o ft h en e t w o r kd e v e l o p m e n t s oh o w t op r o v i d et h ee f f i c i e n t m e a s b r ea n dm e c h a n i s mt og u a r a n t e et h eq o sh a ss i g n i f i c a n t m e a n i n g t h i sp a p e rb a s e do nt h e q o s ”，f i r s ti n t r o d u c e st h er e s e a r c h sb a c k g r o u n da n d t h em a i nr e s e a r c hc o n t e x t t h e nt h i sp a p e r , f r o mt h en e t w o r kl a y e ri d e a , i n t r o d u c e s t h en e t w o r k c o n g e s t i o n i nt h et r a n s l a t i o n l a y e r a n dt h e q o sm e c h a n i s mo f i e e e s 0 2 1 6 i nd a t a l i n kl a y e r , s u c c e s s i v e l y c h a p t e rt w oi n t r o d u c e st h en e t w o r kc o n g e s t i o nq u e s t i o n ，w h i c hi so n eo f t h eh o t p o i n to fq o sr e s e a r c h m e n t f r i s t ，i td i s c u s s e st h ep r i n c i p a la n de s s e n c eo fn e t w o r k c o n g e s t i o n c o n t r 0 1 t h e nm a k e st h ed e t a i l e dd i s c u s s i o nf o rt h ec o m m o nq u e u e a l g o r i t h m n l ep a p e r , b a s e d o nb l u e a l g o r i t h m ，w h i c h i so n eo ft h eq u e u e a l g o r i t h m s p r o v i d e d a l la d a p t i v eb l u ea l g o r i t h m ，w h i c hc a l l e da b l u e t h es i m u l a t er e s u l t ss h o w t 1 1 a tt h ea b l u ei sm o r ea d a p t i v e c o u l dh a v em o r ee f f e c t i v ec o n t r o lo v e rn e t w o r k c o n g e s t i o np h e n o m e n o n c h a p t e r t h r e ef o c u s e so nt h el a t e s tb r o a d b a n dw i r e l e s sa c c e s sp r o t o c o l ：i e e e 8 0 2 1 6 。i tf i r s ts u m m a r i z e st h ec o n c e p t so fi e e e8 0 2 1 6 ，i n t r o d u c e st h ep m pa n d m e s hm o d e l a f t e rt h a t ，b a s e do nt h em e s hs c h e d u l ea l g o r i t h m ，i tp r o v i d e saq o s m e s hs c h e d u l ea l g o r i t h mb a s e do nt h ep r i o r i t y i nt h en ss i m u l a t o rs o f t w a r e ，i t c o m p l e t e st h e m e s hs c h e d n l e a l g o r i t h m i nn s a tt h ee n do ft h e p a p e r , i th a s c o n c l u d e dt h ew h o l ep a p e r ，a n dg i v e ss o m ed i r e c t i o nf o rt h ef u _ r i t l r ew o r k k e yw o r d s ：q o s ，n e t w o r kc o n g e s t i o nc o n t r o l ，i e e e 8 0 2 16 ，s c h e d u l em e c h a n i s m i i 学位论文版权使用授权书 本人完全了解同济大学关于收集、保存、使用学位论文的规定， 同意如下各项内容：按照学校要求提交学位论文的印刷本和电子版 本；学校有权保存学位论文的印刷本和电子版，并采用影e l j 、缩印、 扫描、数字化或其它手段保存论文；学校有权提供目录检索以及提供 本学位论文全文或者部分的阅览服务；学校有权按有关规定向国家有 关部门或者机构送交论文的复印件和电子版；在不以赢利为目的的前 提下，学校可以适当复制论文的部分或今部内容用于学术活动。 学位论文作者签名： 2 0 0 5 年多月i - 7 豫莉 日 经指导教师同意，本学位论文属于保密，在年解密后适用 本授权书。 指导教师签名：学位论文作者签名： 年月日年月 同 同济大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导卜，进行 研究工作所取得的成果。除文中已经注明引用的内容外，本学位论文 的研究成果不包含任何他人创作的、已公开发表或者没有公开发表的 作品的内容。对本论文所涉及的研究工作做出贡献的其他个人和集 体，均已在文中以明确方式标明。本学位论文原创性声明的法律责任 由本人承担。 签名：偿莉 少巧年3 月i - i e t 第1 章引言 第1 章引言 1 1 i p q o s 研究的背景 随着网络体系结构的演变和宽带技术的发展，传统网络向n g n ( 下一代嘲 络) 的演进势不可挡。n g n 的目标是实现“三网融合”，即是让电信、电视以及 数据业务灵活的构建在一个统一的开放平台上，构成可以提供现有三种网络l 的语言、数据、视频和各种业务的网络解决方案，同时能灵活、多样的支持现 有业务和新业务，为用户提供个性化的多媒体业务l l l 。 以i p 协议为核心的分组交换数据网络将是n g n 演进过程中的主要网络技 术。n g n 是一种业务驱动、基于统一协议、基于分组交换的网络。但是目前分 组网络的网络协议是i p v 4 ，现有的网络提供的是“尽力而为”的质量保障，在 加上基于“公平性”的互联网的网络结构以及网络的异质性等原因，网络无法 向用户提供有效的服务质量保障，也不能实现网络资源的有效监控和管理，服 务质量( q o s ) 始终是下一代网络发展技术的“瓶颈”，这种状况严重阻碍了网 络向纵深方向发展。 因此如何在多业务网络中有效地提供各类业务所需的q o s ，同时又能保证 网络的可扩展性，一直是国内外学者和学术界关注的热点问题，这方面的研究 具有很强的理论意义和现实意义。本文是在上海市自然科学基金“本质安全型 宽带丁业以太网关键理论技术研究”( n o 0 2 4 1 1 9 0 2 6 ) 以及国际合作项嗣“车载 系统的移动撞入技术”( n o 0 8 0 0 2 3 9 0 0 1 ) 的支持下完成的。 l 。2i p q o s 研究综述 服务质量( q u a l i t yo f s e r v i c e ，q o s ) ，通常是指通信网络在承载业务时为业务 提供的品质保证。从技术角度上看，则是指为保证所提供的业务的服务质量到 达相应的标准而采取的一系列措施的技术的总称。通常用业务传送的延迟、延 迟抖动、带宽( 吞吐量) 和包丢失率等参数来进行衡量 2 】。不同的通信网络对于 服务质量的定义也各不相同，不同的业务对于每个参数的敏感程度电是不同的。 从涉及的范丽来看，服务质量q o s 是一个涉及面非常广，综合性的问题。 要实现服务质景的保障，不仅需要有一个好的体系结构设计，还需要各个网络 第l 章引吉 层面的q o s 支持。国际标准化组织( i n t e r n a t i o n a ls t a n d a r d i z a t i o no r g a n i t i o n i s o ) 是首先丹始研究q o s 问题的组织。它定义了七层的网络参考模型【3 i ，不仅定义 了低层向高层协议提供服务的机制，还要求低层按照高层要求，提供一定的服 务质量。下面我们从用广终端角度，在数据层面上来分析各层支持的q o s 机制。 最底层的物理层主要提供q o s 支持的物质基础，即提供比特率尽可能高的、 误码率尽可能低的物理信道。其q o s 的研究涉及到信道编码、调制、交织技术 等方面的研究。 数据链路层可以分为逻辑链路控制层( l o g i cl i n kc o n t r o l ，l l c ) 与媒体接入 控制层( m e s a a c c e s sc o n t r o l ，m a c ) 两个子层，由于m a c 层定义了多个用户是 如何共享信道资源，因此，在q o s 保证中具有很重要的地位。数据链路层侧重 于无线资源的管理与利用，具体的包括接入控制、呼叫接纳控制、功率控制以 及无线资源调度等内容。t i m e l y 模型将无线网络的分组调度算法分为5 个部 分，以适合不同的场合 4 - 6 j 。无线局域网i e e e 8 0 2 1 1 也在数据链路层的m a c 子 层上对q o s 进行多方面的研究f 7 。1 1 。针对协议中两种媒体访问控制方法：分布式 防调功能( d i s t r i b u t e dc o r r e s p o n e df u c t i o n ，d c f ) 与点协调功能( p o i n g c o r r e s p o n e df u n c t i o n ，p c f ) ，进行q o s 方面研究，例如基于优先级的q o s 支持、 使用公平调度提供q o s 支持等。尤其是i e e e 8 0 2 1 1 e ，针对q o s ，在以前的版 本基础上定义了更丰富的功能与参数，提出了e d c f 和h c f 机制。虽然 i e e e 8 0 2 1 l 能提供一定的q o s 保证机制，但是数据传输仍然普遍存在着碰撞现 象。为了解决传统的“最后一公里”的接入问题，在城域网范围内支持高达7 5 m b p s 的移动网络，最新的无线城域网接入网协议i e e e 8 0 2 1 6 1 2 1 备受业内外研究界关 注，目前该协议还在讨论中。因此研究i e e e 8 0 2 1 6 的q o s 机制非常具有理论和 实际意义。这也是本文研究的一个重要研究方面。 网络的第三层网络层则主要进行路由选择与分组转发，根据具体的网络进 行流量控制和调节，提出简单有效的算法和实现方案等工作。目前众多的路由 选择算法在本质上都可以归属为距离向量路由选择( b e l l m a n - f o r d ) 算法 0 3 - x s l 和链路状态路由选择算法s p f 两种。 传输层主要提供端到端的数据传输服务，保证连接的迅速建立。传输层中 存在着面向连接的、提供可靠服务的t c p 和不面向连接的、不可靠服务的u d p 两类协议。i e t f ( 国际互联网标准制定组织) 在传输层提出了综合服务资源预 留协议( i n t s e r v r s v p ) 模型【1 6 1 、与区分服务技术( d i f l s e r v ) 模型1 1 7 - 2 0 。这两 2 第l 章引言 个模型受到大家广泛的认可。由于这两个模型最初是基于有线网络提出的，为 了适合无线网络的环境，人们针对这两个模型提出了许多改进，例如提出了主 动和被动资源预留的m r s v p 2 1 1 方式、支持隧道的r s v p t 2 2 1 等方式，以支持无线 网络中提前预留资源。对d i 舔e r v 进行了信令协议、移动性等方面的功能扩展与 支持。 这两个模型是从传输层的整体结构出发，以提供具有q o s 的体系。从传输 层主要处理的功能出发，当网络发生拥塞时，传输层能够采取有效措施缓解拥 塞，恢复正常的网络状态。同时也要保证不同类型的业务、数据流能够比较公 平的占用网络资源。在传输层中重要的q o s 机制就是网络拥塞机制1 2 3 - 2 6 j 。拥塞 控制算法主要分成“基于链路的算法”和“基于源的算法”两大类。目前使用 最为，泛的基于源的算法是基于窗口的t c p 拥塞控制机制，j a c o b s o n 提出的“慢 启动”( s l o ws t a r t ) 1 2 7 2 8 】和“拥塞避免”( c o n g e s t i o n a v o i d a n c e ) 算法以及1 9 9 0 年t c pr e n o 版本【2 9 】增加的“快速重传”( f a s tr e t r a n s m i t ) 、和“快速恢复”( f a s t r e c o v e r y ) 这四个算法，就是t c p 的拥塞控制的四个过程。基于链路的算法从 最初的“被动式队列管理”发展到目前集中研究的“主动队列管理”算法1 3 0 _ 3 1 1 。 主动式队列管理算法主要有随机早期检测算法( r a n d o m v _ m l yd e t e c t i o n ，r e d ) 3 2 1 及其改进的系列算法s r e d ( s t a b l er e d ) 、f r e d ( f a i rr e d ) 、a r e d ( a d a p t i v e r e d ) 3 3 - 3 5 等。r e d 算法在实际应用中被广泛引用，但是基于队列的长度进行判 定的r e d 系列算法占用内存资源比较大。由w u c h a n gf e n g 等人提出的b l u e p 6 j 算法则是基于当前链路利用率和丢包率来进行控制的拥塞算法。较之r e d 算法， b l u e 能够使用相对较小的缓冲区完成拥塞控制，从而减少端到端的延迟，而且 丢包概率比较稳定。但是仍存在链路利用率比较低，受参数影响挺大的缺点。 本文针对这个缺点，对b l u e 算法进行了改进，在本文中探索自适应的a b l u e 算 法。 对于传输层以上的高层而言，主要对数据进行翻译、加密、提供各种应用。 其q o s 桃制涉及到对数据采用不同的编码方法，交织。采用r t p c r t p 来传输 实时数据等措施。但是对于网络的q o s 研究，主要还是集中在下而的各层中， 因此本文重点放在传输层和数据链路层部分进行研究。 3 第1 章引言 1 3 本文的结构安排 本文主要从网络层次的角度出发来研究i p 网络的q o s 问题：分别从传输层 和数据链路层两个层次进行研究。 在传输层层面上，本文第二章针对在q o s 研究中具有重要地位的网络捕塞 问题，研究网络拥塞控制机制。首先详细探讨了网络拥塞控制的概念和本质， 然后介绍了拥塞控制的两大类算法：“基于链路的算法，【3 i 和“基于源的算法” 1 3 2 - 3 3 ，并重点介绍了基于链路的队列管理算法。本章介绍了网络拥塞控制中的 常用队列管理算法，并针对其中的b l u e 算法存在的缺点，提出了一种改进的白 适应的a b l u e 拥塞控制算法。并在n s 中实现仿真，证明该算法具有更好自适应 性，能更有效的改善拥塞。 在数据链路层层面上，本文第三章针对最新的i e e e8 0 2 1 6 协议| “，对 8 0 2 1 6 m a c 层的q o s 问题进行研究。对于共享媒质的网络来说，由于m a c 层的 协议定义了用户之间是如何共享这些共享媒质与接口的，因此它对于用户的性 能、系统的能力和远端终端的负载性具有非常重要的影响。这使得网络的媒体 介入控制m a c 子层在保证网络的q o s 中具有非常关键的作用。本文首先概述 了最新的无线城域网接入标准1 e e e 8 0 2 1 6 ，介绍了p m p 模式和m e s h 模式的主 要特定。然后针对m e s h 模式研究起q o s 机制，在n s 仿真软件中实现了m e s h 模式下的m a c 层的基本过程，并提出了一种基于优先权的分组调度算法，实现 了m a c 层的q o s 保证。 本文第四章对全文进行了总结，并对进一步的研究进行展望。 4 第2 章网络的拥寒控制 第2 章网络的拥塞控制 2 1 网络拥塞的原因 现有的网络使用b e s t e f f o r t 服务机制，所有分组受到同等对待，网络尽力发 送每个进入网络的分组，但是并不保证业务的服务质量( 例如吞吐量、端到端 延迟、丢失率等) 。由于网络并没有提供接入控制( a d m i s s i o nc o n t r 0 1 ) ，因此用 户获得的服务质量不仪取决于网络自身，也取决于其他用户在网络中产生的负 载，这使得整个网络完全缺少隔离和保护。 拥塞现象是一种持续的网络超负荷状态。当用户需求大于网络所能提供的 资源的刚候，也就是当网络中存在过多的数据包的时候，网络的性能就会下降， 这就是拥塞现象。如果网络中存在拥塞现象时，则整个网络的吞吐量会下降， 严重的时候会笈生“网络崩溃”现象叫】。图2 1 给出了网络负载与吞吐量及响 应时问的关系： 吞 吐 量 响 应 时 l 司 ( b ) 图2 l 网络负载与吞吐量及响麻时间的关系 从图2 ，1 可以看出，如果网络的负载比较小的时候，网络的吞吐量基本上 尾呈线性关系的，随着网络负载的增加而增加，而在这种情况下，网络的响应 时间是缓慢的增长的。图中定义了 个叫做k n e e 的点，当网络的负载达到刚络 容量的时候，也就是达到这点的时候，网络的吞吐量开始缓慢增长，而这时 候响应时间则是以较大的增长速度增长。进一步，当网络的负载继续增长到一 定的稃度后，随着网络负载的增加刚络的吞吐量反而下降，通常把这个过渡点 定义为c l i f f 。 第2 章网络的拥塞控制 拥塞现象发生的主要原因在于网络能够提供的资源不足以满足用户的需 求，这些资源包括缓存空间、链路带宽容量和中问节点的处理能力。由于t 呋 网的设计机制导致其缺乏“按纳控制”能力，因此在网络资源不足时小能限制 用户数量，而只能靠降低服务质量来继续为用户服务，也就是“尽力而为”的 服务。为了解决拥塞的问题，由于拥塞问题的动态特征，不能依靠单纯增加网 络资源这种静态方式的解决方案。同时从研究拥塞现象可以看出拥塞总是倾向 于发生在网络中资源相对比较短缺的位置，这种不平衡性反映出了网络的不均 衡性，具体的说就是资源分布的不均衡性和流量分布的不均衡性。从这一点也 可以看出不能试图用单纯的用增加资源的方法来解决网络的拥塞问题。 拥塞控制机制从总体上来说，实际上分为搠塞避免( c o n g e s t i o n a v o i d a n c e ) 和拥塞控制( c o n g e s t i o nc o n t r 0 1 ) 两种策略。拥塞避免的目的就是使网络运行在 k n e e 附近，避免拥塞现象的发生；而拥塞控制则是在拥塞发生后，使得网络运 行在c l i f f 的左侧区域的手段。因此拥塞避免是一种“预防”的措施，试图维持 网络的高吞吐量、低延迟状念，以避免网络进入拥塞状态；而后者是一种“恢 复”措施，当网络发生拥塞的时候，想办法使网络从拥塞中恢复过来，进入正 常的运行状态。 2 2 基于窗口的t c p 拥塞控制机制 根据拥塞算法实现的位置，可以将拥塞控制算法分成“基于链路的算法” 和“基于源的算法”两大类。基于链路的算法指的是在各个网络设备( 比如路 由器和交换机) 中执行的拥塞算法，其目的就是检测网络拥塞的发生，产生反 馈信息以反映网络的拥塞状况。而基于源的算法则是在主机和网络边缘设备当 中执行的，其作用是根据各个网络设备提供的反馈信息来调整数据包的发送速 率。 目前使用最为广泛的基于源的算法是基于窗口的t c p 拥塞控制机制。而基 于链路的算法研究目前集中在“主动队列管理”算法方面。本文的重点是讨论 主要的队列管理算法，这一部分将会在下面的章节中进行详细讨论，本节只简 单地介绍基于窗口的t c p 拥塞控制机制。 早期的t c p 协议只有基于窗口的流控制( f l o wc o n t r 0 1 ) 机制而没有拥塞控 制机制，因而易导致网络拥塞。1 9 8 8 年j a c o b s o n 针对t c p 在网络拥塞控制方面 6 第2 章网络的拥塞控制 的不足闭，提出了“慢启动( s l o w s t a r t ) 和“拥塞避免”( c o n g e s t i o n a v o i d a n c e ) 算法。1 9 9 0 年出现的t c pr e n o 版本增加t t 2 9 】“快速重传”( f a s tr e t r a n s m i t ) 、 “快速恢复”( f a s tr e c o v e r y ) 算法，避免了网络拥塞不严重时采用“陧启动” 算法而造成过度减小发送窗口尺寸的现象，这4 个算法就是t c p 的拥塞控制的 四个过程。图2 2 示意了这四个过程。 时间 塞窗l ：= ：】 ( a ) 慢启动和拥塞避免( b ) 快速重传和快速恢复 图2 2 t c p 拥塞控制的四个过程 1 慢启动阶段 早期的t c p 应用在启动一个连接的时候会向网络发送大量的数据包，这样 很容易导致路由器缓存空间耗尽，从而发生网络发生拥塞，使得t c p 连接的吞 吐量急剧下降。但是t c p 源端是无法知道网络资源当前的利用状况，因此在新 建立一个t c p 连接的时候，不能一开始就发送大量数据，而只能逐步增加每次 发送的数据量，咀避免上述现象的发生。这就是“慢启动”的概念。具体地说， 当建立新的t c p 连接时，拥塞窗口( c o n g e s t i o nw i n d o w ，c w n d ) 初始化为。个 数据包大小。源端按c w n d 大小发送数据，每收到一个a c k 确认，c w n d 就增加 一个数据包发送量，这样c w n d 就将随着回路响应时间( r o u n dt r i pt i m e ，r t t ) 呈指数增长，源端向网络发送的数据量将急剧增加。由于在发生拥塞时，拥塞 窗口会减半或降到l ，因此慢启动确保了源端的发送速率最多是链路带宽的两 倍。 2 拥塞避免阶段 如果t c p 的源端发现超时现象出现或者接收到3 个相同a c k 副本时，即可 认为网络发生了拥塞，此时就进入拥塞避免阶段。慢启动的阈值( s s t h r e s h ) 被 设置为当前拥塞窗口大小的一半；如果发生超时现象，则拥塞窗口被胃l 。如果 拥塞窗口c w n d s s t h r e s h ，t c p 就执行拥塞避免算法，此时，c w n d 在每次收到一 7 丑罗| | 橱一 剐 时攘 韶丁，乙 一 。一 一 一 川珂， 一 一。房一 一茸 一 卜眵 = 一 第2 章网络的拥塞控制 个a c k 时只增加1 c w n d 个数据包，这样，在一个r t t 内，c w n d 将增加1 ，所 以在拥塞避免阶段，c w n d 不是呈指数增长，而是线性增长。 3 快速重传和快速恢复阶段 快速重传是指当t c p 源端收到到三个相同的a c k 副本时，即认为有数据包 丢失，则源端重传丢失的数据包，而不必等待r t o 超时。同时将s s t h r e s h 设置 为当前c w n d 值的一半，并且将c w n d 减为原先的一半。 快速恢复则是基于“管道”模型( p i p em o d e l ) 的“数据包守恒”的原则 ( c o n s e r v a t i o n o f p a c k e t s p r i n c i p l e ) ，即同一时刻在网络中传输的数据包数量是恒 定的，只有当“旧的”数据包离开网络后，才能发送“新的”数据包进入网络。 如果发送方收到一个重复的a c k ，则认为已经有一个数据包离开了嘲络，于是 将拥塞窗口加l 。 以上就是基于源的基于窗口的t c p 拥塞控制机制的简单介绍，接下来的部 分将会对基于链路的队列管理算法进行详细探讨。 2 3 拥塞控制中的队列调度机制 由于基于包交换的路由器的每个端口采用带宽统计复用，为了处理多个数 据包同时向同一端口转发以及端口q o s 等问题，路由器必须在端u 上维护一个 或多个队列。路由器有两类控制队列的算法：队列管理算法和队列调度算法。 其中队列管理算法主要是在必要时通过丢弃数据包来管理队列的长度。而队列 调度算法则主要是用来管理各个流之间的带宽的分配问题，决定n f 一个需要发 送的数据包。 当前的队列管理算法可以分为两大类 3 0 3 1 1 ：被动式队列管理( p a s s i v eq u e u e m a n a g e m e n t ，p q m ) 和主动式队列管理( a c t i v eq u e u em a n a g e m e n t ，a q m ) 。 2 3 1 被动式队列管理p q m 传统的被动式队列管理p q m ，包括去尾d r o p t a i l 算法，随机丢弃r a n d o md r o p 算法和从前丢弃d r o pf r o n t 算法等。它们主要的思想是对每个队列设置一个最大 阙值，当接受数据包的长度没有到达该阈值时，可以继续接受数据包。但是当 队列的长度达到该阈值，即是队列满的时候，就拒绝继续接受数据包，而对其 丢弃。直到队列的长度下降到阈值之下，则可以继续接受数据包。 这些被动式的队列管理算法，存在着几个重大的缺陷，将产生“死锁 8 第2 章网络的拥塞控制 ( 1 0 c k - o u t ) 现象”、“满队列( f u l lq u e u e s ) 现象”以及“全局同步( g l o b a l s y n c h r o n i z a t i o n ) 现象”。 死锁现象；在某些情况下，某个流或者少数几个流会独占整个队列空间， 阻j i = 其他流的数据包进入队列，引起这种“死锁”现象通常是由于同步 或其他定时作用的结果。 满队列现象：由于端到端的延迟主要就是由于在队列中排队等待造成 的，所以队列管理的最重要的目标之一就是降低稳定状态下队列的长 度。但是由于这些算法只有在队列满的时候才会发出拥塞信号，因此会 使得队列在相当长时问内处于充满( 或几乎充满) 的状态。 全局同步现象：由于网络上数据的突发特性，使得到达路由器的包也往 往是突发的。如果出现满队列现象，就会导致在短时间内连续大量地丢 包。由于t c p 流的自适应特性，在这种情况下，源端就会急剧的减少 发送窗口，降低数据包的到达速率，以解除网络的拥塞现象。当网络状 态恢复正常，消除了拥塞状态后，源端开始又增加数据的发送速度，最 终又造成网络拥塞。这种现象常常会周而复始地进行下去，从而在一段 时间内网络处于链路利用率很低的用状态，降低了整体吞吐量，这就是 所谓的”t c p 全局同步”现象。 前述的去尾d r o p t a i l 算法这几个缺陷都具有，而随机丢弃r a n d o md r o p 算法 和从前丢弃d r o p f r o n t 算法可以通过随机丢包或者队列头部丢包的方式，解决“死 锁现象”，但是仍然没有解决“满队列现象”。 因此，要解决被动式队列管理算法的缺陷，需要在网络在满队列现象出现 之问，就丌始丢弃数据包，在拥塞现象发生之前就采取措施。这就是“主动式 队列管理a q m ”的思想。 2 3 2 主动式队列管理a q m 主动式队列管理a q m 是基于f i f o 调度策略的一组队列管理机制。采_ 【 a q m 的路由器能够控制任何时候的数据丢包人小，支持端到端的拥塞控制。 a q m 具有以下几方面的优势：由于a q m 保持了较小的平均队列k 度，提 供更大的容量来吸收突发数据包，从而极大的减少了路由器中丢弃的包的数量。 同时a q m 通过保持较小的平均队列长度，减少了数据包的排队延迟。对于交互 9 第2 章网络的拥塞控制 式应用比如w e b 浏览、t e l n e t 业务和视频会议等，较低的排队延迟是非常重要 的。最后，a q m 能够通过确保到来的包几乎总足有町用的队列空间，来阻止“死 锁”现象以及防止路由器对低带宽高突发的流的偏见。 2 4 常用的主动式拥塞管理队列算法 目前a q m 中常见的拥塞控制管理算法有随机早期检测算法r e d ( r a n d o m e a r l yd e t e c t i o n ) 、显示拥塞指示e c n 、b l u e 算法以及基于算法的改进算法。下 面将会针对主要的算法进行讲解。 2 4 1 随机早期检测算法r e d 及其改进系列 2 4 1 1 随机早期检测算法r e d 算法 r e d l 3 2 】拥塞控制机制的基本思想是通过监控路由器输出端口队列的平均长 度来探测拥塞情况，一旦发觉拥塞快要出现的迹象，就采取措施，随机的选择 连接来通知拥塞，使得在由于队列溢出导致丢包之前减小拥塞窗口，降低发送 数据速度，从而缓解网络拥塞。 r e d 主要试图达到以下目标：最小化包丢失率和排队延迟、避免全局同步 现象、避免对突发业务的偏见( 在采用“去尾”算法的路由器中，如果某个流 的突发性越高，则当该流的包进入队列时越容易造成队列溢出，从而导致连续 地丢弃大量的该流的包) 、以及即使在缺乏传输层协议有效配合的情况下也能控 制平均队列长度等。 为了达成以上目标，r e d 采用了基于时间的平均队列长度，并且随机地选 择j 下进入路由器地包进行丢弃。这种方法能被有效地实旌而无需在路由器中维 持每个流( p e r - f l o w ) 的状态信息。由于r e d 是基于f i f o 队列调度策略的，并 且只是丢弃正进入路由器的数据包，因此其实施起来也较为简单。 r e d 算法主要分为两个过程。首先是计算平均队列长度，并以此长度作为 对拥塞程度的估计。接下来就是计算丢弃包的概率。 1 1 计算平均队列长度 r e d 算法在计算平均队列长度a v g _ q 的时候，采用类似于地通滤波器的带 权值的方法，以避免由于i n t e m e t 数据的突发性质或者由于短暂搠塞导致的实际 1 0 第2 章网络的拥塞控制 队列长度造成暂时的增长现象，使得平均队列的队列长度有明显的变化现象。 a v g _ q 。口一叫x m , g _ q + q x w ( 2 1 ) 其中，w 为权值，q 为采样测量时实际队列长度。权值w 相当于低通滤波器 的时间常数，它决定了路由器对输入流量变化的反应程度。因此w 的选择非常 重要，如果w 选择过大，r e d 就不能够有效地过滤掉短暂的拥塞：另一方面， 如果w 选择太小，那么a v gq 就会对实际队列长度的变化反应过慢，不能合理 地反映搠塞状况，在这种情况下，路由器就不能有效检测到早期的拥塞。因此w 的值应根据不同情况预先设置，一般来说，它是由路由器允许发生的突发业务 的大小和持续的时间所决定的。 2 ) 丢包率的计算 r e d 通过上面的步骤计算出了平均队列长度以反映拥塞状况，然后根据拥 塞的程度来计算丢弃包的概率，从而有效地控制平均队列长度。 在r e d 里有两个和队列长度相关的闽值：m i n t h 和m a x t h 。当数据包到达到 路由器的时候，r e d 首先计算出该数据包的平均队列长度a v g _ q 。若a v g _ q 小于 m i n t h ，则不丢弃任何数据包；当m i n m a v g _ q m a x t h 时，则根据一定的公式 计算出丢包概率p ，并以此概率丢弃包；当a v g _ q m a x t h 时，所有的数据包都被 丢弃( 如图2 3 所示) 。 丢包率 平均队列长度 图2 3 丢包率与平均队列k 度关系 当m i n t h a v g _ q m a x t h 时，计算概率p 的公式如下： p b = m a x px ( a v g _ q m i n t h ) 砌a x t h m i n t h ) p = p b ( t - c o u n t x p b ) ( 2 2 ) 由计算公式可以看出，数据包的丢失概率p ，不仅仅ja v g _ q 有关，而日还 和从上一次丢包开始到现在进入队列的包的数量c o u n t 有关。随着c o u n t 的增加， 下一个包被丢弃的可能性也在缓慢增加。这种措施主要是为了在到柬的包之间 1 1 第2 章网络的拥塞控制 均匀间隔地丢包，避免连续丢包，从而避免对突发流的偏见和产生全局同步现 象。 与传统的队列管理算法相比，r e d 算法有效地控制了平均队k ，限制了平 均时延的大小。消除了对突发流的偏见，在拥塞发生的时候，该算法标记某个 流的数据包的概率基本上与该流在路由器中得的带宽成比例。并且由于该算法 均匀地间隔丢包，避免了由于连续丢包导致地全局同步现象。因此r e d 能够与 传输协议合作，有效的控制网络中的拥塞现象。 但是r e d 仍然存在着参数设置、公平性、不能有效的估计拥塞严重性等问 题，因此人们又基于r e d ，提出了一些改进的算法，如s r e d ( s t a b l er e d ) 、f r e d ( f a i rr e d ) 、a r e d ( a d a p t i v er e d ) 等算法。 2 4 1 2s r e d 算法 采用r e d 算法控制拥塞时，平均队列的长度往往会随着数据流量的显著变 化而大幅度的振荡，引起很大的时延变化。s r e d | 3 3 】算法就是为了获得稳定时延 而对r e d 进行的改进，同时该算法在鉴别行为恶意的流方面也有一定功效。 s r e d 的基本思想是：由于平均队列长度的大幅度振荡主要是由于源端发送 速率的不停变化而引起的。因此如果能够根据当前网络的状态来控制源端的发 送速率，则有利于时延稳定性。同时当一个数据包到达时，随机的从缓冲区中 选出一个包进行比较，如果这两个包属于同一个数据流的时候，则标记该数据 包为“击中”状态，则该数据包可能属于“恶意数据流”。为了让缓冲区有记忆 功能，能比较已经离去的数据包，该算法定义了一个列表来记录最近缓冲区中 流过的数据流以及其他的信息。 因此s r e d 能够保持队列的稳定，从而减少了延迟抖动，并能够鉴别恶意 流，并对其进行惩罚。 2 4 1 3f r e d 算法 众所周知，影响t c p 流对带宽的享用的因素包括不同的r t t 、拥塞窗口的 大小、包的大小、目标速度以及t c p u d p 的相互作用。由于网络上的数据流是 异质的，而r e d 标记包的概率是和该流使用的带宽成比例的，这就会带来不公 平的带宽使用。例如两个t c p 流竞争带宽，一个使用小窗口，另一个使用大窗 口，发生拥塞时，r e d 就会使得小窗口的源端陷入多重超时。另外，由于u d p 1 2 第2 章网络的拥塞控制 之类的流没有拥塞控制机制，其在和t c p f r i e n d l y 流竞争时会获得更多的带宽， 有可能使后者陷入“饥饿”状态。 f r e d l 3 4 1 是r e d 的改进版本，它通过对每个活跃流( p e r - a c t i v e f l o w ) 进行 记帐( a c c o u n t i n g ) 的方式，对使用不同带宽的流作出不同的标记，从而提高了 不同的流享用带宽的公平性。在数据传输中，主要存在着三种类型的流，即： 非适应流、强壮( r o b u s t ) 流、和脆弱( f r a g i l e ) 流。强壮流指的是能够对拥塞 通知作出反应并且充分利用现有的网络条件发送数据。脆弱流则是能够对拥塞 通知作出反应，但它们对丢包过于敏感，或者是对有更多可用带宽的适应很慢。 非适应流就是指的那种不会对任何拥塞控制通知做出相应的数据流。 与随机地选择一个流标记其包的r e d 不同，f r e d 是从缓冲区巾有较多包 在排队的那些流巾选择一个，向其发出拥塞通知。 f r e d 对非适应流进行了有效的鉴别和限制，保护了脆弱的流，在平均传输 时间上也更为公平，从而增强了r e d 算法的公平性问题。 2 4 1 4 脓印算法 由于r e d 工作性能的优劣很大程度上是由其预先设噩的参数wq 、r n i nt h 和m a xt h 决定的。这些参数微小的变化就会给总体性能带来很大的影响。如果 权重wq 设置得比较小，则平均队长的变化就很小。当网络负荷很重时，平均 队长总是在m a xt h 附近缓慢地振动，从而会导致长时间的连续标记包 ( a v g ) 或者长时连续随机地标记包 ，从而产生全局_qmax_th(avg_fl f r e e z e _ t i m e ) p m = p m d 2 ；，碱少丢包概率 l a s t u p d a t e 2 n o w ； 当出现数据包丢弃的时候： i f ( ( n o w l a s tu p d a t e ) f r e e z e _ t i m e ) p m = p m + d i ； 增加丢包概率 l a s t u p d a t e 2 n o w ； 在b l u e 算法中的进队列算法中，首先对当前进入的数据包进行判断，其判 断函数采用了d