TCP拥塞控制-PRR

Prr是rfc对于快速回复算法的改进，实际的在linux中的实现是谷歌的哥们做的。这篇文章改编自网友的另一篇很多英文的文章，为了我自己的理解，我就整理了一下。

快恢复是在检测到拥塞发生的时候将发送窗口降低到一半（怎么才算拥塞由另外的算法决定）。

PRR简介
PRR是最新的linux的默认推荐拥塞算法，之前的是cubic。但是有意思的是，在linux中使用了prr仍然可以以cubic作为默认拥塞算法。因为众所周知的，拥塞算法大致都是一样的，只是在一些参数和细节调整上有区别。Linux上的prr实现就是个对tcp_input.c文件的补充，并不是以模块的形式提供的。

Prr是一个rfc的推荐标准，有推荐的实现方式。内核中对prr的实现是谷歌的一个工程师做的，也就是rfc中推荐的实现方式：PRR-SSRB。

窗口机制的内核实现
传输数据的时候，如果发送方传输的数据量超过了接收方的处理能力，那么接收方会出现丢包。为了避免出现此类问题，流量控制要求数据传输双方在每次交互时声明各自的接收窗口「rwnd」大小，用来表示自己最大能保存多少数据，这主要是针对接收方而言的，通俗点儿说就是让发送方知道接收方能吃几碗饭，如果窗口衰减到零，那么就说明吃饱了，必须消化消化，如果硬撑的话说不定会大小便失禁，那就是丢包了。

虽然流量控制可以避免发送方过载接收方，但是却无法避免过载网络，这是因为接收窗口「rwnd」只反映了服务器个体的情况，却无法反映网络整体的情况。

为了避免过载网络的问题，慢启动引入了拥塞窗口「cwnd」的概念，用来表示发送方在得到接收方确认前，最大允许传输的未经确认的数据。「cwnd」同「rwnd」相比不同的是：它只是发送方的一个内部参数，无需通知给接收方，其初始值往往比较小，然后随着数据包被接收方确认，窗口成倍扩大，有点类似于拳击比赛，开始时不了解敌情，往往是次拳试探，慢慢心里有底了，开始逐渐加大重拳进攻的力度。

发送方通过对「cwnd」大小的控制，能够避免网络过载，在此过程中，丢包与其说是一个网络问题，倒不如说是一种反馈机制，通过它我们可以感知到发生了网络拥塞，进而调整数据传输策略，实际上，这里还有一个慢启动阈值「ssthresh」的概念，如果「cwnd」小于「ssthresh」，那么表示在慢启动阶段；如果「cwnd」大于「ssthresh」，那么表示在拥塞避免阶段，此时「cwnd」不再像慢启动阶段那样呈指数级整整，而是趋向于线性增长，以期避免网络拥塞，此阶段有多种算法实现。

而rwnd对应着内核的接收缓存大小，例如net.ipv4.tcp_rmem就可以很大程度上控制rwnd，它表示的是接收方的物理接收能力。很多tcp性能的瓶颈就发生在这里。

拥塞时发送窗口的变化
拥塞算法实际作用的是cwnd，传统的方法在发送的时候发生拥塞的时候，会把cwnd设置为原来的一半（快速恢复），在linux原来的实现中，这个值被设置为packets_in_flight + 1。在这种情况下，想象一个场景。一个http请求在发送的时候发生了快速恢复。由于cwnd迅速变为原来的一半，所以能发送的数据快速变少，packets_in_flight + 1的值也就迅速变小，而每次收到ack的时候，内核都会把cwnd设置为packets_in_flight + 1。待一次http请求发送完，cwnd就会变的很小。后面再使用这个连接发送数据的时候就得面对一个很小的发送窗口了，也就是一个慢启动过程，而实际上没有这么小。Ppr的目的就是在一次http请发送完即使发生拥塞，cwnd的值接近于ssthresh的慢启动门限，而不是接近0的满启动。

旧的快速恢复算法有RFC3517中定义的和linux中实现的速率减半方案，也就是说linux中实现的与rfc是不一样的。Linux之所以不采用rfc中定义的方案也是因为rfc的方案可能在高丢包率的情况下发送太多的数据。而linux的方案也有问题就是可以导致比较长的恢复时间或者过多重传。

Rfc中定义的快速恢复方法
一、定义

进入恢复时

// cwnd和ssthresh都设置为已经发送没有接收到ack的数据包数目的一半

cwnd = ssthresh = FlightSize / 2

// 然后使用快速重传机制重发第一个没有收到ack的数据包

fast_retransmit()

// 如果cwnd还允许的话就发送更多

Transmit MAX(0, cwnd – pipe)

对于恢复时收到的每个数据包:

update_scoreboard() pipe = (RFC 3517 pipe algorithm)

Transmit MAX(0, cwnd – pipe)

