Hybrid Slow Start混合慢啟動算法

傳統(tǒng)的單純采用指數(shù)增長的慢啟動算法有一個無法避免的問題,在臨界進入擁塞避免階段時类腮,特別是在高帶寬長距離網(wǎng)絡(luò)中扔水,容易出現(xiàn)大規(guī)模丟包,進而導(dǎo)致大量數(shù)據(jù)包重傳钥弯,也有可能出現(xiàn)timeout,致使網(wǎng)絡(luò)帶寬利用率下降督禽。
??這里脆霎,本文將介紹一種新的慢啟動方法——Hybrid Slow Start,它在傳統(tǒng)的慢啟動算法中加入了判斷機制狈惫,強制從慢啟動轉(zhuǎn)入擁塞避免睛蛛。這里主要說說其在CUBIC中是怎么實現(xiàn)的,Hybrid Slow Start算法原理本身就不做過多介紹了胧谈,有興趣可以看看本文最后給出的參考文獻忆肾。

變量介紹

#define HYSTART_ACK_TRAIN      0x1 //進入擁塞避免的條件
#define HYSTART_DELAY          0x2 //進入擁塞避免的條件
#define HYSTART_MIN_SAMPLES    8   //表示至少取一個RTT的前8個ACK作為樣本
#define HYSTART_DELAY_MIN      (4u<<3) 
#define HYSTART_DELAY_MAX      (16u<<3)
/* if x > HYSTART_DELAY_MAX,return HYSTART_DELAY_MAX 
 * else if x < HYSTART_DELAY_MIN菱肖,return HYATART_DELAY_MIN
 * else return x
 */
#define HYSTART_DELAY_THRESH clamp(x, HYSTART_DELAY_MIN, HYSTART_DELAY_MAX)
static int hystart __read_mostly = 1;
static int hystart_detect __read_mostly = HYSTART_ACK_TRAIN | HYSART_DELAY;
static int hystart_low_window __read_mostly = 16;
static int hystart_ack_delta __read_mostly = 2;

struct bictcp {
  ...
  u32    delay_min;   //全局最小rtt
  u32    round_start; //記錄慢啟動的起始時間
  u32    curr_rtt;    //記錄樣本中的最小rtt
  u8      found;
  u8      sample_cnt; //樣本計數(shù)變量
  ...
};

兩類退出slow start機制

在Hybrid Slow Start算法中給出了種類判斷機制用來退出慢啟動進入擁塞避免难菌,分別是ACKs train length和Increase in packet delays。

ACKS train length

這里給出一段原文描述蔑滓,在這段描述中說了怎么測ACKs train length以及為什么要用ACKs train length郊酒。

The ACK train length is measured by calculating the sum of inter-arrival times of all the closely spaced ACKs within an RTT round. The train length is strongly affected by the bottleneck bandwidth, routing delays and buffer sizes along the path, and is easily stretched out by congestion caused by cross traffic in the path, so by estimating the train length we can reliably find a safe exit point of Slow Start.

Increase in packet delays

同樣還是一段原文描述,如果你問我為什么不直接翻譯成中文键袱,我不會回答你這個問題的燎窘。

Increase in packet delays during Slow Start may indicate the possibility of the bottleneck router being congested.

但是Increase in packet delays的測量會受到bursty transmission的影響,所以只測一個RTT中剛開始的幾個數(shù)據(jù)包的往返時間來避免bursty transission的影響蹄咖,在后面給出的code中會看到褐健。

函數(shù)實現(xiàn)

hystart重置函數(shù)

static inline void bictcp_hystart_reset(struct sock *sk)
{
    struct tcp_sock *tp = tcp_sk(sk);
    struct bictcp *ca = inet_csk_ca(sk);
    
    ca->round_start = ca->last_ack = bictcp_clock(); //記錄慢啟動的開始時間
    ca->end_seq = tp->snd_nxt;
    ca->curr_rtt = 0;   //重置樣本最小rtt為0
    ca->sample_cnt = 0; //重置樣本計數(shù)為0
}

Hybrid Slow Start實現(xiàn)的核心部分

