一、拥塞控制的一般原理

在计算机网络中的链路容量(即带宽)、交换节点中的缓存和处理机等都是网络的资源。在某段时间，若对网络中某一资源的需求超过了该资源所能提供的可用部分，网络的性能就要变坏。这种情况就叫作拥塞(congestion)。可以把出现网络拥塞的条件写成如下的关系式：

若网络中有许多资源同时呈现供应不足，网络的性能就要明显变坏，整个网络的吞吐量将随输入负荷的增大而下降。

网络拥塞往往是由很多因素引起的。例如，当某个节点缓存的容量太小时，到达该节点的分组因无存储空间暂存而不得不被丢弃。现在设想将该节点缓存的容量扩展到非常大，于是凡到达该节点的分组均可在节点的缓存队列中排队，不受任何限制。由于输出链路的容量和处理机的处理速度并未提高，因此在这队列中的绝大多数分组的排队等待时间将会大大增加，结果上层软件只好把它们进行重传(因为早就超时了)。由此可见，简单地扩大缓存的存储空间同样会造成网络资源的严重浪费，因而解决不了网络拥塞的问题。

又如，处理机处理的速率太低可能引起网络的拥塞。简单地将处理机的速率提高，可能会使上述情况缓解一些，但往往又会将瓶颈转移到其他地方。问题的实质往往是整个系统的各个部分不匹配。只有所有的部分都平衡了，问题才会得到解决。

拥塞常常趋于恶化。如果一个路由器没有足够的缓存空间，它就会丢弃一些新到的分组。但当分组被丢弃时，发送这一分组的源点就会重传这一分组，甚至可能还要重传多次。这样会引起更多的分组流入网络和被网络中的路由器丢弃。可见拥塞引起的重传并不会缓解网络的拥塞，反而会加剧网络的拥塞。

拥塞控制与流量控制的关系密切，它们之间也存在着一些差别。所谓拥塞控制就是防止过多的数据注入到网络中，这样可以使网络中的路由器或链路不至于过载。拥塞控制所要做的都有一个前提，就是网络能够承受现有的网络负荷。拥塞控制是一个全局性的过程，涉及所有的主机、所有的路由器，以及与降低网络传输性能有关的所有因素。但TCP连接的端点只要迟迟不能收到对方的确认信息，就猜想在当前网络中的某处很可能发生了拥塞，但这时却无法知道拥塞到底发生在网络的何处，也无法知道发生拥塞的具体原因。

相反，流量控制往往是指点对点通信量的控制，是个端到端的问题(接收端控制发送端)。流量控制所要做的就是抑制发送端发送数据的速率，以便接收端来得及接收。

二、举例

可以用一个简单例子说明这种区别。设某个光纤网络的链路传输速率为1000Gbit/s，有一台巨型计算机向一台个人电脑以1Gbits的速率传送文件。显然，网络本身的带宽是足够大的，因而不存在产生拥塞的问题。但流量控制却是必需的，因为巨型计算机必须经常停下来，以便个人电脑来得及接收。

但如果有另一个网络，其链路传输速率为1Mbit/s，而有1000台大型计算机连接在这个网络上。假定其中的 500台计算机分别向其余的500台计算机以100kbits 的速率发送文件。那么现在的问题已不是接收端的大型计算机是否来得及接收，而是整个网络的输入负载是否超过网络所能承受的。

拥塞控制和流量控制之所以常常被弄混，是因为某些拥塞控制算法是向发送端发送控制报文，并告诉发送端，网络已出现麻烦，必须放慢发送速率。这点又和流量控制是很相似的。

流量控制和拥塞控制的区别可以用下图的简单比喻来说明。图中表示一水龙头通过管道向一个水桶放水。图(a)表示水桶太小，来不及接收注入水桶的水。这时只好请求管水龙头的人把水龙头拧小些，以减缓放水的速率。这就相当于流量控制。图(b)表示虽然水桶足够大，但管道中有很狭窄的地方，使得管道不通畅，水流被堵塞。这种情况被反馈到管水龙头的人，请求把水龙头拧小些，以减缓放水的速率，为的是减缓水管的堵塞状态。这就相当于拥塞控制。请注意，同样是把水龙头拧小些，但目的是很不一样的。

