許乾坤，李 燁，董 浩，葉劍飛，李俊何

（上海理工大學(xué) 光電信息與計(jì)算機(jī)工程學(xué)院，上海 200093）

0 引 言

TCP作為Internet上一種占主導(dǎo)地位的端到端傳輸協(xié)議，其數(shù)據(jù)流量占Internet中95%以上。隨著近些年移動寬帶網(wǎng)絡(luò)技術(shù)和用戶數(shù)量的迅猛發(fā)展，TCP網(wǎng)絡(luò)的擁塞問題越來越明顯，因而原本單一的RENO擁塞控制算法[1]發(fā)展為十幾種，以應(yīng)用于不同的網(wǎng)絡(luò)環(huán)境。為了及時調(diào)度部署客戶端和服務(wù)器端的資源，更好地預(yù)防和阻止網(wǎng)絡(luò)擁塞，客戶端需要識別服務(wù)器端所采用的擁塞控制算法。

目前已有的對擁塞控制算法的識別方法存在若干問題，迄今尚未有很好的解決。TBIT[2]是利用初始化窗口值、損失函數(shù)以及發(fā)送的數(shù)據(jù)包數(shù)量等進(jìn)行識別的一種方法，由于提出時間較早，對近年來出現(xiàn)的TCP擁塞控制算法的識別效果不佳。Oshio等提出的集成分析方法[3]假設(shè)系統(tǒng)中僅存在兩種TCP擁塞控制算法版本，應(yīng)用上有很大的局限性。Feyzabadi等研究了Web服務(wù)器上擁塞控制算法的識別，但工作僅限于RENO和CUBIC之間的識別[4]。對于多種TCP擁塞控制算法的同時分類識別，Yang等提出了CAAI方法[5]，但只考慮了擁塞控制過程中的慢啟動和擁塞避免兩個階段，因而對于僅在快速恢復(fù)階段有差別的算法無法識別。

RENO[6]、NEWRENO[7]、CUBIC[8]和 CTCP[9]是當(dāng)前應(yīng)用最廣泛的幾個擁塞控制算法。為了提高對其識別的效率和準(zhǔn)確率，本文分析了擁塞控制四個階段的特點(diǎn)，基于構(gòu)造的特征向量，提出一種極限學(xué)習(xí)機(jī)（Extreme Learning Machine，ELM）和隨機(jī)森林（Random Forest，RF）相結(jié)合的算法對服務(wù)器端的擁塞控制算法進(jìn)行識別，并與多種機(jī)器學(xué)習(xí)方法對比研究。

1 擁塞控制的基本原理

擁塞控制一般分為四個階段，即慢啟動、擁塞避免、快速恢復(fù)以及快速重傳[10]，圖1給出了發(fā)生丟包時各階段擁塞窗口（CWND）的變化。在慢啟動階段，由設(shè)定的初始窗口大小開始，以指數(shù)方式增長，當(dāng)窗口大小到達(dá)設(shè)定的閾值之后進(jìn)入擁塞避免階段。在擁塞避免階段，各擁塞算法的窗口增長函數(shù)不一樣，RENO、NEWRENO等采用線性函數(shù)，STCP采用指數(shù)函數(shù)，也有的擁塞控制算法會根據(jù)確認(rèn)字符（ACK）以及網(wǎng)絡(luò)環(huán)境如往返時間（Round-Trip Time，RTT）來決定增長函數(shù)[11]。在連續(xù)收到三個或以上的重復(fù)ACK時，意味著網(wǎng)絡(luò)擁塞發(fā)生了不止丟一個包的情況，就會進(jìn)入快速重傳階段以重傳丟失的包。快速重傳和快速恢復(fù)階段一般是成對出現(xiàn)的，在快速恢復(fù)階段，窗口值降到一個比例后直接進(jìn)入擁塞避免階段，這個比例不會很小，以避免不必要的帶寬浪費(fèi)。RENO算法不包含快速重傳和快速恢復(fù)階段，在發(fā)生丟包后會超時重傳，重新進(jìn)入慢啟動階段，如圖1中虛線所示。

圖1 TCP擁塞控制機(jī)制

2 特征向量構(gòu)造

2.1 客戶端數(shù)據(jù)采集

