高速网络拥塞控制研究硕士毕业论文.doc

《高速网络拥塞控制研究硕士毕业论文.doc》由会员分享，可在线阅读，更多相关《高速网络拥塞控制研究硕士毕业论文.doc（56页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、 硕士学位论文 论文题目 高速网络拥塞控制研究 英文题目 Research on Congestion Control for High-Speed Network 硕士研究生 指导教师 学科专业 计算机软件与理论 论文提交日期 2009年4月 论文答辩日期 论文评阅人 答辩委员会主席 2009 年 4 月 10 日Abstract摘 要随着高速网络应用的日益广泛，拥塞控制机制的研究变得越来越重要。拥塞控制至少应该包含两部分：首先是要有源端算法响应路径中的拥塞，动态的调节数据发送速率;另一方面，要有一个中间节点管理机制能有效地预测、监测路径中的拥塞程度，通过显式或隐式的方法在拥塞发生前及时警告

2、源端。目前研究适合高速网络的TCP拥塞控制机制成为一个新的研究热点，一些研究者提出了一些新的算法如：STCP，H-TCP等。这些协议都是通过修改发送窗口的增加减小模式来提高TCP在高速网络中的性能。其中TCPW是以可用带宽测量为基础的新的TCP协议，对原有TCP协议改动较小，具有较好RTT公平性和较好的TCP友好性，在真实网络中易于实现，但是TCPW仍存在一些性能缺陷。由于TCPW窗口增长仍采用线性增加模式，因此不能像其他协议一样快速获得更大的发送窗口，而且在该算法的慢启动阶段仍然采用指数增长模式，从而导致大量突发数据的产生，造成拥塞。中间节点控制由路由器拥塞控制算法来实现，主动式队列管理机制

3、（AQM）是IEFT推荐的基于路由器拥塞控制关键技术，它和TCP端到端的拥塞控制相结合，是解决目前网络拥塞控制问题的一个主要手段。RED算法是AQM的一个典型，但其在算法稳定性和参数敏感性方面存在缺陷。本文基于以上两个算法，开展了以下三个方面的工作。首先对TCPW算法进行改进，主要集中在以下两点：一是在慢启动阶段发送窗口较原有算法能较快的到达10个包左右，之后窗口增长速度较原有算法有所减慢，这样有利于短流传输和避免突发数据产生，从而减缓拥塞；二是在拥塞避免阶段采用基于当前拥塞窗口大小的先快后慢的非线性增长方式，使之更适合于高速环境。通过建立新算法的数学模型分析其稳定性、RTT公平性和对TCP友

4、好性，在此基础上分别对以上两点改进采用NS2仿真方法加以验证，发现算法较原有算法在高速环境下有更好的吞吐量和更有利于短流数据传输。另外本文在分析RED算法基础上，提出了一种新的改进型AQM算法DRED算法。DRED相对RED算法，能够动态调整参数，并且采用非线性函数代替原有的丢包率计算方法。通过动态调整来调整向源端发送拥塞通知的速率，维持队列的稳定；通过新丢包率计算方式，提高缓冲的利用率和使队列长度尽量稳定于期望值附近。最后通过仿真来验证新算法更适应网络流量的变化，保持队列长度的稳定和丢包率的稳定，从而提高了网络链路利用率。关键词：高速网； 拥塞控制； TCPW； RED 50Abstract

5、AbstractWith the development of the applications on high-speed network, research on congestion control becomes more and more important. Congestion control should include two parts: end-to-end control and link control. End-to-end control could adjust the data sending rate dynamically in order to resp

6、ond to link congestion. On the other hand, the link control can predicate and monitor the degree of congestion effectively, then send the warning to sender before congestion happening by explicit or implicit method. Now more and more scientists begin on the researches of the TCP congestion control m

7、echanisms for high-speed networks and this research has become a focal subject. There are some typical protocols:, such as STCP, H-TCP,TCPW etc. These new protocols enhance the performance on the high-speed networks through adjusting the increases and decreases mode of window, TCPW algorithm is a be

8、tter one, it is based on BWE (Bandwidth Estimation) and has little changes on TCP protocol. it also provides a sensible fairness increment with respect to TCP Reno, Moreover, TCPW is friendly to Reno. But there are still some shortages in it, Congestion window of TCPW is based on additive increase o