进行拥塞控制需要付出代价。这首先需要获得网络内部流量分布的信息。在实施拥塞控制时，还需要在节点之间交换信息和各种命令，以便选择控制的策略和实施控制。这样就产生了额外开销。拥塞控制有时需要将一些资源(如缓存、带宽等)分配给个别用户(或一些类别的用户)单独使用，这样就使得网络资源不能更好地实现共享。十分明显，在设计拥塞控制策略时，必须全面衡量得失。

三、理解

在下图中的横坐标是提供的负载(ofered load)，代表单位时间内输入给网络的分组数目。因此提供的负载也称为输入负载或网络负载。纵坐标是吞吐量(throughput)，代表单位时间内从网络输出的分组数目。具有理想拥塞控制的网络，在吞吐量饱和之前，网络吞吐量应等于提供的负载，故吞吐量曲线是 45°的斜线。但当提供的负载超过某一限度时，由于网络资源受限，吞吐量不再增长而保持为水平线，即吞吐量达到饱和。这就表明提供的负载中有一部分损失掉了(例如，输入到网络的某些分组被某个节点丢弃了)。虽然如此，在这种理想的拥塞控制作用下，网络的吞吐量仍然维持在其所能达到的最大值。

但是，实际网络的情况就很不相同了。从上图可看出，随着提供的负载的增大，网络吞吐量的增长速率逐渐减小。也就是说，在网络吞吐量还未达到饱和时，就已经有一部分的输入分组被丢弃了。当网络的吞吐量明显地小于理想的吞吐量时，网络就进入了轻度拥塞的状态。更值得注意的是，当提供的负载达到某一数值时，网络的吞吐量反而随提供的负载的增大而下降，这时网络就进入了拥塞状态。当提供的负载继续增大到某一数值时，网络的吞吐量就下降到零，网络已无法工作，这就是所谓的死锁(deadlock)。

从原理上讲，寻找拥塞控制的方案无非是寻找使不等式不再成立的条件。这或者是增大网络的某些可用资源(如业务繁忙时增加一些链路，增大链路的带宽，或使额外的通信量从另外的通路分流)，或减少一些用户对某些资源的需求(如拒绝接受新的建立连接的请求，或要求用户减轻其负荷，这属于降低服务质量)。但正如上面所讲过的，在采用某种措施时，还必须考虑到该措施所带来的其他影响。

实践证明，拥塞控制是很难设计的，因为它是一个动态的(而不是静态的)问题。当前网络正朝着高速化的方向发展，这很容易出现缓存不够大而导致分组的丢失。但分组的丢失是网络发生拥寒的征兆而不是原因。在许多情况下，甚至正是拥塞控制机制本身成为引起网络性能恶化甚至发生死锁的原因。这点应特别引起重视。

由于计算机网络是一个很复杂的系统，因此可以从控制理论的角度来看拥塞控制这个问题。这样，从大的方面看，可以分为开环控制和闭环控制两种方法。开环控制就是在设计网络时事先将发生拥塞的有关因素考虑周到，力求网络在工作时不产生拥塞。但一旦整个系统运行起来，就不再中途进行改正了。

闭环控制是基于反馈环路的概念，主要有以下几种措施:

• 监测网络系统以便检测到拥塞在何时、何处发生。
• 把拥塞发生的信息传送到可采取行动的地方。
• 调整网络系统的运行以解决出现的问题。

有很多的方法可用来监测网络的拥塞。主要的一些指标是:由于缺少缓存空间而被丢弃的分组的百分数、平均队列长度、超时重传的分组数、平均分组时延、分组时延的标准差，等等。上述这些指标的上升都标志着拥塞发生的可能性增加。

一般在监测到拥塞发生时，要将拥塞发生的信息传送到产生分组的源站。当然，通知拥塞发生的分组同样会使网络更加拥塞。

另一种方法是在路由器转发的分组中保留一个比特或字段，用该比特或字段的值表示网络没有拥塞或产生了拥寨。也可以由一些主机或路由器周期性地发出探测分组，以询问拥寒是否发生。

