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

變量介紹

#define HYSTART_ACK_TRAIN      0x1 //進(jìn)入擁塞避免的條件
#define HYSTART_DELAY          0x2 //進(jìn)入擁塞避免的條件
#define HYSTART_MIN_SAMPLES    8   //表示至少取一個(gè)RTT的前8個(gè)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; //記錄慢啟動(dòng)的起始時(shí)間
  u32    curr_rtt;    //記錄樣本中的最小rtt
  u8      found;
  u8      sample_cnt; //樣本計(jì)數(shù)變量
  ...
};

兩類退出slow start機(jī)制

在Hybrid Slow Start算法中給出了種類判斷機(jī)制用來退出慢啟動(dòng)進(jìn)入擁塞避免，分別是ACKs train length和Increase in packet delays。

ACKS train length

這里給出一段原文描述，在這段描述中說了怎么測(cè)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

同樣還是一段原文描述，如果你問我為什么不直接翻譯成中文，我不會(huì)回答你這個(gè)問題的。

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

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

函數(shù)實(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(); //記錄慢啟動(dòng)的開始時(shí)間
    ca->end_seq = tp->snd_nxt;
    ca->curr_rtt = 0;   //重置樣本最小rtt為0
    ca->sample_cnt = 0; //重置樣本計(jì)數(shù)為0
}

Hybrid Slow Start實(shí)現(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)該進(jìn)入擁塞避免
    if (!(ca->found & hystart_detect)) {
        u32 now = bictcp_clock(); //獲取當(dāng)前時(shí)間

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

        /* obtain the minimum delay of more than sampling packets */
        /* 如果樣本計(jì)數(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了，那么就可以判斷是否要進(jìn)入擁塞避免了
            /* 如果前面8個(gè)樣本中的最小rtt大于全局最小rtt與閾值的和，那么表示網(wǎng)絡(luò)出
             * 現(xiàn)了擁塞，應(yīng)立馬進(jìn)入擁塞避免階段，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.
         */
        /* 如果為真就進(jìn)入擁塞避免 */
        if (ca->found & hystart_detect)
            tp->snd_ssthresh = tp->snd_cwnd;
    }   
}

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