TCP Congestion Control

在本章中,我们将会关注拥塞控制的问题,它是在大数据(bulk data)传输中很重要第一个问题。TCP拥塞控制能够保证网络不会被overwhelmed。最简单的方法就是,当TCP认为网络拥塞的时候,就降低发送速度。所以问题就是:如何判断认为网络是拥塞的以及TCP如何来降低发送速率,以及什么时候可以再提高速率。

TCP被设计为数据在双方之间可以可靠传输。在之前,我们介绍了流量控制,接收方来不及处理对方发送过来的数据的时候,通过在返回的报文中的window size字段来减小的对方的窗口。注意,流量控制和拥塞控制不同的是,流量控制关注的是连接的两端,而不是中间的链路。而接下来要介绍的拥塞控制,关注的是两端之间的网络,不会发送太多的数据使得网络陷入拥塞

两台主机之间通信需要经过许多路由器,拥塞控制主要关注的是,不要发送的太快了,以至于中间的路由器存不下数据,而直接造成了丢失。

Detection of Congestion in TCP

就目前所了解的内容来说,TCP来处理的数据丢失的主要手段是重传,包括了快速重传以及timer-based的重传。假设,在网络已经较为拥塞的情况下,重传更多数据会使得网络拥塞的情况进一步加剧。

TCP所交互的对象是对方主机,它在传统方法中无法知道链路中间的路由器的状态是怎么样的。

In the Internet, this can be quite challenging, as there has traditionally been no explicit way for a sending TCP to learn about the state of the intermediate routers

通常来说,TCP判断链路中发生了拥塞最直接的方法就是分组的丢失(packet loss)

This is usually accomplished by detecting that one or more packets have been lost.

另外一些方法用于判断拥塞的方法就是测量时延(measuring delay)以及ECN(explicit Congestion Notification),可以让TCP知道链路中的拥塞情况,以免在后面造成不必要的报文丢失。

在前面的内容,我们主要关注的是TCP使用定时器,确认号(ACK)和选择确认的机制来检测和从数据丢失中恢复。接下来的关注TCP是如何面对拥塞的,如何来降低发送速率的,以及何时能够提高发送速率。

Slowing Down a TCP sender

在前面的内容中,接收方在返回的报文中使用Window size字段来通告他可用的缓冲区大小。我们可以进一步的提高下,让发送方降低速度当接收方太慢或者网络太慢的时候

We can go a step further and arrange for the sender to slow down if either the receiver is too slow or the network is too slow

我们新引入一个变量,叫作拥塞窗口(congestion window),它表示网络的可用容量,简写为cwnd。将接收方返回的Window size称为advertised window,简写为awnd。而发送方的窗口大小W为:
$$
W = min(cwnd,awnd)
$$
以此公式来实现拥塞控制,避免发送的数据太多了,此外从上面公式中,我们可以知道返回的window size不一定是发送方的offered window大小,实际上offered window 会小于window size字段。已经发送但是还未被确认的数据大小叫作flight size。**

The total amount of data a sender has introduced into the network for which it has not yet received an acknowledgment is sometimes called the flight size

主要的问题就是如何确定cwnd,接下来会涉及很多的算法来确定cwnd。

Class Algorithm

当一个TCP连接建立的时候,通常对于cwnd设置为什么值都没数。对于awnd,那么可以通过一个报文的交互就可以知道了。对于cwnd来说,最直接的方法就是尽可能快的发送报文,直到出现报文丢失为止。但是网络是多个连接共享的网络资源,发太快也会影响其他主机。所以TCP在启动的时候会采用一种更为温和的手段来调节发送速率。

原文中提到的conservation of packets没有理解是什么用的。就先略。经典算法主要涉及的两个算法:慢启动(slow start)和拥塞避免(congestion avoidance)都是基于conservation of packets(包守恒)原理的。

Slow Start

慢启动算法会在连接刚建立以及RTO超时的时候执行。慢启动的主要目的是在使用拥塞避免算法来探测网络中还有多少空闲带宽算法之前来寻找到合适的cwnd

The purpose of slow start is to help TCP find a value for cwnd before probing for more available band- width using congestion avoidance and to establish the ACK clock.