此外，过于频繁地采取行动以缓和网络的拥塞，会使系统产生不稳定的振荡。但过于迟缓地采取行动又不具有任何实用价值。因此，要采用某种折中的方法，但选择正确的时间常数是相当困难的。

下面就来介绍更加具体的防止网络拥塞的方法。

四、TCP 的拥塞控制方法

TCP 进行拥塞控制的算法有四种，即慢开始(slow-start)、拥塞避免(congestion avoidance)、快重传(fast retransmit)和快恢复(fast recovery)(见草案标准 RFC 5681)。下面就介绍这些算法的原理。为了集中精力讨论拥塞控制，我们假定：

• 数据是单方向传送的，对方只传送确认报文。
• 接收方总是有足够大的缓存空间，因而发送窗口的大小由网络的拥塞程度来决定。

1、慢开始和拥塞避免

下面讨论的拥塞控制也叫作基于窗口的拥塞控制。为此，发送方维持一个叫作拥塞窗口cwnd (congestion window)的状态变量。拥塞窗口的大小取决于网络的拥塞程度，并且是动态变化着的。发送方让自己的发送窗口等于拥塞窗口。根据假定，对方的接收窗口足够大
发送方在发送数据时，只需考虑发送方的拥塞窗口。

发送方控制拥塞窗口的原则是:只要网络没有出现拥塞，拥塞窗口就可以再增大一些以便把更多的分组发送出去，这样就可以提高网络的利用率。但只要网络出现拥塞或有可能出现拥塞，就必须把拥塞窗口减小一些，以减少注入到网络中的分组数，以便缓解网络出现的拥塞。

发送方又如何知道网络发生了拥塞呢?我们知道，当网络发生拥塞时，路由器就要把来不及处理而排不上队的分组丢弃。因此只要发送方没有按时收到对方的确认报文，也就是说，只要出现了超时，就可以估计可能在网络某处出现了拥塞。现在通信线路的传输质量一般都很好，因传输出差错而丢弃分组的概率是很小的(远小于1%)。因此，发送方在超时重传计时器启动时，就判断网络出现了拥塞。

下面将讨论拥塞窗口 cwnd 的大小是怎样变化的。我们从“慢开始算法”讲起。

慢开始算法的思路是这样的:当主机在已建立的TCP连接上开始发送数据时，并不清楚网络当前的负荷情况。如果立即把大量数据字节注入到网络，那么就有可能引起网络发生拥寨。经验证明，较好的方法是先探测一下，即由小到大逐渐增大注入到网络中的数据字节也就是说，由小到大逐渐增大拥塞窗口数值。

旧的规定是这样的:在刚刚开始发送报文段时，先把初始拥塞窗口cwnd设置为1至2个发送方的最大报文段SMSS(Sender Maximum Segment Size)的数值，但新的 RFC 5681(草案标准)把初始拥塞窗口cwnd设置为不超过2至4个SMSS的数值。

具体的规定如下：

• 若SMSS>2190字节，则设置初始拥塞窗口cwnd=2xSMSS字节，且不得超过2个报文段
• 若(SMSS>1095字节)且(SMSS2190字节)：则设置初始拥塞窗口cwnd=3xSMSS字节，且不得超过3个报文段。
• 若SMSS ≤1095 字节，则设置初始拥塞窗口cwnd=4xSMSS字节，且不得超过4个报文段

慢开始规定，在每收到一个对新的报文段的确认后，可以把拥塞窗口增加最多一个SMSS的数值。更具体些，就是：

其中N是原先未被确认的、但现在被刚收到的确认报文段所确认的字节数。不难看出当N<SMSS时，拥塞窗口每次的增加量要小于SMSS。

用这样的方法逐步增大发送方的拥塞窗口cwnd，可以使分组注入到网络的速率更加合理。

下面用例子说明慢开始算法的原理。请注意，虽然实际上TCP用字节数作为窗口大小的单位。但为叙述方便起见，我们用报文段的个数作为窗口大小的单位，这样可以使用较小的数字来阐明拥塞控制的原理。