二、 缺陷

 Rfc的算法有时太过激进，有时太过保守。

1. 半RTT安静（保守方面）

快速重传机制在发现拥塞的时候，会进行第一次的重传，rfc规定在快速重传算法的重传之后要等待网络中flight（已经发出但是没有收到ack）数据包的一半的ack收到之后才能继续发送数据。而很多情况下，这个等待是无意义的，快速重传变成了慢速重传。

 

2. 高强度的突发重传（激进方面）

由于rfc的算法在快速重传之后接收到一个ack之后可以大量的突发发送数据（取决于设计的管道流），而这种突发在真实的发生了网络拥塞时候会造成更严重的网络丢包。而根据标准，发生的丢包越严重，突发发送的时候产生的突发量越大，也就越加重这个丢包。这种模式在http网页和是频率中有都有不好的表现。

Linux中实现的快速恢复方法
由于rfc的问题，linux做了优化。快速恢复时不时等待收到ack之后才继续发送数据，而是只要进入快速恢复就仍然继续发送数据，但是发送数据的窗口立即降低为原来窗口的一半。这样就避免了半RTT安静问题和减缓了突发重传的问题。

但是同时带来了一个问题，就是如果确实是发生了发送的网络拥塞，发送窗口会快速降低，一方面压制了自己向网络中发送数据的速度（看起来是对的），但是一方面也把自己的后续发送数据的能力降低到慢开始的级别。

也就是在一种业务场景发生时，这个算法会把自己置于慢开始的境地。这个场景就是当发生拥塞时，不是因为网络原因导致发送量减少，而是因为应用程序的原因导致的。此时cwnd会持续的减小，即使网络没有发生拥塞。因为cwnd是否减小是由发送的速度决定的，而此时发送速度又是由应用程序决定的。并且当cwnd下降到ssthresh以下的时候，linux的发送策略就变为必须受到一个ack发能发送一个数据包，此时又进一步加重了此tcp管道的性能恶化。

所以就会出现tcp的效率非正确的快速下降。

PPR_SSRB方法
原来的算法主要有两个问题：发生拥塞的时候发送窗口快速下降，下降速度过快；下降的最下限是cwnd为1，低于慢开始阈值，导致后续的数据包会从慢开始过程开始。SSRB针对性让下降的最小值为ssthresh（慢开始门限），并且发送速度逐步缓慢下降，并且这个下降是根据实时的网络情况确定的，不是估计的。

 

网络中每N个包退出（被接收端缓存了），则发送beta * N个包（重传或新的）。

网络中数据包守恒的情况：

sndcnt = prr_delivered – prr_out; /* 1比1的兑换关系*/

网络中数据包按比例减少：

sndcnt = (snd_sshresh / prior_cwnd) * prr_delivered – prr_out; /* 1/beta比1的兑换关系*/

举例来说，使用cubic算法，beta为0.7。如果有10个包被接收或缓存了（退出网络了），则可以发送7个包（重传或新的），

这样一来，网络中存在的数据包就减少了3个，在整个快速恢复的过程中，网络中存在的数据量逐渐减少为初始的0.7。

这就是所谓的按比例减小，减小的比例即为30%。

                 <-------------------------收N个-------------------------- Server                                                                                          Client                  ----------------发0.7 * N个----------------->

实际上是在用prr_delivered和prr_out来实时测量网络中存在的数据段个数（所以说更加准确，因为这不是猜测）。

这是一个渐变的过程，不断兑换的过程，最终网络中存在的数据量和拥塞窗口都收敛于snd_ssthresh。

这个算法的核心是利用Van Jacobson的数据包守恒定理：发送到网络中的数据包数量是发送数据包的控制时钟。

 

算法分为两部分：一部分是拥塞发送下降的时候采用sndcnt = (snd_sshresh / prior_cwnd) * prr_delivered – prr_out;的公式下降。其中prr_delivered是收到接收方的ack，表示已经被接收方从网络中拿走的部分，prr_out是尚在网络中的部分。此公式保证了发送的速度与接收的速度成正比，由于系数的存在（不同的算法可以设置不同的系数），使得系数在cwnd不断接近sshresh的时候，系数逐渐变为1，在拥塞刚开始的时候系数还是比较大的，所以这个发送数据包下降的过程是先快后慢的，直到到达ssthresh，发送速率稳定。所以最终的窗口会收敛到ssthresh。第二部分是当cwnd一旦下降到ssthresh以下的时候（正常情况不会，但是如果应用程序中断了数据传输,prr_out为0,cwnd也会逐渐下降到0，与rfc一样），此时另外一个配套机制启动，就是当快重传阶段cwnd掉到ssthresh以下时，启动慢启动机制，让cwnd的量慢速上升。

通过这两个部分算法的配合就可以完成整个PRR_SSRB算法。