TCP在最开始的时候,发送一定数量的报文,叫作初始窗口(initial window)。一般来说IW最开始是一个SMSS(send maximum segment size,直接当MSS用也没问题)。当然RFC5681建议IW可以在初始的时候设置的更大一点:

在这里,为了简单起见,我们将IW设置一个SMSS。在没有数据丢失的情况下,一个返回的ACK就可以使得cwnd增长一个SMSS。

Thus, after one segment is ACKed, the cwnd value is ordinarily increased to 2, and two segments are sent. If each of those causes new good ACKs to be returned, 2 increases to 4, 4 to 8, and so on.

窗口长度W经过k 个RTT之后,就达到了$W=2^{k}$字节大小。这种指数级的增长看起来挺快的,但是和一开始就以advertised window的发送窗口大小来说,还是比较慢的。不过注意,W在这种指数增长下还是不能超过awnd。

在以这样指数级的增长下,cwnd很快就会到达一个相当大的值,最终会导致丢包。此时,cwnd马上减少它前一个值的一半,比如说此时cwnds是100,发生了丢包,那么就减小到50。然后,将从慢启动转到拥塞避免的过程,这个切换点是由cwnd和slow start threshold(ssthresh)来决定的。

下图的左边是慢启动的图例,可以看到每返回一个ACK,cwnd就会增长一个SMSS。cwnd的指数增长如右图的cwnd标注的线所示。第二条线表示的是delayed ACK之下的慢启动,可以看到增长的非常慢。因为Delayed ACK不会每一个报文都返回ACK,所以有些TCP的实现会在连接建立以后才使用Delayed ACK,Linux中就是这样的。

窗口的变化过程

Congestion Avoidance

在连接的初始阶段和RTO超时后都会调用慢启动(RTO超时暂时还没涉及到)。cwnd的快速增长来决定ssthresh的值。达到ssthresh的时候,此时并不代表这网络的负载较大了,而是,这意味着应该降低网络发送速率,能够进一步利用网络带宽

Once this is achieved, there is always the possibility that more network capacity may become available for a connection

目前暂时还没涉及到ssthresh的设置,我们接下来要来讨论拥塞避免的过程。一旦ssthresh的值已经设定好而且cwnd已经达到了ssthresh,TCP就运行一个拥塞避免的算法,来进一步挖掘可用的网络带宽。在拥塞避免中,cwnd是每以整个window的数据被接受的时候,才增加一个MSS,而不是之前的一个ACK增加一个MSS(指数增长)。

seeks additional capacity by increasing cwnd by approximately one segment for each window’s worth of data that is moved from sender to receiver successfully

更精确的描述来说,每接收到一个ACK,cwnd的增长公式如下:
$$
cwnd_{t+1}=cwnd_{t}+SMSS\times \frac{SMSS}{cwnd_{t}}
$$
假设,$cwnd_{0}=k\times SMSS$,其中k是发送到网络中的报文数,带入到上述公式:
$$
cwnd_{1}=cwnd_{0} + \frac{1}{k}\times SMSS
$$
这也就是说每个返回的ACK会导致cwnd在之前基础上增加1/k SMSS。在图像上表示来说,拥塞避免使得cwnd的增长表现的更加地线性,而不是之前的指数增长。

然而,这种拥塞避免的方法只能在Bit errors不怎么发生的情况下才适用,在这种情况下,我们可以大胆的将丢包认为是网络情况拥塞的特征。而对于bit errors比较常见的无线网络中,出错的报文会被直接丢弃,不返回ACK。如果被错误的认为是拥塞导致的丢包,会使得网络利用率变低。

The assumption of the algorithm is that packet loss caused by bit errors is very small (much less than 1%), and therefore the loss of a packet signals congestion somewhere in the network between the source and destination. If this assumption is false, which it sometimes is for wireless networks, TCP slows down even when no congestion is present

Selecting between Slow Start and Congestion Avoidance

前面提到过了ssthresh,当慢启动的cwnd达到了ssthresh的时候,由慢启动转到拥塞避免的状态。本节,我们来讨论如何确认ssthresh。

When cwnd < ssthresh, slow start is used, and when cwnd > ssthresh, congestion avoidance is used. When they are equal, either can be used.