在一开始发送方先设置cwnd=1，发送第一个报文段，接收方收到后就发送确认。慢开始算法规定，发送方每收到一个对新报文段的确认(对重传的确认不算在内)，就把发送方的拥塞窗口加 1。因此，经过一个往返时延 RTT 后，发送方就增大拥塞窗口，使cwnd=2即发送方现在可连续发送两个报文段。接收方收到这两个报文段后，先后发回两个确认。现在发送方收到两个确认，根据慢开始算法，拥塞窗口就应当加2，使拥塞窗口从cwnd=2增加到 cwnd=4，即可连续发送4个报文段。发送方收到这4个确认后，就可以把拥塞窗口再加4，使cwd=8(如下图所示)。显然，发送方并不是要在所有的确认都收齐了之后才调整其拥塞窗口，而是收到一个确认就调整一下拥塞窗口，抓紧时间发送报文段。但这样的细节不是我们现在所要研究的，我们想知道的只是拥塞窗口的大致增长趋势。

由此可见，慢开始的“慢”并不是指cwnd 的增长速率慢，而是指在 TCP开始发送报文段时，只发送一个报文段，即设置cwnd=1，目的是试探一下网络的拥塞情况，然后视情况再逐渐增大 cwnd。这当然比一开始设置大的cwnd 值，一下子把许多报文段迅速注入到网络要“慢得多”。这对防止出现网络拥塞是一个非常好的方法。

为了防止拥塞窗口 cwnd 增长过大引起网络拥塞，还需要设置一个慢开始门限 ssthresh状态变量(可以把门限 ssthresh 的数值设置大些，例如达到发送窗口的最大容许值)。慢开始门限 ssthresh的用法如下:

• 当 cwnd<ssthresh 时，使用上述的慢开始算法。
• 当cwnd>ssthresh 时，停止使用慢开始算法而改用拥塞避免算法。
• 当cwnd=ssthresh 时，既可使用慢开始算法，也可使用拥塞避免算法。

