摘  要  随着网络技术的发展，网络拥塞日益严重，如何解决拥塞，充分、高效地利用网络资源，成为当今急需解决的问题。由于Internet上大多数业务都采用TCP协议，因此TCP的拥塞控制机制对控制网络拥塞具有特别重要的意义。本文分析了TCP的四个交互式拥塞控制算法：慢启动、拥塞避免、快速重传和快速恢复，介绍了TCP基于窗口的拥塞控制策略和目前常用端到端拥塞控制算法，并对它们的性能进行仿真比较。

    关键字  AIMD；拥塞控制；TCP；NS 

1  引言

    在Internet上，随着信息传送量的逐渐增大和网络组成的日益复杂，网络发生拥塞的可能性越来越大。网络中的拥塞来源于网络资源和网络流量分布的不均衡性，它不会随着网络处理能力的提高而消除。目前为止拥塞问题还没有得到很好的解决，因此网络拥塞的避免和控制成为越来越重要和急待解决的问题。    Internet中拥塞控制的大部分工作是由TCP完成的，目前标准的TCP协议实现都包含了一些避免和控制网络拥塞的算法。当今Internet的可靠性和稳定性与TCP拥塞控制机制密不可分，而TCP的成功也要归功于其稳固的拥塞控制机制。拥塞控制是确保Internet鲁棒性(robustness)的关键因素，因此成为当前网络研究的一个热点问题。

2  TCP基于窗口的拥塞控制策略

2.1  加法增加乘法减少(AIMD)窗口算法

    TCP是Internet中最流行的端到端传输协议，为主机之间提供可靠按序的传输服务。在现有的TCP/IP协议体系下，TCP拥塞控制机制主要基于加法增加乘法减少(AIMD)算法。在该算法中主要用到三个窗口变量：    (1)拥塞窗口(cwnd)：限定源端在拥塞控制中在一定时间内允许传送的最大数据量，是来自源端的流量控制。    (2)通告窗口(awnd)：连接建立及传输过程中，接收端向源端通告的最大可接收速率，是来自接收端的流量控制。    (3)有效窗口(win)：源端数据发送的实际窗口大小，限定为win＝min(cwnd，awnd)。由于计算机计算能力和存储能力的提高，通告窗口一般都比较大，因此当前发送窗口的大小大多数情况下等于拥塞窗口的大小。    AIMD的具体工作过程为：    (1)源端每收到一个ACK，拥塞窗口按下式增加：    Incr＝MSS×(MSS/cwnd)   (MSS为分组大小)    cwnd＝cwnd＋Incr    也就是，如果每个发出的分组都在最近的RTT(往返时延)时间内获得确认，源端就将cwnd增加1，即加法增加。    (2)当发生超时，TCP将超时看作拥塞的标志，并减小发送速率。每发生一次超时，源端重新计算拥塞窗口值：    cwnd＝cwnd/2    也就是，一次超时，拥塞窗口值减为当前值的一半，即乘法减少。

2.2  TCP拥塞控制的四个阶段

2.2.1  启动阶段    当连接刚建立或超时时，进入慢启动阶段。    当新建TCP连接时，拥塞窗口(cwnd)被初始化为一个数据包大小。源端按cwnd大小发送数据，每收到一个ACK确认，就增加一个数据包发送量，这样慢启动阶段cwnd随RTT呈指数级增长。    慢启动采用逐渐增大cwnd的方法，可以防止TCP在启动一个连接时向网络发送过多的数据包而造成不必要的数据丢失和网络拥塞，并且它还能够避免采用单纯的AIMD算法造成的吞吐量增加过慢的问题。    为了防止cwnd的无限制增长引起网络拥塞，引入一个状态变量：慢启动阈值ssthresh。    当cwnd<ssthresh时，使用上述的慢启动算法，cwnd随RTT呈指数增长。    当cwnd>ssthresh时，使用拥塞避免算法，减缓cwnd的增长速度。2.2.2  拥塞避免阶段    当TCP源端发现超时或收到3个相同的ACK确认帧时，即认为网络将发生拥塞，此时进入拥塞避免阶段。    在拥塞避免阶段，慢启动域值ssthresh将被设置为当前cwnd的一半，当发生超时时，cwnd被置为初始值1。此时，如果cwnd<ssthresh，TCP重新进入慢启动过程；如果cwnd> =ssthresh，则执行拥塞避免算法，即cwnd在每次收到一个ACK确认时只增加1/cwnd个数据包。拥塞避免阶段cwnd随RTT呈线性增长。2.2.3  快速重传和快速恢复阶段    在拥塞避免阶段，当数据包超时时，cwnd被置为1，重新进入慢启动阶段，这会导致过大地减小发送窗口尺寸，降低TCP连接的吞吐量。因此，引入了快速重传和快速恢复机制。    在快速重传阶段，当源端收到3个或3个以上重复的ACK时，就判定数据包丢失，同时将ssthresh设置为当前cwnd的一半，并重传丢失的包，进入快速恢复阶段。    在快速恢复阶段，每收到重复的ACK，则cwnd加1；收到非重复ACK时，置cwnd＝ssthresh，转入拥塞避免阶段；如果发生超时重传，则置ssthresh为当前cwnd的一半，cwnd＝1，重新进入慢启动阶段。    这种方法避免了数据包超时后就重新进入慢启动阶段，提高了TCP连接的吞吐量。

