（计算机应用技术专业论文）ecn拥塞控制算法研究.pdf

南京邮电大学硕士研究生学位论文摘要 摘要 在因特网中，近总字节数的9 5 采用t c p 进行传输，t c p 端到端的拥塞控制策略对 i n t e r n e t 的鲁棒性和稳定性具有重要的作用，拥塞控制一直是网络研究领域的热点之一。 本文首先讨论了网络拥塞的成因，给出了网络拥塞控制算法性能的基本评价方法，从多个 角度对拥塞控制算法进行分类；接着详细介绍 t c p 拥塞控制源算法的演进，并针对几种 经典的t c p 源算法做了比较研究。t a h o e 、r e n o 等t c p 拥塞控制源算法通过检测丢包( 收到 重复确认包或重传计时器超时) 推断拥塞，但是这种方法容易造成经过同一路由器的连接 发生全局同步：另外，t c p 会对具有较长r t t 的连接产生偏见，造成占用瓶颈链路带宽的不 公平。针对t c p 源算法的弊端，研究者认为最有效的拥塞检测位置在网关，网关可提供显式 拥塞信息，网络的发展也要求网络本身必须参与其资源的控制，于是提出了基于中间设备 的i p 链路算法，如d e c - b i t 、e c n 、a e c n 和b e c n 等。 本文对这些算法进行了探讨，并将提供显式拥塞信息的算法归于显式拥塞控制算法， 做了深入的研究，在e c n 和b e c n 的基础上提出一种改进的e c n 算法c m e c n 。c m e c n 算法能更早 更可靠地进行拥塞通知，降低丢包率，提高吞吐量，缩短端到端时延，减少队列长度的波 动，同时不会产生过多逆向流量。因为拥塞控制链路算法与队列管理和调度机制密切相关， 所以本文简单讨论了队列管理算法和调度算法，介绍了一种典型的主动队列管理算法r e d 。 最后，本文通过仿真实验，分析了r e n o 、r e d 、e c n 和c m e c n 算法的性能，同时也验证了所 给出的改进方案c m e c n 的有效性。 南京邮电大学硕士研究生学位论文a b s t r a c t a b s t r a c t a si nt h ei n t e r n e t ，a l m o s t9 5 o ft o t a lb y t e sw e r et r a n s m i t t e db yt c p ，a n di ti sv e r y i m p o r t a n tt h a tat c pe n d - t o e n dc o n g e s t i o nc o n t r o li su s e df o ri n t e r n e t sr o b u s t n e s sa n ds t a b i l i t y c o n g e s t i o nc o n t r o lh a v i n gb e e nah o t s p o ti nn e t w o r kr e s e a r c hr e a l m a tf i r s t ，t h i st h e s i s d i s c u s s e st h er e a s o n st h a tr e s u l ti nn e t w o r kc o n g e s t i o n ，l i s t ss o m eb a s i cm e t h o d st oe v a l u a t e n e t w o r kc o n g e s t i o nc o n t r o l a l g o r i t h m s p e r f o r m a n c e ， a n dc l a s s i f i e st h e c o n g e s t i o nc o n t o l a l g o r i t h m sf r o ms e v e r a la s p e c t s a f t e rt h a t ，t h i st h e s i si n t r o d u c e st h ee v o l m i o no ft c p c o n g e s t i o nc o n t r o ls o u r c ea l g o r i t h m s ，s e v e r a lc l a s s i c a la l g o r i t h m so ft h e mw e r ec o m p a r e da n d r e s e a r c h e d t c p 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 s ，s u c ha l s t a h o e ，r e n o ，e t c i n f e r c o n g e s t i o nt h r o u g hp a c k e tl o s sd e t e c t i n g ( r e c e i v e dd u p l i c a t ea c kp a c k e t so rr e t r a n s m i tt i m e o u t ) ， ： t h i sl o s s - d e t e c t i o nm e c h a n i s mi sp r o n et oc a u s eag l o b a ls y n c h r o n i z a t i o no ft h ef l o w sa c r o s st h e s a m er o u t e r b e s i d e st h e s ei s s u e s ，t c pa l s oh a sab i a sa g a i n s tc o n n e c t i o nw i t hl o n g e rr o u n d t r i p t i m e sw h i c hr e s u l t si nu n f a i rs h a r i n go ft h ea v a i l a b l eb a n d w i d t ho fab o t t l e n e c kl i n k t or e s o l v e t h ep r o b l e mo ft c ps o u r c ea l g o r i t h m s ，r e s e a r c h e r sr e a l i z e dt h a tt h em o s te f f e c t i v ed e t e c t i o no f c o n g e s t i o nc a no c c u ri nt h eg a t e w a yi t s e l f , g a t e w a yc a np r o v i d ee x p l i c i tc o n g e s t i o ni n f o r m a t i o n ， a n dw i t ht h en e t w o r kd e v e l o p m e n t ，t h en e t w o r km u s tp a r t i c i p a t ei nc o n t r o l l i n gi t so w nr e s o u r c e u t i l i z a t i o n c o n s e q u e n t l y ，t h ei pl i n ka l g o r i t h m sw h i c hb a s e do ni n t e r m e d i a t ee q u i p m e n t sw e r e p r o p o s e d ，s u c ha sd e c - b i t ，e c n ，a e c n ，b e c n ，e t c t h i st h e s i sd i s c u s s e st h e s ea l g o r i t h m sw i t hd e t a i l ，a n dc a t e g o r i z e st h e a l g o r i t h mw h i c h s u p p l y i n ge x p l i c i tc o n g e s t i o ni n f o r m a t i o na se x p l i c i tc o n g e s t i o nc o n t r o la l g o r i t h m ，t h e nm a k ea d e e p l yr e s e a r c h ，p r o p o s e sa ni m p r o v e de c na l g o r i t h mc m e c nb a s e do ne c na n db e c n c m e c n a l g o r i t h mc a nn o t i f i c a t ec o n g e s t i o ne a r l i e ra n dm o r er e l i a b l e ，i ta l s oc a nr e d u c ep a c k e t l o s s ，i m p r o v et h r o u g h p u t ，s h o r t e ne t ed e l a y ，r e d u c eq u e u ef l u c t u a t i o na n de l i m i n a t e u n n e c e s s a r yi s qr e v e r s et r a f f i c t h e n ，q u e u em a n a g e m e n ta n ds c h e d u l ea l g o r i t h m sw e r e i n t r o d u c e db r i e f l yb e c a u s eo ft h e i rc l o s e l yr e l a t i o nw i t hc o n g e s t i o nc o n t r o ll i n ka g o r i t h s f i n a l l y ， t h i st h e s i sa n a l y z e st h ep e r f o r m a n c eo fr e n o ，r e d ，e c na n dc m e c n v a l i d a t e st h ee n h a n c e d e c ns h e m eu s i n gs i m u l a t i o n 南京邮电大学学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究 工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的 地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包 含为获得南京邮电大学或其它教育机构的学位或证书而使用过的材 料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了 明确的说明并表示了谢意。 研究生签名： 簦塑星日期：鲨三：笙多 南京邮电大学学位论文使用授权声明 南京邮电大学、中国科学技术信息研究所、国家图书馆有权保留 本人所送交学位论文的复印件和电子文档，可以采用影印、缩印或其 他复制手段保存论文。本人电子文档的内容和纸质论文的内容相一 致。除在保密期内的保密论文外，允许论文被查阅和借阅，可以公布 ( 包括刊登) 论文的全部或部分内容。论文的公布( 包括刊登) 授权 南京邮电大学研究生部办理。 研究生签名：守纠多导师签名： 南京邮电大学 硕士学位论文摘要 学科、专业： 工学计算机应用技术 研究方向： 计算机通信与网间互连技术 作 题 2 0 0 4 级研究生宁相军 目：e c n 拥塞控制算法研究 英文题目：t h er e s e a r c ho ne c n 指导教师杨庚 c o n g e s t i o nc o n t r o la l g o r i t h m s 主题词： 拥塞控制窗口机制源算法链路算法 显式拥塞通知队列管理 k e y w o r d s ： c o n g e s t i o nc o n t r o l w i n d o w b a s e dm e c h a n i s m s o u r c ea l g o r i t h ml i n ka l g o r i t h m e x p l i c i tc o n g e s t i o nn o t i f i c a t i o n q u e u em a n a g e m e n t 南京邮电大学硕士研究生学位论文 引言 引言 2 1 世纪是以网络为核心的信息时代，网络化、信息化和数字化正从整体上引导着世界 经济和人类社会的发展进程，以网络化为重要内容的信息技术已成为经济发展的关键因 素。随着网络技术的迅速发展及全球信息高速公路的日臻完善，人类的生活形态和工作模 式已出现了很大的改变，这种改变将继续进行，深刻而全面地影响人类社会的未来。 就近几年来说，网络技术的发展日新月异，网络规模迅速扩大，依靠拥塞控制作为鲁 棒性保证，以t c p i p 为基础的i n t e r n e t 呈爆炸式增长，逐渐发展成为全球性的信息基础设 施。随着新型网络应用的不断涌现和用户数量的迅速增加，使得i n t e r n e t 的流量急剧增长， 数据流的本质也开始发生变化，其中除了传统的f t p 、t e l n e t 、h t t p 等数据流外，还出 现了大量的实时多媒体数据流，由于网络中不同的数据流在路由器处交汇，因而给网络的 路由节点造成很大的负担，越来越严重的网络拥塞问题逐渐暴露出来。同时，基于u d p ( u s e r d a t a g r a mp r o t o c 0 1 ) 协议的实时多媒体应用如i p 电话、视频会议等开始成为网络中的重要 应用，由于这些数据流不遵守t c p 协议，如果它们不能对网络拥塞做出正确响应，将会造 成竞争网络资源不公平现象，甚至使网络面临拥塞崩溃的危险。 事实上，拥塞控制一直是网络研究领域的热点之一。多年来，人们已经对拥塞控制进 行了大量研究，提出或改进了多种多样的拥塞控制算法，致使现在的t c p 实现版本不少于 2 0 0 多种，中间链路设备上的拥塞控制机制也层出不穷。这一方面表明t c p i p 拥塞控制是 网络研究领域的一个热点问题，另一方面也说明t c p i p 拥塞控制仍然没有得到很好的解 决。新型网络技术的应用，使网络的异构性进一步加大，已有的拥塞控制算法的弊端会逐 步显露，更需对其进行研究改进。另外，目前己有越来越多的移动用户通过无线网络接入 i n t e r n e t ，但由于无线通信和卫星网络固有的特点，使得拥塞控制的研究更加困难，极具 挑战性。 本文对拥塞控制进行了较为深入的研究，首先讨论了网络拥塞的成因，给出了网络拥 塞控制算法性能的基本评价方法，从多个角度对拥塞控制算法进行分类：接着主要探讨了 几种经典的拥塞控制算法，重点对显式拥塞通知算法进行研究，分析了算法的局限性及存 在的问题，并讨论了与拥塞控制密切相关的队列管理算法和调度算法；将主动队列管理、 e c n 和b e c n 相结合，提出一种改进的e c n 算法c m e c n 。最后本文对r e n o 、r e d 、e c n 和c m e c n 进 行了仿真研究分析。 南京邮电大学硕士研究生学位论文 第一章绪论 第一章绪论 1 1 研究的背景及必要性 近十几年i t 技术的进步，网络新技术的应用，i n t e r n e t 得到突飞猛进的发展，拥塞 控制机制是其鲁棒性( r o b u s t n e s s ) 的关键因素。 在最初的传输控制协议中只有流量控制( f l o wc o n t r 0 1 ) 而没有拥塞控制( c o n g e s t i o n c o n t r 0 1 ) ，靠接收端通告的t c p 报头中窗口大小字段值限制发送端发送速率。这种只考 虑接收端接收能力而不考虑网络的传输承受能力的控制机制，导致了网络拥塞崩溃 ( c o n g e s t i o nc o l l a p s e ) 的发生【1 1 。1 9 8 6 年1 0 月因特网首次出现了拥塞崩溃后，在拥塞控 制领域便展开了大量的研究工作。 由于最初设计的i n t e r n e t 是非面向连接的分组交换网络，不对业务分组加以区分，网 络的承诺是尽自己最大的努力传输进入网络中的每一分组，无法给出一个定量的性能指 标，如吞吐量、分组丢失率、端到端时延等参量的界限。相应地，用户也无需进行业务许 可请求，因此，网络的性能除本身外，还受用户施加的负载影响。这种网络体系结构缺乏 一定的隔离和保护机制，但建立在这种体系结构上的传统网络应用和网络协议具有较强的 灵活性和适应性【2 】。随着网络的发展，网络业务类型也不断增加，尤其是音频、视频等多 媒体业务在i p 网络中的应用，网络业务模型的建立也越来越重要。而业务体系结构技术 的核心都需要在恰当的层次和粒度上对流量进行必要的管理，包括接纳控制、流量成型、 队列管理、调度和拥塞控制等诸多方面，但最基本和最核心的依旧是拥塞控制，因为对于 一个时常可能发生拥塞且无法及时加以解决的网络来说，实现良好的q o s 保证将无从谈起。 而随着互联网技术的迅猛发展，更多的用户使用网络中的资源，网络中业务流种类呈 现多样性。除了w e b 、f r p 、t e l n e t 等传统数据流外，即时通讯、v o i p 、i p t v 技术的应 用，使音频、视频等多媒体业务流也呈增长趋势。由于网络中不同的数据流在路由器处交 汇，虽然网络带宽、路由器的处理能力和缓存等资源在不断增加，但与日益增长的用户数 量和业务流相比起来，仍然不能满足用户的需求，网络拥塞问题一直威胁着网络的鲁棒性， 已经成为制约网络发展和应用的一个瓶颈。如何更好地预防和控制拥塞，使网络在具有低 丢包率和低时延的同时达到资源的最大效用，是近年来网络研究的热点问题。 网络的发展也导致网络资源和网络流量分布的不均衡性，网络中数据流的数量和种类 也日益增加，不同数据流类在共享网络资源时，会表现出不同的行为，一种“恶意的数 据流会影响其它良好行为流，造成不公平现象，甚至导致网络拥塞。不同种类的数据流对 2 南京邮电大学硕士研究生学位论文第一章绪论 拥塞的响应不同，非响应流会加剧拥塞，若不加以控制将最终导致拥塞崩溃。为控制拥塞 所设计的拥塞控制机制的主要目标是控制进入网络的数据流量，保证通信网络不会被用户 发送的数据流阻塞，并合理地使用瓶颈资源，但其实际效果很大程度上依赖于数据流源端 的响应。拥塞控制算法的分布性、网络的复杂性和对拥塞控制算法的性能要求又使拥塞控 制算法的设计具有很高的难度。到目前为止，拥塞控制问题还没有得到很好的解决【3 1 ，需 要我们进一步研究探索。 1 2i n t e r n e t 的体系结构特点 i n t e r n e t 采用开放互连体系结构，以其为依据开发的t c p i p 协议簇成为当今互联网的 基石，有力地推动了网络技术的发展。可以说拥塞的发生是i p 网络的固有属性，i n t e r n e t 的成功很大程度上取决于拥塞控制的有效执行，而网络中的拥塞与网络的体系结构有着密 切联系，以下将对i n t e r n e t 的体系结构作一简单介绍。 i n t e r n e t 的体系结构有如下几个特点h ：第一，采用报文交换，通过共享提高了资源的 利用效率，但在共享方式下，如何保证用户的服务质量是一个很棘手的问题，在报文交换 网络中可能出现报文“乱序”现象，对乱序报文的处理增加了端系统的复杂性；第二，采 用无连接方式，简化了网络的设计，在网络的中间节点上不需要保存和连接有关的状态信 息，但是使用无连接方式难以引入“接纳控制”算法，在用户需求大于网络资源时难以保 证服务质量，在无连接模型中对数据发送源的追踪能力很差，给网络的安全带来了隐患， 这也是网络中乱序报文出现的一个主要原因；第三，采用“尽力而为的服务模型，即 网络不对数据传输的服务质量提供保证，这个选择和早期网络中的应用有关，但这不能很 好地满足新出现的多媒体应用的要求，这些应用对延迟、速率等性能的变化比较敏感。 i n t e r n e t 的体系结构特点造成了乱序报文的产生，其尽力传输的特点也造成网络拥 塞，使得报文丢失，数据段的重传又进一步加重网络的负担。要解决网络拥塞必须依据其 体系结构进行。 1 3 网络流量的分类及其特点 随着i n t e r n e t 的迅速发展，网络中数据流的数量也逐步增加，数据流的种类也有所增 加，流量的性质发生了很大的变化。不同性质的流在竞争带宽时会彼此产生一些影响，导 致出现不公平等现象。结果可能使得网络的丢包率增高，严重的还会发生拥塞崩溃，对网 络性能产生很大的影响。因此，分析不同流量的特点和可采用的拥塞控制手段，对预防和 解决拥塞具有重要意义。以下对现有的i p 网络流量进行分类并结合拥塞控制进行分析。 首先，从传输层协议的角度讲，网络流量分为t c p ( t r a n s m is sio nc o n t r o lp r o t o c o l 。 3 南京邮电大学硕士研究生学位论文 第一覃绪论 传输控制协议) 流和u d p ( u s e rd a t a g r a mp r o t o c o l ，用户数据报协议) 流。t c p 流指利用 t c p 协议建立t c p 连接所传送的数据流，女i t e l n e t 、f t p 、s m t p 、w w w 服务等所传送的数据流。 t c p 是可靠的、面向连接的数据传输协议，使用一对套接字( 由主机i p 地址和该主机上的 t c p 端口号组成) 来识别连接，使用带重传的肯定确认技术作为提供可靠性的基础，使用 滑动窗口机制来控制流速。对于t c p 流而言，可以采用多种t c p 拥塞控制机制进行管理。u d p 流指采用u d p 协议传送的数据流，女i s n m p 、多媒体流等，u d p 使用底层的i n t e r n e t 协议在网 络之间传输报文，提供和i p 一样的不可靠、无连接的数据报交付服务，不使用确认来确保 报文的到达，没有对传入的报文排序，也不提供反馈信息来控制机器之间信息的流动速度。 因此，u d p 报文可能会出现丢失、重复、或乱序到达的现象，分组到达的速率也可能大于 接收进程能够处理的速率。使用u d p 的应用程序要承担可靠性方面的全部工作，包括处理 报文的丢失、重复、时延、乱序以及连接失效等问题【5 1 。对u d p 流的控制主要依靠网络链路 上中间节点的增强功能实现。 其次，从对拥塞的响应角度来看，可分为响应流( r e s p o n s i v ef l o w ) 和非响应流 ( n o n r e s p o n s i v ef l o w ) 两大类。 响应流采用拥塞控制算法，在网络发生拥塞后采取措施减小注入网络的流量，以缓解 拥塞，采用t c p 拥塞控制机制的t c p 流就属于响应流；响应流包括t c p 兼容流和t c p 非兼容流。 1 t c p 兼容流( t c p c o m p a ti b l ef l o w ) t c p 兼容流与t c p 流类似，采用了端到端的拥塞控制策略，能够对网络提供的丢包或拥 塞指示信息做出响应，调整自己的数据发送速率。在相同条件下，处于稳定阶段时，t c p 兼容流不会l i s t c p 流占用更多的额外带宽。这类流量严格地执行t c p 标准，因而可以采用主 动队列管理技术进行有效控制。 2 t c p 非兼容流( t c pu n c o m p a ti b l ef l o w ) t c p 非兼容流虽然响应拥塞指示，但由于应用程序没有严格地执行t c p 标准，因而与标 准t c p 流是不兼容的。这类流量与其它t c p 兼容流共享带宽时，将会不公平地占用网络带宽。 这种流是在i n t e r n e t 发展过程中产生的不 h j t c p 执行标准造成的。在开放的环境下，有些 应用根本不执行t c p 拥塞控制机制，而有些则比其它t c p 执行占用更多的带宽，声称所谓的 “快速t c p ”。此外，有的还通过使用多个t c p 连接来获取更多带宽，例如某些w e b 浏览器在 浏览w e b l 艮务器时同时建立多个连接以加快浏览速度，还有一些多线程的f 1 p 工具等，这些 应用所产生的流量同样会不公平地占用网络带宽。 非响应流是一种不对丢包率的增加作出响应减小其对路由器施加的负载的数据流【6 1 。 非响应流不采用端到端拥塞控制算法，即使在出现严重丢包时也不会降低数据的传输速 4 南京邮电大学硕士研究生学位论文 第一荦绪论 度。非响应流的这种“不良行为 会造成两种问题，其一是非响应流影响“行为良好的 响应流，造成带宽饥饿( b a n d w i d t hs t a r v a t i o n ) ；其二是使网络忙于传送未到达最终目 的地就被丢弃的数据包，导致网络拥塞崩溃。目前i n t e r n e t 中不断增加的基于u d p 的应用 如音频、视频传输等u d p 流都属于非响应流。如果不采取有效措施，这类流将导致新的拥 塞崩溃。通常情况下，所有的基于u d p 流的应用都应在应用层采取相应的拥塞控制机制。 但事实上，为了追求应用效率，许多u d p 流在应用层未采用相应的控制措施。因此，网络 如何保护自身的资源、有效地控制非响应流是很重要的，并可借以促使非响应流应用采用 相应的拥塞控制机制，保证网络资源的公平使用。 显然，非响应流和非t c p 兼容流对i n t e r n e t 的性能产生巨大的威胁，它们对网络的带 宽具有不公平的侵占性。因而，迫切地需要监视与控制手段对这些数据流进行管理，而最 有效的实施手段主要依赖于路由器的增强机制。：目前，在如何区分和控制非响应流、非t c p 兼容流的算法、以及这些算法的执行对路由器的产生的额外开销能否接受等方面仍然存在 着难点。 另外，从发送流速的角度讲，可将数据流分为t c p 友好流和非t c p 友好流【6 1 。 ，1 t c p 友好流( t c p - f r i e n d l yf l o w ) 如果一个流的到达速率不超过同样情况下任何t c p 连接的速率，就称该流为t c p 友好 流。 2 非t c p 友好流( n o tt c p f r i e n d l yf l o w ) 如果一个流的到达速率长时间超过同样情况下任何t c p 连接的速率，就称该流为非- t c p 友好流。 对于t c p 友好流，收到拥塞指示时对拥塞的响应是将拥塞窗口至少减小一半，然后以 常数速率增加拥塞窗口，每个r t t 至多将窗口增加1 ，给定丢包率p ，t c p 连接的最大发送速 率为tb p s ，t 的范围由式卜l 确定。 tt1523x b( 式卜1 ) r 4 p 其中，b 为一个数据包的最大字节数，r 为最小r t t 。当某数据流的发送速率大于t 时( 不 包括偶尔的突发数据流) ，那么可断定该数据流是非t c p 友好流【6 1 。 当前网络中，一方面，需要一致的t c p 流量控制来达到公平的带宽分配；另一方面，为 了适应业务的特点又期望放弃t c p 流量控制机制，这种为难的局面促使研究者提出新的流 量控制机制。 5 南京邮电大学硕士研究生学位论文 第一章绪论 1 4 小结 本章概括介绍了进行拥塞控制研究的背景和必要性以及与拥塞控制相关的i n t e r n e t 的体系结构特点，并对现有网络中的数据流进行了分类，为以后本论文要做的工作做了铺 垫。 1 5 论文安排 本文主要是以拥塞控制算法为研究对象，并将显式拥塞控制算法作为重点进行了研 究。介绍了拥塞控制研究的背景和必要性，并从多个角度对拥塞控制进行分类，对几种经 典拥塞控制算法作了详细描述，进行了分析研究，并基于e c n 和b e c n 算法提出一种综合 的e c n 算法c m e c n 。之后又对与拥塞控制密切相关的队列管理和调度算法作了探讨，最后 利用仿真工具o p n e t 对几种算法进行了仿真分析。全文结构安排如下： 第一章简要介绍拥塞控制研究的背景及必要性，总结了与拥塞相关的网络体系结构特 点，并对造成网络拥塞的主体数据流进行了分类； 第二章探讨了网络产生拥塞的原因，介绍了几种形式的拥塞崩溃，对拥塞控制和流量 控制加以区分，接着简述了拥塞控制机制的发展和衡量拥塞控制算法性能的指标，并从多 个角度对拥塞控制算法进行分类，进一步描述了t c p 拥塞控制算法； 第三章详细介绍了几种经典的拥塞控制算法，对源算法t a h o e 、r e n o 、n e wr e n o 、s a c k 、 v e g a s 和显式拥塞控制算法e c n 、a e c n 、b e c n 进行了分析研究，提出一种c m e c n 算法； 第四章探讨了与拥塞控制密切相关的队列管理和调度机制； 第五章对仿真平台o p n e t 进行简介，介绍了建模过程，最后利用o p n e t 仿真工具对 r e n o 、r e d 、e c n 和c m e c n 算法进行了建模仿真，对其性能进行了比较分析。 6 南京邮电大学硕士研究生学位论文 第二章拥塞控制 第二章拥塞控制 从因特网诞生起网络拥塞就威胁着其稳定性，虽然随着技术的发展因特网的相关技术 日渐成熟，可对某些方面的问题加以解决，但拥塞控制是一个系统性的问题，单方面条件 的改善只会导致产生瓶颈，网络拥塞却仍不能很好解决，反而随着因特网的规模、用户和 应用的急剧增加，使网络拥塞问题日益突出。要解决网络拥塞问题，首先要了解导致网络 拥塞的原因，对现有的拥塞控制机制有清楚的了解。本章将对关于拥塞控制的一些根本性 问题进行探讨。 2 1 网络拥塞及拥塞崩溃 2 1 1 拥塞的定义及成因 ： 当通信网络中存在过多的报文时，网络性能会下降，这种现象称为拥塞【1 1 。拥塞会导 致报文传输时延急剧增加并进一步导致报文的大量丢失，报文因丢失而重传又会加重拥 塞，造成恶性循环，网络的有效吞吐率( g o o d p u t ) 也因此迅速下降，更为严重的会导致 拥塞崩溃的发生。 网络发生拥塞的根本原因在于用户( 端系统) 提供给网络的负载大于网络资源容量和 处理能力( 即过载，o v e r l o a d ) 。表现为数据包时延增加、丢弃概率增大、上层应用系统性 能下降等。发生拥塞的情况如图2 - 1 所示。 网 络 吞 吐 量 发送数据包量 图2 1 网络拥塞情况 从局部看，拥塞产生的直接原因有以下3 点： 1 带宽容量不足 用户( 端系统) 往往产生高速的数据流，如果不对源端的高速数据流加以控制而让其 直接进入低带宽链路，就会产生拥塞。数据流从高带宽链路经转接进入低带宽链路时，若 不加控制也会因带宽瓶颈产生拥塞。根据香农( s h a n n o n ) 公式，任何信道带宽最大值即 7 堕塞塑皇奎堂堡主翌窒生堂垡笙苎 蔓三童塑墨丝型 信道容量c = b * l o g ：( i + s n ) ( b 为信道带宽，n 为信道加性带限高斯白噪声的平均功率，s 为信 源的平均功率) 。所有信源发送的速率r 必须小于或等于信道容量c 。如果r c ，则在理论上 无差错传输就是不可能的，所以在网络低速链路处就会形成带宽瓶颈，当其满足不了通过 它的所有源端带宽要求时，网络就会发生拥塞。 2 存储空间不足 数据流经由链路传输到达交换机或路由器后，首先在输入接口缓冲区排队，交换机或 路由器对其处理后再在要转发出去的输出端口排队。排队时如果没有足够的存储空间存 储，数据包就会丢弃，对突发数据流更是如此。增加存储空间在某种程度上可以缓解这一 矛盾，但如果交换机或路由器有无限存储量时，拥塞反而会变得更坏，而不是更好，因为 在网络里数据包经过长时间排队完成转发时，它们早已超时，源端认为它们已经被丢弃， 而这些数据包还会继续向下一节点( 交换机或路由器) 转发，：从而浪费网络资源，加重网 络拥塞。 3 处理器处理能力弱、速度慢也会引起拥塞 主要表现在路由器的c p u 方面，路由器对数据包进行选路转发，若其在执行缓冲排队、 更新路由表等功能时，处理数据速度跟不上高速链路，输出能力低于输入流之和，就会产 生拥塞。 发生拥塞事实上是由以上原因导致网络中的包不守恒所致。要避免拥塞发生，必须从 几个方面综合考虑。解决单方面问题，只会转移网络瓶颈，而不能避免拥塞【3 】【7 】。 从全局看，拥塞产生的原因有： 1 b e s t e f f o r t 服务模型网络不对数据传输提供服务质量保证； 2 由于没有“接纳控制 算法和缺乏中央控制，网络无法根据资源的情况限制用户的 数量： 3 i n t e r n e t 资源分布的不均衡和流量分布的不均衡性，导致拥塞总是发生在资源相对 短缺的位置。 随着网络用户数量和服务类型的不断增加，网络流量分布的不均衡性更加明显，从根 本上避免拥塞的产生是很难的。因此，必须采取一定的拥塞控制措施尽可能避免和缓解网 络拥塞，使网络运行在高吞吐量、低延迟的状态下，同时在拥塞发生时使网络尽快从拥塞 状态中恢复过来。 2 1 2 拥塞崩溃 当拥塞发生时，如果没有一个很好的拥塞响应控制机制，则很容易发生网络拥塞崩溃 8 南京邮电大学硕士研究生学位论文第二章拥塞控型 现象。典型的拥塞崩溃主要是由不必要的重传数据包( 这些数据包已经被接收端收到或正 在传输途中却被重传) 引起的；未送达的数据包( u n d e l i v e r e dp a c k e t ) 也可引起拥塞崩 溃，在传送这些数据包时，未到达最后目的地就被丢弃，浪费了带宽，更具破坏性的是尽 力服务应用在丢包率上升时仍增加发送速率。这些潜在的拥塞崩溃危险主要在于未使用端 到端拥塞控制。此外，还有基于分片的拥塞崩溃( f r a g m e n t a t i o n b a s e dc o n g e s t i o n c 0 1 1 a p s e ) ，当网络层数据包被分割后的某些分片( f r a g m e n t ) 或信元( c e l l ) 在传输过程中 丢失( 如在数据链路层) ，其余的到达接收端后由于不能被重组为有效的数据包而被丢弃， 就造成带宽浪费，主要是由于链路层传输单元( 如分片或信元) 与高层传输单元( 如数据 包) 不匹配造成的，可以通过路径最大传输单元( m a x i m u mt r a n s f e ru n i t ，m t u ) 发现机 制或早期丢包( e a r l yp a c k e td i s c a r d ) 等机制解决；另一种拥塞崩溃是由增加的控制流 ( 如带有少量数据信息的数据包、路由更新信息包、组播加入或修剪信息等) 造成的；最 后一种拥塞崩溃是由过时的或不再想要的数据包造成的，因为发生拥塞时链路延时太长， 用户等不及就不再想要，而网络却仍忙于传送这些过时的数据包，浪费带宽导致拥塞崩溃 【8 1 。图2 2 显示了吞吐量( t h r o u g h p u t ) 、响应时间( r e s p o n s et i m e ) 和网络性能随着 网络负载的增加大致变化情况。 吞 吐 量 k n e ec l i f fk n c l i f f 负载负载 ；i n 。 图2 2 吞吐量、响应时l 司和网络性能随网络负载变化情况 从图2 - 2 可以看出，当网络负载较轻时，吞吐量与负载之间呈线性关系，响应时间增 长缓慢；到达膝点( k n e e ) 之后，随着负载的增加，吞吐量增加逐渐变小，而响应时间大幅 度增加：当负载越过崖点( c l i f f ) 之后，吞吐量急剧下降。通常将k n e e 点附近称为拥塞避 免区间，k n e e 和c l i f f 之间是拥塞恢复区间，而c l i f f 之外是拥塞崩溃区间【引。为了最 大限度地利用网络资源，网络工作在轻度拥塞状态时应该是较为理想的，但这也增加了滑 向拥塞崩溃的可能性，因此需要一定的拥塞控制机制来加以约束和限制。 2 2 拥塞控制 既然拥塞始终威胁着网络的稳定，就必须采取拥塞控制措施。对网络实施拥塞控制的 主要目标是控制进入网络的数据流量，保证通信子网不会被用户发送的数据流淹没，合理 地使用瓶颈资源，使网络资源的利用率得以优化，实现网络要求的性能目标和对服务质量 q 南京邮电大学硕士研究生学位论文第二荦拥暴控制 的承诺。 2 2 1 拥塞控制描述 拥塞控制就是网络节点采取措施来避免发生拥塞或对拥塞的发生做出反应【4 】。拥塞控 制包括拥塞避免机制和拥塞控制机制。拥塞避免机制是一种预防机制，允许网络运行在低 延时、高吞吐量区域，防止网络进入会发生丢包的拥塞状态；拥塞控制机制是一种恢复机 制，可使网络从拥塞状态恢复过来，保护网络不让其用户( 位于源端和目的端的传输实体) 发送过多的数据造成数据流洪泛( f l o o d i n g ) 【9 】。i p 网中的资源预留( r e s o u r c er e s e r v a t i o n p r o t o c o l ，r s v p ) ，a t m 网中的连接准许控制( c o n e c t i o na d m i s s i o nc o n t r o l ，c a c ) 等均属 于拥塞避免机制；拥塞时按一定策略对分组进行丢弃的随机早期检测( r a n d o me a r l y d e t e c t i o n ，r e d ) 算法、自适应r e d 算法等属于拥塞控制机制。后边所述的r e n ot c p 、v e g a s t c p 和e c n 等诸多拥塞控制算法既包含拥塞避免机制也包含拥塞控制机制。 拥塞控制和拥塞避免是动态系统控制问题，和其他控制机制一样，包括反馈机制和控 制机制两部分。反馈机制允许网络系统把当前的网络状态通告给用户( 源端或目的端) ， 控制机制允许用户调节系统负载。反馈机制可采用的反馈信息包括以下几个方面【9 】： 1 源端发出的专门用于探测网络状况的端到端探测包； 2 路由器发给源端的拥塞反馈数据包，称为源抑制信息( s o u r c eq u e n c hm e s s a g e ) 或阻塞包( c h o k ep a c k e t ) ； 3 包含在路由器间交换的路由信息中的反馈信息； 4 数据包中包含一个拥塞反馈域( c o n g e s t i o nf e e d b a c kf i e l d ) ，该域由包向前转 发路径上的路由器填充前向反馈( f o r w a r df e e d b a c k ) ： 5 经过拥塞相反路径的数据包中附带一个拥塞反馈域，该域由拥塞相反路径上的路 由器填充逆向反馈( r e v e r s ef e e d b a c k ) 。 2 2 2 拥塞控制和流量控制的关系 流量控制1 0 】是通过对端节点( 用户) 实施一定的控制策略使得用户的数据流量与 j 网络资源相匹配，从而避免或消除用户的数据流过多地占用网络有限资源，实现网络 资源在不同需求的用户之间公平合理地分配。流量控制主要关注端节点注入网络中的 流量，是局部性的问题；拥塞控制最关心的是如何避免、减轻和消除网络拥塞的问题， 采取的措施与网络的各个部分密切相关，包括端节点、路由器或交换机等网络元素， 是一个全局性的问题。拥塞控制往往借助于流量控制对端节点的数据发送速率进行调 节，以减轻或消除拥塞。在网络发展开始的很长一段时间内，基于端节点的流量控制 1 n 南京邮电大学硕士研究生学位论文 第二苹拥塞控制 是唯一有效可行的拥塞控制手段，因而导致“流量控制”和“拥塞控制”术语的混淆。 事实上，前者只是后者的一种技术实现途径而已。t c p 流量控制主要依据流控自时钟1 】 ( s e l f c l o c k i n g ) 的分组守恒定理，采用加性增加乘性减小( a d d i t i v ei n c r e a s ea n d m u l t i p l i c a t i v ed e c r e a s e ，a i m d ) 的窗口管理算法【1 1 1 。 2 3 拥塞控制算法 2 3 1 拥塞控制算法的发展 拥塞控制机制的采用起因于1 9 8 6 年1 0 月，美国l b l 到u cb e r k e l e y 的数据吞吐量从 3 2 k b p s 跌落到4 0 b p s ，i n t e r n e t 经历了第一次所谓的“拥塞崩溃 【1 1 。自此，v a nj a c o b s o n 等人在拥塞控制领域不断进行研究，提出了一系列t c p i p 拥塞控制算法。 自1 9 8 8 年j a c o b s o n 提出拥塞控制算法后，拥塞控制算法经历了t a h o e 、r e n o 、n e w r e n o 和s a c k 等基于丢包的隐式t c p 拥塞控制算法，后来又出现了v e g a s 等新的基于延时的算 法。刚开始的算法主要在端节点实施，归于源算法，因其主要基于t c p 协议，所以也称为 t c p 拥塞控制算法，其利用的拥塞反馈信息多是重复a c k 和计时器超时，所以这些算法多 是隐式拥塞控制算法；而随着异构网络的发展，i p 层也参与进来，就产生了基于i p 层的 链路算法，如s q 、d e c b i t 、e c n 、n e w - e c n 、a e c n 和b e c n 等，主要借助路由器的标记功 能或者产生源抑制包提供显式拥塞信息，属于显式拥塞控制算法。随着高速宽带网、无线 网的发展，在特定网络上的t c p i p 拥塞控制算法也不断改进。 2 3 2 拥塞控制算法的性能评价 在设计和比较拥塞控制算法时，需要一定的评价方法。从用户的角度出发，主要关注 吞吐量、丢包率、时延等指标； 1 吞吐量 端节点的吞吐量就是其有效发送速率，指端节点在单位时间内向网络中成功发送的数 据量，单位一般以b p s ( b i tp e rs e c o n d ) 计。我们定义每个源端j 在时刻f 的传输速率为x ) 。 其中发送速率z f ( f ) 和发送方的拥塞