拥塞避免算法的目的是让拥塞窗口cwnd 缓慢地增大(具体算法见[RFC56811)。执行算法后的结果大约是这样的:每经过一个往返时间RTT，发送方的拥塞窗口cwnd 的大小就加1，而不是像慢开始阶段那样加倍增长。因此在拥塞避免阶段就称为“加法增大”AI(Additive Increase)，表明在拥塞避免阶段，拥塞窗口 cwnd 按线性规律缓慢增长，比慢开始算法的拥塞窗口增长速率缓慢得多。

可以用曲线来说明 TCP 的拥塞窗口 cwnd 是怎样随时间变化的(如下图所示)。但这里请特别注意横坐标采用的单位是往返时延RTT。在实际的互联网中，TCP发送的每一个报文段的往返时延 RTT 都是不一样的(不会像下图中所画出的那样很理想的情况)。但在这里我们是讲解拥塞控制的原理，因此应当把图中的RTT理解为一个大致的时间，在这样的时间之内，发送方发出了一批报文段，并且都收到了接收方的确认。下图中的数字1至5是特别要注意的几个点。现假定TCP的发送窗口等于拥塞窗口。

当 TCP连接已建立后，把拥塞窗口cwnd 置为1。在本例中，慢开始门限的初始值设置为16个报文段，即ssthresh=16。在执行慢开始算法阶段，每经过一个往返时间 RTT，拥塞窗口 cwnd 就加倍。当拥塞窗口 cwnd 增长到慢开始门限值 ssthresh 时(图中的点1，此时拥塞窗口cwnd=16)，就改为执行拥塞避免算法，拥塞窗口按线性规律增长。但请注意“拥塞避免”并非完全避免拥塞，而是让拥塞窗口增长得缓慢些，使网络不容易出现拥塞。

当拥塞窗口 cwnd = 24时，网络出现了超时(图中的点2)，这就是网络发生拥塞的标志于是调整门限值 ssthresh=cwnd/2=12，同时设置拥塞窗口cwnd=1，执行慢开始算法。

按照慢开始算法，发送方每收到一个对新报文段的确认 ACK，就把拥塞窗口值加1。当拥塞窗口cwnd=ssthresh=12时(图中的点3，这是 ssthresh第1次调整后的数值)，改为执行拥塞避免算法，拥塞窗口按线性规律增大。

当拥塞窗口cwnd=16时(图中的点4)，出现了一个新的情况，就是发送方一连收到 3个对同一个报文段的重复确认(图中记为3-ACK)。关于这个问题要解释如下。

有时，个别报文段会在网络中意外丢失，但实际上网络并未发生拥塞。如果发送方迟迟收不到确认，就会产生超时，并误认为网络发生了拥塞。这就导致发送方错误地启动慢开始，把拥塞窗口 cwnd 又设置为1，因而不必要地降低了传输效率。

采用快重传算法可以让发送方尽早知道发生了个别报文段的丢失。快重传算法首先要求接收方不要等待自己发送数据时才进行捎带确认，而是要立即发送确认，即使收到了失序的报文段也要立即发出对已收到的报文段的重复确认。如下图所示，接收方收到了M1 和M2后都分别及时发出了确认。现假定接收方没有收到M3但却收到了M4。本来接收方可以什么都不做。但按照快重传算法，接收方必须立即发送对M的重复确认，以便让发送方及早知道接收方没有收到报文段M;。发送方接着发送M和M6。接收方收到后也仍要再次分别发出对 M,的重复确认。这样，发送方共收到了接收方的4个对M,的确认，其中后3个都是重复确认。快重传算法规定，发送方只要一连收到3个重复确认，就可知道现在并未出现网络拥塞，而只是接收方少收到一个报文段 M，因而立即进行重传 M、(即“快重传”)。使用快重传可以使整个网络的吞吐量提高约20%。

因此，在上图中的点，发送方知道现在只是丢失了个别的报文段。于是不启动慢开始，而是执行快恢复算法。这时，发送方第2次调整门限值，使ssthresh=cwnd/2=8,同时设置拥塞窗口cwnd=ssthresh=8(见图5-25 中的点6)，并开始执行拥塞避免算法。

在上图中还标注有“TCP Reno 版本”，表示区别于老的 TCP Tahao 版本。

请注意，也有的快恢复实现是把快恢复开始时的拥塞窗口cwnd值再增大一些(增大3个报文段的长度)，即等于新的 ssthresh+3xMSS。这样做的理由是:既然发送方收到3个重复的确认，就表明有3个分组已经离开了网络。这3个分组不再消耗网络的资源而是停留在接收方的缓存中(接收方发送出3个重复的确认就证明了这个事实)。可见现在网络中并不是堆积了分组而是减少了3个分组。因此可以适当把拥寨窗口扩大些。

从上图可以看出，在拥塞避免阶段，拥塞窗口是按照线性规律增大的，这就是前面提到过的加法增大AI。而一旦出现超时或3个重复的确认，就要把门限值设置为当前拥塞窗口值的一半，并大大减小拥塞窗口的数值。这常称为“乘法减小”MD(Multiplicative Decrease)。二者合在一起就是所谓的AIMD 算法。

采用这样的拥塞控制方法使得TCP的性能有明显的改进

根据以上所述，TCP的拥塞控制可以归纳为下图的流程图。这个流程图就比上面的特例要更加全面些。例如，特里没有说明在慢开始阶段如果出现了超时(即出现了网络拥塞)或出现 3-ACK，发送方应采取什么措施。但从下面的流程图就可以很明确地知道发送方应采取的措施。

在这一节的开始我们就假定了接收方总是有足够大的缓存空间，因而发送窗口的大小由网络的拥塞程度来决定。但实际上接收方的缓存空间总是有限的。接收方根据自己的接收能力设定了接收方窗口 rwnd，并把这个窗口值写入 TCP 首部中的窗口字段，传送给发送方因此，接收方窗口又称为通知窗口(advertised window)。因此，从接收方对发送方的流量控制的角度考虑，发送方的发送窗口一定不能超过对方给出的接收方窗口值rwnd。

如果把本节所讨论的拥塞控制和接收方对发送方的流量控制一起考虑，那么很显然，发送方的窗口的上限值应当取为接收方窗口rwnd和拥塞窗口cwnd 这两个变量中较小的一个，也就是说:

• 当 rwd<cwnd 时，是接收方的接收能力限制发送方窗口的最大值。
• 反之，当 cwnd<rwnd 时，则是网络的拥塞程度限制发送方窗口的最大值。
• 也就是说，rwnd 和cwnd中数值较小的一个，控制了发送方发送数据的速率。

五、主动队列管理AOM

1、背景

上一节讨论的 TCP 拥塞控制并没有和网络层采取的策略联系起来。其实，它们之间有着密切的关系。

例如，假定一个路由器对某些分组的处理时间特别长，那么这就可能使这些分组中的数据部分(即TCP报文段)经过很长时间才能到达终点，结果引起发送方对这些报文段的重传。根据前面所讲的，重传会使TCP连接的发送端认为在网络中发生了拥塞。于是在TCP的发送端就采取了拥塞控制措施，但实际上网络并没有发生拥塞。

网络层的策略对 TCP拥塞控制影响最大的就是路由器的分组丢弃策略。在最简单的情况下，路由器的队列通常都按照“先进先出”FIFO(First InFirst Out)的规则处理到来的分组。由于队列长度总是有限的，因此当队列已满时，以后再到达的所有分组(如果能够继续排队，这些分组都将排在队列的尾部)将都被丢弃。这就叫作尾部丢弃策略(tail-droppolicy).

路由器的尾部丢弃往往会导致一连串分组的丢失，这就使发送方出现超时重传，使TCP进入拥塞控制的慢开始状态，结果使TCP连接的发送方突然把数据的发送速率降低到很小的数值。更为严重的是，在网络中通常有很多的TCP连接(它们有不同的源点和终点)，这些连接中的报文段通常是复用在网络层的IP数据报中传送的。在这种情况下，若发生了路由器中的尾部丢弃，就可能会同时影响到很多条TCP连接，结果使这许多TCP连接在同一时间突然都进入到慢开始状态。这在TCP的术语中称为全局同步(globalsynchronization)全局同步使得全网的通信量突然下降了很多，而在网络恢复正常后，其通信量又突然增大很多。

2、介绍

为了避免发生网络中的全局同步现象，在1998年提出了主动队列管理AOM(ActiveQueue Management)。所谓“主动”就是不要等到路由器的队列长度已经达到最大值时才不得不丢弃后面到达的分组。这样就太被动了。应当在队列长度达到某个值得警惕的数值时(即当网络拥塞有了某些拥塞征兆时)，就主动丢弃到达的分组。这样就提醒了发送方放慢发送的速率，因而有可能使网络拥塞的程度减轻，甚至不出现网络拥。AOM 可以有不同实现方法，其中曾流行多年的就是随机早期检测RED(RandomEarlyDetection)。RED还有几个不同的名称，如 Random Early Drop或 Random Early Discard(随机早期丢弃)。

3、实现

实现 RED时需要使路由器维持两个参数，即队列长度最小门限和最大门限。当每一个分组到达时，RED就按照规定的算法先计算当前的平均队列长度。

• 若平均队列长度小于最小门限，则把新到达的分组放入队列进行排队。
• 若平均队列长度超过最大门限，则把新到达的分组丢弃。
• 若平均队列长度在最小门限和最大门限之间，则按照某一丢弃概率p把新到达的分组丢弃(这就体现了丢弃分组的随机性)。

由此可见，RED不是等到已经发生网络拥塞后才把所有在队列尾部的分组全部丢弃，而是在检测到网络拥塞的早期征兆时(即路由器的平均队列长度达到一定数值时)，就以概率丢弃个别的分组，让拥塞控制只在个别的TCP连接上进行，因而避免发生全局性的拥塞控制。

在RED的操作中，最难处理的就是丢弃概率p的选择，因为p并不是个常数。对每-个到达的分组，都必须计算丢弃概率p的数值。IETF曾经推荐在互联网中的路由器使用RED机制[RFC 2309]，但多年的实践证明，RED的使用效果并不太理想。因此，在2015年公布的RFC 7567已经把过去的RFC 2309列为“陈旧的”，并且不再推荐使用RED。对路由器进行主动队列管理AQM 仍是必要的。AQM 实际上就是对路由器中的分组排队进行智能管理，而不是简单地把队列的尾部丢弃。现在已经有几种不同的算法来代替旧的RED，但都还在实验阶段。目前还没有一种算法能够成为IETF的标准，读者可注意这方面的进展。