- 里论外几
-
网络中的路由器因无法处理高速到达的流量而被迫丢弃数据信息的现象称为拥塞。这里可能是因为路由器缓存较小或者处理不及时,虽然和流量控制时接收方的情况相似,但是这里有本质区别。因为后者是一对一的,几乎只影响一条连接;后者则影响多个连接。
当网络中大量的发送方和接收方被要求承担超负荷的通信任务时,可以采用 降低发送方发送速率 或者 丢弃部分数据 (也可二者结合)来降低拥塞。
通常来说,接收方没有一个精确的方法去知道中间路由器的状态。目前基本的方法有:
之前的文章提到,发送方为了适应接收方接受速度,设置了一个发送窗口来控制流量。同样的,当拥堵发生时,也需要控制发送速率,于是引入了一个窗口变量,来反映网络传输能力,称为 拥塞窗口 (Congestion window),记作 cwnd。很直观的,我们可以知道,发送端实际可用窗口 W 表示如下,其中 awnd 表示接收方窗口大小:
W = min(cwnd, awnd)
也就是说,还没有收到 ACK 的数据量(也称在外数据量)不能多于 W 。通常 W 以字节或包为单位。很明显, W 的值是在随时变化的,并且我们希望 W 接近一个最佳窗口大小——带宽延时积(Bandwidth-Delay Product, BDP),BDP 表示某一时刻的在外数据量,但是确定一个连接的 BDP 也是一个难点。
当连接建立之初,还无法获知可用的连接资源,也无法确定 cwnd 初始值(有例外,就是之前文章里提到的目的度量)。这时候不应该直接大量快速的向网络中发送数据,因为会造成更严重的网络拥堵。获得 cwnd 最佳值的唯一方法就是以越来越快的速度发包,直到有数据包丢失(或网络拥堵)。可以考虑 慢启动 发送。在讨论具体算法之前,需要先了解 数据包守恒 的概念。
TCP 发送端的拥塞控制行为是由 ACK 的接收来驱动或“控制”的。并且链路的传输能力是固定的,当发送方接收到一个 ACK 时,就表示链路上多了一个“空位”,于是发送方可以再发送一个数据包。数据包守恒就是指链路中最大包的数量守恒。
当一个连接刚启动时,或者检测到重传超时导致的丢包时,需要执行慢启动 ; TCP 长时间处于空闲状态也可能触发慢启动。其目的是探寻到 cwnd 值已经帮助 TCP 建立 ACK 时钟。
TCP 发送一定数目的报文开始慢启动,该数目称为初始窗口(IInitial Window,IW)。为了简便,我们讨论 IW 为一个 SMSS (sender"s MSS)的情况。意味着初始 cwnd 大小为 1 SMSS。
假设没有丢包且每一个数据都有相应的 ACK。那么第一个 ACK 到达,说明可以再发送一个新的报文段(数据包守恒),每收到一个“好的” ACK, cwnd = cwnd + min(N, SMSS) ,这里的 N 是指那个“好的” ACK 所确认的字节数。所谓“好的”是指 ACK 号使窗口更新了。
因为通常来说 N 的值等于 SMSS,使得 cwnd 在收到一个 ACK 后增大一倍。所以慢启动实际上是以指数增长,在 K 轮之后,cwnd = 2^K。如下图:
当接收方开启延时 ACK,则发送方 cwnd 增长曲线如图中蓝色曲线,虽然起步看起来慢,但仍是指数增长。当然这对于带宽延时积很大的网络来说,确实有所浪费,应该采用更好的办法。
当然不可能让窗口大小无限增长,否则会造成严重的网络拥堵直至网络瘫痪。在上述情况下,cwnd 将大幅减小(减至原值一半),也是慢启动和 拥塞避免 的转折点,与 慢启动阈值 (slow start threshold, ssthresh)有关。
当 cwnd 达到 ssthresh 时,可能还有一些传输资源未被占用。但这时候需要谨慎的试探,不能再以较快速度增大 cwnd。采用避免拥塞算法,每接收到一个新的 ACK,cwnd 会做以下更新:
cwnd = cwnd + SMSS * SMSS / cwnd
假设 cwnd = k * SMSS,则可推导如下:
cwnd = cwnd + SMSS / k
发包来看像这样:
通常认为拥塞避免阶段 cwnd 呈线性增长,称为累加增长。
通常 TCP 连接总是会选择慢启动和拥塞避免中的一个,依据就是之前提到的慢启动阈值。当 cwnd < ssthresh,采用慢启动算法, cwnd > ssthresh 采用拥塞避免,相等时选择任意都行。所以关键就是 ssthresh 的值,该值并不是固定的,它的主要目的是, 记录上一次最好的窗口估计值 。
ssthresh 初始值可以任意设定(如 awnd 或更大),这通常会使 TCP 总是以慢启动开始。当出现重传,无论是超时重传还是快速重传,都会导致 ssthresh 值更新如下:
ssthresh = max(在外数据值 / 2, 2 * SMSS)
在外数据值其实就是当前窗口大小。这样通常会使 ssthresh 变小(但也可能使其变大),然后触发拥塞避免。
Tahoe 算法规定当重传时,都会进入慢启动,并且丢包时,将 cwnd 设为 1 SMSS。这显然性能不太好,已被弃用,不用深究。
Reno 算法是标准 TCP 的基础,它根据之前提到的“包守恒”实现了快速恢复,较好的利用了带宽。快速恢复是针对快速重传的情景实现的,来看一下它在标准 TCP 中的使用:
以下是 Reno 的状态转换图:
Reno 算法在同一窗口下丢失多个包时,其中一个包快速重传成功,就会停止 cwnd 膨胀,造成其它丢失的包可能触发超时重传,然后 cwnd 降为 1 SMSS,吞吐量大大降低。NewReno 采用了一个“恢复点”,指的是收到的 ACK 号大于已发送包的序列号的最大值,达到这个恢复点,才会退出快速恢复。下图最右图中, ACK11 达到了恢复点。
限制传输策略对 TCP 做了微小改进,主要是为了解决窗口较小时,出现丢包,但是没有足够的包去引发快速重传/快速恢复机制。为了尽快触发快速重传,每接收两个连续重复 ACK,就发送一个新的包,使网络中的数据量维持一定数量。这是 TCP 推荐策略。
这里对应 TCP/IP 详解卷一里,书上对于“应用受限”说法不正确。书上说此时“无法发送”,但是查阅 rfc 原文如下:
拥塞窗口校验(Congestion Window Validation)机制规定,需要发送新数据时,距离上次发送操作超过一个 RTO,如果是:
在长时间发送暂停后,cwnd 低于 ssthresh,再次发送时会进入慢启动。Linux 默认开启 CWV。
在之前的超时重传里,我们提到了 伪超时,再来回顾下(注意下图是相当简易的情形,没有考虑延时 ACK 以及 cwnd 增长,会意即可):
伪超时可能引起“回退 N 步”的行为,并且可能触发快速重传,浪费不少资源。
该算法利用 TCP 的 TSOPT 选项,在发送生超时后,重传报文并记录 TSV,期待一个 ACK,若 ACK 的 TSER 小于重传报文的 TSV,则认为该 ACK 是对原始报文的确认而不是对重传报文的确认,即认定该重传是伪重传。
前面提到过,发生超时,则 ssthresh 减半,cwnd 降为 1 SMSS。发生伪超时的话,在 RTO 之后到来的 ACK 会使 cwnd 快速变大,但仍会有不必要重传。
采用 Eifel 算法,在判定伪超时后,会撤销对 ssthresh 的修改。在每次超时对 ssthresh 修改之前,会用 pipe_prev 变量来保存当前的 ssthresh,以便撤销修改。
若出现伪重传,当 ACK 到达时,假设 ACK 确认的报文段长度为 A:
前面讨论了当失序或者超时的时候 TCP 的行为,这些行为都是通过 ACK 的反馈来触发或者驱动的,换句话说,这些“拥塞”的情况是“猜出来的”。当明确知道发生拥堵了,TCP 会执行 拥塞窗口缩减 (congestion window reducing,CWR)。明确知道拥堵的情况主要有两种:
CWR 处理过程如下:
直到 cwnd 达到新的 ssthresh 值或者由于其他原因(如丢包)打断 CWR。
到此,我们总结一下 TCP 拥塞控制的几个重要状态:
这个问题还是很有趣的,所以拿出来讲一下。先说结论,网络设备的缓冲区并不是越大越好,也不是越小越好,而是需要根据链路速率和RTT进行计算,得到一个经验值。
缓冲区过小的问题很明显,如果缓冲区太小,很容易就被写满了,只要不能进行适当的排队,丢包率会高,导致传输效率差。
假设如下场景:
上图中,我们假设中间的路由设备的buffer极大,理论来说无论来多少数据,都能buffer起来。中间的路由设备,接收速率是1M/s,而发送速率只有10k/s。
到某一时刻,发送方认为某一数据超时丢失(实际上没有丢失,而是在缓冲区没来得及处理),于是重发,导致缓存区有冗余数据。大量的冗余数据导致利用率变得极低。
而缓冲区为正常大小的时候,多的数据会被丢弃,过一会而缓冲区有新的位置,新的数据会到来,接收方收到数据是失序的,于是发送冗余 ACK,促进快速重传,反而使链路利用率得到保障。
大多数攻击是强迫 TCP 发送速率比一般情况更快或更慢。
原理是接收方将原来的确认范围划分成很多小块,把一个 ACK 变成多个 ACK,使得发送方不断增大 cwnd,使网络变的拥堵。可以通过计算每个 ACK 的确认量(而不是一个包)来判断是否是正确的 ACK。
接收方对还没到达的数据进行提前确认,使得 RTT 变得比较小,同样使得发送方不断增大 cwnd。可以采用一个可累加的随机数,动态匹配 ACK。