PPR_SSRB的改动
 

 PPR_SSRB的改动包括在tcp_sock上添加了几个域：

 

1. struct tcp_sock {  

2.     …  

3.     /* Congestion window at start of Recovery. 进入Recovery前的拥塞窗口*/  

4.     u32 prior_cwnd;       

5.   

6.     /* Number of newly delivered packets to receiver in Recovery. 

7.      * 实际上用于统计data_rate_at_the_receiver，数据离开网络的速度。 

8.       */  

9.     u32 prr_delivered;   

10.   

11.     /* Total number of pkts sent during Recovery.  

12.      * 实际上用于统计sending_rate，数据进入网络的速度。 

13.       */  

14.     u32 prr_out;      

15.     …  

16. }   

@net/ipv4/tcp_input.c

 

1. static inline void tcp_complete_cwr (struct sock *sk)  

2. {  

3.     struct tcp_sock *tp = tcp_sk(sk);  

4.     /* Do not moderate cwnd if it’s already undone in cwr or recovery. */  

5.     if (tp->undo_marker) {  

6.         if (inet_csk(sk)->icsk_ca_state == TCP_CA_CWR)  

7.             tp->snd_cwnd = min(tp->snd_cwnd, tp->snd_ssthresh);  

8.   

9.         else /* PRR */  

10.             tp->snd_cwnd = tp->snd_ssthresh; /* 防止不必要的进入慢启动*/  

11.   

12.         tp->snd_cwnd_stamp = tcp_time_stamp;  

13.     }  

14.     tcp_ca_event(sk, CA_EVENT_COMPLETE_CWR);  

15. }  

[java] view plain copy

1. /* This function implements the PRR algorithm, specifically the PRR-SSRB 

2.  * (proportional rate reduction with slow start reduction bound) as described in 

3.  * http://www.ietf.org/id/draft-mathis-tcpm-proportional-rate-reduction-01.txt. 

4.  * It computes the number of packets to send (sndcnt) based on packets newly 

5.  * delivered: 

6.  *    1) If the packets in flight is larger than ssthresh, PRR spreads the cwnd 

7.  *         reductions across a full RTT. 

8.  *    2) If packets in flight is lower than ssthresh (such as due to excess losses 

9.  *         and/or application stalls), do not perform any further cwnd reductions, but 

10.  *         instead slow start up to ssthresh. 

11.  */  

12.   

13. static void tcp_update_cwnd_in_recovery (struct sock *sk, int newly_acked_sacked,  

14.                 int fast_rexmits, int flag)  

15. {  

16.     struct tcp_sock *tp = tcp_sk(sk);  

17.     int sndcnt = 0; /* 对于每个ACK，可以发送的数据量*/  

18.     int delta = tp->snd_ssthresh – tcp_packets_in_flight(tp);  

19.   

20.     if (tcp_packets_in_flight(tp) > tp->snd_ssthresh) {  

21.   

22.         /* Main idea : sending_rate = CC_reduction_factor * data_rate_at_the_receiver， 

23.           * 按照拥塞算法得到的减小因子，按比例的减小pipe，最终使pipe收敛于snd_ssthresh。 

24.           */  

25.         u64 dividend = (u64) tp->snd_ssthresh * tp->prr_delivered + tp->prior_cwnd – 1;  

26.         sndcnt = div_u64(dividend, tp->prior_cwnd) – tp->prr_out;  

27.   

28.     } else {  

29.         /* tp->prr_delivered – tp->prr_out首先用于撤销之前对pipe的减小，即首先让网络中的数据包恢复守恒。 

30.          * 然后，tp->prr_delivered < tp->prr_out，因为目前是慢启动，网络中数据包开始增加： 

31.          * 对于每个ACK，sndcnt = newly_acked_sacked + 1，使pipe加1，即慢启动。 

32.          * delta使pipe最终收敛于snd_ssthresh。 

33.          */  

34.         sndcnt = min_t(int, delta, max_t(int, tp->prr_delivered – tp->prr_out, newly_acked_sacked) + 1);  

35.     }  

36.   

37.     sndcnt = max(sndcnt, (fast_rexmit ? 1 : 0));  

38.     tp->snd_cwnd = tcp_packets_in_flight(tp) + sndcnt;  

39. }  

@tcp_ack()

[java] view plain copy

1. /* count the number of new bytes that the current acknowledgement indicates have 

2.  * been delivered to the receiver. 

3.  * newly_acked_sacked = delta(snd.una) + delat(SACKed) 

4.  */  

5. newly_acked_sacked = (prior_packets – tp->packets_out) + (tp->sacked_out – prior_sacked);  

6.   

7. …  

8.   

9. tcp_fastretrans_alert(sk, prior_packets – tp->packets_out, newly_acked_sacked, flag);