|
|
|
因特网是一种无连接、尽力服务的分组交换网，这种网络结构和服务模型与网络拥塞现象的发生密切相关。与电路交换技术相比，因特网采用的分组交换技术通过统计复用提高了链路的利用率，但是很难保证用户的服务质量。端节点在发送数据前无须建立连接，这种方式简化了网络设计，使得网络的中间节点无须保存状态信息。但是，这种无连接方式难以控制用户注入到网络中的报文数量，当用户注入网络的报文数量大于网络容量时，网络将会发生拥塞，导致网络性能下降。
|
|
|
|
拥塞控制的基本功能是消除已经发生的拥塞，或避免拥塞的发生。目前的拥塞控制机制主要在网络的传输层实现，最典型的是TCP中的拥塞控制机制。实际上，最初的TCP协议只有流量控制机制而没有拥塞控制机制，接收方在应答报文中将自己能够接收的报文数目通知发送方，以限制发送窗口的大小。这种机制仅仅考虑了接收方的接收能力，而没有考虑网络的传输能力，因此会导致拥塞崩溃（Congestion Collapse）。1986年10月，因特网发生了第一次拥塞崩溃。那时，从LBL（Lawrence Berkeley Laboratory）到加州大学伯克利分校的数据吞吐量从32kb/s下降到40b/s。此后，拥塞控制成为计算机网络研究领域的热点问题。
|
|
|
|
|
|
网络拥塞是计算机网络运行过程中经常发生的一种现象，可以从不同的角度给出网络拥塞（简称拥塞）的具体定义。从拥塞的表现形式来定义，拥塞是指由于路由器中排队的报文足够多，导致缓存溢出，路由器开始丢弃报文的现象；从拥塞对网络的影响来定义，拥塞是指网络中存在过多的报文时，导致网络性能下降的现象；从拥塞产生的根本原因来定义，拥塞是指当报文到达速率大于路由器的转发速率时发生的一种现象。
|
|
|
|
拥塞控制是指网络节点采取措施避免拥塞的发生或对已经发生的拥塞做出的响应。从拥塞控制的定义可以看出，拥塞控制机制包括两个部分：拥塞避免和拥塞控制。拥塞避免是一种“主动”机制，它的目标是使网络运行在高吞吐量、低延迟的状态，避免网络进入拥塞状态；拥塞控制是一种“响应”机制，它的功能是把网络从拥塞状态恢复出来。
|
|
|
|
从控制理论的角度分析，因特网中的拥塞控制主要采用闭环控制的方式。一般包括3个阶段：根据网络状况检测拥塞的发生，将拥塞信息反馈到拥塞控制点，拥塞控制点根据拥塞信息进行调节以消除拥塞。根据拥塞控制算法的实现位置，可以分为链路算法和源算法。链路算法主要是在网络设备（如路由器）中执行，路由器负责检测拥塞的发生，产生拥塞反馈信息；源算法在主机中执行，主要作用是根据拥塞信息调节发送速率。其中，拥塞控制的源算法中使用最广泛的是TCP拥塞控制机制。
|
|
|
|
对于任何一种拥塞控制机制，都需要采用特定的评价准则来衡量它们是否公平有效地分配带宽。拥塞控制机制的有效性度量指标主要包括吞吐量、利用率、效率、延迟、队列长度、有效吞吐量（Goodput）和能量（Power，吞吐量／延迟）等。
|
|
|
|
|
|
TCP拥塞控制是在20世纪80年代后期由Van Jacobson引入因特网的。为了进行拥塞控制，TCP为每条连接维持两个新变量：一个是拥塞窗口cwnd；另一个是慢启动阈值ssthresh，ssthresh被用来确定是进入慢启动阶段还是进入拥塞避免阶段，一般将ssthresh的初始值设定为通告窗口值。
|
|
|
|
引入拥塞窗口cwnd后，TCP发送方的最大发送窗口修改为“允许发送方发送的最大数据量为当前拥塞窗口和通告窗口的极小值”。这样，TCP的有关窗口变量修改为：
|
|
|
|
|
|
EffectiveWindow=MaxWindow-（LastByteSent-LastByteAcked）
|
|
|
|
也就是说，在有效窗口（EffectiveWindow）的计算中用最大窗口（MaxWindow）代替了通告窗口。这样，TCP发送方发送报文的速率就不会超过网络或目的节点可接受的速率中的较小值。
|
|
|
|
TCP拥塞控制主要根据网络拥塞状况调节拥塞窗口（cwnd）的大小，其机制主要有慢启动、拥塞避免、快速重传和快速恢复，而且这4个机制共同发挥作用以实现TCP拥塞控制。下面先分别介绍这4个机制，然后再通过一个实例来说明这4个机制是如何共同发挥作用的。
|
|
|
|
|
|
慢启动（Slow Start）是指TCP刚建立连接时将拥塞窗口cwnd设为1个报文大小，然后以指数方式放大拥塞窗口，直到拥塞窗口等于慢启动阈值ssthresh。
|
|
|
|
具体来说，TCP开始将拥塞窗口设为1个报文大小，然后TCP发送1个报文；如果发送方TCP收到接收方TCP返回的ACK报文，TCP将拥塞窗口设为2个报文大小，然后TCP发送2个报文；如果发送方TCP又收到接收方返回的2个ACK报文（或1个累计确认报文），则TCP将拥塞窗口设为4个报文大小，直到拥塞窗口cwnd大于等于慢启动阈值ssthresh，然后进入拥塞避免阶段，如下图所示。
|
|
|
|
|
|
|
|
进入拥塞避免阶段，TCP采用线性增加（Additive Increase，AI）方式放大拥塞窗口，即发送方TCP每收到一个ACK确认报文，TCP将拥塞窗口cwind增加1个报文大小，如下图所示。
|
|
|
|
|
|
|
|
不管是在慢启动阶段还是在拥塞避免阶段，如果发生超时重传，则必须回到慢启动阶段，即此时拥塞窗口cwnd必须从1重新开始，而慢启动阈值ssthresh设置为上一次拥塞窗口值cwnd的一半。注意，以后每发生一次超时，慢启动阈值ssthresh就减半，这就表明，慢启动阈值ssthresh是按照指数规律减小的，这就是乘倍减小（Multiplicative Decrease，MD）。
|
|
|
|
在实际应用中，TCP不会等待整个拥塞窗口值的报文都得到确认后才给拥塞窗口加1个报文长度的值，而是每收到一个确认报文就逐渐增大拥塞窗口。具体地说，TCP每收到一个确认报文后，就将拥塞窗口按照下面的公式增大：
|
|
|
|
Increnment=MSS×(MSS/cwnd)
|
|
|
|
|
|
也就是说，TCP不是在每个RTT时间内将拥塞窗口增加整个MSS值，而是每收到一个确认报文，就将拥塞窗口增加MSS的一部分（即上面公式中的Increment）。
|
|
|
|
|
|
在TCP中，当TCP报文不能按序到达接收方TCP时，接收方TCP就会产生一个重复ACK返回给发送方；发送方收到一个重复ACK后，还不能确定是由于TCP报文丢失还是TCP报文乱序。如果发送方TCP收到3个重复ACK，则意味着是某个TCP报文丢失了，此时发送方TCP不必等待该报文超时，而是立即重传该报文，这就是快速重传。快速重传避免了让发送方TCP必须等待超时后才重传丢失的报文。下图给出了快速重传示意图。
|
|
|
|
|
|
|
|
在上图中，当发送方TCP连续收到3个重复的ACK：301时，发送方TCP立即重传序号为301～400的报文段，而不必等到超时，这就是快速重传。同时，发送方TCP会将拥塞窗口减半以及重传定时器宽度加倍。
|
|
|
|
但是快速重传之后，发送方TCP不是进入慢启动阶段，而是进入拥塞避免阶段，这就是快速恢复的意思。理由是重复ACK的出现不仅意味着某个报文的丢失，而且意味着在丢失的报文之后还接收到其后的报文，即网络上仍然可以传输报文，发送方TCP认为网络拥塞还不是非常严重，如果这个时候进入慢启动阶段，有点保守，而是应该进入拥塞避免阶段。
|
|
|
|
下图给出了拥塞避免、慢启动、快速重传及快速恢复4种机制组合在一起的TCP拥塞控制。
|
|
|
|
|
|
|
|
下图给出了一个实际的TCP拥塞控制实例，假定最大拥塞窗口值是32个报文段，则慢启动阈值ssthresh等于16（最大窗口值的一半）。TCP连接刚刚建立时进入慢启动过程，拥塞窗口cwnd从1指数增长到2，到4，到8，直到16（这里假设重传定时器不发生超时）；然后进入拥塞避免阶段，这时，拥塞窗口cwnd从16，到17，到18，到19，一直到20（加法增大）。此时，发生重传定时器超时现象，发送方首先将慢启动阈值ssthresh设为当前拥塞窗口cwnd的一半（乘法减小），即等于10，然后进入慢启动过程，即拥塞窗口cwnd又从1开始，接着指数增长到2，到4，到8，直到10，最后进入拥塞避免阶段，开始线性增加到11，到12。此时，连续收到3个重复ACK，于是进行快速重传，之后直接进入拥塞避免阶段而不是慢启动阶段。
|
|
|
|
|
|
|
|
在过去的十几年时间里，TCP拥塞控制经过不断的改进，性能逐渐得到完善，先后提出了多个TCP协议的实现版本。TCP Tahoe是TCP最早的版本，包含了3个最基本的拥塞控制机制：慢启动、拥塞避免、快速重传。TCP Reno在TCP Tahoe的基础上增加了快速恢复机制。TCP NewReno和TCP SACK都考虑了一个发送窗口内有多个报文丢失的情况，TCP NewReno对Reno中的快速恢复算法进行了补充，只有当所有报文都被应答后才退出快速恢复状态；TCP SACK采用“选择性重传”策略。所谓选择性重传是指当接收方发现报文乱序到达接收方时，接收方通过选择性应答策略通知发送方立即发送丢失的报文，而不需要等到发送方超时重传。
|
|
|