3  典型TCP拥塞控制算法分析

3.1  TCP Tahoe算法

    Tahoe算法是TCP的早期版本。它的核心思想是：让cwnd以指数增长方式迅速逼进可用信道容量，然后慢慢接近均衡。Tahoe包括3个基本的拥塞控制算法：“慢启动”、“拥塞避免”和“快速重传”。    (1)慢启动：避免了连接建立时突发数据流对网络的冲击。    初始设置cwnd为1，并按指数型方式增长，直至cwnd超过ssthresh。    当cwnd>=ssthresh时，Tahoe进入拥塞避免阶段。    (2)拥塞避免：限制传输过程中无限制的速率增长，避免由此可能导致的拥塞。    cwnd以线性方式增长。    如果发生超时或者连续收到3个重复ACK，Tahoe认为发生了拥塞。    对于超时，置ssthresh为当前拥塞窗口的一半，cwnd=1，转入慢启动。    如果收到3个连续ACK，则Tahoe进入快速重传阶段。    (3)快速重传：根据3个重复的应答报文来判断丢包，减少了超时重传的发生，加快了源端对拥塞的响应，使得拥塞能快速消除。立即重传丢失的分组，同时置ssthresh为当前拥塞窗口的一半，cwnd=1，转入慢启动。    Tahoe算法存在着不足之处：在收到3个重复ACK或在超时的情况下，Tahoe置cwnd为1，然后进入慢启动阶段。这一方面会引起网络的激烈振荡，另一方面大大降低了网络的利用率。

3.2  TCP Reno

    针对Tahoe算法的不足之处，1990年Jacobson在Tahoe的基础上提出了改进算法Reno。改进主要有两个方面：一是对于收到连续3个重复ACK，算法不经过慢启动，而直接进入拥塞避免阶段；二是增加了快速重传/快速恢复机制。具体实现过程为：    (1)收到三个重复的ACK，进入快速重传/快速恢复，此时ssthresh设置为当前拥塞窗口的一半。    (2)重传丢失的数据包，并置cwnd＝cwnd＋ndup(ndup为收到的重复ACK数)。    (3)发送新的数据包。    (4)当收到非重复的ACK时，cwnd＝ssthresh。    (5)进入拥塞避免阶段。    从上面的过程可以看出，Reno在收到3个重复ACK后，就转入快速重传/快速恢复阶段；而遇到超时时，Reno和Tahoe一样进入慢启动阶段。    Reno目前被广泛采用，以其算法的简单、有效和鲁棒性成为TCP源算法的主流。但是如果在一个发送窗口内有多个包丢失时，该算法不能有效恢复出来，为此提出了一些改进，如NewReno、Sack等。

　　[8]电大学习网.免费论文网[EB/OL]. /d/file/p/2024/0424/fontbr /> 

3.3  TCP NewReno

    NewReno对Reno中“快速恢复”算法进行了补充，它考虑了一个发送窗口内多个报文同时丢失的情况。在Reno算法中，发送方收到一个不重复的应答后就退出“快速恢复”状态。而在NewReno中，只有当所有报文都被应答后才退出“快速恢复”状态。    具体执行过程是：在快速恢复期间，TCP发送端收到一个ACK后，发送端通过此ACK应答推断出下一个丢失的数据包序列号，并且立即重传那个数据包。这样，NewReno在每个RTT内重传一个丢失的数据包，直到发生多个数据包丢失的窗口中所有丢失数据包被重传，而不是等到超时。在这个期间如果还有其它重复的ACK到来，则继续快速恢复算法，直到在快速恢复初始时所有未确认数据包都被确认。    NewReno的实现只要修改TCP发送端的实现代码，实现简单。

