网络拥塞控制算法研究综述

姚丽君　孔金生

摘要：在本文中，作者着重阐述了TCP拥塞控制和IP拥塞控制中的典型算法以及目前一些较有影响的拥塞控制算法，分析了当前拥塞控制算法设计过程中存在的不足，并给出了一个有意义的研究方向。

关键词：TCP拥塞控制IP拥塞控制控制理论

0引言

近二十年来，计算机网络经历了飞速的发展，使得信息的交流变得方便和快捷，然而由于网络数据流量的激增，拥塞问题随之而产生，且变得越来越严重，己经成为制约网络发展和应用的一个瓶颈，如何更好的预防和控制拥塞是近年来网络研究的热点问题之一。产生网络拥塞的根本原因在于用户(或叫端系统)提供给网络的负载大于网络资源容量和处理能力，表现为数据包延时增加、丢弃概率增大、上层应用系统性能下降。

1TCP拥塞控制

据统计，Internet上的95％的数据流使用的是TCP协议，因此TCP拥塞控制一直是网络拥塞控制研究的重点。

1.1TCP Tahoe Tahoe是TCP的早期版本，它包括了最基本的TCP拥塞控制算法，由“慢启动”、“拥塞避免”和“快速重传”三部分组成。“快速重传”根据3个重复的确认分组来判断分组丢失的出现，从而减少等待“重传时钟”超时的过程，提高了分组的传输效率。除此之外，Tahoe对往返时间的计算也作了相应的改进，以便更准确地设定超时重传的时间。

1.2TCP Reno Reno在Tahoe的基础上增加了“快速恢复”算法来提高拥塞恢复的效率。当发送端收到一定数量的重复ACK之后，即进入“快速恢复”阶段。源端在接收到足够多的重复的ACK之后，用接着到来的重复ACK触发新数据分组的发送。只有在接收到新发分组的ACK后，源端才退出“快速恢复”阶段。Reno的“快速恢复”优化了单个分组从数据窗口。

1.3TCP New-Reno New-Reno对Reno算法作了一些小改进，以消除有多个分组从同一数据窗口丢失时对重传定时器的等待。改进考虑到发送端在“快速恢复”阶段收到的“恢复ACK”是确认部分而不是全部出现在“快速恢复”阶段的分组。New-Reno直到所有在“快速恢复”阶段开始时出现的分组都被确认，才会退出“快速恢复”。

1.4TCP SACK Sack算法也是对Reno的改进，当检测到拥塞后，不用重传数据包丢失到检测到丢失时发送的全部数据包，而是对这些数据包进行有选择的确认和重传，从而避免不必要的重传，减少时延，提高网络吞吐量。由于使用选择重传，所以在一个窗口中数据包多包丢失的情况下，Sack性能优于New-Reno。但是Sack的主要缺点是要修改接收端TCP。

1.5TCP Vegas Vegas对Reno进行了三项改进：首先采用新的重传触发机制，即只要收到一个重复的ACK就断定超时，以便及时检测到拥塞；而在慢启动阶段则采用了更加谨慎的方式来增加拥塞窗口cwnd，以减少不必要的分组丢失：改进“拥塞避免”阶段的窗口调整算法，通过观察以前的TCP连接中RTT值改变情况来控制cwnd，当RTT变大时就认为发生拥塞，开始减小cwnd，如果RTT变小，就增加cwnd，解除拥塞，理想情况下cwnd就会稳定在一个合适的值上。这样使拥塞机制的触发不再依靠包的具体传输时延，而只与RTT的改变有关。

2IP拥塞控制

在互联网这样的复杂系统中，不能指望所有用户在其应用中兼容端到端的TCP拥塞控制机制，网络也需要参与资源的控制工作。因此，需要采用路由器的拥塞控制方法，即IP拥塞控制。

