摘要：随着网络规模的不断扩展，网络上的用户和应用都在快速地增长，拥塞已经成为网络研究的一个十分重要的问题。为了适应实时数据流在网络中的高效传输，研究者提出了多种拥塞控制和队列管理算法，并不断改进。通过比较几种算法的优缺点来说明拥塞控制算法的发展与改进，并分析了和提出了进一步的研究方向。
关键词：拥塞；拥塞控制；主动队列管理
中图分类号：TP393文献标识码：A文章编号：1009-3044(2008)27-1935-02
Research on Network Congestion Control Mechanisms
ZHANG Hua
(Department of Information Management,Hunan Finance & Economic, Changsha 410205, China)
Abstract: With the evolvement of the Internet, the number of users and applications using Internet increases very quickly. Congestion has become the key of current network research. For high rate real-time data flow transmission in the network，Several kinds of congestion control and queue management algorithms are proposed and enhanced continually. Advantage and disadvantage comparison among several kinds of algorithms gives a description of development and enhancement of congestion control algorithms, and further research problems in this area are also discussed.
Key words: congestion; congestion control; active queue management
1 引言
随着Internet的飞速发展，各种多媒体应用不断涌现，用户数量迅速增加，使得因特网的流量也随之急剧增加，由此而引发的网络拥塞已经成为制约网络发展和应用的瓶颈问题。在Internet设计的初期，对于拥塞的控制是通过TCP协议中端到端基于滑动窗口的流量控制完成的。但随着应用需求的丰富和技术的发展，研究者认识到要想完全依赖实现在终端系统上的策略与算法是很难满足QoS这样复杂的应用需求的。于是，人们开始将部分研究转向路由器等中间节点设备，期望通过增强它们的功能来实现主机端无法达到的技术目标。
2 网络拥塞的定义及产生的原因
2.1 拥塞和拥塞控制
拥塞是一种持续过载的网络状态，此时用户对网络资源（包括链路带宽、存储空间和中间节点的处理能力等）的需求超过了其固有的容量。
图1刻画了负载与吞吐量之间的关系：当负载较小时，吞吐量与负载之间呈线性关系，到达膝点（knee）之后，随着负载的增加，吞吐量的增量逐渐变小；当负载越过崖点（cliff）之后，吞吐量却急剧下降。通常将knee点附近称为拥塞避免区间，knee和cliff之间是拥塞恢复区间，而cliff之外是拥塞崩溃区间。
为了最大限度地利用资源，网络工作在轻度拥塞状态时应该是较为理想的，但这也增加了滑向拥塞崩溃的可能性，因此需要一定的拥塞控制机制[1]来加以约束和限制。可以从两个方面考虑如何解决拥塞问题：一是增加网络资源；二是降低用户需求。前者一般是通过动态配置网络资源来提高网络系统容量。降低用户需求主要表现在三个方面：拒绝服务、降低服务质量和调度。
2.2 拥塞产生的原因
拥塞发生的主要原因在于网络能够提供的资源不足以满足用户的需求。由于互联网的设计机制导致其缺乏“接纳控制”能力，因此在网络资源不足时不能限制用户数量，而只能靠降低服务质量来继续为用户服务，也就是“尽力而为”的服务。
拥塞虽然是由于网络资源的稀缺引起的，但单纯增加资源并不能避免拥塞的发生。例如增加缓存空间到一定程度时，只会加重拥塞，而不是减轻拥塞，这是因为当数据包经过长时间排队完成转发时，它们很可能早己超时，从而引起源端超时重发，而这些数据包还会继续
传输到下一路由器，从而浪费网络资源，加重网络拥塞。
3 拥塞控制策略机制及算法改进
3.1 基于源端的拥塞控制策略
基于源端的拥塞控制策略中，使用最为广泛的是TCP协议中的拥塞控制策略，TCP协议是目前网络中使用最为广泛的传输协议。根据MCI的统计，网络上总字节数的95%及总数据包数的90%使用TCP协议传输。
1998年，Van Jacobson等人提出了“慢启动”、“拥塞避免”算法，随后于1990年在TCP Reno版本增加了“快速重传”、“快速恢复”算法。下面着重介绍慢启动、拥塞避免、快速重传和快速恢复四个核心算法[2]。
1） 慢启动
端系统不能预测网络资源的使用情况，如果在建立新的连接时向网络中发送大量的数据包，容易导致耗尽路由器的资源，使网络吞吐量急剧下降，为了避免新建立的连接产生的突发通信量超过网络的承载能力，TCP使用了慢启动算法来逐渐探测网络的可用带宽。
慢启动算法为每个连接设置两个参数：拥塞窗口（cwnd）和慢启动阀值（ssthresh）。当建立新的TCP连接时，cwnd被初始化为一个数据包大小（一个数据包缺省值为512或536bytes），实际发送窗口win取拥塞窗口和通告窗口中的较小值，即win=min（cwnd，awnd），源端按win大小发送数据，每收到一个ACK确认，cwnd就增加一个数据包发送量，结果cwnd随往返时间呈指数增长：1个、2个、4个、8个…，因此，源端向网络中发送的数据量将急剧增加。直到拥塞窗口达到慢启动阀值，就进入拥塞避免阶段。
2） 拥塞避免
在拥塞避免阶段，源端每收到一个ACK确认，cwnd增加1/cwnd个数据包，即每个tRTT内增长一个数据包大小，所以在拥塞避免算法中cwnd的增长是线性的。
拥塞避免有两种进入方式：① 当源端收到三次相同的重复ACK。此时表明网络发生拥塞，慢启动阀值ssthresh被设置为当前cwnd的一半；② 当拥塞窗口达到慢启动阀值，即cwnd=ssthresh。源端超时重传定时器超时，源端每收到ACK确认时，定时器被复位，发送端通过重传定时器超时而检测出网络拥塞，此时，慢启动阀值置为当前cwnd的一半，再将cwnd置为1，传输进入慢启动阶段。
3） 快速重传
如果一个TCP连接由于拥塞而被丢弃了一个数据包，接收端对每个收到的错序的数据包发送相应的重复确认，直到丢失的数据包收到为止。源端在接收到重复ACK时并不能确定是由于分组丢失还是分组乱序造成的，如果假定是分组乱序，在目的端处理之前源端只可能收到一个或两个重复ACK；如果收到三个或更多的重复ACK，表明网络已经发生拥塞。源端不等到重传定时器超时就重发这个可能丢失的分组，这就是快速重传。
4） 快速恢复
当快速重传算法重传了可能丢失的分组之后，如果TCP重新进入慢启动阶段，将会使拥塞窗口cwnd减为1，重新开始探测网络带宽，从而严重影响网络吞吐量，因此快速恢复算法在快速重传之后转去执行拥塞避免算法，避免了过大地减小发送窗口而导致的网络性能下降。
针对TCP拥塞控制算法的改进研究有很多。有对慢启动算法的改进，比如quick start、 smooth start，还有ECN机制。此外，在一些特殊的环境中，TCP的拥塞控制算法需要改进和优化。如在无线链路、卫星链路和“非对称”链路（asymmetric link）上的拥塞控制算法需要增加特殊的考虑。
3.2 基于路由器的拥塞控制策略
现有的路由器扩展功能，主要包括调度和队列/缓存管理，并没有与Internet将流状态信息保存在主机端的早期设计理念相冲突。调度（scheduling）直接管理输出链路的带宽资源，而队列/缓存管理通过控制缓存与队列的占用间接影响带宽的分配。
3.2.1 队列调度策略
队列调度算法性能的评价指标主要包括队列延时、公平性、复杂性等。下面列出了一些主要的多队列调度策略。
1） 归一化共享处理（Generalized Processor Sharing，GPS）[3]将到达的分组数据列于不同的队列，在一定的时间间隔，每一个非空的队列都有机会接受至少一次服务。如果为队列赋予一定的权值，接受的服务与权值成比例，那么GPS可以实现最大一最小比例公平性。GPS仅仅是一种理论模型，最简洁的实现是轮循队列。
2） 轮循（Round Robin，RR）策略是对多个队列进行调度。传统的轮循策略对不同队列进行无区别的循环调度服务，由于分组长度是可变的，因此，如果不同队列具有不同的分组长度，则分组长度大的队列会比分组长度小的队列占用更多的输出带宽，使队列之间产生不公平现象，而且，这种策略不能提供时延保证。为弥补其在变长度分组环境下的不公平性及改善时延特性，提出了加权轮循、差额轮循等算法。
3） FQ（Fair Queueing）是一种轮循的调度算法。为解决变长分组存在的不公平性，同时考虑到按比特（Bit）单位轮循的复杂性，FQ采用了一种近似的方法：首先计算一个数据包按轮循方式发送时完成的时间，再按这个完成的时间对数据包进行排序。FQ的带宽分配独立于数据包大小，各业务的队列几乎是同时开始的。FQ的缺点是实现复杂，因为它需要对每数据流的排队处理、每流状态统计、数据包的分类以及数据包调度的额外开销等。
4） 加权公平队列（Weighted Fair Queueing，WFQ）是FQ的一种改进。WFQ是一种基本的QoS保障机制，当分组较小时，WFQ调度的网络中，端到端时延存在确定的上界。为解决FQ和WFQ的计算复杂问题，提出了W2FQ（Worst Case WFQ）、自同步公平队列（Self-clocked Fair Queue）等改进算法。
5） 在区分服务网络中，通常将网络中的路由节点分为边界节点和核心节点，核心节点不需要维护所有数据流的状态信息，可以降低调度的复杂性，这方面的代表有CSFQ（Core Stateless Fair Queueing），RFQ（Rainbow Fair Queueing），QLFQ（Queue Length based Fair Queueing）等算法，它们在可扩展性和鲁棒性等方面表现不错。
网络中间节点上的调度功能对于保障拥塞控制机制的公平性具有重要的作用。随着应用需求的增强，为保证网络的公平性，调度在拥塞控制中的作用将逐渐得到重视，基于队列调度的策略将会是加强网络拥塞控制的一个有效途径。
3.2.2 队列管理策略
队列管理通常是指用特定的分组丢弃策略来维护队列长度的大小，实现网络的控制。队列管理策略是主要的基于路由器端的拥塞控制策略。根据路由器对队列长度维护的参与性，可以将队列管理策略分为“丢尾”算法和AQM。
1） “去尾”算法（Drop Tail）
在目前的TCP/IP网络中，当网络负载增大时，路由器缓冲区会由于突发的大量数据而溢出。传统的路由器在发生拥塞时只是简单的丢弃队列尾部的数据包，TCP通过检测到包的丢失来触发拥塞控制算法以降低拥塞程度。这种算法简单、自观，易于实现，但它存在两个重要的缺点：① 公平性问题；② 经常保持满队列状态。
2） 主动队列管理策略（Active Queue Management，AQM）
AQM策略通过主动队列管理策略来维持一个稳定的队列目标长度，从而达到减小排队时延的同时保证较高的吞吐量的目的。具体来说，AQM[4]主要解决以下四个方面的问题：① 早期探测路由器可能发生的拥塞，并通过随机丢弃或标记分组来通知源端减小发送速率，以避免可能发生的拥塞；② 公平地处理包括突发性、持久性和间隙性的各种TCP业务；③ 避免多个TCP连接的全局同步；④ 维持稳定的队列长度，在低时延和高吞吐量之间做出合理的平衡。由此可见，AQM的主要优点包括：减少路由器的分组丢失，使用AQM可以保持较小的队列长度，从而增强路由器容纳突发流量的能力；减小分组通过路由器的延迟，减小平均队列长度可以有效地减小分组在路由器中的排队延迟；避免死锁（lock-out）的发生。针对主动队列管理算法的研究成为拥塞控制研究的热点，许多新的AQM算法被不断地提了出来。
3.2.3 拥塞控制策略进一步的研究方向
由于网络本身是一个复杂的系统，在设计网络拥塞控制机制方面还有大量课题有待解决，下一步研究的方向有：1）建立精确的网络机制模型。有必要在网络的流量控制及其排队分析的基础上更进一步地进行研究，得到更准确的模型，从而更好地对主动队列进行管理；2）实现AQM高级策略，引入新的智能控制算法如遗传算法与模糊逻辑的综合应用；3）在多种源端拥塞控制策略和路由器拥塞避免策略并存时,如何分析整个网络的稳定性，如何分析各种不确定因素（如路由器或通信线路故障）对稳定性的影响等，也是需要认真解决的问题。
4 结束语
该文对近年来网络拥塞控制的主要研究进行分析并给出了新的展望，通过对各种拥塞控制算法的研究分析，我们知道不可能有一种算法的设计与实现在所有的环境中都是最好的，只能是对网络性能某些方面的折衷。对于网络这样一个复杂系统的分析与控制,只有通过综合通信、控制和数学等多学科的共同努力,才有望获取更具实际意义的成果。
参考文献：
[1] Peterson L L, Davie B S. Computer Networks: a System Approach[M].Morgan Kaufmann Publishers,2000.
[2] Stevens W. TCP Slow Start,Congestion Avoidance,Fast Retransmit,and Fast Recovery Algorithms[S].RFC2001,1997.
[3] Parekh A, Gallager R. A generalized processor sharing approach to flow control-The single node case[J].ACM/IEEE Trans on Networking,1993,1(3):344-357.
[4] Braden B.IETF RFC 2309.Recommendations on queue management and congestion avoidance in the Internet[S],1998.