客戶端只能通過接收的數(shù)據(jù)來提取擁塞控制算法的特征信息。根據(jù)TCP協(xié)議，通信過程在每個RTT內(nèi)服務(wù)器會向客戶端發(fā)送一定窗口值的數(shù)據(jù)，利用數(shù)據(jù)包的接收序號（Received Sequence Number，RSN）可計(jì)算出客戶端接收到的來自服務(wù)器的數(shù)據(jù)總和。在服務(wù)器進(jìn)行數(shù)據(jù)傳送時，每個TCP協(xié)議包自動開啟時間戳，且同一個CWND內(nèi)的數(shù)據(jù)包，服務(wù)器端默認(rèn)同時發(fā)出，每個包的時間戳近似相等，RSN在客戶端根據(jù)時間戳計(jì)算每個RTT內(nèi)的窗口值。對采集的數(shù)據(jù)進(jìn)行處理后，可獲得類似圖1實(shí)線所示的擁塞控制四個階段CWND大小的變化軌跡。

2.2 特征提取

對于所研究的四種主流擁塞控制算法，RENO、NEWRENO與CUBIC、CTCP在擁塞避免階段和丟包點(diǎn)的處理上有差異，而NEWRENO作為RENO的改進(jìn)算法，主要是在快速恢復(fù)階段進(jìn)行了改進(jìn)。文獻(xiàn)[5]的CAAI方法可識別RENO、CUBIC和CTCP，對于RENO和NEWRENO的區(qū)分則無能為力。為了更準(zhǔn)確地識別服務(wù)器端采用的擁塞控制算法，同時使得識別方法可應(yīng)用于所有主流擁塞控制算法，本文提取如下特征：

（1）窗口值下降比例β：當(dāng)擁塞發(fā)生丟包時，連續(xù)收到三個重復(fù)的ACK，此時窗口閾值會下降一定比率。不同擁塞算法采用的比值不同，比如RENO為0.5，而CUBIC為0.8。根據(jù)丟包點(diǎn)前后擁塞窗口值的比值可確定窗口值下降比率：

其中，CWND′為丟包后進(jìn)入快速恢復(fù)階段的擁塞窗口值，CWND′為丟包點(diǎn)的擁塞窗口值，MSS（Maximum Segment Size）為每個TCP包傳輸?shù)淖畲髨笪拈L度。

（2）擁塞避免窗口增長函數(shù)g(x)：在擁塞避免階段，對于窗口增長函數(shù)g(x)特征，采用該階段中兩個時間點(diǎn)的窗口值ws+i和ws+j分別與擁塞避免階段的起點(diǎn)窗口值ws+1作差，使用相對值ws+i-ws+1和ws+j-ws+1表示該階段的函數(shù)曲線特征。

（3）快速恢復(fù)窗口增長函數(shù)h(x)：在快速恢復(fù)階段，當(dāng)服務(wù)器連續(xù)收到三個DUPACK時，不同的算法處理不同，比如等待超時重傳（RTO），或者不斷增加窗口值直到收到重傳的包。本文采用該階段中的某個時間點(diǎn)窗口值與起點(diǎn)值作差wk-w1表示該特征。

由此，構(gòu)造特征向量如下：

3 識別方法

3.1 極限學(xué)習(xí)機(jī)

ELM是一種單隱層前饋神經(jīng)網(wǎng)（Single-hidden Layer Feedforward Neural Network，SLFN）學(xué)習(xí)算法，該算法能夠隨機(jī)產(chǎn)生輸入層與隱含層之間的連接權(quán)重以及隱含層神經(jīng)元的閾值，且在訓(xùn)練過程中無需調(diào)整，只需要設(shè)置隱含層神經(jīng)元的個數(shù)，便可以獲得唯一的最優(yōu)解。與傳統(tǒng)前饋神經(jīng)網(wǎng)絡(luò)算法相比，ELM避免了容易陷入局部極小值、學(xué)習(xí)率選擇敏感以及迭代學(xué)習(xí)方法常見的過擬合等問題[12]，并且學(xué)習(xí)速度快、泛化性能好。

理想SLFN模型的數(shù)學(xué)表達(dá)式為：

其中，Y為期望輸出矩陣；β為隱含層與輸出層之間的權(quán)矩陣；H=(W,b)為神經(jīng)網(wǎng)絡(luò)隱含層輸出矩陣，W表示輸入層與隱含層之間的權(quán)矩陣，b表示隱含層的偏置向量。

由于參數(shù)W和b是任意給定的，利用二者計(jì)算出H并令其保持不變，只需確定參數(shù)β即可。權(quán)值β可通過求解下式獲得：

其中，||·||為歐式范數(shù)，H+為H的Moore-Penrose廣義逆矩陣。

