面向異構(gòu)網(wǎng)絡(luò)的多路徑數(shù)據(jù)重傳研究?

戴卓臣 陸江東

（第二軍醫(yī)大學(xué) 上海 200433）

1 引言

隨著互聯(lián)網(wǎng)和相關(guān)技術(shù)的快速發(fā)展，網(wǎng)絡(luò)終端可使用的接入技術(shù)越來(lái)越多，如3G、4G、WIFI、藍(lán)牙等［1～3］。多路徑并行傳輸（CMT）就是在這樣的環(huán)境下發(fā)展而來(lái)?，F(xiàn)有研究成果多集中在數(shù)據(jù)包重傳策略、數(shù)據(jù)包丟失恢復(fù)及數(shù)據(jù)包的路徑選擇上［4］。現(xiàn)有重傳算法可以分為單一因素考慮重傳以及多因素考慮重傳。單一因素重傳主要包含五種經(jīng)典的基本重傳算法，對(duì)丟包率、擁塞窗口大小、時(shí)延等單一因素進(jìn)行判斷［5］，來(lái)選擇重傳路徑。還有相關(guān)學(xué)者綜合多種因素考慮重傳，并設(shè)計(jì)出TRX-CLS重傳算法［6］。該算法分別對(duì) largest cwnd、largest ssthresh、lowest rate path依次判斷，選出最合適的重傳信道?，F(xiàn)有研究成果都是基于現(xiàn)有路徑網(wǎng)絡(luò)態(tài)進(jìn)行決策，并沒(méi)有涉及異構(gòu)網(wǎng)絡(luò)狀態(tài)［7-9］。而異構(gòu)網(wǎng)絡(luò)狀態(tài)在重傳路徑的選擇決策上起到非常重要的作用。RTX-LR重傳策略基于最小丟包率、最小超時(shí)記錄吋間、最小重傳間隔確定重傳信道［10］。但是仍然存在不足，該算法首先對(duì)活躍路徑中的丟包率進(jìn)行判斷，選擇丟包率小的路徑，但是丟包率小并不能保證數(shù)據(jù)包一定能盡快到達(dá)接收端。此外，當(dāng)現(xiàn)有的網(wǎng)絡(luò)信息不足以選擇重傳路徑時(shí)，RTX-LR重傳算法會(huì)對(duì)路徑的異構(gòu)信息進(jìn)行判斷，選擇異構(gòu)記錄良好的那條［11］。然而，作為一個(gè)異構(gòu)記錄指標(biāo)，最小的超時(shí)時(shí)間也并不能保證數(shù)據(jù)包最快到達(dá)接收端，只能表明曾經(jīng)最優(yōu)。同時(shí)，在多變的異構(gòu)網(wǎng)絡(luò)環(huán)境下，該算法不能很好地適應(yīng)路徑性能發(fā)生突變的情況，因此本文在該算法的基礎(chǔ)之上，做進(jìn)一步的改進(jìn)研究。

2 數(shù)據(jù)重傳

2.1 異構(gòu)網(wǎng)絡(luò)環(huán)境

在異構(gòu)網(wǎng)絡(luò)環(huán)境下進(jìn)行并行傳輸，應(yīng)該首先保證重傳數(shù)據(jù)包能盡快到達(dá)接收端，以減少接收端緩沖區(qū)阻塞。由于RTX_LR重傳算法在考慮重傳時(shí)采用的是異構(gòu)最小超時(shí)時(shí)間［12］，但是只能表明該條鏈路曾經(jīng)具有最小的超時(shí)時(shí)間，因此并不能保證數(shù)據(jù)包一定最快到達(dá)接收端［13］。假設(shè)某條路徑Pi最開始有最小的超時(shí)重傳時(shí)間，但是后來(lái)超時(shí)嚴(yán)重，因此在這種場(chǎng)景下，還是選擇原路徑Pi作為重傳路徑，顯然是不合理的。