static void hystart_update(struct sock *sk, u32 delay)
{
    struct tcp_sock *tp = tcp_sk(sk);
    struct bictcp *ca = inet_csk_ca(sk);

    //如果ca->found & hystart_detect為真,表示應(yīng)該進入擁塞避免
    if (!(ca->found & hystart_detect)) {
        u32 now = bictcp_clock(); //獲取當(dāng)前時間

        /* first detection parameter - ack-train detection */
        /* 前后到來的兩個ACK的間隔時間小于hystart_ack_delta才有效 */
        if ((s32)(now - ca->last_ack) <= hystart_ack_delta) {
            ca->last_ack = now;  //更新上一個ACK到來的時間
            /* 每次慢啟動時會重置round_start為0,結(jié)合前面的if條件蚜迅,下面的
             * if成立的條件是:從慢啟動開始到現(xiàn)在經(jīng)過的時間如果大于
             * delay_min>>4舵匾,那么可以進入擁塞避免了。至于為什么選
             * delay_min>>4這個值谁不,鬼知道坐梯。
             */
            if ((s32)(now - ca->round_start) > ca->delay_min >> 4)
                ca->found |= HYSTART_ACK_TRAIN;
        }   

        /* obtain the minimum delay of more than sampling packets */
        /* 如果樣本計數(shù)小于HYSTART_MIN_SAMPLES(默認(rèn)為8) */
        if (ca->sample_cnt < HYSTART_MIN_SAMPLES) {
            if (ca->curr_rtt == 0 || ca->curr_rtt > delay)
                ca->curr_rtt = delay;/* 更新樣本中的最小rtt */

            ca->sample_cnt++;
        } else {//如果樣本大于8了,那么就可以判斷是否要進入擁塞避免了
            /* 如果前面8個樣本中的最小rtt大于全局最小rtt與閾值的和刹帕,那么表示網(wǎng)絡(luò)出
             * 現(xiàn)了擁塞吵血,應(yīng)立馬進入擁塞避免階段,HYSTART_DELAY_THRESH()的返
             * 回值在前面的變量介紹中有說明偷溺。
            if (ca->curr_rtt > ca->delay_min +
                HYSTART_DELAY_THRESH(ca->delay_min>>4))
                ca->found |= HYSTART_DELAY;
        }   
        /*  
         * Either one of two conditions are met,
         * we exit from slow start immediately.
         */
        /* 如果為真就進入擁塞避免 */
        if (ca->found & hystart_detect)
            tp->snd_ssthresh = tp->snd_cwnd;
    }   
}

最近做實驗需要探測網(wǎng)絡(luò)帶寬蹋辅,需要用到Hybrid Slow Start,所以看了paper和其在Linux CUBIC算法中的實現(xiàn)挫掏,然后就寫了這篇blog侦另。
參考文獻:Hybrid Slow Start for High-Bandwidth and Long-Distance Networks

最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末,一起剝皮案震驚了整個濱河市尉共,隨后出現(xiàn)的幾起案子褒傅,更是在濱河造成了極大的恐慌,老刑警劉巖爸邢,帶你破解...
    沈念sama閱讀 216,591評論 6 501
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件,死亡現(xiàn)場離奇詭異拿愧,居然都是意外死亡杠河,警方通過查閱死者的電腦和手機,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 92,448評論 3 392
  • 文/潘曉璐 我一進店門浇辜,熙熙樓的掌柜王于貴愁眉苦臉地迎上來券敌,“玉大人,你說我怎么就攤上這事柳洋〈纾” “怎么了?”我有些...
    開封第一講書人閱讀 162,823評論 0 353
  • 文/不壞的土叔 我叫張陵熊镣,是天一觀的道長卑雁。 經(jīng)常有香客問我,道長绪囱,這世上最難降的妖魔是什么测蹲? 我笑而不...
    開封第一講書人閱讀 58,204評論 1 292
  • 正文 為了忘掉前任,我火速辦了婚禮鬼吵,結(jié)果婚禮上扣甲,老公的妹妹穿的比我還像新娘。我一直安慰自己齿椅,他們只是感情好琉挖,可當(dāng)我...
    茶點故事閱讀 67,228評論 6 388
  • 文/花漫 我一把揭開白布启泣。 她就那樣靜靜地躺著,像睡著了一般示辈。 火紅的嫁衣襯著肌膚如雪寥茫。 梳的紋絲不亂的頭發(fā)上,一...
    開封第一講書人閱讀 51,190評論 1 299
  • 那天顽耳,我揣著相機與錄音坠敷,去河邊找鬼。 笑死射富,一個胖子當(dāng)著我的面吹牛膝迎,可吹牛的內(nèi)容都是我干的。 我是一名探鬼主播胰耗,決...
    沈念sama閱讀 40,078評論 3 418
  • 文/蒼蘭香墨 我猛地睜開眼限次,長吁一口氣:“原來是場噩夢啊……” “哼!你這毒婦竟也來了柴灯?” 一聲冷哼從身側(cè)響起卖漫,我...
    開封第一講書人閱讀 38,923評論 0 274
  • 序言:老撾萬榮一對情侶失蹤,失蹤者是張志新(化名)和其女友劉穎赠群,沒想到半個月后羊始,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體,經(jīng)...
    沈念sama閱讀 45,334評論 1 310
  • 正文 獨居荒郊野嶺守林人離奇死亡查描,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點故事閱讀 37,550評論 2 333
  • 正文 我和宋清朗相戀三年突委,在試婚紗的時候發(fā)現(xiàn)自己被綠了。 大學(xué)時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片冬三。...
    茶點故事閱讀 39,727評論 1 348
  • 序言:一個原本活蹦亂跳的男人離奇死亡匀油,死狀恐怖,靈堂內(nèi)的尸體忽然破棺而出勾笆,到底是詐尸還是另有隱情敌蚜,我是刑警寧澤,帶...
    沈念sama閱讀 35,428評論 5 343
  • 正文 年R本政府宣布窝爪,位于F島的核電站弛车,受9級特大地震影響,放射性物質(zhì)發(fā)生泄漏蒲每。R本人自食惡果不足惜帅韧,卻給世界環(huán)境...
    茶點故事閱讀 41,022評論 3 326
  • 文/蒙蒙 一、第九天 我趴在偏房一處隱蔽的房頂上張望啃勉。 院中可真熱鬧忽舟,春花似錦、人聲如沸。這莊子的主人今日做“春日...
    開封第一講書人閱讀 31,672評論 0 22
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽。三九已至浩姥,卻和暖如春挑随,著一層夾襖步出監(jiān)牢的瞬間,已是汗流浹背勒叠。 一陣腳步聲響...
    開封第一講書人閱讀 32,826評論 1 269
  • 我被黑心中介騙來泰國打工兜挨, 沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留,地道東北人眯分。 一個月前我還...
    沈念sama閱讀 47,734評論 2 368
  • 正文 我出身青樓拌汇,卻偏偏與公主長得像,于是被迫代替她去往敵國和親弊决。 傳聞我的和親對象是個殘疾皇子噪舀,可洞房花燭夜當(dāng)晚...
    茶點故事閱讀 44,619評論 2 354

推薦閱讀更多精彩內(nèi)容

  • 文/蔥蔥 早上出小區(qū)与倡,走在上班的路上,突然聽見120救護車高嚷著飛快行駛在馬路上昆稿,心里正琢磨著可能是小區(qū)某戶人家的...
    蔥蔥_閱讀 776評論 12 11
  • 上次說了最近瘦身的見證纺座,其實自從心里不匱乏了開始,突然感覺不餓了溉潭,今天又去吸引了健身卡净响! 其實我超級討厭運動...
    貓公主喵閱讀 102評論 0 2
  • 從深圳到廣州 這個距離 417等了兩
    cy_chan閱讀 180評論 0 0
  • 就像個默默無聞的教徒,做了自己覺得所有應(yīng)該做的事岛抄,卻還是任由上帝宰割别惦。毫無還擊之力狈茉。當(dāng)人力無法掌控的時候夫椭,就開始相...
    果綠a閱讀 350評論 0 0