在最开始的时候ssthresh的值会设置的相当大,那么就慢启动的过程会使得cwnd持续增长。一旦超时重传或者快速重传开始后,根据如下公式来设置:
$$
ssthresh=max(flight size/2,2\times SMSS)
$$
可以观察到,将ssthresh设置为当前窗口的一半。

PS:前面说过flight size是已经被发送但是还未被确认的数据。

Tahoe, Reno, and Fast Recovery

到目前讨论的算法慢启动,拥塞避免构成了第一个版本的TCP的拥塞控制算法,他是在1980s BSD(Berkeley Software Distribution)引入的。

在BSD的版本中(Tahoe,太浩湖),在重传以后(无论是因为超时还是快速重传造成的重传),Tahoe很直接地将cwnd设置以为一个1 MSS,接着开始慢启动直到达到了ssthresh。

Tahoe was implemented by simply reducing cwnd to its starting value (1 SMSS at that time) upon any loss, forcing the connection to slow start until cwnd grew to the value ssthresh.

不过它这个太保守了,后面的4.3中的BSD的TCP Reno结合了快速恢复(fast recovery)的算法。在快速恢复阶段,每收到一个ACK,cwnd就会增加一个MSS,直到一个 nonduplicate ACK被接收,就回到之前的拥塞避免的模式。Reno变得十分流行并且在最后成为了标准TCP的基础。快速恢复算法只是用于替代Tahoe中对于快速重传过于保守的策略,而对于超时重传,Reno中也是将cwnd= 1 MSS开始。

Any nonduplicate (“good”) ACK causes TCP to exit recovery and reduces the congestion back to its pre-inflated value.

Standard TCP

RFC 5681中给出了TCP的拥塞控制的基本算法。在开始阶段,cwnd=IW(initial window),且在初始阶段ssthresh设置的相当大,通常来说ssthresh=awnd

TCP begin s a connection in slow start (cwnd = IW) with a large value of ssthresh, generally at least the value of awnd.

在接收到了新的ACK之后,TCP按照以下公式来更新Cwnd:

更新公式

快速重传(因为收到了三个冗余ACK)发生以后,执行接下来的操作:

  1. ssthresh被更新为不能超过max(flight size /2 ,2*MSS),更加准确的来说,应该是设置原来cwnd的一半。

Reducing the estimate of the optimal window size is accompanied by altering ssthresh to
be about half of what the current window size is (but not ever below twice the SMSS)

  1. 当执行快速重传的时候,cwnd = ssthresh+3*SMSS;
  2. cwnd每接收到一个ACK就增加一个SMSS
  3. 当一个好的ACK(新的ACK,而不是duplicate ACK),cwnd被重新设置为ssthresh,这也使得,接下来就会执行线性增长。

上面的步骤2和3叫作快速恢复(在Reno中才引入的)。它不像Taheo在发生快速重传的时候将cwnd设置为1 SMSS。在第二步中,加上三个MSS的原因是,在快速恢复内,每一个ACK会增加一个SMSS,duplicate ACK恰好是三个。慢启动总是会在超时重传以及连接建立以后使用。

Slow start is always used in two cases: when a new connection is started, and when a retransmission timeout occurs.

下图是来自《计算机网络--自顶向中》的一张图,很好的概括了这些内容):

拥塞控制的状态转变

Evolution of Standard Algorithm

Reno TCP仍然有些地方可以提高,也就是说他还是有那么些问题。

New Reno

在Reno中,当多个包丢失的时候,只要有一个包重传后且收到了一个non-duplicate ACK,会使得TCP退出快速恢复阶段。在之前的内容中,我们说到过什么是partial ACK,即(来自14.6 Retransmission with Selective Acknowledge):

This number is larger than the previous highest ACK value seen (23801), but not enough to meet or exceed the recovery point (44801).

原文中提到了在Reno中遇到一个non-duplicate ack就会退出fast recovery:

once one packet is recovered (i.e., successfully delivered and ACKed), a good ACK can be received at the sender that causes the temporary window inflation in fast recovery to be erased before all the packets that were lost have been retransmitted

Reno TCP在面对partial ACK的时候会将他的窗口减小到相当小,使得TCP陷入idle状态直到超时定时器的超时。为了理解这个为什么会发生,回想一下non-SACK TCP依赖于冗余ACK的。比如说窗口变得非常小,没有新的数据可以发送了,对方就一直不会返回ACK,那么就达不到冗余ACK的条件,只能等待超时重传的发生。