3.2 隨機(jī)森林

RF是由Breiman提出的集成學(xué)習(xí)方法[13]。RF由多棵決策樹組成，每棵決策樹使用隨機(jī)抽樣方法從總的訓(xùn)練集（n個樣本，m維特征）中有放回的抽取樣本來訓(xùn)練，且每組樣本的樣本容量一般與總訓(xùn)練集相同。使用的特征同樣是從所有特征中按照一定的比例無放回抽取，這個比例大小由自己定義，一般取為特征數(shù)目的開方、開方的一半、或者兩倍的開方等。RF包含的決策樹的數(shù)量由自己設(shè)定，且每棵樹的分類結(jié)果相互獨(dú)立，最后所有樹的決策結(jié)果可通過多數(shù)投票法組合，即得票最多的類可以判定為RF的分類結(jié)果。RF不容易陷入過擬合，對很多數(shù)據(jù)集表現(xiàn)良好，精確度較高且具有很好的抗噪聲能力[14]。

3.3 本文方法

出于網(wǎng)絡(luò)實(shí)時通信和故障快速恢復(fù)的需求，對TCP擁塞控制算法的識別要求有較高的準(zhǔn)確率和識別效率。為了解決此問題，可以從兩方面考慮。一方面，盡可能的減少分類器的訓(xùn)練時間，優(yōu)化參數(shù)調(diào)整過程，避免不必要的迭代計(jì)算；另一方面，為了提高識別的準(zhǔn)確率，需要盡可能的提取有效特征，避免冗余信息對識別結(jié)果造成干擾。因此，將ELM和RF相結(jié)合，即用ELM算法代替RF算法原理中決策樹的位置來進(jìn)行樣本的訓(xùn)練和結(jié)果分類，最后ELM算法的分類結(jié)果可通過多數(shù)投票法組合。算法模型如圖2所示。

算法步驟為：

1）假設(shè)訓(xùn)練集為D，測試集為T，特征維數(shù)為M，極限學(xué)習(xí)機(jī)的數(shù)量為N，每個極限學(xué)習(xí)機(jī)的隱藏節(jié)點(diǎn)的個數(shù)為n，算法輸入的特征數(shù)量為m。

2）應(yīng)用自展法在訓(xùn)練集D上有放回地隨機(jī)抽取N個新的自助樣本集。

3）在總的M個特征上隨機(jī)抽取m個特征作為每一個極限學(xué)習(xí)機(jī)算法模型的輸入，結(jié)合步驟2）的樣本集Di進(jìn)行極限學(xué)習(xí)機(jī)i的模型訓(xùn)練計(jì)算。

4）采用多數(shù)投票法將訓(xùn)練得到的多個極限學(xué)習(xí)機(jī)進(jìn)行組合。

圖2 所提算法模型

4 仿真實(shí)驗(yàn)

4.1 數(shù)據(jù)的獲取與處理

在服務(wù)器端為RENO、NEWRENO、CUBIC、CTCP四種擁塞控制算法設(shè)置不同的網(wǎng)絡(luò)環(huán)境參數(shù)，以實(shí)現(xiàn)數(shù)據(jù)的多樣性。其中RTT的值（單位為毫秒）設(shè)置為20、40、60、80、90；丟包點(diǎn)設(shè)置為接通后的3～18秒內(nèi)；丟包數(shù)設(shè)置為：1、3或5個。在通信過程中，產(chǎn)生通信數(shù)據(jù)信息，在服務(wù)端獲取擁塞窗口變化軌跡，生成768個樣本。在接收端采集RSN數(shù)據(jù)，根據(jù)時間戳獲取測試集。

實(shí)驗(yàn)中，在擁塞避免階段提取出第4個RTT和第8個RTT的窗口值，即取i=4和j=8，在快速恢復(fù)階段提取第4個RTT對應(yīng)的窗口值，即取k=4。因此，特征向量為：

4.2 實(shí)驗(yàn)設(shè)置

為驗(yàn)證所提基于ELM和RF的識別方法的有效性，與K-最近鄰算法（k-Nearest Neighbor，KNN）、Logistic回歸（Logistic Regression，LR）、支持向量機(jī)（Support Vector Machine，SVM）、極限學(xué)習(xí)機(jī)（Extreme Learning Machine，ELM）以及隨機(jī)森林（Random Forest，RF）進(jìn)行對比研究，算法參數(shù)設(shè)置如下：

1）KNN：k值取為3，采用歐氏距離作為距離度量方式，以少數(shù)服從多數(shù)的規(guī)則進(jìn)行分類。