具體如圖1所示，假設(shè)發(fā)端和接收端有3條可用路徑，調(diào)度模塊按照調(diào)度策略將數(shù)據(jù)塊按序依次分發(fā)到這3條路徑上。圖中灰色標(biāo)識(shí)的數(shù)據(jù)包表示在傳輸過(guò)程中發(fā)生了丟包，并需要對(duì)該數(shù)據(jù)包進(jìn)行重傳，重傳時(shí)間在圖中已經(jīng)被標(biāo)識(shí)。按照RTX_LR重傳算法，當(dāng)丟包率相同時(shí)，該算法會(huì)選擇異構(gòu)最小的重傳時(shí)延的路徑B進(jìn)行重傳，圖中可知選擇路徑B進(jìn)行重傳是不合理的。因此本文提出了面向異構(gòu)網(wǎng)絡(luò)的多路徑數(shù)據(jù)重傳算法。該算法將對(duì)最小重傳時(shí)延、min｛max｛路徑重傳超時(shí)時(shí)間｝｝、最小丟包率依次進(jìn)行判斷，最終確定要選擇的重傳路徑。

圖1 RTX_LR重傳算法不足示意圖

2.2 重傳模型建立

根據(jù)異構(gòu)網(wǎng)絡(luò)環(huán)境下多路徑并行傳輸中重傳算法的設(shè)計(jì)原則，即保證重傳的數(shù)據(jù)包快速準(zhǔn)確地到達(dá)接收端，避免接收端緩存阻塞，以提高重傳效率［14］。本文提出的MDRA算法，首先對(duì)丟包類型進(jìn)行判斷，若是快重傳，則在源路徑上進(jìn)行重傳即可。若為超時(shí)重傳，則需要選擇其他路徑進(jìn)行重傳。首先掃描除源路徑之外的活躍路徑，若無(wú)，則從源路徑上重傳［15］，若存在，則先計(jì)算各活躍路徑的重傳時(shí)延期望值，然后選擇最具有最小期望值的路徑作為重傳路徑，如果當(dāng)前路徑不唯一，則判斷這些路徑的max｛路徑重傳時(shí)間｝，選擇最小的作為重傳路徑。若仍然無(wú)法判斷，則選擇路徑丟包率小的作為重傳路徑。如果仍然不唯一，則在其中隨機(jī)選擇一條作為重傳路徑，算法結(jié)束。

數(shù)據(jù)包超時(shí)重傳時(shí)間的計(jì)算與丟包率 p、端到端時(shí)延RTTs/2、超時(shí)計(jì)時(shí)器設(shè)定的超時(shí)重傳時(shí)間t，其值為RTO以及重傳次數(shù)有關(guān)。為了便于分析，假設(shè)數(shù)據(jù)包在重傳期間沒(méi)有發(fā)生擁塞。那么，數(shù)據(jù)包經(jīng)過(guò)一次重傳后，能成功到達(dá)接收端的概率為1-p［16］。設(shè)Ti為經(jīng)過(guò)i次超時(shí)重傳到達(dá)接收端并確認(rèn)的時(shí)間。那么，第一次超時(shí)重傳到達(dá)接收端的時(shí)間滿足：

同理可知，經(jīng)過(guò)兩次超時(shí)重傳和三次超時(shí)重傳到達(dá)接收端所需要的時(shí)間為

假設(shè)最大超時(shí)重傳次數(shù)為3，超過(guò)3次就不再對(duì)該數(shù)據(jù)包進(jìn)行重傳。因此，數(shù)據(jù)包成功到達(dá)接收端的期望值為

其中，pi為第i次超時(shí)重傳后，數(shù)據(jù)包成功到達(dá)接收端的概率，可以得到：

將式（5）代入式（4），可以得出每條路徑傳輸該數(shù)據(jù)包的重傳時(shí)延期望值。然后進(jìn)行比較，選出期望值最小的路徑作為重傳路徑。同時(shí)，MDRA算法將會(huì)為每條路徑做一個(gè)記錄，這個(gè)記錄存儲(chǔ)著該路徑從建立開始到現(xiàn)在，數(shù)據(jù)塊的最大超時(shí)重傳時(shí)間tmax。若多條路徑具有最小重傳期望，則從中選擇具有最小的tmax作為重傳路徑，若仍然無(wú)法判斷，則對(duì)丟包率進(jìn)行判斷，仍然無(wú)法判斷的則從其中隨機(jī)選擇一條。

