linux内核工程导论-网络：tcp拥塞控制——PRR

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

快恢复是在检测到堵塞产生的时候将发送窗口下降到1半（怎样才算堵塞由另外的算法决定）。

PRR简介

PRR是最新的linux的默许推荐堵塞算法，之前的是cubic。但是成心思的是，在linux中使用了prr依然可以以cubic作为默许堵塞算法。由于尽人皆知的，堵塞算法大致都是1样的，只是在1些参数和细节调剂上有区分。Linux上的prr实现就是个对tcp_input.c文件的补充，其实不是以模块的情势提供的。

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

窗口机制的内核实现

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

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

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

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

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

堵塞时发送窗口的变化

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

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

Rfc中定义的快速恢复方法

1、定义

进入恢复时

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

cwnd = ssthresh = FlightSize / 2

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

fast_retransmit()

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

Transmit MAX(0, cwnd - pipe)

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

update_scoreboard() pipe = (RFC 3517 pipe algorithm)

Transmit MAX(0, cwnd - pipe)

2、 缺点

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

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

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

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

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

Linux中实现的快速恢复方法

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

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

也就是在1种业务场景产生时，这个算法会把自己置于慢开始的地步。这个场景就是当产生堵塞时，不是由于网络缘由致使发送量减少，而是由于利用程序的缘由致使的。此时cwnd会延续的减小，即便网络没有产生堵塞。由于cwnd是不是减小是由发送的速度决定的，而此时发送速度又是由利用程序决定的。并且当cwnd降落到ssthresh以下的时候，linux的发送策略就变成必须遭到1个ack发能发送1个数据包，此时又进1步加重了此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个包（重传或新的），

这样1来，网络中存在的数据包就减少了3个，在全部快速恢复的进程中，网络中存在的数据量逐步减少为初始的0.7。

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

                 <-------------------------收N个--------------------------

Server                                                                                          Client

                 ----------------发0.7 * N个----------------->

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

这是1个渐变的进程，不断兑换的进程，终究网络中存在的数据量和堵塞窗口都收敛于snd_ssthresh。

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

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

生活不易，码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