傳統(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