2.3 算法流程及偽代碼

算法步驟具體如下：

Step1：發(fā)端發(fā)現(xiàn)數(shù)據(jù)包丟失，首先判斷重傳類別，若是快重傳，則在源路徑上重傳，進(jìn)入Step6，否則，進(jìn)入Step2；

Step2：掃描路徑，計(jì)算各路徑的超時(shí)重傳期望值，選擇期望值最小的路徑作為重傳路徑；

Step3：若具有最小超時(shí)重傳期望值的路徑不唯一，則從中選擇具有min{tmax}的路徑作為重傳路徑；

Step4：若選擇出的min{tmax}路徑仍然不唯一，則從中選擇具有最小丟包率的路徑進(jìn)行重傳；

Step5：若所選的路徑最小丟包率仍然無(wú)法判斷，則在其中隨機(jī)選擇一條路徑作為重傳路徑；

Step6：算法結(jié)束。

MDRA重傳算法具體設(shè)計(jì)如圖2所示。

圖2 MDRA重傳算法

MDRA重傳算法偽代碼如下：

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

3.1 實(shí)驗(yàn)環(huán)境

仿真試驗(yàn)的具體網(wǎng)絡(luò)拓?fù)淙鐖D3所示，發(fā)送端和接收端均有兩個(gè)接口，分別接入兩個(gè)網(wǎng)絡(luò)中進(jìn)行并行傳輸，這兩條鏈路的具體參數(shù)如表1所示。

圖3 MDRA重傳算法仿真拓?fù)浣Y(jié)構(gòu)

表1 鏈路參數(shù)設(shè)置

這樣設(shè)置的目的是，對(duì)于重傳算法而言，丟包率占有非常重要的作用，為了分析丟包率對(duì)重傳算法的影響，故仿真中一條路徑的丟包率為固定值1%，而另一條路徑丟包率從1%～10%逐步增加，遞增間隔設(shè)置為0.01。通過(guò)這種仿真場(chǎng)景，就可以分析出丟包率差異對(duì)重傳算法的影響。R1、R2、R3和R4為四個(gè)路由器。瓶頸鏈路的隊(duì)列長(zhǎng)度設(shè)定為100個(gè)數(shù)據(jù)包，鏈路的排隊(duì)模型為DropTail。應(yīng)用層協(xié)議使用FTP協(xié)議，為了評(píng)估協(xié)議在較長(zhǎng)的一段時(shí)間內(nèi)的有效吞吐量性能，仿真中使用FTP協(xié)議傳輸一個(gè)足夠大的文件來(lái)模擬數(shù)據(jù)傳輸?shù)倪^(guò)程，仿真時(shí)長(zhǎng)設(shè)定為100s。

3.2 結(jié)果分析

根據(jù)上述的拓?fù)浣Y(jié)構(gòu)，本文得出如下的仿真結(jié)果，如圖4～6所示，分別展示了不同接收緩存RB（Receive Buffer）下，三種重傳算法的性能趨勢(shì)。其中，MDRA算法是指本文所提出的基于記錄的綜合參數(shù)算法設(shè)計(jì)；RTX_LR是基于最小丟包率、最小超時(shí)重傳時(shí)間、最小重傳間隔來(lái)確定重傳路徑；RTX_LOSSRATE是基于最小丟包率的經(jīng)典重傳算法，其思想是選擇丟包率最小的路徑作為重傳路徑。RB=128KB下的仿真結(jié)果如圖4所示。

圖4 當(dāng)RB=128KB時(shí)吞吐量對(duì)比圖

圖4中，可以看出本文提出的算法明顯優(yōu)于其他兩種重傳算法，大概高出5.5%左右。并且還可以得出，隨著路徑2丟包率的提高，兩條鏈路的差異性也隨之變大，網(wǎng)絡(luò)整體吞吐量性能趨勢(shì)不斷下降，但利用本文提出的MDRA算法比其他兩種重傳算法可以獲得更好的吞吐量。RB=64KB下的仿真結(jié)果如圖5所示。

圖5 當(dāng)RB=64KB時(shí)吞吐量對(duì)比圖