9、f linear mode. So, in high-speed networks it cant obtain high throughput rapidly. During the slow-start stage, the congestion window of TCPW is based on exponential growth mode, then this will cause the datagram increases too fast and prompt the probability of congestion. Link control is implemented

10、 by router. The active queue management mechanism(AQM) is, which the IETF recommends, the essential technology based on the router congestion control, combining with the TCP end-to-end congestion control, it provide an effective method to solve the congestion control question on Internet. RED algori

11、thm is typical algorithm in AQM, but it exist some drawbacks, for example, the instability and the parameter sensitivity. In this paper, we give the researches on the following three aspects based on the above algorithm: TCPW and RED. At first, we improve the performance of the TCPW from two points.

12、 One enhances the former method by reducing the increasing speed of the datagram and increasing the increasing speed before the window is 10 during the slow-start stage. This decreases the occurring rate of congestion and improves the performance of short-term linkages transmission. On the other han

13、d, we use a simple nonlinear mode to increase the congestion widow instead of the linear mode. This new mathematical model and the new algorithm is friendly to Reno and have fairness increment with respect to TCP Reno. Through the simulation on NS-2 platform, the experiments show that the new algori

14、thm can obtain more throughput than TCPW in high-speed network and improve the short-term linkages transmission. Secondly, the other work an improved algorithm DRED of active queue management (AQM), is proposed. Based on the interpolations size, DRED can adjust dynamically the size Pmax, and therefo

15、re adjust the sending rate of congestion notification to the source end in time. The new algorithm uses the nonlinear mode to adjust the probability of drop, and maintain the stability of queue length of mathematical expectation. At last, the simulations on NS-2 show that DRED can adapt the change o

16、f network flow validly, hold the stability of queue length and also decrease the probability of drop. So it is superior to the RED algorithm in maintaining the stability of queue length and enhancing the utilization ration of the links.Key words: high-speed networks; congestion control; TCPW; RED目录目

17、录摘 要IAbstractII第一章 绪 论11.1 研究背景11.2 研究现状31.3 主要研究工作51.4 论文的内容及安排6第二章 拥塞控制算法综述82.1 拥塞产生的原因82.2 拥塞控制算法分类102.2.1 拥塞控制源端算法102.2.2 源端拥塞控制的研究现状112.2.3 拥塞控制链路算法142.2.4 链路拥塞控制研究现状152.3 拥塞控制算法的评价标准182.3.1 稳定性分析182.3.2 公平性分析192.3.3 友好性分析202.4 小结20第三章 TCP Westwood拥塞控制算法改进213.1 引言213.2 TCPW算法的分析223.2.1 TCPW算法的简

18、介223.2.2 TCPW算法优点233.2.3 TCPW算法存在的不足233.3 改进的拥塞控制算法NLTCPW243.3.1 拥塞避免阶段改进253.3.2 慢启动阶段改进253.3.3 NLTCPW算法的数学模型263.3.4 仿真环境下NLTCPW算法的吞吐量性能分析293.3.5 NLTCPW算法RTT公平性实验323.3.6 NLTCPW算法短流数据传输性能分析323.4 小结34第四章 RED算法改进354.1 一种新的自适应RED算法DRED算法354.1.1 RED算法概述354.1.2 RED算法的优点364.1.3 RED算法存在的不足364.1.4 DRED算法384.

19、2 DRED算法性能分析404.3 小结45第五章 结论及未来的工作465.1结论465.2 未来的工作47致 谢48攻读硕士学位期间从事的主要科研工作及发表的论文49参考文献50第一章 绪论第一章 绪 论1.1 研究背景近年来随着信息技术迅速发展，以互联网为代表的信息网络已经逐渐渗透到当今社会的各个领域，成为了国家进步和社会发展的重要支柱，以及知识经济的基础载体和支撑环境，它的重要性就如同铁路和高速公路的蓬勃发展给工业社会带来了广泛而深远的影响一样，必将成为21世纪全球最重要的基础设施之一。就目前的现状和未来的发展而言，下一代互联网的骨干带宽必将呈现指数型增长。下一代互联网建设与发展的各种趋

