一種適用于地空通信的負(fù)載分布算法*

余 翔，劉 晗，段思睿，陳宇博

(重慶郵電大學(xué) 通信與信息工程學(xué)院，重慶 400065)

0 引 言

日益增加的航空旅客通信業(yè)務(wù)對(duì)航空通信質(zhì)量提出了更高的要求[1]。據(jù)估計(jì)，在未來(lái)幾年內(nèi)民航的乘客人次將從2020年的69 312萬(wàn)增長(zhǎng)到2025年的122 152萬(wàn)。為了滿足乘客的需求，未來(lái)航空通信要求具有高吞吐量和低時(shí)延的傳輸能力。多路徑傳輸協(xié)議是一種適用于有線互聯(lián)網(wǎng)和異構(gòu)無(wú)線網(wǎng)絡(luò)的并發(fā)傳輸協(xié)議，能夠在具有多終端的通信網(wǎng)絡(luò)上實(shí)現(xiàn)數(shù)據(jù)并發(fā)傳輸。采用多路徑傳輸不僅可以保證吞吐量性能的提升，也能保證在惡劣環(huán)境下的通信質(zhì)量。

多路徑網(wǎng)絡(luò)的流量分配一直是一個(gè)重要且活躍的研究領(lǐng)域[2-3]，而現(xiàn)有的分配策略可以分為基于流和數(shù)據(jù)包的流量分割方法?；诜纸M數(shù)據(jù)包的模型通常根據(jù)信道狀態(tài)信息、分組延遲約束等將分組的數(shù)據(jù)包發(fā)送到不同的路徑上。盡管調(diào)度策略減少了單個(gè)路徑上的排隊(duì)延遲，但也可能導(dǎo)致嚴(yán)重的數(shù)據(jù)包重新排序問(wèn)題，從而導(dǎo)致較大的端到端延遲。為了解決端到端時(shí)延問(wèn)題，Wu等人[4]提出了一種旨在通過(guò)將多個(gè)并行路徑聚合為單個(gè)虛擬路徑來(lái)最小化總數(shù)據(jù)包延遲的多路徑負(fù)載分布(Sub-packet Based Multipath Load Distribution，SPLMD)模型，從而減少包延遲的變化和接收端包重新排序的風(fēng)險(xiǎn)，同時(shí)用一個(gè)混合的M/M/1模型估計(jì)了每條路徑的排隊(duì)延遲，并分割流量以最小化延遲變化的成本。Raiciu等人[5]提出了一種基于機(jī)會(huì)調(diào)度的調(diào)度器，對(duì)每個(gè)路徑分配與流量分配關(guān)聯(lián)的權(quán)重，可以在保持每條路徑傳輸字節(jié)比例的同時(shí)，向多個(gè)路徑發(fā)送數(shù)據(jù)包。而目前應(yīng)用最廣泛的多路徑TCP協(xié)議(Multipath TCP，MPTCP)也是通過(guò)分割流的方式對(duì)多路徑網(wǎng)絡(luò)流量進(jìn)行分配。Li等人[6]提出了一種基于系統(tǒng)編碼的多路徑TCP(Multipath TCP with Systematic Coding，SC-MPTCP)方案，該方案引入線性系統(tǒng)編碼來(lái)解決在接收緩沖區(qū)限制下容忍路徑異構(gòu)的問(wèn)題。Chen等人[7]對(duì)蜂窩和WiFi網(wǎng)絡(luò)上的MPTCP的性能進(jìn)行了測(cè)量研究，以調(diào)查路徑多樣性對(duì)應(yīng)用級(jí)別度量的影響。Le等人[8]也提出了一種基于轉(zhuǎn)發(fā)延遲的數(shù)據(jù)包調(diào)度(Forward-Delay-Based Packet Scheduling，F(xiàn)DPS)算法，通過(guò)發(fā)送方估計(jì)的轉(zhuǎn)發(fā)延遲和吞吐量差異為并發(fā)路徑分派數(shù)據(jù)包。

本文考慮到地空通信信道的不對(duì)稱性，提出了一種擁塞感知負(fù)載分布(Congestion-aware Load Distribution，CALD)算法。該算法針對(duì)在地空通信場(chǎng)景下的高丟包、高時(shí)延特性重新估計(jì)了傳輸損失率，同時(shí)分別預(yù)估了各子路徑的擁塞窗口大小，解決了統(tǒng)一的擁塞控制窗口不適用于非對(duì)稱路徑傳輸?shù)膯?wèn)題。

1 系統(tǒng)模型及問(wèn)題公式

1.1 系統(tǒng)模型

