Windows XP Windows 7 Windows 2003 Windows Vista Windows教程綜合 Linux 系統教程
Windows 10 Windows 8 Windows 2008 Windows NT Windows Server 電腦軟件教程
 Windows教程網 >> Linux系統教程 >> Linux系統常見問題解答 >> Googles BBR TCP擁塞控制算法的四個變速引擎

Googles BBR TCP擁塞控制算法的四個變速引擎

日期:2017/1/20 17:34:52      編輯:Linux系統常見問題解答
台風海馬來臨前的兩個幾乎通宵的夜晚,我用一篇關於BBR算法的文章的迎接海馬!公司在昨晚響應深圳市停工,停課號召,發布了在家辦公(請注意,不是放假...)通知...其實吧,我覺得停電才是王道,你覺得呢?
在前一篇關於bbr算法的文章《來自Google的TCP BBR擁塞控制算法解析》(這可能是第一篇中文版的bbr算法相關的文章)中,我簡述了bbr算法的框架,算是大致介紹了。本文中,我想深入bbr算法pipe狀態機的一些細節,但是我不會繼續使用”狀態機“這樣的術語,我選擇使用變速引擎這樣的說法,來展示一個現代高速的TCP變速引擎是如何為數據傳輸提供強勁動力的。
這組引擎完全從bbr算法中抽象生成,想法來自於我們奔跑或者開車的過程,突然發現,bbr算法的思想精髓簡直就和我們在人多的跑道上奔跑以及在高速公路上開車時的思路完全一致啊!
我不禁感歎萬物的統一並詛咒虛無,在胃裡灼燒感正嗨的時候,完成了本文!
就要開始了!

1.Linux TCP迄今為止的擁塞控制機制

我並不了解其它平台的TCP擁塞控制算法實現,但是我了解Linux的,迄今為止,在bbr剛剛被引入之後,Linux的擁塞控制算法分為兩類:

保守模式

bbr之前以Reno為基礎,包括Reno,NewReno,...原理幾乎都不變,這些算法有兩個特點:
1).反饋性差
以Reno為例,TCP發送端在擁塞避免階段收到ACK後,無條件地將cwnd增加1/cwnd,在慢啟動階段收到ACK後cwnd增加1,這是毫無根據的,然而Reno並沒有什麼更好的做法,只能瞎猜!後來的Westwood,Vegas,BIC等算法,相對Reno/NewReno更加智能了一步,但還是傻瓜!再往後,CUBIC搞了一個高大上的以三次方程凸凹曲線來抉擇的增窗機制,看似十分地“博士”,並且十分地“經理”,然而還是無法高效利用互聯網的空閒帶寬,相反在碰到異常現象,比如丟包,擁塞的時候,反應太過保守,在保守的路線上趨於激烈,即激烈地保守降低擁塞窗口,更加可悲的是,這個窗口下降的過程並不受這些算法所控制。
2).擁塞算法被接管
在TCP擁塞控制機制發現丟包時(即RTO或者N次重復的ACK等),TCP會完全接管擁塞控制算法,自己控制擁塞窗口。然而問題是,這種所謂的丟包可能並不是真的丟包,這只是TCP認為丟包而已,這是30年前的丟包判斷機制了...真的丟包了嗎?不一定啊!然而只要TCP認為丟包,就會接管擁塞控制算法(起碼在Linux上是這樣...)。這使我不得開心顏!我曾經修改過Linux TCP的PRR邏輯,只求降窗過程不那麼猛而已...Linux TCP為了這個降窗也是費盡心思,先後經歷了多種方案,比如Halving Rate,PRR等,唉,干嘛不直接都交給擁塞控制算法呢??

總的來講,bbr之前的擁塞控制邏輯在執行過程中會分為兩種階段,即正常階段和異常階段。在正常階段中,TCP模塊化的擁塞控制算法主導窗口的調整,在異常階段中,TCP核心的擁塞控制狀態機從擁塞控制算法那裡接管窗口的計算,在Linux的實現中,這是由以下邏輯表示的:

static void tcp_cong_control(struct sock *sk, u32 ack, u32 acked_sacked,
                 int flag)
{
    if (tcp_in_cwnd_reduction(sk)) { // 異常模式
        /* Reduce cwnd if state mandates */
        // 在進入窗口下降邏輯之前,還需要tcp_fastretrans_alert來搜集異常信息並處理異常過程。
        tcp_cwnd_reduction(sk, acked_sacked, flag);
    } else if (tcp_may_raise_cwnd(sk, flag)) { // 正常模式或者安全的異常模式!
        /* Advance cwnd if state allows */
        tcp_cong_avoid(sk, ack, acked_sacked);
    }
    tcp_update_pacing_rate(sk);
}