3.4  SACK(selective acknowledgement，选择性应答)

    SACK也关注一个窗口内有多个报文的丢失，它使用“选择性重传”策略，提高TCP在拥塞较严重且一个窗口中有多个分组丢失时的性能。SACK的基本思想是：接收方TCP发送SACK分组来通知发送方接收数据的情况，这样源端就能准确的知道哪些数据包被正确的传到接收端，从而避免不必要的重传，减少时延，提高网络吞吐量。    SACK算法是对Reno算法的改进。它的改进之处在于：在快速恢复阶段，SACK保持一个变量pipe来表示出现在路由器上报文的估计数量。当pipe小于拥塞窗口大小时，源端只发送一个新报文分组或重发一个老报文，pipe加1；当发送端接收到一个带SACK选项的重复ACK时，表明新数据已被接收端接收，pipe减1；此外，对收到的“恢复ACK”使用特殊的处理方法，对pipe变量值减2。SACK算法降低了不必要的重传，能有效的从多个数据包丢失中恢复。但是它的实现需要修改TCP发送端和接收端的实现代码，增加了TCP的复杂性，不易大规模的应用。

3.5  Vegas算法

    Vegas算法是一个得到普遍认可，但是未能获得广泛应用的算法。Vegas与上述介绍的算法不同，它以RTT的变化作为拥塞信号，调节源端的发送速率。如果发现RTT变大，Vegas就认为网络发生拥塞，开始减小cwnd；如果RTT变小，Vegas则解除拥塞，再次增加cwnd。这样，在理想情况下，cwnd值会稳定在一个合适的范围内。Vegas的重传策略与上述算法也不同，它是在收到一个重复ACK后，比较数据包发出的时间和当前时间，然后决定是否重发。这样能更及时地重传丢失的数据包，提高响应速度。    该算法采用RTT的改变来判断网络的可用带宽，能较好的预测网络带宽的使用情况，其公平性、效率都较好。但是，由于Vegas与其它算法在竞争带宽方面存在不公平现象，因此未能在Internet上普遍采用，还需不断改进。

4  算法性能比较

    在上述介绍的几种拥塞控制算法中，Tahoe在快速重传后转向慢启动算法，这样不能有效地利用网络带宽并且还引入较大的时延；Reno在Tahoe的基础上提出了快速恢复算法，对于单个数据包的丢失在传输性能上有显著的提高，但是它不能有效的处理多个包丢失的情况；于是提出了改进算法NewReno和SACK，两种改进措施都大大提高了TCP的传输性能；Vegas在理论上是可行的，但是在实际应用中存在着局限性，因而未能得到广泛应用。TCP的拥塞控制算法还在不断的改进。图1  拥塞控制算法仿真实验

 

    图1是在NS仿真平台下，对各拥塞控制算法进行的仿真实验，通过追踪数据得到的各时刻的cwnd变化情况。

5  总结

    端到端的拥塞控制是网络拥塞控制的基本前提，只有将端到端的拥塞控制工作做好，才能为网络中的整体拥塞控制措施打下良好的基础。随着Internet的迅速扩展，网络中的数据流负载处理会快速加重，如果端节点与网络拥塞控制关系能够很好的配合，网络负载将会大大减轻，有利于传输性能和资源利用。如何建立有限的协调机制，有待于进一步研究。    现有的TCP拥塞控制算法都存在一些局限性，因此，对网络拥塞控制的进一步研究具有极其重要的理论和应用价值。

参考文献

[1] 冯波，基于NS的TCP/IP拥塞控制算法研究，燕山大学硕士学位论文，2003.9[2] 徐恪，吴建平，徐明伟 高等计算机网络—体系结构、协议机制、算法设计与路由器技术，机械工业出版社，2003.9，Page299－322[3] 章淼，吴建平，林闯 互联网端到端拥塞控制研究综述，软件学报，2002.13，Page354－363[4] Sally Floyd，A Report on Some Recent Developments in TCP Congestion Control，IEEE Communications Magazine，April 2001，Page1－7[5] Sally Floyd，Senior Member，IEEE，and Kevin Fall，Promoting the Use of End-to-End Congestion Control in the Internet，IEEE/ACM TRANSACTIONS ON NETWORKING，August 1999，Page458－472

　　[8]电大学习网.免费论文网[EB/OL]. /d/file/p/2024/0424/fontbr /> 

相关文章：

无线通信系统通道校准算法研究04-26

用于英文字母识别的三种人工神经网络的设计04-26

浅论计算机虚拟实验室的建设04-26

计算机辅助夹具设计系统的研究与开发04-26

一种可信计算机系统的设计与实现04-26

计算机教学游戏的基本结构与特征综述04-26

计算机液位过程控制综合实验系统研制与开发04-26

IBM高性能计算机系统一次重大故障分析04-26

基于C/S和B/S结构的多数据源电能质量数字化管理平04-26

计算机辅助绘图的工作过程实训04-26