所提MPTCP解決方案系統(tǒng)模型如圖1所示。本文研究了多個(gè)可用接入網(wǎng)絡(luò)與MPTCP的端到端通信問(wèn)題，所提出的CALD方案旨在端到端延遲約束下更好地調(diào)度非對(duì)稱路徑上傳輸?shù)淖恿?。?dāng)數(shù)據(jù)到達(dá)本地服務(wù)器，服務(wù)器將接收到的數(shù)據(jù)劃分為多個(gè)子流，將每個(gè)子流劃分為多個(gè)數(shù)據(jù)包，并暫存在多個(gè)可用通信路徑的發(fā)送緩存區(qū)中。系統(tǒng)框架中的主要決策模塊在本地服務(wù)器端實(shí)現(xiàn)，遠(yuǎn)端服務(wù)器端負(fù)責(zé)數(shù)據(jù)的接收重組。

圖1 子流分配系統(tǒng)模型

本文考慮一個(gè)地空異構(gòu)覆蓋網(wǎng)絡(luò)，并在其中部署了具有多個(gè)端到端通信路徑的代理服務(wù)器。為了實(shí)現(xiàn)端到端的通信，可以通過(guò)將源IP和目的IP進(jìn)行綁定來(lái)構(gòu)造。由于構(gòu)造的可用通信路徑不相交，不具有共享瓶頸鏈路，即每個(gè)通信路徑都可被認(rèn)為是與其他路徑無(wú)關(guān)的獨(dú)立傳輸路徑。因此，可以假設(shè)每個(gè)通信路徑的可用容量、損失率以及RTT往返時(shí)延等物理特性是相互獨(dú)立的[9-10]。

基于獨(dú)立的端到端通信路徑特性，設(shè)可用帶寬為μp，其表示端到端感知到的帶寬變化情況，具體數(shù)值可以通過(guò)發(fā)送緩存區(qū)內(nèi)的數(shù)據(jù)和往返時(shí)延來(lái)計(jì)算。往返時(shí)間RTTp，代表發(fā)送數(shù)據(jù)包到接收到ACK確認(rèn)消息的總時(shí)間。

(1)

首先，假設(shè)傳輸?shù)目倲?shù)據(jù)流為Sm，劃分的子流可以表示為

(2)

(3)

(4)

由公式(4)可以得到路徑p的狀態(tài)轉(zhuǎn)移矩陣為

(5)

(6)

由公式(5)、(6)可得，可以將路徑p的第i個(gè)數(shù)據(jù)包錯(cuò)誤的概率重寫為

(7)

(8)

由于地空通信之間的移動(dòng)性和長(zhǎng)距離傳輸會(huì)造成長(zhǎng)時(shí)間的鏈路中斷和每次RTT時(shí)延不定的問(wèn)題，可能會(huì)出現(xiàn)在規(guī)定時(shí)間內(nèi)并不能收到ACK的情況，因此本文用逾期損失來(lái)衡量這種ACK的逾期情況。文獻(xiàn)[12]中提到Sarkar等人提出逾期損失可以用M/G/1排隊(duì)模型來(lái)近似，因此，單個(gè)路徑上的端到端延遲遵循指數(shù)分布[13],可以建模為

(9)

式中：w表示數(shù)據(jù)包的到達(dá)率，可用平均時(shí)延w=1/E(Dp)來(lái)表示。因此公式(9)改寫為

(10)

式中：T為約束逾期時(shí)間，E(Dp)表示端到端的平均時(shí)延。由于E(Dp)是一個(gè)基于大量端到端延時(shí)的統(tǒng)計(jì)數(shù)據(jù)集的估計(jì)值，因此Wu等人在文獻(xiàn)[14]中提出了一個(gè)估計(jì)模型：

(11)

(12)

有效損失率可以表示為信道損失的數(shù)據(jù)包和數(shù)據(jù)包過(guò)期的總損失比，可表示為

(13)

基于有效損失率，估計(jì)總路徑的聚合流量為

(14)

正如文獻(xiàn)[15-17]所述，為了消除可用地空通信路徑之間的較大延遲差異，將最小化端到端時(shí)延作為最優(yōu)子流分配的一個(gè)約束條件。為了便于求解，本文將上述對(duì)通信路徑p的線性約束優(yōu)化問(wèn)題轉(zhuǎn)化成一個(gè)最大化實(shí)時(shí)流量Si的線性約束問(wèn)題。

(15)

1.2 路徑狀態(tài)估計(jì)

為了有效地利用地空通信網(wǎng)絡(luò)中可用的信道資源，更準(zhǔn)確地對(duì)各個(gè)路徑上的子流進(jìn)行調(diào)度，準(zhǔn)確地估計(jì)每個(gè)通信路徑的狀態(tài)是相當(dāng)重要的。為了得到有效帶寬參數(shù)，本文采用文獻(xiàn)[18]中的方案進(jìn)行估計(jì)，通信路徑的可用帶寬可被表征為

