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);
下一篇 滑動窗口的最大值
程序員人生，我編程，我富裕，記住wfuyu網，php教程，php學習，php手冊，CMS模版制作
聲明：本站大部分內容是作者原創，少部分收集于互聯網供大家一起學習，原版權很多不明，如有侵權請聯系本站，謝謝！
粵ICP備14040726號-1?? 2015-2020 程序員人生 版權所有