2.1先进先出(First ln first Out，FIFO)FIFO是一种最简单的调度算法，又被称为“先到先服务”，即第一个到达路由器的数据包首先被传输，接着到达的数据分组在路由器中排队，等待输出，如果包到达时缓存己满，那么路由器就不得不丢弃该包。这种方法的优点是实施简单，但没有考虑被丢弃包的重要程度。由于FIFO总是丢弃到达队尾的包，所以又称为“去尾”(drop tail)算法。但“去尾”和FIFO是两个不同的概念。FIFO是一种包调度策略，决定包传送的顺序；“去尾”是一种丢弃策略，决定哪些包被丢弃。

2.2随机早期检测(Random Early Detection，RED)RED解决的问题主要包括：①早期探测路由器可能发生的拥塞，并通过随机丢弃或标记分组来通知源端采取措施避免可能发生的拥塞：②公平地处理包括突发性、持久性和间隙性的各种TCP业务流；③避免多个TCP连接由于队列溢出而造成同步进入“慢启动”状态；④维持较小的队列长度，在高吞吐量和低时延之间做出合理平衡。

2.3显式拥塞指示算法(ExpIicit Congestion Notification，ECN)在ECN算法中，路由器采用RED算法管理缓冲区，当平均队列长度处于两个阈值之间时，路由器按照一定概率给报文设置CE使能位，而不是简单地丢弃该报文。当下端路由器发生拥塞时，首先选择有CE使能位的报文丢弃。ECN优势在于不需要重传超时，有效地提高网络带宽的使用效率。

2.4公平排队算法(Fair queuing，FQ)FQ算法是一种“轮询”调度算法。在FQ算法中，路由器对每个输出线路有一个排队队列，路由器按“轮询”方式处理包。当一条线路闲时，路由器就来回扫描所有队列，依次将每队第一个包发出。当某个流的数据包到达过快时，其队列就会很快占满，属于这个流的新到的包就会被丢弃。采用这种方式，每个数据流就不可能牺牲其它数据流而多占资源。

2.5加权公平排队算(Weighted Fair queuing，WFQ)WFQ是FQ的改进算法。对每个流(排队)分配一个权值。这个权值决定了路由器每次发往该队列的比特数量，从而控制数据流得到的带宽。WFQ中权值可以由路由器自己决定，也可以由源端通过某种信令通知路由器来决定。总之，WFQ根据不同数据流应用的不同带宽要求，对每个排队队列采用加权方法分配缓存资源，从而增加了FQ对不同应用的适应性。

3TCP与IP拥塞控制比较

显然TCP基于窗口的端到端拥塞控制，本质上是一种基于信源的控制策略。它有明显的不足：①在感知到拥塞到采取控制行动之间存在着显著的时延；②信源可能不按照网络的指令操作；③某些策略中反馈需要在网络中增加额外的分组。基于IP的拥塞控制策略实施在网络层，不必依赖信源来均匀地分配资源，所以不存在以上那些问题。基于IP的拥塞控制策略是公平的，基于IP控制的主要问题在于增加共享资源(主要是路由器)的复杂性。事实上，很多策略的复杂性是与共享路由器的信源数成正比的，当网络的链路速率增加时信源数量也随之增加。

4总结

从以上的TCP和IP拥塞控制中典型算法的分析介绍中不难看出，这些算法虽然在以往算法的基础上进行了改进，系统性能有所改善，但其自身几乎都存在着这样或那样的问题。其直接原因就是这些算法的设计都是针对局部的某一具体问题进行，依靠直觉的推断，根据经验改进算法，缺乏一套有效的系统的理论分析工具对算法的设计进行指导。控制理论作为一门相当成熟的系统理论，有相当多的方法可以借鉴到拥塞控制中来。近来，国内外的很多专家学者都认识到了可以应用控制理论的方法来解决Internet中的拥塞控制问题，并进行了一些尝试工作。然而，由于Internet本身是一个复杂的巨系统，而且其中的各种不同控制策略之间也会互相影响，使得对网络稳定性和动态性能的分析更加困难，因而这方面的研究还不成熟，所以，如何有效的将控制理论的思想运用于日趋复杂的Internet中，来指导目前单纯根据经验来改进算法的不足，将是一个未来研究的热点问题，也是一个难点问题。