(16)

式中：wp代表當(dāng)前時(shí)刻的擁塞窗口大小，而RTTp代表往返時(shí)延。由于在低質(zhì)量的通信路徑中，統(tǒng)一的擁塞控制很可能會(huì)導(dǎo)致性能下降，因此本文分別估計(jì)了各路徑的擁塞窗口大小。由于MPTCP的特點(diǎn)是要求對(duì)TCP是友好的，因此本文采用文獻(xiàn)[19]中研究人員模擬的對(duì)單條TCP擁塞窗口的平均大小作為通信路徑p的擁塞窗口估計(jì)值。在本文中wp可以被表征如下

(17)

2 基于信道狀態(tài)感知的負(fù)載分布策略

本文基于實(shí)用理論的流量分配方案，使用連續(xù)分段線性方法去最大化目標(biāo)函數(shù)的輸出結(jié)果[20]。由于此方案傾向于給具有更高質(zhì)量和傳輸能力的通信路徑分配更大的流量，因此極易導(dǎo)致地空異構(gòu)通信網(wǎng)絡(luò)中的流量負(fù)載分布不平衡。為了緩解嚴(yán)重的流量負(fù)載不平衡問(wèn)題，本文引入了一個(gè)負(fù)載不平衡參數(shù)Lp來(lái)表示路徑p的負(fù)載水平，并表示為

(18)

式中：μp·(1-πp)表示為當(dāng)前路徑p的無(wú)損帶寬。如果Lp的值明顯高于設(shè)定的閾值TLV[21],則路徑p將過(guò)載。為了更快地達(dá)到收斂條件，將初始子流設(shè)置為無(wú)損帶寬的比值，即

(19)

同時(shí)，將路徑p上每次迭代的變化率設(shè)置為ΔSp，則下一次子流的分配情況可以表示為Sp+ΔSp。為了計(jì)算每次迭代的變化率，根據(jù)文獻(xiàn)[22]中提出的鏈路增長(zhǎng)算法來(lái)對(duì)每次的增量進(jìn)行估計(jì)：

(20)

從而可以估計(jì)每條路徑迭代后的有效增量為

(21)

基于信道狀態(tài)估計(jì)的漸進(jìn)式流率分配(Subflow Allocation)算法如下：

輸入： {μp,ξp}p∈∈P,TLV=1.2,D=max(Dp),ΔSp=0.05Sp。

輸出：S=max{Sp}p∈P。

1 for each elementpin available setPdo

2 InitializeSp,RTTp,E(Dp),Lp,wp

3 while(Sp≤μp·(1-πp))&&(Lp≤TLV)&&(E(Dp)≤D)do

4Sp=Sp+ΔSp

5 Update the elementLp,wp,RTTp,D=E(Dp)

6 end

7 Reset the above parameterSp,RTTp,E(Dp),Lp

8 while(Sp≤μp·(1-πp))&&(Lp≤TLV)&&(E(Dp)≤D) do

9Sp=Sp-ΔSp

10 Update the elementLp,wp,RTTp,D=E(Dp)

11 end

12 Determine the allocation vector of the subflow

13 end

14 Specific inter-path allocation:

15 find another avilable pathp′

16 if(Sp′≤μp′·(1-πp′))&&(Lp′≤TLV)&&(E(Dp′)≤D)

do

17Sp′=Sp′-ΔSp′orSp′=Sp′+ΔSp′

18 end

19 end

由于初始子流Sp被設(shè)置為無(wú)損帶寬的比值，并不是從原點(diǎn)開始計(jì)算，可能會(huì)導(dǎo)致初值分配權(quán)重過(guò)高的問(wèn)題,因此在算法中采用前向與后向迭代同時(shí)進(jìn)行來(lái)解決此問(wèn)題，得到最終的子流分配結(jié)果。本文按照所提算法的分配結(jié)果對(duì)接收到的流進(jìn)行分配，并在下一節(jié)給出實(shí)驗(yàn)結(jié)果。

3 數(shù)據(jù)仿真及分析

基于shdowsock搭建了一個(gè)多路徑端到端實(shí)驗(yàn)平臺(tái)。本地服務(wù)器端和遠(yuǎn)端服務(wù)器端被映射到本地網(wǎng)絡(luò)中的實(shí)際計(jì)算機(jī)中，并配置了多條可用通信路徑。本文通過(guò)綁定本地服務(wù)器端和遠(yuǎn)端服務(wù)器端的多對(duì)IP地址構(gòu)建了端到端通信網(wǎng)絡(luò)。如圖2所示，發(fā)送端輸入的流量可以途經(jīng)通信網(wǎng)絡(luò)中所有可用路徑到達(dá)接收端。

圖2 端到端測(cè)試系統(tǒng)架構(gòu)