20、势表明：大规模的高速网络试验环境已经形成，未来几年内，互联网骨干将全面升级到支持近10Gbps的高速链路，而且很有可能持续增长。但是，虽然下一代互联网的骨干带宽呈现指数性的增长，实践中上述海量数据传输业务的用户却并没有切身感受到网络带宽剧增所带来的好处，于是人们开始怀疑高速网络中传输协议的性能。这是由于TCP/IP协议在高速网络中确实存在效率问题1。因此研究适应于高速网络的拥塞控制算法成了网络研究的新热点。目前，Internet上用户和应用的数量都在迅速增长，当多个用户对网络的需求总量大于网络实际传输能力时，必然会导致网络拥塞的发生。虽然拥塞源于资源短缺，但增加资源并不能避免拥塞的发生，有时甚

21、至会加重拥塞程度2。所以选择和引进更多、更合理的拥塞控制机制对网络的高效稳定运行是至关重要的。随着应用需求的丰富和技术的发展，研究者开始认识到想完全依赖实现在终端系统上的策略与算法很难满足越来越多的复杂应用需求。于是，人们把注意力转向网络中的路由器等中间节点设备，期望通过增强它们的功能来实现主机端无法达到的目标网。就拥塞控制而言，网络中间节点有可能更及时，甚至可以提前准确了解网络的拥塞状态，并依此实施有效的资源管理策略，使网络能有效地避免拥塞，或尽早从严重的拥塞状态中恢复过来。当然，对路由器功能的扩展要受继承性和延续性的限制，否则将影响技术的实用性。事实上，现有的路由器扩展功能，主要包括调度和

22、队列/缓存管理。调度(Scheduling)直接管理下次发哪个分组和分配各个流的带宽。而队列/缓存算法管理路由器缓冲区中分组队列的长度，即在必要或适当的时候丢掉一些分组。因此根据拥塞控制算法实现的位置不同主要分为两大类：源端控制和链路控制，源算法在主机和网络边缘设备中的执行作用主要是根据获得的反馈信息调整发送速率。链路算法在网络设备(如路由器和交换机)中执行，作用是检测网络拥塞的发生，产生拥塞反馈信息。源算法和链路算法形成反馈，共同实现拥塞控制，两者形成的反馈系统共同形成了拥塞控制系统，所以必须在这两方面同时进行研究和综合。在实际部署中要考虑效率和费用比的问题同时又要要求源端控制和链路控制必须

23、相互独立，一个对原有系统改动过大的拥塞控制算法不利于部署。比如XCP3(eXplicit Control Protocol)，是美国麻省理工和伯克利针对高带宽时延乘积网络提出的一个Internet拥塞控制的新体系结构，它是将端节点和路由器相结合完成拥塞控制的执行模式。XCP协议其路由器算法主要由有效控制算法（EC）和公平性控制算法（FC）构成。EC仅考虑链路的总流量，而不考虑单条流的流量及公平性问题。FC实现目标是将EC计算出来的总的反馈量在包层次上公平地分配给每条流。FC以包为单位来分配EC计算出的总的反馈量。在端节点数据包结构中增加了cwnd、RTT估计和feedback三个域。发送端发送

24、数据包时使用feedback域请求希望得到的拥塞窗口调整的变化量，数据包途经的路由器根据当时网络可用带宽的状况修改feedback域的值。当数据包到达接收端时，feedback域保留的是该数据包途径的各路由器允许发送端可以增加的带宽的最小值或要求发送端需要减少的带宽的最大值，然后接收端通过ACK包将feedback域的值反馈给发送端，最终发送端按照反馈调整随后的发送速率。但是XCP的关键算法全部在路由器内实现，在实际网络中要建造如此强大功能的路由器的造价是十分昂贵的；同时若端节点或中间路由节点其中一个不支持此协议，算法将失效；因此XCP在实际网络中难以实现和部署。拥塞控制算法的分布性、网络的复

25、杂性和对拥塞控制算法性能要求等使拥塞控制算法的设计具有很高的难度Error! Reference source not found.，其主要表现如下：1) 算法的分布性拥塞控制算法的实现分布在多个网络节点中，必须使用不完整的信息完成控制，并使各节点协调工作，还必须考虑某些节点工作不正常的情况。2) 网络环境的复杂性Internet中各处的网络性能有很大的差异，算法必须具有很好的适应性。另外，由于Internet对报文的正确传输不提供保证，算法必须处理报文丢失、乱序到达等情况。3) 算法的性能要求。拥塞控制算法对性能有很高的要求，包括算法的公平性、效率、稳定性和收敛性等。某些性能目标之间存在矛盾