從圖5可以看出，接收端緩存減小對(duì)吞吐量性能非常明顯。因?yàn)椴町惢穆窂皆诓⑿袀鬏敃r(shí)，會(huì)造成接收端數(shù)據(jù)的亂序，已接收的亂序數(shù)據(jù)會(huì)暫存在接收端緩存當(dāng)中，等待亂序數(shù)據(jù)包的到達(dá)，因此在緩存受限的情況下，若超時(shí)重傳的數(shù)據(jù)包遲遲不能到達(dá)接收端，勢(shì)必會(huì)導(dǎo)致接收端緩存阻塞，嚴(yán)重影響路徑的傳輸性能。同時(shí)從圖5中看出，當(dāng)RB減小時(shí)，三種算法的吞吐量均有所減少，但本文提出的算法相較于其他兩種算法，吞吐量性能提高了7.5%左右。RB=64KB下的仿真結(jié)果如圖6所示。

圖6 RB=32KB時(shí)吞吐量對(duì)比圖

類似地，圖6中吞吐量的仿真結(jié)果，可知，本文提出的算法明顯高于其他兩種算法，性能提高9%左右。由此可知，當(dāng)RB越小，則MDRA算法所帶來(lái)的性能提升越明顯。

為了更加清楚地論證本文所提算法的優(yōu)越性，本文將對(duì)三種重傳算法在三種不同的RB下的平均吞吐量進(jìn)行比較。平均吞吐量是指在一定丟包率范圍內(nèi)的平均吞吐量?；谝陨系姆抡娼Y(jié)果，本文丟包率的取值范圍為1%～10%。具體統(tǒng)計(jì)結(jié)果如表2所示。

從表2可以看出，在不同的接收端緩存下，MDRA算法的平均吞吐量性能均優(yōu)于其他兩種算法，并且可以得出當(dāng)RB=128KB時(shí)，MDRA算法的平均吞吐量比RTX_LR高了大概2.5%；當(dāng)RB=64KB時(shí)，提高了約8%；當(dāng)RB=32KB時(shí)，提高了約為12%。因此，可以得知，RB越小，則MDRA算法表現(xiàn)越優(yōu)秀。

表2 三種重傳算法平均吞吐量

為了找到吞吐量性能提高的原因，本文對(duì)接收端亂序數(shù)據(jù)包的個(gè)數(shù)做了統(tǒng)計(jì)。依然利用圖3仿真拓?fù)浣Y(jié)果，RB設(shè)置為64KB，仿真時(shí)間為30s，應(yīng)用層依然采用FTP文本。鏈路1、2的丟包率采保留原來(lái)的設(shè)置。得到仿真結(jié)果如圖7所示。

圖7 三種重傳算法亂序包個(gè)數(shù)比較

從圖7中可知，接收端亂序數(shù)據(jù)包個(gè)數(shù)隨著丟包率增大而增大。但本文MDRA算法相較于其他兩種算法，亂序包個(gè)數(shù)有明顯的減少。由此可知，MDRA算法可以有效減少接收端亂序數(shù)據(jù)包的個(gè)數(shù)，最終提升網(wǎng)絡(luò)的吞吐量性能。

4 結(jié)語(yǔ)

針對(duì)本文以吞吐量性能為目標(biāo)，對(duì)差異化網(wǎng)絡(luò)環(huán)境下數(shù)據(jù)重傳策略進(jìn)行了分析研究，并提出了基于記錄的綜合參數(shù)數(shù)據(jù)重傳算法，該算法分別對(duì)最小超時(shí)重傳時(shí)延、min｛max｛路徑重傳時(shí)間｝｝、最小丟包率依次進(jìn)行判斷，最終確定要選擇的重傳路徑。保證了重傳數(shù)據(jù)包最快地到達(dá)接收端，降低接收端緩存阻塞，提高多路徑傳輸系統(tǒng)整體吞吐性能。通過(guò)NS-2仿真實(shí)驗(yàn)證明，在異構(gòu)網(wǎng)絡(luò)環(huán)境下，相較于默認(rèn)的重傳算法，本文所提出的基于綜合參數(shù)重傳算法可以有效提高重傳效率，減少接收端緩存阻塞，一定程度上提高了網(wǎng)絡(luò)的吞吐性能。