（计算机应用技术专业论文）基于源端拥塞规律的主动队列管理算法研究.pdf

江苏大学硕士学位论文 摘要 随着互联网规模的扩大及网络应用的递增，网络状况不断恶化， 拥塞现象频频产生。为了缓解网络拥塞，需要实施一定的拥塞控制算 法。当前的拥塞控制算法根据实现的t c p i p 层次可以分为两类：一 类是传输层的源算法，一类是网络层的链路算法。事实上，实际的网 络状况会受到源算法与链路算法的共同作用，本文将两者相结合，旨 在获得更高的拥塞控制能力。本文首先概述了网络拥塞控制算法，然 后将a q m 算法分为a q m 传感器算法与a q m 控制器算法两个层面，着重 对a q m 的传感器算法进行研究。之后提出一种基于源端拥塞控制规律 的a q m 算法。最后通过m a t l a b 与n s 2 的仿真表明：提出的算法具有 更高的性能与鲁棒性。 本文的主要工作包括： 1 利用自动控制系统中的传感器与控制器的概念对队列管理策 略进行建模，将a q m 算法划分为a q m 传感器算法与a q m 控制器算法两 个层次。 2 对三种常用的流量速率估计法一_ e w m a 算法、结合变化趋势 的e w m a 算法和p l m a 算法进行分析，指出其缺陷并进行改进，提高了 流量速率估计法对聚集流的估计精度。 3 对源端拥塞控制规律进行归纳，并以此设计了一种基于t c p 源端拥塞控制规律的a q m 算法，给出了传感器的选择与控制器算法内 容，并给出了伪代码。 4 对基于源端拥塞控制规律的a q m 算法进行了仿真和分析。通 过与此前五个a q m 算法进行比较后得出，提出的算法具有更高的性能 与鲁棒性。 关键词：拥塞控制，源算法，链路算法，主动队列管理，速率估计 江苏大学硕士学位论文 a b s t r a c t w i t ht h ee x p a n s i o no ft h ei n t e r n e ts i z ea n dt h ei n c r e a s eo ft h en u m b e ro fn e t w o r k a p p l i c a t i o n ，t h en e t w o r kc o n d i t i o ni sd e t e r i o r a t i n g i no r d e rt om i t i g a t en e t w o r k c o n g e s t i o n , ac e r t a i na m o u n to fc o n g e s t i o nc o n t r o la l g o r i t h m s a r en e e d e dt ob e e n f o r c e d a c c o r d i n gt ot h et c p i pl a y e r so ft h ei m p l e m e n t a t i o no ft h e s ea l g o r i t h m s ， t h e yc a nb ed i v i d e di n t ot w oc a t e g o r i e s ：o n ei st h es o u r c ea l g o r i t h mc a t e g o r yi nt h e t r a n s p o r tl a y e r ；t h eo t h e ri st h el i n ka l g o r i t h mc a t e g o r yi nt h en e t w o r kl a y e r i nf a c t ， t h ea c t u a lc o n d i t i o n so ft h en e t w o r kw i l lb es u b j e c tt ob o t ht h es o u r c ea l g o r i t h ma n d t h el i n ka l g o r i t h m b o t ht h ea l g o r i t h m sa r eu s e di n t h i sp a p e r t h i sa r t i c l ef i r s t p r o v i d e sa no v e r v i e wo fn e t w o r kc o n g e s t i o nc o n t r o la l g o r i t h m s t h e nd i v i d e st h e a q ma l g o r i t h m si n t ot w os t e p st h a ta q m s e n s o ra l g o r i t h m sa n da q mc o n t r o l l e r a l g o r i t h m ，a n ds e l e c t i v e l ys t u d y st h ea q ms e n s o ra l g o r i t h m s l a t e r , a na q m a g l o r t h mb a s e do ns o u r c ec o n g e s t i o nc o n t r o ll a wi sp r o p o s e d f i n a l l yb ym a t l a ba n d n s 2t o o l st h i sp r o p o s e da l g o r i t h mp r o v e st oh a v eb e t t e rp e r f o r m a n c ea n dr o b u s t n e s s t h i sa r t i c l em a i n l yi n v o l v e st h a t 1 t a k ea d v a n t a g eo ft h ec o n c e p to fa u t o m a t i cc o n t r o ls y s t e ms e n s o ra n d c o n t r o l l e ro nm o d e l i n gt h eq u e u em a n a g e m e n ts t r a t e g yt od i v i d et h ea q m a l g o r i t h m s i n t ot w ol e v e l st h a ta q ms e n s o ra l g o r i t h ma n da q mc o n t r o l l e ra l g o r i t h m 2 a n a l y z et h r e ek i n d so ff l o wr a t ee s t i m a t i o na l g o r i t h mc o n t a i n i n ge w m a ， e w m ac o n s i d e r i n gt h ed i r e c t i o no fr a t e c h a n g e sa n dp l m aa n dp r o p o s et h e i r w e a k n e s s e s ，a n dt h e ni m p r o v et h e mt oah i g e ra c c u r a c y 3 c o n c l u d et h el a wo fs o u r c ec o n g e s t i o nc o n t r o lb e h a v i o r , a n dd e s i g n e da q m a l g o r i t h m sb a s e do nt h es o u r c ec o n g e s t i o nc o n t r o ll a w t h ec h o i c eo fi t ss e n s o r , t h e c o n t e n to ft h ec o n t r o l l e ra l g o r i t h ma n di t sp s e u d o c o d ea r eg i v e n 4 s i m u l a t ea n da n a l y z et h ea q ma l g o r i t h mb a s e do nt h es o u r c ec o n g e s t i o n c o n t r o ll a w b yc o m p a r ew i t l lt h ep r e v i o u s5a q m a l g o r i t h m s ，t h ep r o p o s e da l g o r i t h m p r o v e st oh a v eh i g h e rp e r f o r m a n c ea n dr o b u s t n e s s k e yw o r d s c o n g e s t i o nc o n t r o l ，s o u r c ea l g o r i t h m ，l i n ka l g o r i t h m ，a c t i v e q u e u em a n a g e m e n t ，f l o wr a t ee s t i m a t i o n 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定， 同意学校保留并向国家有关部门或机构送交论文的复印件和电子版， 允许论文被查阅和借阅。本人授权江苏大学可以将本学位论文的全部 内容或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫 描等复制手段保存和汇编本学位论文。 保密口，在年解密后适用本授权书。 本学位论文属于 不保密口。 学位论文作者签名：导师签名： 签字日期：年月 e l签字e l 期：年月e 1 独创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进 行研究工作所取得的成果。除文中已经注明引用的内容以外，本论文 不包含任何其他个人或集体己经发表或撰写过的作品成果。对本文的 研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本人 完全意识到本声明的法律结果由本人承担。 学位论文作者签名： 日期：年月日 江苏大学硕士学位论文 1 1 研究背景 第一章绪论 互联网起源于2 0 世纪6 0 年代。1 9 6 9 年，美国国防部的高级研究计划局 ( a d v a n c e dr e s e a r c hp r o j e c ta g e n c y , 心) 资助研究了一个著名的网 络a r 弹n e t ( a d v a l l c e dr e s e a r c hp r o j e c ta g e n c yn e t w o r k ) 。它通过租用电话线 实现了位于美国不同地区的四所大学之间的资源共享、互换信息、文件传输等服 务。2 0 世纪7 0 年代木，美国国家科学基金会( n a t i o n a ls c i e n c ef o u n d a t i o n ，n s f ) 认识到a r p a n e t 对大学研究工作的重要意义，于1 9 8 6 年采用t c p i p 协议建立 起n s f n e t 网。它通过5 6 k b s 的通信线路将美国6 个超级计算机中心相连接，实 现了广域网与计算机中心之间以及各个计算机中心之间的互连。n s f n e t 最终取 代a r p a n e t ，并于1 9 8 9 年正式改名为i n t e m e t 。此后各国相继加入i n t e m e t 的热 潮中，逐步形成了覆盖世界的i n t e m e t 网络，承担了异地用户的远程登陆、实时 通信、文件传输、电子商务、视频会议等诸多业务。 在互联网实施异地数据传输时，往往需要路由器等网络设备进行数据中转。 对于实时性要求不是很高的信息，通常采用报文分组交换的方式，将长的报文分 成若干报文分组( p a c k e t ) ，以报文分组为单位进行数据的发送、暂存和转发，具 有传送灵活、链路利用率高、传输可靠性强等优点。然而，随着互联网规模的不 断扩大以及互联网应用的剧增，传输线路的负载( l o a d ) 也逐渐增大，致使中途的 路由器常常挤压大量报文分组，造成网络的拥塞现象。 网络中拥塞的定义为：由一个或多个中间节点的超载所引起的一种服务延时 的状况i ij 。( c o n g e s t i o ni sd e f i n e da sac o n d i t i o no fs e v e r ed e l a yc a u s e db ya no v e r l o a d o fp a c k e t sa to n eo rm o r ei n t e r m e d i a t en o d e s ) 图1 1 表示了网络吞吐量与负载的关系：当负载较小时，吞吐量与负载成线 性关系，延迟随负载增加而缓慢增大；当负载增大并越过膝点( k n e e ) 后，吞吐量 仍随负载的增加而增加，但其增加的增量逐渐减小，而延迟以更大的增量上升； 而当负载越过崖点( c l i f f ) 继续增加时，吞吐量急剧下降，延迟的增量进一步扩大， 此时整个网络传输面临瘫痪，造成拥塞崩溃( c o n g e s t i o nc o l l a p s e ) 现象。1 9 8 6 年 1 0 月，i n t e m e t 遭遇历史上第一次拥塞崩溃，美国l b l 到u cb e r k e l e y 的数据吞 吐量从3 2 k b p s 跌落至4 0 b p s 。2 0 0 1 年2 月及2 0 0 6 年1 2 月，由于我国通往美国 的海底光缆发生阻断，我国临时启用卫星通讯。卫星线路带宽远小于海底光缆， 导致大量报文分组被丢弃，严重影响了国内用户对北美网站的访问。 江苏大学硕士学位论文 吞 吐 量 延迟 负载 负载 图1 1 网络的吞吐量、延迟随负载变化的示意图 网络拥塞产生的原因是多方面的。其中，网络设施条件的供应不足是产生网 络拥塞的直接原因。对此，中国科学院计算机计算技术研究所学者罗万明指出以 下几点1 2 1 ( 1 ) 存储空间不足。几个输入数据流共同需要同一个输出端口，在这个端口 就会建立排队。如果没有足够的存储空间存储，数据包就会丢弃。对突发数据流 更是如此。增加存储空间在某种程度上可以缓解这一矛盾，但如果路由器有无限 存储量时，拥塞只会变得更坏，而不是更好，因为在网络里数据包经过长时间排 队完成转发时，它们早已超时，源端认为它们已经被丢弃，而这些数据包还会继 续向下一路由器转发，从而浪费网络资源，加重网络拥塞。 ( 2 ) 带宽容量不足。低速链路对高速数据流的输入也会产生拥塞。根据香农 信息理论，任何信道带宽最大值即信道容量c = b l o g ：( 1 + s n ) ( 为信道白噪 声的平均功率，s 为信源的平均功率，召为信道带宽 ) 。所有信源发送的速率r 必须小于或等于信道容量c 。如果r c ，则在理论上无差错传输就是不可能的， 所以在网络低速链路处就会形成带宽瓶颈，当其满足不了通过它的所有源端带宽 要求时，网络就会发生拥塞。 ( 3 ) 处理器处理能力弱。速度慢也能引起拥塞，如果路由器的c p u 在执行 排队缓存，更新路由表等功能时，处理速度跟不上高速链路，也会产生拥塞。同 样，低速链路对高速c p u 也会产生拥塞。 另外，用户对网络的应用需求状况也呈现了一定的不确定状况导致了网络拥 塞的产生。对此，重庆大学的郭松涛学者在其博士论文中指出两方面原因【3 】： ( 1 ) 宏观原因。网络中有限的资源由多个用户共享使用，由于没有准入控制 算法，网络无法根据资源的利用情况决定用户的数量：由于缺乏中央控制，网络 也无法控制用户使用资源的数量。 ( 2 ) 微观原因。假设有刀个流经过同一个路由器r ，流i 在，时刻到达路由 器的速率是n ( d ，路由器r 输出链路的带宽是c ，力个流的聚合到达速率是： 江苏大学硕士学位论文 a ( t ) = ( ，) ，如果么( d 5c ，所有到达的报文无需等待，立刻被发送出去。如 百 果彳( 妒c ，到达的报文需要经过排队等待，才能发送出去。如果这种状态维持下 去，排队等待的报文数量就将逐渐增多。存储容量有限的缓冲区最终会溢出，以 后达到的报文将被丢弃。 可以看出，网络拥塞实际上是由网络设施条件不能满足网络用户的需求( 即： 供不应求) 所引起的。为解决网络拥塞状况，就需实施一定措施，来改善网络供 给与用户需求的供求关系。一种直接的方案是提高网络设施的传输能力，如增加 存储空间、提高线路带宽，增强处理器的处理能力等。然而，由于用户对网络需 求复杂多变，单纯提高网络设施的传输能力往往成本高、效果低，有时甚至会适 得其反，例如：当用户对网络传输的实时性要求较高时，增大路由器的存储空间， 会带来额外的延时，导致用户的网络应用会因应答超时重传大量报文，使网络状 况进一步恶化。从而，网络拥塞现象的改善更需要采用一定控制算法，在用户需 求高于网络的承载能力时实施拥塞控制，减少网络传输中的负荷，进而缓解拥塞 状况。 1 2 国内外研究现状 当前的a q m 算法根据其控制原理主要可分为如下三大类：基于队列长度的 a q m 算法、基于流量速率的a q m 算法和基于队列长度与流量速率的a q m 算 法。 ( i ) 基于队列长度的a q m 算法 早在1 9 9 3 年，f l o y d 等人就提出了r e d ( r a n d o me a r l yd e t e c t i o n ) 主动队列管 理算法。r e d 是一个基于队列长度进行队列管理的典型算法。它在每个报文分 组到达路由器时计算当前的队列长度统计值，并据此设置一个概率值，使得到达 的报文分组以此概率被丢弃或标记，从而早期避免拥塞的发生。 在r e d 之后，部分学者对r e d 算法进行改进，如：a w e y a 等提出的动态 r e d ( d y n a m i cr e d ，d r e d ) 1 4 算法、安智平等学者提出的自适应阀值的 r e d ( s a t r e d ) t s l 算法、w a n g 等提出的自适应模糊r e d ( a d a p t i v ef u z z y b a s e dr e d ， a f r e d ) 1 6 j 算法、s u n 等提出的p d r e d 7 。，f e n g 等提出的改良r e d ( m o d i f i e d r e d ，m r e d ) 8 】算法，b a r b e r a 等提出的动态自适应r e d ( d y n a m i c a l l ya d a p t i v e r e d ，d a r e d ) t 9 】算法，h u 等提出的双曲线r e d ( h y p e r b o l ar e d ，h r e d ) 1 1 0 1 算法， z h o u 等提出的非线性r e d ( n o n l i n e a rr e d ，n l r e d ) 】算法，曹振臻等提出的预 3 江苏大学硕士学位论文 估r e d - - p e r e d t l 2 1 及其改进算法d s p e r e d ( d i f f s e r vp e r e d ) t 1 3 1 ，p a t r o 等提出 的改进算法【1 4 1 ，s a h u 等提出的多级r e d 15 1 ，m a h a j a n b 等提出的r e d p d ( r e d w i t hp r e f e r e n t i a ld r o p ) 1 6 1 ，夏奕等提出的基于动态阀值的d s r e d 算法【1 7 】， a b b a s o v 等提出的e r e d ( e f f e c t i v er e d ) t 博j 。 其改进的主要方向如下： 基准收敛思想。针对r e d 算法的延时性能问题，d r e d 算法提出将一个基 准队列长度( q r e t ) 作为控制目标，并设置改进策略，使得平均队列长度能够随时 间的增加趋于q r e f 这种思想在此后的许多a q m 算法( 如e r e d ，y e l l o w ) 中 均有一定的体现。 参数自适应设置。针对r e d 的参数配置问题，s a t r e d 提出对r e d 中的阀 值进行自适应设置。a f r e d 提出通过自适应机制来动态的调节r e d 中的参数的 设置规则，使其在动态网络环境下能够保持稳定。p d r e d 与m r e d 分别运用 比例加微分控制器( p r o p o r t i o n a l d e r i v a t i v ec o n t r o l l e r ) 和网络负载来调节r e d 算法 中m a x 。的值，提高了r e d 的性能与适用性。此外，d a r e d 、h r e d 、n l r e d 、 r e d - - p e r e d 也运用几何、控制系统等领域的模型进行应用，优化配置r e d 算 法的参数。 公平策略。r e d p d 对流的带宽占用率进行检测，并在拥塞程度恶化时优先 选择带宽占用率高的流实施丢包。d s p e r e d 、d s r e d 增加区分服务设置，为 不同优先级的服务提高不同的拥塞控制措施，以满足不同的q o s ( q u a l i t yo f s e r v i c e ) 需求。此外，r e d 的公平性问题也可以通过队列调度、缓存管理的相应 措施来解决，如：队列调度中的轮询法，缓存管理中的依流分配、依优先级分配， 依类分配等方法，均取得了较高的公平性。 ( i i ) 基于流量速率的a q m 算法 r e d 及其改进算法之外，还有其它方向的发展，其中，引进了速率工具来 刻画拥塞程度和实施控制成为a q m 算法的一大突破。早在1 9 9 8 年，s t o c i c a 等 利用带权幂指数移动平均( e x p o n e n t i a lw e i g h t e dm o v i n ga v e r a g i n g ，e w m a ) 算法 进行了各个流速率及聚集流的估计，并以此估计的流率设计了公平a q m 算法一 一c s f q ( c o r e - s t a t e l e s sf a i rq u e u e i n g ) ，开启了以速率工具来估计拥塞程度的先 河。 2 0 0 2 年，w y d r o w s k i 等提出g r e e n 算测1 9 】，进一步引用此算法对聚集流的 流率进行估计，以流率与带宽的差值作为拥塞标志，对报文分组的丢弃或标记的 概率值进行迭代设置，取得了较d t 、r e d 、b l u e 、r e m 更高的链路利用率， 更低的丢包率和延时，验证流率在a q m 设计中的价值。 4 江苏大学硕士学位论文 之后，p a r k 等设计了虚拟速率控$ 1 j ( v i r t u a lr a t ec o n t r o l ，v r c ) 2 0 】算法，能对负 载变化做出快速的反应，及时调整控制策略，从而在动态网络环境下获得了更高 的链路利用率和更低的丢包率。k a m r a 提出了一个基于速率的公平自适应带宽分 配( f a i ra d a p t i v eb a n d w i d t ha l l o c a t i o n ，f a b a ) 2 1 方法，使得a q m 的公平性得到 了直接的体现。 ( i i i ) 基于队列长度与流量速率的a q m 算法 队列长度的运用可以在小范围内对拥塞进行较为精确的控制，流量速率的运 用可以承受较大程度的负荷，实施更为有力的拥塞控制。从而，一些学者提出将 两者相结合的a q m 算法的研究。如：l o n g 等利用路由器的输入流速率与队列长 度统计值刻画一个负载因子，并提出的y e l l o w 2 2 】算法；s u n 等综合考虑路由器的 输入流速率与队列长度设计的a q m 鲁棒控制器一r a q 【2 3 1 ，a w e y a 等将p i 控制 器与流率相结合【2 4 j 设计的a q m ，c h e n 等为保证了闭环系统的渐进稳定性，基于 非线性系统模型提出的变结构控$ i j ( v a r i a b l es t r u c t u r ec o n t r o l ，v s c ) 2 5 】算法。 ( i v ) 其它a q m 算法 还有其它方向的发展，如自动控制理论的应用：基于t c p a q m 非线性模型 的p i 【2 6 1 、a p i ( a d a p t i v ep i ) 【2 7 】；c h e n 等利用极点配置法提出的s t - p i p p ( s e l f - t u n i n g p r o p o r t i o n a l p l u s i n t e g r a lc o n t r o l l e rb a s e do np o l ep l a c e m e n t ) 1 2 8 】【2 9 】；y a n g 等基于经 典控制理论提出的p 、p i 、p i d 3 0 1 ；y a s s i n e 等基于模糊控制理论提出的f a f c ( f a s t a d a p t i v ef u z z yc o n t r o l l e r ) 【3 i 】，c h e 等提出的f a f d ( f u z z ya p p r o x i m a t ef a i r d r o p p i n g ) 3 2 1 ，s u b a s r e c 等提出的f d s r e d ( f u z z yd o u b l es l o p er e d ) 和 f e r e m ( f u z z ye n h a n c e dr e m ) 3 3 1 ，p i e r r e f r a n c o i s 等利用鲁棒h o o 控制技术设计 的a q m 算法【3 4 1 ，a n d r e a s 等利用非线性控制理论设计的i d c c ( i n t e g r a t e dd y n a m i c c o n g e s t i o nc o n t r 0 1 ) 3 5 】，基于虚队列进行控制的a v q l 3 矾，c h e n 等对p i d 的改进 算法g a b a s e dp i d t 3 7 1 ，w a n g 等对内膜控制器的应用【3 8 】，z h e n g 等的h o o a q m 算法f 3 9 1 ，m a r a m i 等的模型预测控制器( m o d e lp r e d i c t i v ec o n t r o l l e r , m p c ) 的应用 m ，c h a n g 等的自适应比例积分控制器( a d a p t i v ep r o p o r t i o n a l i n t e g r a l ，s a p i ) 4 1 】。 此外，还有基于队列满空事件完成a q m 控制的b l u e 4 2 】算法，基于影子价格模 型对网络拥塞程度进行估计和控制的r e m t 4 3 j 等等。 1 3 主要研究内容 本文首先概述了网络拥塞控制，分别阐述了传输层的源算法与网络层的链路 算法，为后文提出结合两者的a q m 算法作铺垫。然后将a q m 算法分为控制器 江苏大学硕士学位论文 与传感器两个层次，并对两类传感器算法队列长度统计法与流量速率估计法 进行研究，并对流量速率估计法中存在的问题进行改进。之后研究并提出一种基 于源端拥塞控制规律的主动队列管理算法e r f u 算法，给出了传感器算法的 选择与控制器算法的生成过程，并给出了算法的伪代码。最后通过m a t l a b 与n s 2 的仿真和分析表明：该算法应用于主动队列管理是可行的，并且具有较之b l u e 、 p i 、r e m 、y e l l o w 、e r e d 更高的性能与鲁棒性。 本文的主要工作包括： 1 给出一种a q m 算法的设计层次，将自动控制系统中的传感器与控制器 的概念应用于队列管理策略，对其进行建模，将a q m 算法划分为a q m 传感器 算法与a q m 控制器算法。 2 对a q m 传感器算法进行研究，对三种常用的流量速率估计法叫w m a 算法、结合变化趋势的e w m a 算法和p l m a 算法进行分析，指出其在对聚集流 进行估计时存在较低的精度，并根据流率测量值的相对波动量进行算法中参数的 自适应设置，从而提高了算法的估计精度。 3 对源端拥塞控制行为的进行了分析，总结了源端拥塞的控制规律，并以 此设计了一种基于t c p 源端拥塞控制规律的a q m 算法，对传感器的选择、控 制器算法的内容进行了阐述，并给出了算法的伪代码。 4 分性能与鲁棒性两个方面对基于源端拥塞控制规律的a q m 算法进行了 仿真和分析。仿真中，提出的算法与五个此前的a q m 算法进行比较，给出了实 时延时状况与吞吐量、平均延时与队列长度标准差值来评价控制效果，验证了算 法的优良特性。 1 4 章节安排 第一章：绪论 简要介绍主动队列管理算法的相关背景和研究现状，概述本论文的主要研究 内容。 第二章：网络拥塞控制概述 概括叙述网络拥塞控制，包括t c p i p ，源算法，链路算法。 第三章：a q m 传感器算法的研究与改进 将a q m 算法分为控制器与传感器两个层次，着重对传感器进行研究，并对流 量速率估计算法进行分析与改进。 第四章：基于源端拥塞控制规律的主动队列管理算法 6 江苏大学硕士学位论文 本章是本文的主要章节，提出一种全新的a q m 设计方法。将源端拥塞控制规 律进行概括，应用与主动队列管理算法的设计之中。 第五章：仿真实验 对第四章提出的算法进行计算机仿真模拟，通过n s 2 构建仿真环境，利用 m a t l a b 进行数据处理并作图。 第六章：总结与展望 本章全面总结了本文论述的内容，同时对进一步的研究作了展望。 江苏大学硕士学位论文 2 1 引言 第二章网络拥塞控制概述 t c p d p ( t r a n s f e rc o n t r o l np r o t o c o l i n t e m e tp r o t o c o l ，传输控制协议网际协 议) ，是因特网互连通讯的一簇协议的总称。它是2 0 世纪7 0 年代中期美国国防 部为其a r p a n e t 广域网开发的网络体系结构和协议标准，而i n t e m e t 基于 a r p a n e t 组建，随着i n t e m e t 的广泛使用，t c p i p 也得到了发展和革新。现今， 它为i n t e m e t 的传输交换，传输中的故障处理，以及路径的管理提供了规范，成 为了i n t e m e t 国际互联网络的传输标准。传输控制协议( t c p ) 协议和网际协议( i p ) 协议是t c p i p 中保证数据完整传输的两个基本的重要协议。除此之外，t c p i p 还包括u d p ( u s e rd a t a g r a mp r o t o c 0 1 ) 用户数据报协议、i c m p ( i n t e r n e tc o n t r o l m e s s a g ep r o t o c 0 1 ) - f f 联网控制信息协议、r i p ( r o u t i n gi n f o r m a t i o np r o t o c 0 1 ) 路由信 息协议、t e l n e t 远程登录协议、s m i p ( s i m p l em a i lt r a n s f e rp r o t o c 0 1 ) 简单邮件 传输协议、s n m p ( s i m p l en e t w o r km a n a g ep r o t o c 0 1 ) 简单网络管理协议、 a r p ( a d d r e s sr e s o l a t i o np r o t o c 0 1 ) 地址解析协议、f t p ( f i l et r a n s f e rp r o t o c 0 1 ) 文件 传输协议、t f t p ( t r i v i a lf i l et r a n s f e rp r o t o c 0 1 ) 简单文件传输协议、h t t p f h y p e r t e x tt r a n s f e rp r o t o c 0 1 ) 超文本传输协议等上百个其它协议，以实现其它的 如无连接传输、传输控制、路由选择、远程登录、电子邮件、网络管理、地址解 析、文件传输、超文本传输等功能。t c p i p 可分为应用层、传输层、互联网络 层( 网络层) 、网络接口层四个层次，如表2 1 所示： 表2 1t c p i p 的层次结构 t c p i p 结构滇体协议 陌f t p ，h r r p ，s n m p ，f t p ，s m t p ，d n s ， | 应用层 肫l n e t 传输层 t c p ，u d p 网络层 i p ，i c m p ，r i p ，o s p f ，b g p ，i g m p g l i p ，c s l i p ，p p p ，a r p ，r a i p ，m t u ， 网络接口层 s 0 2 11 0 ，l e e e 8 0 2 。i e e e 8 0 2 2 本章所要介绍的网络拥塞控制算法存在于t c p i p 结构的两个层次之中。根 据其层次的不同，网络拥塞控制算法可分为两类 4 4 1 ：一类是位于传输层的源算 法( s o u r s ea l g o r i t h m ) ，它在信息发送端的主机上实施的传输控制策略。另一类是 8 江苏大学硕士学位论文 网络层的链路算法( 1 i n ka l g o r i t h m ) ，它在传输的中转设备路由器上实施传输 控制策略。 源算法面向t c p i p 结构中传输层的t c p 协议。t c p 采用闭环传输方式，在 进行t c p 流传输时，t c p 报文的接收端主机每收到一个报文分组即反馈一个 a c k 应答至发送端的主机。从而，信息发送端的主机可以通过反馈的a c k 的标 识或数量及到达发送端主机的时间来判断网络的拥塞程度，进而采取相应的拥塞 控制策略。 链路算法面向t c p i p 结构中的网络层，当报文分组到达网络设备时，通过 判断网络设备内部的状态、最近报文分组的到达情况等来确定网络的拥塞程度， 从而根据此拥塞程度实施相应的拥塞控制策略。 下面分别介绍两类拥塞控制算法。 2 2 传输层的源算法 源算法面向t c p 协议，采用闭环控制方式实施拥塞控制。它通过序列号来 组织待发送或待接收的报文分组，通过a c k 到达发送端的情况来确认报文分组 传送是否成功，进而判断是否存在拥塞状况。若判断网络无拥塞，则发送方就会 增加其每次的发送量；若判断网络存在拥塞，则发送方就会降低其发送速率，来 减缓拥塞程度。 源算法自t c p 流量控制机制发展而来。它基于流量控制机制中的发送窗口 与接收窗口，建立拥塞窗口，实施传输的限制，下面从t c p 的流量控制开始， 详细阐述这类控制算法。 2 2 1t c p 流量控制 t c p ( t r a n s m i s s i o nc o n t r o lp r o t o c 0 1 ) 是一种传输控制协议，提供面向连接的、 可靠的字节流服务。它位于o s i 模型的传输层，负责接收应用层待传输的数据 流，将其分割为适当的报文段并往下传输，通过网络层、数据链路层、物理层， 开始数据的传输。t c p 协议是目前在i n t e m e t 中使用最广泛的传输协议。据m c i 统计，i n t e m e t 互联网上总字节数的9 5 及总数据包数的9 0 是采用t c p 协议传 输。 t c p 对待传输的字节流采纳一种滑动窗口的传输机制。它为发送方与接收方 各自创建的一个缓冲区作为窗f l ( w i n d o w ) ，存储待发送或待接收的数据帧，并对 收到应答之前可以发送的数据帧或可以接收的无序数据帧的个数进行限制。在流 量控制机制中，接收端将接收窗口的值放在t c p 报文的首部中的窗口字段中， 9 江苏大学硕士学位论文 传送给发送端，以限制发送端的发送量。接收窗口又称为通知窗口( a d v e r t i s e d w i n d o w , a w i n ) 。 发送方为每一个要发送的帧都给定一个编号，根据发送窗口依次发送多个报 文分组；接收方根据接收窗口指定可接收数据帧的编号范围，当收到一个或多个 数据帧后，对发送方进行a c k 应答，并根据可提交数据帧的数目进行接收窗口 的滑动；发送方收到a c k 后，发送窗口作相应的滑动，并进行下一次的发送。 设窗口为7 ，则发送过程如图2 1 所示： 已确认 i 可发送未确认 l 不可发送 已确认 l 可发送未确认 l 不可发送 图2 1 发送窗口滑动示意图 其中每个数字代表一帧，可发送未确认部分即为发送窗口涵盖的部分。 根据滑动窗口机制，收到a c k ( 5 ) j 毒，标号为4 及之前的帧被确认，于是发, 4 送端可以额外再发一帧，发送窗口往右滑动1 帧 同样的，接收端也将要接收的部分根据编号分为三部分，如图2 2 所示： 已提交 l 己接收但未提交 f 未接收 1 617 101 1 1 21 3 匡415画1 61710112 3141516 1 710111213 1 已提交 l 已接收但未提交 i 未接收 虹盘b 丘蓝山占瞳o _ 王- 二乞z 二岂幽 图2 2 接收面口滑动示意图 其中，已接受但未提交的部分即为接收窗口涵盖的部分。在收到4 之后，接 收窗口右移，从而可以另外接收一个编号为3 的报文分组。 通过上面对滑动窗口的流量控制机制的叙述可以看出，基于滑动窗口的t c p 流量控制机制对报文分组的收发量起到了限制作用，保证了收发双发对流量的可 控性，从而为拥塞控制提供了基础。 l o 江苏大学硕士学位论文 2 2 2t c p 源端的拥塞控制 最初的t c p 协议中只有基于窗口的流量控制机制而没有拥塞控制机制。流 量控制机制只考虑了发送端与接收端，并未考虑网络的传输能力，当用户提供给 网络的负载大于网络资源容量和处理能力时，网络拥塞现象就会发生。其中，网 络资源容量是指如缓存空间、通信信道带宽容量、处理机处理能力等指标。无论 增加缓存容量还是提高处理器及链路的速度都不能从根本上解决问题，相反，某 些情况甚至可能会进一步加剧拥塞【4 5 j 。例如，如果增加路由器的缓冲，那么报 文通过路由器的延迟就会增大，当延迟超过源端系统中重传定时器的值时，就会 导致报文的重传，而这种重传反而增加了拥塞的程度。当网络流量过大时，会导 致整个网络完全瘫痪，造成拥塞崩溃现象。 v a nj a c o b s o n 与k a r e l s 于1 9 8 8 年指出了t c p 在控制网络拥塞方面的不足， 并开发了t a h o e 算法，提出了慢启动( s l o ws t a r t ) 、拥塞避免( c o n g e s t i o n a v o i d a n c e ) 算法作为拥塞控制策略，极大的改善了i n t e m e t 端对端连接的性能和稳定性【46 。 下面详细阐述两算法的内容。 ( a ) 慢启动 在只含有流量控制机制的t c p 中，当接收方与发送方确定好发送的窗口后， 发送方就可依据这个窗口值，一次发送多个分组，这样会使得流量从0 骤变到一 个较大的值，将使得中间节点有可能耗尽其存储空间，导致网络吞吐量急剧下降。 慢启动就是为了避免这种现象的发生而提出的。 定义一个拥塞窗口( c o n g e s t i o nw i n d o w , c w n d ) ，这是发送方根据自己估计的 网络拥塞程度而设置的窗口值，是发送方依据网络状况对发送窗口的另一个限 制。从而，发送窗口的大小受到通知窗口与拥塞窗口c w n d 的双重限制。 慢启动的基本原理是：当建立t c p 连接后，由小到大逐渐增大发送端的拥 塞窗口c w n d 的数值，从而减缓了发送窗口的增长，降低了网络的拥塞状况。具 体操作为：初始阶段设置c w n d = l ，每收到一个a c k 确认，拥塞窗口就增加一 倍的数据分组的发送量( 设接收窗1 2 相对较大) ，从而，拥塞窗1 2 随着 r t t ( r o u n d t r i pt i m e ) 数目的增长呈指数增长，如图2 3 所示： 可见慢启动的“慢”并不是指c w n d 的增长速率慢，但是，和一开始就设置 较大的发送窗口相比，慢启动算法可以使发送端在开始发送时向网络注入的分组 数大大减少。这对防止网络出现拥塞是个非常有力的措施。 c w n d 的过度增长也会使网络产生拥塞，因而还需要另一个状态变量，即慢 启动阀值s s t h r e s h 。在c w n d s s t h r e s h 时改 江苏大学硕士学位论文 用拥塞避免算法。当c w n d = s s t h r e s h 时，发送端既可以使用慢启动也可以使用拥 塞避免。s s t h r e s h 的初始值可以任意取值或使用接收端通知窗口的尺寸，但通常 设置为6 5 5 3 5 b y t e s 。在收到搠塞信号后，s s t h r e s h 大小会降低。 开始 - - )c w r l d = l 经过1 个i 汀t 后 - - c w n d = 2 幸1 = 2 1 2 经过2 个r t t 后 - - )e w n d = 2 拳2 = 2 2 = 4 经过3 个i 盯t 后 - - )c w n d = 2 * 4 = 2 3 = 8 经过4 个r t t 后 - - ) c w r x l = 2 * 8 = 2 4 = 1