26、，在算法设计时需要进行权衡。4) 算法的开销 拥塞控制算法必须尽量减少附加的网络流量，特别是在拥塞发生时。在使用反馈式的控制机制时，这个要求增加了算法设计的困难。算法还必须尽量降低在网络节点（特别是网关）上的计算复杂性。1.2 研究现状目前对网络拥塞控制的研究主要从以下两个方面进行：首先是解决源端的算法，通过依靠动态的调节源端数据发送速率，及时能响应路径中的拥塞；另一方面是解决链路算法，通过对中间节点的有效管理机制能，不断地预测并监测路径中的拥塞程度，通过显式或隐式的方法在拥塞发生前及时警告源端，在拥塞发生之后抑制源端的发送速率以超出中间节点转发速率的速度发送报文分组。传统的源端TCP拥塞控制

27、算法使得当前的Internet网络获得了巨大的成功，但是近几年来人们越来越清楚的认识到传统的TCP拥塞控制机制主要采用了慢启动机制和AIMD（和式增加积式减少）的拥塞避免机制，它在高速长距离网络中的性能已达到瓶颈4。文献4分析了传统TCP在高速长距离网络中不能达到高吞吐量的主要的原因表现在如下几个方面：1) 现存的拥塞控制机制对拥塞反应性比较差TCP在高速长距离网络中对包丢失的敏感程度远远高于局域网或者普通的广域网，这主要归因于它的拥塞避免算法中基于AIMD（和式增加积式减少）的窗口增加减少原则。在它的拥塞避免算法中每一个往返时延（RTT）至多增加一个数据包的小尺寸来增加拥塞窗口（和式增加），

28、而单个包丢失在高速长距离网络中的影响是非常普遍的的，当一个TCP连接一旦被探测到有数据包丢失时，立刻要将它的拥塞窗口减少一半（积式减少），这需要花去几百毫秒甚至几秒才能重新恢复到原来的窗口大小，这种缓慢的窗口恢复速度会直接导致吞吐率不高，无法充分利用带宽。相反窗口减小又显得过于激烈，造成了网络流量的巨大震荡，同时也会降低网络的吞吐量。而另一方面慢启动也会造成TCP在网络中的性能下降，但相对而言这方面的影响比拥塞避免阶段要小很多，这是因为在TCP连接中往往是通过收到三个重复ACK而不是超时来检测丢包，所以TCP连接在拥塞避免阶段比慢启动阶段要花费更多的时间。2) 对数据包丢失的解释不同数据包在传

29、输过程中可能会由于缓冲区溢出或者传输介质的出错而引起包丢失或者包损坏的情况，传统TCP假定链路错误造成的损失是可以忽略不计的，但是在高速网络中，当数据传输的速率较高时，链路错误是不能被忽略的，由数据链路错误引起的丢包和由网络拥塞引起的丢包的可能性是相同的，所以在高速网络中不能笼统的认为只要是分组丢失就一定由网络拥塞引起的。3) 拥塞窗口和丢包率之间存在固定的函数关系在TCP的拥塞控制算法中窗口大小w与丢包率p之间的约束关系为5，由此可见，在这种固定的关系约束下，要保持大的拥塞窗口需要极小的丢包率，即使丢包率能达到这个要求，对于发送端来说，这也是一个极为不精确的反馈；所以在最后TCP的拥塞控制算

30、法不得不引入丢包来估计带宽，但是随着带宽时延乘积的增加，在实际网络中该平衡状态难以实现，从而使网络带宽不能得到有效的利用。4) 拥塞避免阶段传统TCP在连续收到三个重复ACK，才开始重传并且减少慢启动阀值和拥塞窗口。但在拥塞严重的情况下，第二个或第三个重复ACK包很可能不会到达源端。这一方面增加了网络重传丢失数据包的时间，另一方面会造成不必要的重传，而转入不必要的慢启动阶段。从而降低了系统吞吐量、增加了延时、影响了系统的性能。这些对于高速网络来说都是非常不利的。5) 过长的恢复周期每个TCP连接发生丢包后窗口减半，然后再恢复到原来的窗口大小需要花去很长时间。就单个TCP连接而言，它的调整周期和