2）LR：懲罰項(xiàng)選用L2范數(shù)，由于是四類分類問題，采用一對多的拆分策略進(jìn)行處理，共構(gòu)造4*(4-1)/2=6個兩類分類器。

3）SVM：采用C-SVC模型，核函數(shù)為徑向基函數(shù)（Radial Basis Function，RBF）核，gamma取為0.1，懲罰系數(shù)C為0.5。采用一對多的拆分策略進(jìn)行處理。

4）ELM：隱含層節(jié)點(diǎn)數(shù)為8，激活函數(shù)采用Sigmoid函數(shù)。

5）RF：隨機(jī)森林的樹的深度為8，樹的數(shù)量為180。

4.3 實(shí)驗(yàn)結(jié)果

采用查準(zhǔn)率和召回率作為算法的性能度量，由于二者是一對矛盾的指標(biāo)，將其綜合如下：

其中，P表示查準(zhǔn)率，R表示召回率，α的取值代表了對查準(zhǔn)率和召回率的偏好，α＞1時，模型更看重對正樣本的識別，α＜1時，模型更看重對負(fù)樣本的區(qū)分能力，而α=1時即為標(biāo)準(zhǔn)F1值，是基于兩者的加權(quán)調(diào)和平均，表示兩者同等重要。本文實(shí)驗(yàn)取α=1，分類結(jié)果如表1～表4所示。

表1 不同分類模型F1值

表2 不同分類模型R值

表3 不同分類模型P值

表4 平均分類準(zhǔn)確率

比較表1～表3數(shù)據(jù)可見，本文方法對于擁塞控制算法的識別結(jié)果最優(yōu)，其綜合指標(biāo)F1值明顯高于其他五種分類算法，特別是對RENO和NEWRENO的識別有明顯的提升，而對于CUBIC和CTCP兩種算法均達(dá)到了100%的識別率。由表4可以看出，本文分類算法對數(shù)據(jù)集中四種擁塞控制算法的平均分類準(zhǔn)確率最高，由此驗(yàn)證了所提算法的有效性。

4.4 特征提取效果分析

文獻(xiàn)[5]提出了可以對多個擁塞控制算法進(jìn)行識別的算法CAAI，采用從擁塞避免和快速重傳階段提取的三個特征。相比于CAAI算法，本文構(gòu)造的特征向量增加了快速恢復(fù)窗口增長函數(shù)h(x)。為了研究其對于擁塞控制算法的識別效果的作用，將本文算法與CAAI識別算法進(jìn)行對比研究，實(shí)驗(yàn)結(jié)果如圖3所示。

圖3 本文算法和CAAI識別結(jié)果對比圖

可以看出，對于CUBIC和CTCP，采用兩種算法均可以很好的識別，但對于RENO和NEWRENO，僅采用CAAI算法提取的三個特征時幾乎無法對其進(jìn)行識別。而采用本文算法提取的四個特征時，在保持對CUBIC和CTCP 100%識別率的前提下，對RENO和NEWRENO兩種算法的識別也有了很大的提高。

經(jīng)驗(yàn)證，在實(shí)際應(yīng)用中為獲取上述識別所需的特征向量，最小只需要3.14兆TCP流的大小，即可獲得較為理想的識別效果，因此對TCP流的大小要求較低。

5 結(jié) 語

TCP協(xié)議在網(wǎng)絡(luò)傳輸中普遍使用，使得擁塞控制算法的識別在改善網(wǎng)絡(luò)環(huán)境、提高用戶的網(wǎng)絡(luò)體驗(yàn)等方面越來越重要，也對互聯(lián)網(wǎng)性能與穩(wěn)定性的分析具有重要意義。本文基于客戶端接收的數(shù)據(jù)估計(jì)服務(wù)器端擁塞控制算法窗口變化軌跡，提取擁塞控制各階段特征信息以構(gòu)造特征向量，并提出了一種ELM與RF相結(jié)合的新算法應(yīng)用于擁塞控制算法的識別。相比于已有方法，所設(shè)計(jì)的特征向量包含的信息更加全面，提高了識別準(zhǔn)確率，擴(kuò)大了應(yīng)用范圍，取得了更好的識別效果。

致謝：感謝華為技術(shù)有限公司合作項(xiàng)目“無線智能網(wǎng)絡(luò)架構(gòu)仿真平臺技術(shù)研究”為本文提供研究和實(shí)驗(yàn)環(huán)境支持。