Prr是rfc对快速回复算法的改进，实际的在linux中的实现是谷歌的哥们做的。这篇文章改编自网友的另外一篇很多英文的文章，为了我自己的理解，我就整理了1下。
快恢复是在检测到堵塞产生的时候将发送窗口下降到1半（怎样才算堵塞由另外的算法决定）。
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的方案也有问题就是可以致使比较长的恢复时间或过量重传。
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网页和是频率中有都有不好的表现。
由于rfc的问题，linux做了优化。快速恢复时不时等待收到ack以后才继续发送数据，而是只要进入快速恢复就依然继续发送数据，但是发送数据的窗口立即下降为原来窗口的1半。这样就避免了半RTT安静问题和减缓了突发重传的问题。
但是同时带来了1个问题，就是如果确切是产生了发送的网络堵塞，发送窗口会快速下降，1方面压抑了自己向网络中发送数据的速度（看起来是对的），但是1方面也把自己的后续发送数据的能力下降到慢开始的级别。
也就是在1种业务场景产生时，这个算法会把自己置于慢开始的地步。这个场景就是当产生堵塞时，不是由于网络缘由致使发送量减少，而是由于利用程序的缘由致使的。此时cwnd会延续的减小，即便网络没有产生堵塞。由于cwnd是不是减小是由发送的速度决定的，而此时发送速度又是由利用程序决定的。并且当cwnd降落到ssthresh以下的时候，linux的发送策略就变成必须遭到1个ack发能发送1个数据包，此时又进1步加重了此tcp管道的性能恶化。
所以就会出现tcp的效力非正确的快速降落。
原来的算法主要有两个问题：产生堵塞的时候发送窗口快速降落，降落速度过快；降落的最下限是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的改动包括在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);
下一篇 滑动窗口的最大值