31、连接回路的往返时间及拥塞窗口值大小有关，即调整周期等于拥塞窗口大小的二分之一乘以一个窗口数据传输的往返时间。特别是在高带宽网络中，传统TCP在一次丢包后要经过几个甚至几十个RTT才能恢复到原来的窗口大小。要达到100%完全利用链路的理想状态那更是不可能实现的。从以上分析可以看出，造成TCP拥塞控制算法在高速网络中性能不好的主要原因是其拥塞控制机制不适应于高速网络，目前已经有一些学者提出了多种解决方案，主要分为四类：1)基于丢失的算法;2)基于延迟的算法;3)基于丢失和延迟相混合的算法;4)基于显示拥塞指示的算法。传统TCP是典型的基于丢失的算法；FAST TCP5将延迟作为拥塞指示的算法,Af

32、rica TCP6用队列延迟和包丢失作为网络的拥塞指示。在正常的工作环境下，拥塞窗口经过一个RTT被更新且依赖于平均RTT的估计。TCP Africa算法就是一个基于丢失和延迟的“双模式”算法。XCP3属于最后一类，它需要通过从网络环境中获取的指示信号来推断网络是否发生拥塞，这种算法的配置需要和路由器同时进行操作。基于路由器的拥塞控制（即链路控制算法）主要是通过对其队列进行管理来实现的，目前的队列管理主要还是被动式队列管理(Passive Queue Management，PQM)。本质上PQM并没有参与到网络拥塞管理中去，只是在队列溢出的情况下被动地丢包。若路由器上使用主动式队列管(Acti

33、ve Queue Management，AQM)机制来控制在什么时候丢多少包，将有效地管理队列长度，以支持端到端的拥塞控制。其基本思想是通过监控路由器输出端口队列的平均长度来探测拥塞。一旦发现拥塞逼近，就随机地选择时机对源端进行通知拥塞，使它们在队列溢出导致丢包之前降低发送数据速率，从而缓解网络拥塞。主要的AQM算法有RED8、ARED9、FRED10 、BLUE11 、WRED12、PI13、AVQ14和 REM 15。其中RED、ARED和FRED属于一类，都是随机早期检测算法。PI是基于控制理论提出一种算法，PI控制算法可以有效消除“稳态误差”，但同时也会减慢系统的反应速度，而且PI控制

34、器只能很好的工作在一定得分范围的环境中，这使PI难以在真实的网络环境中使用；REM是基于优化理论提出的。AQM算法的共同特点是，计算出丢包率后反馈给源端系统，源端系统可以采取的动作包括“丢弃”（Dropping）和“标记”（Marking）。“丢弃”是现有系统都支持的一种操作，而“标记”的方法，可经“显示”的通知源端系统拥塞的发生，比较而言“标记”方法性能更好。随着“显示拥塞通知”(ECN)的标准化和广泛采用，将有越来越多的网关支持“标记”的策略。从实际的应用来看，路由器厂商纷纷在自己的产品中支持RED算法，如Ciseo7500等系列路由器，Juniper的M40、M80等；在Differv的

35、业务框架下，由RED演化出来的RIO(RED with IN/OUT)成为提供确保服务(Assured Services)的基本算法。由于RED算法的有效性目前己被广泛使用在网络队列管理中来提高系统的综合性能。随着高速网络的发展，拥塞控制算法的研究由于其巨大的复杂性，已不满足于以往的基于主观方法提出解决方案再进行模拟分析拥塞控制算法性能的思路，而必须建立起其理论上的框架，用控制理论和优化理论等现代分析方法来研究网络的动力学模型和特性，揭示Internet网络形成拥塞现象的物理机制，分析各种算法以及算法的组合的性能，发展更有效的拥塞控制算法，以满足人们对网络快速增长的需求。总的来说，高速网络拥塞

36、控制的研究从最初单纯解决TCP的低效问题，到围绕公平性、稳定性以及收敛性等方面开展了一系列更深入的研究，但是到目前为此，在该研究领域仍然存在很多开放性问题，其中作者认为最为突出的一点是目前的多数研究没有充分强调模型分析的重要性，缺乏具有总结性结论和定律的归纳与描述。同时在拥塞控制机制和算法的设计上过分依赖于基于经验的启发式设计结合典型、有限和局部仿真试验验证的设计方法，得到的算法往往是静态的和准静态的，不能适应快速变化的动态网络化环境。高速网络环境下拥塞控制算法的优化设计还存在很大的研究空间。1.3 主要研究工作随着Internet的发展，它的传输拥塞控制机制必须保持有效性。技术的趋势表明越来