原文中的这一段话我认为不够全面,这篇讲的比较好。

This happens when, for each segment loss, Reno enters fast recovery, reduces its cwnd and aborts fast recovery on the receipt of a partial ACK. (A partial ACK is one which acknowledges some but not all of the outstanding segments.) After multiple such reductions, cwnd becomes so small that there will not be enough dupacks for fast recovery to occur and a timeout will be the only option left.

所以NewReno为了解决这个问题,它在面对partial ACK的时候,会认为这些数据还是丢失的。而不是如同Reno中直接退出快速恢复。这篇论文中说明了NewReno在面对partial ACK的行为:

In New-Reno, partial ACKs do not take TCP out of Fast Recovery. Instead, partial ACKs received during Fast Recovery are treated as an indication that the packet immediately following the acknowledged packet in the sequence space has been lost, and should be retransmitted

所以在newReno中,每接收到一个ACK之后仍然会使得窗口增加一个MSS长度。直到接收的ACK超过了recovery point。

This allows a TCP to continue sending one segment for each ACK it receives while recovering and reduces the occurrence of retransmission timeouts, especially when multiple packets are dropped in a single window of data

这里简要的概括了Reno存在的一些问题,但是没有对partial ACK的情况做详细解释。

最后,NewReno可以处理在不支持SACK下的多个丢包处理。它在实现上也比SACK简单不少,所以他成为了一个非常流行的TCP版本。

NewReno is a popular variant of modern TCPs—it does not suffer from the problems of the original fast recovery and is significantly less complicated to implement than SACKs.

TCP Congestion With SACK

引入SACK能够使得TCP更好的直到在接收方中的数据空洞,而不会出现Go back to N的形式。在快速恢复/重传的例子中,当一个分组丢失的时候,发送方可以发送新的数据只要在窗口内部。因为在快速恢复阶段,窗口会因为每一个ACK的接收都增长一个SMSS,在窗口较大的时候能够发送一些额外的信息

Because the window is inflated for each arriving ACK during fast recovery, with larger windows TCP typically is able to send some addi-tional data after performing its retransmission.

但是这可能会导致网络中塞入太多的数据,所以对TCP的拥塞控制有影响。为了解决这个问题,引入了一个新的变量叫作pipe,它反映了fight size的字节数。cwnd-pipe >= SMSS的时候,才可以发送数据,而不是像之前有空闲窗口就发数据。对于该不等式如何得来,我没有深入研究。原文中给出了论文[FF96]

FACK

原文中对于FACK的描述感觉十分晦涩。我无法理解FACK到底解决了什么问题。FACK的论文:Forward acknowledgement: Refining TCP congestion control.有机会看看。

另外,Linux系统中支持FACK,并且可以通过net.ipv4.tcp_fack=1 来启用FACK。

Limited Transmit

这篇论文提到,usable window超级小的时候,可能没有足够的分组来触发fast retransimit/recovery,因为这些算法都依赖于duplicate ACK。

there may not be enough packets in the network to trigger the fast retransmit/recovery algorithms when loss occurs, as these algorithms typically require three duplicate ACKs to be observed prior to initiation

所以在RFC3042中提出,每两个连续的ACK接收的时候,那么就发送一个新报文--这就使得在网络中总是有一定数量的报文,可以触发快速重传。因此也可以避免了重传定时器的超时,影响TCP的吞吐率。

Doing this helps to keep at least a minimal number of packets in the network—enough so that fast retransmit can be triggered upon packet loss

Congestion Window Validation (CWV)

当TCP在发送数据一段时间后,可能会因为暂时没有数据发送了或者因为其他原因导致发送停止。虽然原文说,通常不会暂停,和接收方之间的连续交互能够更新ssthresh和cwnd。

If all goes well, a sender never pauses, and it continues sending data and receiving ACKs from its peer. This continuous feedback enables it to keep a reasonably current (within one RTT) estimate of what cwnd and ssthresh should be

发送一段数据之后,此时的窗口可能比较大了。然后暂停一会,接着在恢复的时候。此时cwnd较大,会使得直接发送大量的数据。此外,一段时间不发送数据之后,此时它的cwnd已经不再适合了。