3.1 參數(shù)設(shè)置

本次實(shí)驗(yàn)主要從吞吐量和端到端時(shí)延兩個(gè)指標(biāo)來(lái)衡量算法的性能。為了評(píng)估可用通信路徑對(duì)整個(gè)網(wǎng)絡(luò)吞吐量等性能的影響，對(duì)不同的路徑的流量分布進(jìn)行了實(shí)驗(yàn)(p=2,3,4,5)。實(shí)驗(yàn)中每條通信路徑的參數(shù)設(shè)置如表1所示。本文使用地空通信鏈路仿真器對(duì)每條路徑進(jìn)行參數(shù)設(shè)定，分別模擬了并在遠(yuǎn)端服務(wù)器端實(shí)時(shí)統(tǒng)計(jì)流量分配情況。同時(shí)為了獲得可靠的結(jié)果，重復(fù)每一組模擬實(shí)驗(yàn)10次，最后給出了一個(gè)平均結(jié)果。對(duì)于單一時(shí)間的結(jié)果，本文對(duì)TLV值進(jìn)行了仿真分析。在圖3中通過(guò)調(diào)整TLV值觀察得到不同的端到端時(shí)延，進(jìn)而得出最優(yōu)的TLV值，給出了更具代表性的一組仿真結(jié)果。

表1 多通信路徑參數(shù)

圖3 最優(yōu)負(fù)載均衡值TLV

3.2 數(shù)值分析

本文將得到的仿真結(jié)果與DEAM、ADMIT、EMTCP 以及MPTCP多路徑協(xié)議中的子流分配算法進(jìn)行了對(duì)比。首先,設(shè)置可用路徑p=2，統(tǒng)計(jì)傳輸數(shù)據(jù)流分別為4 Mb、5.25 Mb、6.5 Mb、7.75 Mb下的數(shù)據(jù)包重傳結(jié)果。本文統(tǒng)計(jì)了總的包重傳數(shù)量，并在圖4中展示了不同數(shù)據(jù)流下數(shù)據(jù)包的重傳次數(shù)。從圖中可以看出，由于MPTCP對(duì)于TCP應(yīng)該是友好的，因此在引入預(yù)估的單條通信路徑所對(duì)應(yīng)的TCP平均擁塞窗口作為判定路徑質(zhì)量的一個(gè)標(biāo)準(zhǔn)后，數(shù)據(jù)包重傳數(shù)量明顯降低。

圖4 數(shù)據(jù)包重傳數(shù)量

同時(shí)，本文在遠(yuǎn)端服務(wù)器端統(tǒng)計(jì)了從數(shù)據(jù)包發(fā)送到數(shù)據(jù)重組后的端到端時(shí)延。如圖5所示，本文所提算法展示了更低的端到端時(shí)延，其性能隨可用通信路徑和傳輸數(shù)據(jù)流的增加而提升。這是由于本文更加準(zhǔn)確地估計(jì)了通信路徑的一個(gè)質(zhì)量情況，給質(zhì)量較好的通信路徑分配了較大的子流,因此鏈路擁塞情況得到了明顯的改善，從而降低了端到端時(shí)延，并減少了連續(xù)的損失。圖6表示一段時(shí)間內(nèi)的平均損失率的變化。

圖5 平均端到端時(shí)延

圖6 平均丟包率

此外，由于本文在算法中使用最優(yōu)鏈路增長(zhǎng)算法對(duì)每次迭代的增量進(jìn)行估計(jì)，使得每次分配的子流量與對(duì)應(yīng)的信道狀態(tài)的變化情況成正相關(guān)，從而更加準(zhǔn)確地分配了通信路徑所對(duì)應(yīng)子流的數(shù)據(jù)量，因此更好地緩解了鏈路的擁塞情況，得到了較高吞吐量。圖7和圖8分別展示了吞吐量隨可用路徑數(shù)量的變化情況和隨時(shí)間的變化情況。

圖7 平均吞吐量

圖8 瞬時(shí)吞吐量

4 結(jié)束語(yǔ)

本文提出了一種擁塞感知負(fù)載分布算法，通過(guò)預(yù)估MPTCP通信路徑的一個(gè)擁塞窗口變化情況，映射到多路徑的擁塞感知負(fù)載分布模型中；同時(shí)將每次的路徑增量與通信路徑的變化情況對(duì)應(yīng)，預(yù)估對(duì)應(yīng)的最優(yōu)鏈路增長(zhǎng)值，從而有效降低了端到端時(shí)延，提高了多路徑傳輸?shù)目偼掏铝俊?/p>

未來(lái)的工作中，將繼續(xù)考慮改進(jìn)地空通信的擁塞控制，并將路徑傳播能耗納入到相關(guān)變量中進(jìn)行綜合研究。