37、越多的高带宽链路将应用到互联网络中，高速网络拥塞控制协议的设计分类两类:修改TCP协议、终端与路由器联合的协议。针对高速网络的特点基于TCP协议采用不同的机制进行改进而来的新协议包括前面提到的FAST TCP在内的诸如：High-Speed TCP16 、Scalable TCP17、BIC18、CUBIC19和H-TCP20。这些协议设计的主要目的是在高速网络下能快速的获得高的稳定的吞吐量，从而提高高速网络链路的利用率。本文首先分析TCPW21算法在高速网环境下，慢启动和拥塞避免阶段存在问题提出一种改进NLTCPW算法。NLTCPW将TCPW在高带宽时延积网络中窗口增加采用线性方式改为一种非

38、线性增长方式，使之窗口增加先快后慢，窗口维持在一个较大的水平，从而获得更好的带宽利用率；慢启动阶段窗口开始阶段较快的增加到10（包），超过10（包）后减缓增长速度，这样可以提高WEB流的传输，降低网络丢包率，降低网络突发数据量；建立NLTCPW的数学模型，从理论上对NLTCPW的稳定性，RTT公平性、TCP友好性进行分析，利用仿真工具在网络吞吐量、WEB流数据传输、丢包率等方面对NLTCPW和TCPW进行了比较分析，结果表明NLTCPW相对TCPW在保持原有算法优点情况下提高网络吞吐量和其在传输短流数据方面效率。由于RED算法是IEFT推荐在路由器上的算法，所以研究RED算法实用性更好且易于部

39、署,RED算法存在的一个主要问题就是其参数是静态配置的，而互联网是基于带宽统计复用的，一条链路上往往有很多活跃流，并且流量变化很大，RED算法不能适应这种变化导致其在很多情况下性能会大大下降。我们的研究目的就是对RED算法的参数配置进行改进，使其能够根据流量的变化来自动配置参数，从而保证性能的稳定。另一方面修改RED的丢包率计算策略，由原来的线性计算变为非线性，这样有利于缓冲队列资源的有效使用和队列长度的稳定。1.4 论文的内容及安排第一章绪论介绍网络拥塞控制的研究概况及研究背景，最后对本文的研究内容进行了概述。第二章网络网络拥塞控制机制对网络拥塞的原因，网络拥塞的现象及拥塞控制的基本机制进行

40、了阐述，对TCP拥塞控制源算法、链路算法及算法的评价标准逐一进行了讨论。第三章从理论分析和模拟实验证实了TCP WestWood算法在链路利用率、稳定性、RTT公平性、TCP友好性和收敛性等方面的性能，针对TCP WestWood 算法在拥塞避免阶段窗口任然采用传统线性增长方式的缺点，提出了采用非线性增长方式NLTCP WestWood 算法，并且优化其慢启动，并对该算法进行了详细的仿真实验。第四章在分析RED算法的基础上，构建一种改进的DRED算法,并且验证其队列长度和丢包率更为稳定。第五章是结论部分，在总结本文的研究工作基础上指出本文研究存在的一些问题，给出进一步的研究方向。重庆邮电大学硕

41、士论文第二章 拥塞控制算法综述第二章 拥塞控制算法综述当网络中存在过多的数据包时，网络的性能就会下降，这种现象称为拥塞。在网络发生拥塞时，会导致吞吐量下降，严重时会发生“拥塞崩溃”(congestion collapse)现象22。一般来说，拥塞崩溃发生在网络负载的增加导致网络效率的降低的时候。目前对互联网进行的拥塞控制主要是依靠在源端执行的基于窗口的TCP拥塞控制机制和依靠路由执行的链路控制机制。图2-1 显示了负载与吞吐量的关系23，当负载较小时，吞吐量与负载之间呈现线性关系，到达膝点(Knee)之后，随负载的增加，吞吐量的增量逐渐变小。当负载越过崖点(Cliff)24之后，吞吐量却急剧下

42、降，此时网络陷入了严重拥塞状态，若不及时进行控制，则有可能导致网络崩溃。拥塞控制的目的就是使吞吐量尽量保持在膝点与崖点之间，使网络的负载始终保持在一个相应的区间之间。通常将Knee点附近定义成为拥塞避免区，Knee和Cliff之间是拥塞恢复区，而Cliff之外是拥塞崩溃区间。图2-1 网络性能与负载之间关系2.1 拥塞产生的原因拥塞的发生和的互联网的设计机制有着密切关系，这种机制包括：1) 数据包交换(packets witched)网络与电路交换(circuit switched)网络相比，由于包交换网络对资源的利用是基于统计复用(statistical multiplexing)的，因此提

