TCP拥塞控制

主要参考：谢希仁《计算机网络》第七版。

拥塞控制一般原理

计算机网络中包括了各种各样的资源，例如链路带宽、交换机/路由器内的缓存大小、处理器性能等。若在某个时间段内，网络中某一资源的需求炒股了该资源所能提供的可用部分，网络性能变差，就叫做拥塞。即：
$\sum对资源的需求>可用资源$∑对资源的需求>可用资源
网络拥塞是由许多因素引起的，简单加资源并不能完全解决问题。

拥塞控制与流量控制的区别

这两者关系密切，但是存在差别。
拥塞控制是防止过多数据进入网络，可以使得网络中的路由器/链路不至于过载，拥塞控制的前提是网络能够承受的负荷，是一个全局性的过程。
流量控制是指点对点通信量的控制，是端到端的问题。

对拥塞控制的理解

如上图所示，横坐标是提供的负载，代表单位时间内输入给网络的分组数目，即请求的资源数量，亦称输入负载/网络负载；纵坐标是吞吐量，代表单位之间内从网络输出的分组数量。

• 理想的拥塞控制：在吞吐量饱和之前，网络吞吐量等于网络负载，成线性关系。当负载超过限度时，由于网络资源的限制，吞吐量达到饱和，保持最大吞吐量。
• 无拥塞控制：随着负载的增大，吞吐量的增长速率逐渐减小。即，在网络达到饱和之前，已经有一部分输入分组被丢弃，当吞吐量明显小于负载时，就进入轻度拥塞的状态。继续增大负载，可能进入拥塞甚至死锁。
• 实际的拥塞控制：在吞吐量饱和以后依然无法达到最大吞吐量，只能接近最大吞吐量。

TCP的拥塞控制方法

TCP进行拥塞控制的方法包括：慢开始(slow-start)、拥塞避免(congestion avoidance)、快重传(fast retransmit)、快恢复(fast recovery)。
前提假设：

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

慢开始&&拥塞避免

基于窗口的拥塞控制，发送方维护一个状态变量拥塞窗口cwnd。其大小取决于网络的拥塞程度，并动态变化，发送方的发送窗口大小等于拥塞窗口cwnd。
拥塞窗口的控制原则：网络没有拥塞，cwnd可以增大一些，把更多的分组发出去，提高网络利用率；网络如果出现拥塞，就把cwnd缩小一些，减少注入网络的分组数，缓解网络可能出现的拥塞。
慢开始的思想：开始时不清楚网络的负荷情况，故由小到大增大cwnd。旧版本的慢开始规定初始cwnd为1或2个发送方最大报文段SMSS的数值，新版规定初始cwnd不超过2~4个SMSS的数值（根据不同SMSS的值变化，具体可以查书）。
在慢开始中，每次收到一个对新的报文的确认后，可以把拥塞窗口增加最多一个SMSS的值，即： $\Delta cwnd=min(N,SMSS)$Δcwnd=min(N,SMSS),其中N是原先未被确认的、但是现在刚被收到的确认报文字段所确认的字节数。
拥塞避免算法是让拥塞窗口cwnd缓慢增大，即每个RTT，cwnd++，而不是像慢开始那样翻倍，在此阶段，cwnd按线性规律缓慢增长，使得网络比较不容易出现拥塞。

实际上慢开始的cwnd在开始阶段是指数增长的（N < SMSS时）,
为了避免cwnd增长过快引起网络拥塞，还需要一个状态变量：慢开始门限ssthresh，

• 当cwnd < ssthresh时，使用慢开始算法；
• 当cwnd > ssthresh时，使用拥塞避免算法；
• 当cwnd = ssthresh时，使用慢开始和拥塞避免都可以。

对于ssthresh，当发生超时（即发生拥塞），就把ssthresh变化为超时时cwnd的值的一半， $ssthresh=\frac{cwnd}{2}$ssthresh=2cwnd​。

快重传&&快恢复

有些时候，个别报文丢失会引起超时，但是并没有发生拥塞，发送方若错误的重新开始慢启动，就会降低传输效率，采用快重传可以让发送方尽快知道发生了个别报文的丢失。
首先，快重传要求接收方不进行稍待确认，而是立即发送确认，即使收到失序报文，也要立即发出已收到的报文段的重复确认,而发送方一旦收到三个重复确认，则立刻进行已确认报文的下一个报文的重传（例如下图，收到了3个 $M_2$M2​的ACK，意味着 $M_3$M3​丢失，则重传 $M_3$M3​），这样就不会出现超时，发送方就不会误认为发生了网络拥塞。

如上上图中的点4，发送方收到了3-ACK，并不启动慢开始，而是执行快恢复，令 $ssthresh=\frac{cwnd}{2}=8$ssthresh=2cwnd​=8，同时设置cwnd=ssthresh=8，执行拥塞避免算法。

在本文开头曾理想化设置接收方的缓存为无限大，但是实际上接收方会根据自己的能力设定一个rwnd，亦称通知窗口，发送方的发送窗口一定不能超过接收方的rwnd。所以：
，但是实际上接收方会根据自己的能力设定一个rwnd，亦称通知窗口，发送方的发送窗口一定不能超过接收方的rwnd。所以：
$发送方窗口_{MAX}=Min[rwnd,cwnd]$发送方窗口MAX​=Min[rwnd,cwnd]