是否進入tcp_cwnd_reduction的異常模式,是由下面的邏輯來判斷的:
if (tcp_ack_is_dubious(sk, flag)) {
    is_dupack = !(flag & (FLAG_SND_UNA_ADVANCED | FLAG_NOT_DUP));
    tcp_fastretrans_alert(sk, acked, is_dupack, &flag, &rexmit);
}

這個會讓TCP擁塞模塊怎麼想?!除了拋出一個ssthresh之外對異常的處理無能為力,事實上這根本與它無關!

全速模式

bbr之後以bbr為基礎的算法,其核心並不是bbr本身,而是bbr算法為了運行對Linux TCP框架的修改!bbr並不是最終的算法,更不是神話,它只是個開始,它把TCP的tcp_ack完全改了,改了之後,如果你有什麼好的想法,便可以自由發揮了!
都改了什麼呢?我們看一下核心函數tcp_cong_control就知道了(我這裡不談2.6內核以及3.x內核中沒有抽離cong_control的版本):
static void tcp_cong_control(struct sock *sk, u32 ack, u32 acked_sacked,
                 int flag, const struct rate_sample *rs)
{
    const struct inet_connection_sock *icsk = inet_csk(sk);
    // 這裡是新邏輯,如果回調中宣稱自己有能力解決任何擁塞問題,那麼交給它!
    if (icsk->icsk_ca_ops->cong_control) {
        icsk->icsk_ca_ops->cong_control(sk, rs);
        // 直接return!TCP核心不再過問。
        return;
    }
    // 這是老的邏輯。
    if (tcp_in_cwnd_reduction(sk)) {
        /* Reduce cwnd if state mandates */
        // 如果不是Open狀態...記住,tcp_cwnd_reduction並不受擁塞控制算法控制!!
        tcp_cwnd_reduction(sk, acked_sacked, flag);
    } else if (tcp_may_raise_cwnd(sk, flag)) {
        /* Advance cwnd if state allows */
        tcp_cong_avoid(sk, ack, acked_sacked);
    }
    tcp_update_pacing_rate(sk);
}

bbr算法實現了cong_control回調函數,而你可能實現一個別的,寫在cong_control中。
理解了現狀,當然就知道問題之所在了,bbr解決了問題。當然,Appex也解決了問題,但是那幫人是傻逼!這不符合耶稣的邏輯,Appex會受到詛咒。

2.bbr並不基於預測

不基於數據反饋的預測都是假的,不真實的,騙人的。這就是為什麼基於大數據的人工智能比基於算法的人工智能更厲害的原因,算法再猛都是扯淡,只有數據才能訓練出聰明的模型。在TCP擁塞控制算法領域,CUBIC的三次凸凹函數看起來是那麼的晦澀卻顯得高大上,大多數人無力深究這個算法的細節,然而bbr算法卻是一個隨便什麼人都看得懂的....

bbr不斷采集連接內時間窗口內的最大帶寬max-bw和最小RTT min-rtt(見下面的win_minmax),並以此計算發送速率和擁塞窗口,依據反饋的實際帶寬bw和max-rtt調節增益系數。其背後的思想是,一旦在一個時間窗口內采集到更大的帶寬和更小的rtt,bbr就認為客觀上它們的乘積,即BDP是可以填充的客觀管道容量,並按此作為基准,萬一沒有達到,bbr會認為這是發生了擁塞,調小增益系數即可,但在時間窗口范圍內並不改變基准(時間局部性使然),由於增益系數是根據反饋調節的且基准BDP不變,一旦擁塞緩解,bbr可以第一時間發現並增大增益系數!

bbr能做到以上這些並工作地很好,全在於tcp擁塞狀態機控制邏輯不會打擾它的行為,而這些在之前的擁塞控制算法中幾乎是做不到的,比如CUBIC算法,一旦丟包,CUBIC便會被接管,直到Linux按照硬性標准判斷其TCP擁塞狀態已經恢復到了Open狀態。
此外,更加重要的,bbr算法采用真實的值,它的帶寬bw是真實測量出來的(測量方法見《來自Google的TCP BBR擁塞控制算法解析》),而RTT則包含了原始數據包的RTT以及SACK數據包的RTT等所有可以測量的RTT,然而我們無法預測一個TCP連接的生命周期到底有多久,為了讓采樣結果更加平滑,幾乎所有的算法都會采用“移動指數平均”的方案,RTO為了展示波動的影響,加入了一個srtt的類似方差的值,但是這些都是不真實的。brr算法采用了真實的值!
Copyright © Windows教程網 All Rights Reserved