43、高了资源的利用效率。但在基于统计复用的情况下，很难保证用的服务质量(quality of service，QoS)，并且很容易出现数据包“乱序”的现象，对乱序数据包的处理会大大增加拥塞控制的复杂性。2) 无连接(connectionless)网络互联网的节点之间在发送数据之前不需要建立连接，从而简化了网络的设计，网络的中间节点上无需保留和连接有关的状态信息。但无连接模型很难引入接纳控制(admission control)，在用户需求大于网络资源时难以保证服务质量:此外，由于对数据发送源的追踪能力很差，给网络安全带来了隐患;无连接也是网络中出现乱序数据包的主要原因。3) “尽力而为”的服务模型

44、不对网络中传输的数据提供服务质量保证。在这种服务模型下，所有的业务流被“一视同仁”的公平地竞争网络资源，路由器对所有的数据包都采用先来先处理(First Come First Service，FCFS)的工作方式，它尽最大努力将数据包包送达日的地。但对数据包传递的可靠性、延迟等不能提供任何保证。这很适合Email、Ftp、WWW等业务。但随着互联网的飞速发展，IP业务也得到了快速增长和多样化。特别是随着多媒体业务的兴起，计算机已经不是单纯的处理数据的工具。这对互联网也就相应地提出了更高的要求。对那些有带宽、延迟、延迟抖动等特殊要求的应用来说，现有的“尽力而为”服务显然是不够的。导致拥塞发生的原

45、因在于网络能够提供的资源不足以满足用户的需求，这些资源包括缓存空间、链路带宽容量和中间节点的处理能力等25。由于互联网的设计机制导致其缺乏“接纳控制”能力，因此在网络资源不足时不能限制用户数量，而只能靠降低服务质量来继续为用户服务，也就是“尽力而为”的服务。主要有三方面原因：1) 路由器缓存不足当多条线路上有多个数据包到达时，而且这些数据包都需要相同的输出线路，路由器则建立一个队列。如果路由器没有足够的缓存来存放这些到达的数据包，那么数据包就会被丢弃。但是盲目增加缓存空间不仅不能缓解拥塞，甚至加重26。2) 带宽容量不足低速链路对高速数据流的输入也会产生拥塞。所有信源发送的速率必须小于或等于信

46、道容量。所以在网络低速链路处就会形成带宽瓶颈，当其满足不了通过它的所有源端带宽的要求时，网络就会发生拥塞。3) 处理器能力弱处理器的处理能力弱，难以完成必要的维护工作（缓冲区排队、更新路由表等），处理速度跟不上高速链路，也会产生拥塞。单纯地增加网络资源之所以不能解决拥塞问题，是因为拥塞本身是一个动态问题，它不可能只靠静态的方案来解决，而需要协议能够在网络出现拥塞时保护网络的正常运行。2.2 拥塞控制算法分类根据算法的实现位置，可以将拥塞控制算法分为三大类:源算法(source Algorithm)、链路算法(Link Algorithm)和两者结合的算法。源算法在主机和网络边缘设备中执行作用是

47、根据获得的反馈信息调整发送速率。链路算法在网络设备(如路由器和交换机)中执行，作用是检测网络拥塞的发生，产生拥塞反馈信息。源算法和链路算法形成反馈共同实现拥塞控制。2.2.1 拥塞控制源端算法源端算法中使用最广泛的是TCP协议中的拥塞控制算法。1988年V.Jacobson在文献27中指出了TCP在控制网络拥塞方面的不足，并提出了“慢启动（slow start）”算法和“拥塞避免（congestion avoidance）”算法。1990年出现了TCP Reno版本增加了“快速重传”（fast retransmit）算法、“快速恢复”（fast recovery）算法，避免了网络拥塞不够严重时采用“慢速启动”算法而造成过大地减少发送窗口尺寸的现象，这样TCP的拥塞控制就有慢启动、拥塞避免、快速重传和快速恢复三个阶段组成，这就是目前Internet上大多数机器运行的TCP拥塞控制机制，即TCP Reno算法。1) 慢启动：这个状态窗口的初始值是一个数据包大小（缺省为512）一个数据包被发送，当发送端收到来自接收端的ACK响应，窗口增