Furthermore, if the pause is sufficiently long, its last cwnd value may no longer be appropriate for the path and congestion state

RFC 2861中提出了一个实验性的方法,称为Congestion Window Validation,如果一段时间以后都没发送报文cwnd会逐渐的递减。以ssthresh来反映之前的cwnd。

Essentially, the sender’s current value of cwnd decays over a period of nonuse, and ssthresh maintains the “memory” of it prior to the initia- tion of the decay.

CWV的算法主要如下,在发送新报文的时候,计算上一次发送报文的时间到现在已经过去了多久,并且根据是否超过了RTO做如下操作:

如果超过了RTO:

  • sshthresh修改为max(ssthresh,(3/4)cwnd)
  • 在空闲的时候,cwnd会随着每经过一个RTT就减半,但是不小于SMSS。

对于是application-limited,而非idle来说执行的操作相似。先介绍下什么是application-limited:

The application-limited sender does have more data to send but has been unable to for some reason. This could be because the sending computer is busy doing other tasks, or because some mechanism or protocol layer below TCP is preventing data from being sent.

CWV算法执行的操作是:

  • 当前窗口大小为W_used
  • sshthresh修改为max(ssthresh,(3/4)cwnd)
  • cwnd设置为cwnd和W_used的平均值

Linux默认使用CWV算法。

Handling Suprious RTO-the Eifel Response Algorithm

在之前的章节中,我们介绍过伪重传的概念。当RTT突然变得比较大的时候,即使本次数据被正确的接收了,但是还是会触发RTO。

As we saw in Chapter 15, when TCP encounters a large delay spike, it can experience a retransmission timeout even if no packet has been lost.

当这个发生以后,TCP会调节ssthresh以及cwmd到IW,这会造成非必要的分组重传。前面我们说过为重传的检测算法和响应算法(D-SACK,Eifel,F-RTO)。在前面我们提到过Eifle 响应算法,它会重新设置RTO,来避免伪重传。接下来要讨论的是Eifel响应算法在拥塞控制中的操作。

如果检测到伪重传,Eifel响应算法会取消对ssthresh的设置(因为超时重传会将sshthresh设置到当前窗口一半)。如果是因为超时需要对ssthresh(无论是真的超时还是伪超时),在修改ssthresh之前,需要有一个特殊的变量,pipe_prev=min(flig size,ssthresh)。接下来再调用之前提到过的检测算法(D-SACK,F-RTO,Eifel)来判断是否发生了伪重传,如果是,在重传后的ACK到达之后,执行如下操作:

  • 若接收到的ACK有ECN标志(暂时还没说到),停止操作
  • cwnd=flight size + min(bytes_acked,IW)
  • ssthresh=pipe_prev

Sharing Congestion State

在很多情况下,新建立的连接可以利用之前的连接的信息,来用于设置ssthresh和cwnd。Linux可以通过net.ipv4.tcp_no_metrics_save来设置是否会保存这些信息。当一个TCP关闭后,以下的信息会被保存:

RTT measurements (srtt and rttvar), an estimate of reordering, and the congestion control variables cwnd and ssthresh.

Delay-Based Congestion Control

之前介绍过的拥塞控制算法都是基于报文丢失的,比如说发生了冗余ACK我们就判断丢包发生了,或者定时器超时了,还有SACK,ECN(还未涉及到)等等。另外一种方法就是基于对于RTT的测量来判断网络拥塞。

One clue that congestion may be forming is an increase in measured RTT as the sender injects more packets into the network.

这种方法叫作delay-based 拥塞控制。这里有好几种算法。先略有时间再补充吧。

Active Queue Management and ECN

在之前对于拥塞的检测最直接的方法就是丢包。通常来说,路由器不会来通知主机马上说:马上就要拥塞了。路由器在没空闲位置的时候直接将数据都直接丢弃。

ECN主要是显示的来表示拥塞了,让路由器拥有表达链路拥塞的能力:

These RFCs describe Explicit Congestion Notification (ECN), which is a way for routers to mark packets (by ensuring both of the ECN bits in the IP header are set) to indicate the onset of congestion

暂无评论

发送评论 编辑评论

|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