先說幾個輔助的宏，因為內核不支持浮點運算，當然還有實現需要，minstrel對很多浮點值做了縮放：
/*
scaled fraction values
*/
#define
MINSTREL_SCALE 16
#define
MINSTREL_FRAC(val, div) (((val) << MINSTREL_SCALE) / div)
#define
MINSTREL_TRUNC(val) ((val) >> MINSTREL_SCALE)
MINSTREL_SCALE是一個放大的倍數，minstrel設定的是16，縮放16位也就是2^16倍，我不知道為什么要設置成這么大的數，不過沒有關系不影響理解。MINSTREL_FRAC是兩個數相除之后放大，MINSTREL_TRUNC則是逆運算，將某個被放大的數縮小。
下面進行源碼分析，根據對外暴露的結構體對指針函數的定義：
static
struct
rate_control_ops mac80211_minstrel_ht =
{
.name
=
"
minstrel_ht
"
,
.tx_status
= minstrel_ht_tx_status,
.get_rate = minstrel_ht_get_rate,
.rate_init =
minstrel_ht_rate_init,
.rate_update
=
minstrel_ht_rate_update,
.alloc_sta
=
minstrel_ht_alloc_sta,
.free_sta
=
minstrel_ht_free_sta,
.alloc
=
minstrel_ht_alloc,
.free
=
minstrel_ht_free,
#ifdef CONFIG_MAC80211_DEBUGFS
.add_sta_debugfs
=
minstrel_ht_add_sta_debugfs,
.remove_sta_debugfs
=
minstrel_ht_remove_sta_debugfs,
#endif
};
我們需要著重關注核心的三個函數：tx_status負責每次發送完聚合幀之后根據ACK的狀況更新各個速率狀態，get_rate負責每次要發新的數據包的時候指定發送速率，rate_init在與另一站點建立連接的時候初始化相關參數。下面首先介紹一個抽隨機速率用的表的生成，然后按照rate_init、get_rate、tx_status的順序介紹minstrel的原理。
1. 初始化探測速率表
minstrel對速率的管理是通過速率組來管理的，這關乎幾個重要的變量：
const struct mcs_group minstrel_mcs_groups[];
static u8 sample_table[SAMPLE_COLUMNS][MCS_GROUP_RATES];
mi->groups[]
先說minstrel_mcs_groups，我的實驗環境最多支持雙流，minstrel_mcs_groups也就是一個長度為8的數組，如果是三流就是長度為12的數組，這8個group的配置按順序分別是：
| 組號 | 空間流數 | 是否支持SGI | 20MHz/40MHz |
| 0 | 1 | 否 | 20 |
| 1 | 2 | 是 | 20 |
| 2 | 1 | 否 | 20 |
| 3 | 2 | 是 | 20 |
| 4 | 1 | 否 | 40 |
| 5 | 2 | 是 | 40 |
| 6 | 1 | 否 | 40 |
| 7 | 2 | 是 | 40 |
這個變量存的是這幾個速率組不變的配置信息，mi->groups這個數組和minstrel_mcs_groups相對應，存儲在對應配置下8個速率的動態數據統計。
sample_table是隨機生成的一個速率表，本節就是講這個表的生成和作用。
當Minstrel模塊加載的時候，首先初始化速率表，也就是sample_table，當需要進行探測的時候，探測順序就是以這個速率表做參考：
static u8
sample_table[SAMPLE_COLUMNS][MCS_GROUP_RATES];
static
void
init_sample_table(
void
)
{
int
col, i, new_idx;
u8 rnd[MCS_GROUP_RATES];
memset(sample_table,
0xff
,
sizeof
(sample_table));
for
(col =
0
; col <
SAMPLE_COLUMNS
; col++
) {
for
(i =
0
; i <
MCS_GROUP_RATES
; i++
) {
get_random_bytes(rnd,
sizeof
(rnd));
new_idx
= (i + rnd[i]) %
MCS_GROUP_RATES;
while
(sample_table[col][new_idx] !=
0xff
)
new_idx
= (new_idx +
1
) %
MCS_GROUP_RATES;
sample_table[col][new_idx]
=
i;
}
}
}
SAMPLE_COLUMNS的默認取值是10，MCS_GROUP_RATES是每組MCS中有幾個速率，也就是8（單流、雙流、三流里面各有8個速率），這個速率取樣表就是一個10*8的方陣。這段函數生成的速率表，一共10行，每一行都是0-7這七個數字的隨機分布，minstrel是隨機探測，但是用哪個速率不是在發送的時候才隨機獲取的，而是提前隨機生成這個表，發送的時候依次遍歷這個表，所以說這個速率表其實沒有什么講究，就是避免了在運行過程中頻繁的抽隨機數罷了，這個表已經提前生成了10組MCS隨機排列的序列，運行過程中只要順序讀取，就是隨機探測了。
2. 初始化探測的相關參數
minstrel_ht_rate_init和minstrel_ht_rate_update分別在連接站點初始化或者需要更新的時候被調用，他們的本質都是調用了minstrel_ht_update_caps，其中和速率調整相關的呢是這么幾句：
mi->avg_ampdu_len = MINSTREL_FRAC(1, 1);
/*
When using MRR, sample more on the first attempt, without delay
*/
if
(mp->
has_mrr) {
mi
->sample_count = 16;
mi->sample_wait = 0
;
}
else
{
mi
->sample_count =
8
;
mi
->sample_wait =
8
;
}
mi
->sample_tries = 4
;
……
for
(i =
0
; i < ARRAY_SIZE(mi->groups); i++
) {
u16 req
=
0
;
mi
->groups[i].supported =
0
;
if
(minstrel_mcs_groups[i].flags &
IEEE80211_TX_RC_SHORT_GI) {
if
(minstrel_mcs_groups[i].flags &
IEEE80211_TX_RC_40_MHZ_WIDTH)
req
|=
IEEE80211_HT_CAP_SGI_40;
else
req
|=
IEEE80211_HT_CAP_SGI_20;
}
if
(minstrel_mcs_groups[i].flags &
IEEE80211_TX_RC_40_MHZ_WIDTH)
req
|=
IEEE80211_HT_CAP_SUP_WIDTH_20_40;
if
((sta_cap & req) !=
req)
continue
;
mi
->groups[i].supported =
mcs
->rx_mask[minstrel_mcs_groups[i].streams -
1
];
if
(mi->
groups[i].supported)
n_supported
++
;
}
if
(!
n_supported)
goto
use_legacy;
這一段的主要作用呢，就是初始化平均AMPDU長度（聚合幀長度）為1，因為我們需要MRR（Multi-rate retry，多速率重傳），設置sample_count=16\sample_wait=0\sample_tries=4，這三個參數和探測的頻率相關，后面會介紹，最后，確定本文最前面介紹的關于（空間流數、SGI、帶寬）設置的數組中的每一數組項是不是被硬件支持。
3. 發送時確定發送速率
minstrel_ht_get_rate是速率調整最重要的兩個函數之一，它決定了當前待發送數據包的發送速率。
if
(rate_control_send_low(sta, priv_sta, txrc))
return
;
首先，當目標站點不存在，或者本次發送不需要等ACK的時候，為了確保數據包盡可能被對方正確接收，那么會直接用傳統速率來發送，不給它分配MCS速率。
下面獲取本次取樣的速率：
sample_idx = minstrel_get_sample_rate(mp, mi);
深入minstrel_get_sample_rate：
mg = &mi->groups[mi->
sample_group];
sample_idx
= sample_table[mg->column][mg->
index];
mr
= &mg->
rates[sample_idx];
sample_idx
+= mi->sample_group *
MCS_GROUP_RATES;
minstrel_next_sample_idx(mi);
前面已經介紹，有一個隨機生成的速率表用作獲取隨機數用，首先在這個速率表中選取下一個sample_idx，之后，調用minstrel_next_sample_idx把mi->sample_group指向下一個可用的group，這個group就是前面介紹的擁有空間流數、SGI、帶寬配置的組了。然后sample_idx在自身取值的基礎上加上了sample_group*MCS_GROUP_RATES，所以這個sample_idx可以用來得到當前用的第幾個取樣組，比如sample_idx=27，那么就是8*3+4，它表示的就是第4個速率組（雙流、SGI、20MHz）的第四個速率，因為是雙流，就表示MCS11。正常情況下，minstrel_get_sample_rate這個函數會把sample_idx返回，如果不探測，則返回-1，下面繼續看minstrel_get_sample_rate的幾個返回-1的情況：
if
(!mp->has_mrr && (mr->probability > MINSTREL_FRAC(
95
,
100
)))
return
-
1
;
如果不支持mrr（多速率重傳），并且當前速率的投遞率已經達到了95%以上，就不再取樣。
if
(minstrel_get_duration(sample_idx) >
minstrel_get_duration(mi
->
max_tp_rate)) {
if
(mr->sample_skipped <
20
)
return
-
1
;
if
(mi->sample_slow++ >
2
)
return
-
1
;
}
這里把剛剛得到的這個要取樣的速率sample_idx和當前吞吐率最高的速率進行比較，那么這個duration是個什么東西？這個duration就是對網卡用當前速率發送一個數據包所用時間的估算，duration越大，基本等效于速率值越低，具體含義如下：
#define
AVG_PKT_SIZE 1200
#define
MCS_NBITS (AVG_PKT_SIZE << 3)
#define
MCS_NSYMS(bps) ((MCS_NBITS + (bps) - 1) / (bps))
#define
MCS_SYMBOL_TIME(sgi, syms) \
(sgi
?
\
((syms)
*
18
+
4
) /
5
:
/*
syms * 3.6 us
*/
\
(syms)
<<
2
/*
syms * 4 us
*/
\
)
#define
MCS_DURATION(streams, sgi, bps) MCS_SYMBOL_TIME(sgi, MCS_NSYMS((streams) * (bps)))
/*
* Define group sort order: HT40 -> SGI -> #streams
*/
#define
GROUP_IDX(_streams, _sgi, _ht40) \
MINSTREL_MAX_STREAMS
*
2
* _ht40 +
\
MINSTREL_MAX_STREAMS
* _sgi +
\
_streams
-
1
/*
MCS rate information for an MCS group
*/
#define
MCS_GROUP(_streams, _sgi, _ht40) \
[GROUP_IDX(_streams, _sgi, _ht40)]
=
{ \
.streams
=
_streams, \
.flags
=
\
(_sgi
? IEEE80211_TX_RC_SHORT_GI :
0
) |
\
(_ht40
? IEEE80211_TX_RC_40_MHZ_WIDTH :
0
), \
.duration
=
{ \
MCS_DURATION(_streams, _sgi, _ht40
?
54
:
26
), \
MCS_DURATION(_streams, _sgi, _ht40
?
108
:
52
), \
MCS_DURATION(_streams, _sgi, _ht40
?
162
:
78
), \
MCS_DURATION(_streams, _sgi, _ht40
?
216
:
104
), \
MCS_DURATION(_streams, _sgi, _ht40
?
324
:
156
), \
MCS_DURATION(_streams, _sgi, _ht40
?
432
:
208
), \
MCS_DURATION(_streams, _sgi, _ht40
?
486
:
234
), \
MCS_DURATION(_streams, _sgi, _ht40
?
540
:
260
) \
} \
}
這一段宏的定義比較復雜，簡單來說，假定平均每個數據包長度是1200字節，也就是（1200<<3）即（1200*8）bits，根據每個碼元（symbol）包含幾個bit算出來這個數據包一共有多少碼元（MCS_NSYMS），最后根據數據率計算數據包在每一個MCS參數下的發送延時。
花了這么多時間介紹minstrel_get_sample_rate，因為這個函數包括了最主要的，探測速率從哪兒來的問題，現在回到minstrel_ht_get_rate，剛才是從：
sample_idx = minstrel_get_sample_rate(mp, mi);
展開的，獲取到sample_idx，后面就是重頭戲了：
if
(sample_idx >=
0
) {
sample
=
true
;
minstrel_ht_set_rate(mp, mi,
&ar[0], sample_idx, true,
false
);
info
->flags |=
IEEE80211_TX_CTL_RATE_CTRL_PROBE;
}
else
{
minstrel_ht_set_rate(mp, mi,
&ar[0], mi->max_tp_rate, false,
false
);
}
如果sample_idx為-1，那么就不探測，仍然用之前確定的最高吞吐率的速率mi->max_tp_rate來發送，除了前面說的幾個情況下會返回-1之外，還有一個重要的控制，就是關于探測周期的控制，本文最后一部分會做介紹，下面繼續看需要探測的情況下怎么選擇速率，minstrel_ht_set_rate這個函數的其他參數可以不關注，重點是我標紅的這三個，第一個是一個（struct ieee80211_tx_rate）類型的參數，最后驅動底層就是從這個結構體里面拿到發送的MCS、重傳次數、發送帶寬等參數，minstrel用一個ar數組來存，ar[0]是第一個速率，重傳多次仍然失敗的話就用ar[1]，以此類推，第二個參數就是速率索引sample_idx/max_tp_rate，第三個參數代表當前幀是不是探測采樣用的幀。對這個函數要重點說的，是重傳策略：
if
(sample)
rate
->count =
1
;
else
if
(mr->probability < MINSTREL_FRAC(
20
,
100
))
rate
->count =
2
;
else
if
(rtscts)
rate
->count = mr->
retry_count_rtscts;
else
rate
->count = mr->retry_count;
如果當前速率用作探測，則只發送一次，如果當前速率的投遞率小于20%，則發兩次，其他情況下重傳次數依賴于mr->retry_count，這個變量是在每次更新各個速率狀態之后更新的，如果該速率的投遞率小于10%，初始為1，否則初始為2，然后根據幀平均發送時間還要適當增加。
最后就是MRR，也就是多速率重傳的其它幾個速率怎么設置了：
if
(mp->hw->max_rates >=
3
) {
if
(sample_idx >=
0
)
minstrel_ht_set_rate(mp, mi,
&ar[
1
], mi->max_tp_rate,
false
,
false
);
else
minstrel_ht_set_rate(mp, mi,
&ar[
1
], mi->max_tp_rate2,
false
,
true
);
minstrel_ht_set_rate(mp, mi,
&ar[
2
], mi->max_prob_rate,
false
, !
sample);
ar[
3
].count =
0
;
ar[
3
].idx = -
1
;
}
else
if
(mp->hw->max_rates ==
2
) {
minstrel_ht_set_rate(mp, mi,
&ar[
1
], mi->max_prob_rate,
false
, !
sample);
ar[
2
].count =
0
;
ar[
2
].idx = -
1
;
}
else
{
ar[
1
].count =
0
;
ar[
1
].idx = -
1
;
}
如果驅動支持的速率個數多于3，那么按照max_tp_rate>max_prob_rate的順序來設置剩下兩個速率，如果第一個速率不作為探測速率，也就是說第一個速率是用max_tp_rate，那么第二三個速率就用max_tp_rate2>max_prob_rate，如果底層支持的多速率就是能支持兩個，則第二速率就用max_prob_rate發送，這個速率是投遞率最高的速率，確保在有限次發送后正確傳輸。
4. 更新各個速率狀態
minstrel_ht_tx_status函數是當每個幀發送完成時的回調函數，但是每個聚合幀中只有一個幀攜帶了該聚合幀都使用了哪些速率發送、哪一次發送才成功等我們需要的信息，因此對于未攜帶這些信息的幀，直接返回不予處理：
if
((info->flags & IEEE80211_TX_CTL_AMPDU) &&
!(info->flags &
IEEE80211_TX_STAT_AMPDU))
return
;
之后根據ar[0]、ar[1]和ar[2]里面攜帶的實際發送次數，得到每個速率在本次發送中共發送了多少個幀（指單幀）、成功了多少個（單幀）。然后進入核心處理邏輯：
rate = minstrel_get_ratestats(mi, mi->
max_tp_rate);
if
(rate->attempts >
30
&&
MINSTREL_FRAC(rate
->success, rate->attempts) <
MINSTREL_FRAC(
20
,
100
))
minstrel_downgrade_rate(mi,
&mi->max_tp_rate,
true
);
rate2
= minstrel_get_ratestats(mi, mi->
max_tp_rate2);
if
(rate2->attempts >
30
&&
MINSTREL_FRAC(rate2
->success, rate2->attempts) <
MINSTREL_FRAC(
20
,
100
))
minstrel_downgrade_rate(mi,
&mi->max_tp_rate2,
false
);
if
(time_after(jiffies, mi->stats_update + (mp->update_interval /
2
* HZ) /
1000
)) {
minstrel_ht_update_stats(mp, mi);
if
(!(info->flags &
IEEE80211_TX_CTL_AMPDU))
minstrel_aggr_check(sta, skb);
}
minstrel_downgrade_rate是把系統當前的max_tp_rate或者max_tp_rate2切換到比原來速率所在組的前一個較低或相同流數的組的對應值上，比如，現在的max_tp_rate是第3個group的max_tp_rate，此時就會判斷，第2組包含的速率都是幾個空間流的，如果組3是雙流的，則組2是單流或雙流的話，就把組2的max_tp_rate作為當前系統的max_tp_rate，如果組3是單流，但組2是雙流，就會再看組1是不是單流，以此類推。
根據驅動的注釋，是為了防止空間流突然不能用，比如本來用的雙流，有一個流突然不起作用了，所以這里判斷一下，如果max_tp_rate或者max_tp_rate2已經嘗試30次以上，投遞率還不超過20%，則降空間流，最后要解決的一個問題就是，每個組的max_tp_rate和max_tp_rate2是怎么算出來的，看代碼的最后幾行，每過(mp->update_interval / 2 * HZ) / 1000 這些時間（單位是jiffies），就會更新整個速率表中各個mcs_group，針對每個mcs_group，會遍歷8個MCS：
for
(i =
0
; i < MCS_GROUP_RATES; i++
) {
if
(!(mg->supported &
BIT(i)))
continue
;
mr
= &mg->
rates[i];
mr
->retry_updated =
false
;
index
= MCS_GROUP_RATES * group +
i;
minstrel_calc_rate_ewma(mr);
minstrel_ht_calc_tp(mi, group, i);
針對每一個速率，也就是mr，都會調用minstrel_calc_rate_ewma去計算吞吐率和投遞率的加權平均：
mr->sample_skipped =
0
;
mr
->cur_prob = MINSTREL_FRAC(mr->success, mr->
attempts);
if
(!mr->
att_hist)
mr
->probability = mr->
cur_prob;
else
mr->probability = minstrel_ewma(mr->probability, mr->
cur_prob, EWMA_LEVEL);
mr
->att_hist += mr->
attempts;
mr
->succ_hist += mr->success;
計算這個速率在這個計算周期內的投遞率cur_prob，EWMA_LEVEL默認為75，如果之前沒有發送成功過，也就是歷史嘗試數等于0，就直接更新該速率的投遞率，否則調用minstrel_ewma以（原投遞率*75%+本次投遞率*25%）的計算方式更新投遞率。算完了prob的ewma之后就調用minstrel_ht_calc_tp計算各個速率的吞吐率，這個吞吐率結合了實際數據包的長度、各個編碼方案的數據率，應該是比較準確的算法。
在每個循環中，在算完當前速率的投遞率和吞吐率之后，就會和當前組的最佳值進行比較，如果優于最佳值，就進行交換，再把以前的最佳值和以前的max_tp_rate2比較：
if
((mr->cur_tp > cur_prob_tp && mr->probability >
MINSTREL_FRAC(
3
,
4
)) || mr->probability >
cur_prob) {
mg
->max_prob_rate =
index;
cur_prob
= mr->
probability;
cur_prob_tp
= mr->
cur_tp;
}
if
(mr->cur_tp >
cur_tp) {
swap(index, mg
->
max_tp_rate);
cur_tp
= mr->
cur_tp;
mr
=
minstrel_get_ratestats(mi, index);
}
if
(index >= mg->
max_tp_rate)
continue
;
if
(mr->cur_tp >
cur_tp2) {
mg
->max_tp_rate2 =
index;
cur_tp2
= mr->
cur_tp;
}
最后再用同樣的方法遍歷各個組，更新整個系統的max_tp_rate、max_tp_rate2等域，不再重復帖代碼。
5. 探測頻率
那么minstrel多久或者說在什么條件下會進行探測呢，這和前文提到的三個重要的變量有關，就是sample_wait、sample_tries和sample_count。我的理解，sample_wait是說再過多少個數據包之后進行探測，sample_tries是說拿幾個幀來探測，但不是說經過一個sample_wait+sample_tries之后就開始計算那個速率最好，什么時候重新計算各個速率的吞吐率是用時間來控制的，在下一次計算之前，最多進行sample_count組（sample_wait+sample_tries）的循環。
在聚合幀發送完成的回掉函數minstrel_ht_tx_status中，對這幾個值進行判斷：
if
(!mi->sample_wait && !mi->sample_tries && mi->sample_count >
0
) {
mi
->sample_wait =
16
+
2
* MINSTREL_TRUNC(mi->
avg_ampdu_len);
mi
->sample_tries =
2
;
mi
->sample_count--
;
}
mi->avg_ampdu_len是每個聚合幀聚合長度的加權平均：
mi->avg_ampdu_len = minstrel_ewma(mi->avg_ampdu_len, MINSTREL_FRAC(mi->ampdu_len, mi->ampdu_packets), EWMA_LEVEL);
而在一個數據包將要發送請求采樣速率sample_idx的minstrel_get_sample_rate函數中，一開始會做如下處理：
if
(mi->sample_wait >
0
) {
mi
->sample_wait--
;
return
-
1
;
}
if
(!mi->
sample_tries)
return
-
1
;
mi
->sample_tries--;
因為要等sample_wait個包之后探測，因此先判斷這個值是不是大于0，如果是，則把這個計數器減1，之后返回-1不進行探測。每次探測時會把控制探測數量的計數器sample_tries減1，當這個數已經減到0的時候返回-1不探測。
以上就是Minstrel速率調整算法的基本流程。
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
