面向時延敏感服務的多路徑傳輸調度算法

◎青島大學計算機科學技術學院◎馮飛宇◎陳飛◎

為了解決多路徑傳輸控制協議（MultiPath TCP，MPTCP）子流任務完成時間不同步、整體傳輸延遲過大的問題。文章圍繞多路徑中的鏈路差異性設計了一種優化傳輸調度算法。通過實時監控多路徑的鏈路狀況和待發送數據流，將優化調度方案分為兩部分，當多路徑鏈路帶寬被充分利用時采用傳輸速率優先，多條路徑并發的傳輸數據；當多路徑鏈路帶寬未被充分利用時采用最快完成鏈路優先，以緩解子流完成時間不同步的問題。仿真結果顯示，在文件下載、網頁加載和視頻播放等場景下，該算法性能比默認的最小往返延遲優先（MinRtt）算法綜合提升了25%，可以降低傳輸延遲。

1.引言

傳統的TCP網絡架構只允許設備利用一個網絡接口建立網絡連接，這導致了大量的網絡帶寬資源沒有被充分利用。為此，Multi-Connectivity的解決方案是通過在兩個網絡設備的網卡之間建立多條通訊鏈路，實現數據的聚合和分離[17]。其中MPTCP網絡協議是由IETF研發的位于傳輸層的實現，是目前使用最廣泛的多路徑網絡協議解決方案[1]。MPTCP允許設備利用其攜帶的多個網卡接口與對端設備建立多條網絡連接進行數據傳輸任務，目前該協議應用于多種實際場景，如：配備wifi和LTE的智能移動終端[2][3]和數據中心中同時具有多條網絡鏈路的主機等[4]。MPTCP還可以與傳統TCP兼容且無需更改現有的上層應用[5]，是目前最成熟的多路徑傳輸協議。

傳輸調度機制作為MPTCP中的一個重要組件，負責調度分配應用層需要發送的數據，其通過傳輸調度算法將數據包分配給可用的子流進行傳輸。作為傳輸調度機制核心的傳輸調度算法是決定MPTCP性能的主要因素之一[12]。但由于鏈路之間RTT、丟包率和擁塞窗口等網絡參數的差異性，會對傳輸調度算法性能造成很大的影響，甚至會出現性能比使用一條最佳TCP連接還要差的現象[6][11][13]。

目前MPTCP默認的數據調度算法是MinRTT，該方法將優先選擇RTT最小且存在擁塞窗口的鏈路以實現降低傳輸延遲的目的[7]。但由于終端設備的不同網絡接口普遍存在異構性，網絡狀態也是動態變化的，直觀的選擇RTT最小的鏈路并不一定獲得最佳的傳輸效率和系統資源利用率，具體體現在以下兩方面：首先，RTT并不能完全反映當前網絡的擁塞狀況[14]，盲目選擇RTT小的鏈路分配傳輸任務很容易閑置其他擁有大量帶寬資源的鏈路，而且易造成較大的尾延遲。其次，雖然MinRTT可以結合機會重傳和懲罰機制避免丟包以降低網絡波動造成的影響[11]，但其無法適應網絡中類似視頻流等突發流量的場景[6]。

目前傳輸調度算法的設計主要存在以下兩個問題：（1）調度算法選用的網絡參數無法完全描述當前網絡狀況，鏈路傳輸完成時間存在較大的尾延遲，進而影響總傳輸延遲；（2）調度算法易受網絡波動的影響，無法適應類似視頻流這樣的突發流量。

針對以上問題，本文以協調多鏈路的總體傳輸延遲為主要目標，解決了傳輸鏈路尾延遲較大的問題，較好的應對傳輸流量的突變，設計了不限制設備網絡接口數量的同步完成傳輸調度算法（synchronous completion transmission scheduling，SCTC），通過盡可能同步各鏈路傳輸任務完成時間以實現低延遲傳輸。

2.相關工作介紹

雖然目前仍沒有完善的調度算法，但已經有很多工作針對不同的性能優化目標提出了一些改進的調度算法。目前MPTCP調度器研究工作的性能優化目標主要分為：降低總的傳輸延遲、提高數據傳輸的吞吐量等。

低延遲是數據傳輸性能的一個關鍵指標，是傳輸調度算法的優化主要方向。MinRTT是目前linux-MPTCP內核中默認的調度算法，該算法將優先選擇RTT最小且存在擁塞窗口的鏈路以實現降低傳輸延遲的目的[7]，但RTT反映不了網絡的真實狀況，由于子鏈路的異構性，會出現擁塞堵塞等降低網絡資源使用率的現象；REMP[10]中所有子流冗余的發送相同數據，以帶寬換取低延遲和魯棒性，網絡中往往會存在大量無用的冗余數據，增加了網絡的負載，帶寬有效利用率低；DEMS[8]通過同步兩個子流的完成時間來實現低延遲傳輸，同時通過添加適量的冗余數據以適應網絡波動，該算法的限制在于MPTCP連接只支持兩條子流，同時會占用接收端大量的緩存空間，只適用于中小型文件（小于8M）[8][9]；DAPS[15]根據每個鏈路的實時傳輸時間選擇要在每個路徑上傳輸的分組序列，以有序接收，降低緩存占有率，降低應用層提取數據的延遲，但受鏈路差異性影響，無法對網絡變化做出快速反應。

在一些高帶寬需求應用場景，例如視頻流媒體，吞吐量成為影響用戶服務質量的重要因素。ECF[6]通過通過計算慢路徑與快路徑的傳輸完成時間來選擇鏈路，提高快鏈路的使用效率，從而提高吞吐量，但該算法的復雜度隨鏈路數量增加而指數增加，且易受網絡波動的影響。文獻[14]中提出的調度算法，在MinRTT的基礎上加入了鏈路擁塞狀況的考慮，通過分配與鏈路可用容量成比例的數據包，盡可能避免擁塞來提高吞吐量，但對于可用容量的計算會因為網絡變化出現誤差。BLEST[16]則通過檢測發送窗口是否阻塞，最大限度地減少異構網絡中的LOL阻塞問題，從而減少重傳數量提高吞吐量。

3.多路徑傳輸性能分析

為了驗證MPTCP的可靠性，在VMware平臺安裝IEFT發布的Linux-MPTCP操作系統，配置了三個網絡接口，使用MPTCP默認的三種傳輸調度算法MinRtt、Round Robin(RR)和Opportunity Redundant(OR)進行文件傳輸速率測試，并于傳統TCP傳輸進行比較。實驗中設計了兩種實驗場景，在鏈路差異較小的情況，三個網絡接口的帶寬分別為：10M，9M，8M；鏈路差異較大的場景下，網絡接口的帶寬為：10M，5M，1M；TCP實驗組網絡接口帶寬固定為10M。每組實驗做五次，并取實驗結果平均值作為最終的結果。

實驗結果顯示傳統TCP的平均傳輸速率為1.1M/s，而MPTCP的傳輸速率隨鏈路的差異大小而變化。如表1所示，在鏈路差異較小的情況下，MPTCP傳輸速率可以達到傳統TCP的250%；而在鏈路差異較大的情況下，MPTCP的傳輸性能只有傳統TCP的53%。可見網絡環境的差異性對于MPTCP的傳輸性能影響很大。

表1 MPTCP與TCP下載性能對比

接下來通過動態的加載網卡實驗來表現網絡環境差異性與動態性的綜合影響，該實驗初始時只有一個網卡投入使用，之后每隔10秒多加載一塊網卡，最多同時加載三塊，實驗結果如圖1所示。在鏈路差異較小的情況下動態的加載網卡，整體的網絡傳輸速率呈線性的上升；而當鏈路差異較大時，動態的加載網卡對傳輸性能提升有限，而且隨著網卡數量的逐漸增加，傳輸性能反而大幅下降。

圖1 網絡接口動態加載

4.問題模型與解決方案

為了能夠在異構網絡中降低傳輸延遲，我們進行以下建模分析。

參數列表 說明n 未發送的數據包數量n′ 可能造成尾延遲的數據包數量m可用鏈路數量i當前鏈路i cwndi 鏈路i當前可用的擁塞窗口rtti 鏈路i當前的往返延遲

表2 參數說明

每輪的發送周期以當前時刻未發送的數據包作為接下來需要傳輸調度的數據。假設一個周期內存在n個數據包需要發送，終端設備擁有m條可用鏈路，每條鏈路的擁塞窗口大小為cwndi，每條鏈路的往返時延為rtti，傳輸調度算法需要設計合理的調度算法來給每條鏈路分配數據包，使得傳輸任務總延遲T最低。假設一個周期內，每條鏈路需要發送的數據包數量為si，則每條鏈路的傳輸完成時間ti可以通過公式（1）的分段函數求出。在實際傳輸過程中，未填充滿擁塞窗口的數據傳輸仍會耗時一個rtt，所以需要合理的給子流分配數據包，盡可能的同步子流的完成時間，提高每條鏈路的使用效率，減少每個周期傳輸任務的完成時間。即在求解ti的時候需要盡可能的滿足si%cwndi=0 的條件。（1）

通過對以上問題的建模，可以得到： （2）

由于該模型目標函數t 是非線性的，隨著數據包數量的增加，目標函數圖像呈階梯狀。又由于決策變量s和鏈路的窗口cwnd、時延rtt為離散的整數，所以該問題是混合整數非線性規劃問題，是非凸優化問題[18]。這類問題通常是NP的，無法在多項式時間內求解出最優解，可以使用近似算法得到近似解。

4.1多路徑并發傳輸

首先多路徑并發傳輸模塊作為SCTC算法的一部分，在發送緩沖區數據較大時調用，此時各鏈路可以充分利用帶寬資源。該部分按照鏈路的數據傳輸速率來為每條鏈路分配數據包，其中cwndi可以表示鏈路的實際網絡負載能力，rtti表示鏈路的往返時延，用來代表鏈路的實際網絡傳輸能力。該調度算法在終端需要發送數據的時候調用，分配的數據即為當前發送緩沖區的數據，該調度算法根據各鏈路的傳輸速率的比例分配傳輸任務，盡量實現各子流完成時間同步。在傳輸過程中產生新的發送請求則等待當前傳輸任務都結束后執行，傳輸調度算法默認每個發送周期內網絡參數不變。偽代碼如下所示。

Repeat

篩選出當前所有擁有擁塞窗口的鏈路集合sbfCandidates

if sbfCandidates is NULL

當前無可用鏈路，退出并等待下一個發送周期

else

Until（鏈路選擇結束）

圖2 尾延遲

在每個發送周期內，該模塊首先篩選出當前所有的具備擁塞窗口的可用鏈路，之后計算的各個子流的傳輸速率并優先選擇傳輸速率大的鏈路分配傳輸任務。這個方法可以在一定程度上緩解鏈路異構性帶來的影響，但該方法通過公式（1）計算得到的子流完成時間差異仍比較大。如圖2所示，T′為理想的完成時間線，即n個數據包按照MPTCP所有鏈路的傳輸能力之和計算所需要花費的時間，但一般情況下很難實現絕對同步的情況；T為執行該調度算法完成傳輸任務的實際完成時間線，可以按照公式（1）計算，各鏈路最后一次都會傳輸少量的剩余數據。T-T′為尾延遲。可以分析得到尾延遲現象的原因是快速鏈路的使用效率較低，慢鏈路上負載了較多的數據傳輸任務，且尾延遲現象會隨著鏈路差異性的增加，越來越明顯。

4.2尾延遲處理

圖3 SCTC鏈路選擇流程

為了盡可能避免尾延遲現象對整體傳輸延遲的影響，需要進一步完善傳輸調度算法SCTC。由于模型（2）是NP的，無法在有限時間內求出最優解，所以為了能夠盡可能的同步子流的完成時間，SCTC在造成尾延遲的部分數據通過貪心算法來獲得次優解。

在多路徑并發傳輸階段每條鏈路進行數據傳輸的數據量是其擁塞窗口的整數倍，各子流完成所分配的數據傳輸任務所需要的時間為如公式（3）所示：

結合公式（1）與公式（3），子流的完成時間滿足等式（4），當si剛好為子流擁塞窗口的整數倍時，不存在造成尾延遲的數據，所以其傳輸任務完成時間等于公式（1）計算所得時間；如果si不是子流擁塞窗口的整數倍，則此時其完成時間與公式（1）計算所得相差一個rtti的時間，傳輸調度算法所要做的正是優化由于子流鏈路屬性差異性使得最后一次傳輸造成子流完成時間的不同步，以減少總的傳輸時間。（4）

SCTC用n′表示剩余未分配的數據包。通過公式（5）可求得n′。如果多路徑并發傳輸階段T′=T，則n′=0，各子流的傳輸完成時間完美同步，不需要優化；若每條鏈路在最后一次傳輸時其擁塞窗口都只差一個數據包塞滿時，此時n′獲得最大值，是最壞情況，不存在優化空間。n′取值范圍如公式（6）所示。

圖4 實驗架構

圖5 不同帶寬下文件下載實驗

圖6 網頁對象加載實驗

經過上面的分析，尾延遲是由于快速鏈路的使用效率低造成的，所以分配最后的n′個數據包時，優先選擇可以提前完成任務的鏈路k，貪心規則為：

其中ti為鏈路i當前任務的完成時間，rtti為鏈路i的往返時延。

傳輸速率優先模塊分配數據時，會出現數據無法完整的填充子流擁塞窗口的現象，剩下的數據雖然很少，但仍需要一個rtt的傳輸時間，所以使用傳輸速率優先模塊的傳輸時間為T=t′i+rttmax；而做了尾延遲處理的SCTC傳輸完成時間是T′=Min(t′i+rtti)，可得出T′≤T。SCTC算法偽代碼與流程圖如下所示：

Repeat

篩選出當前所有擁有擁塞窗口的鏈路集合sbfCandidates

if sbfCandidates is NULL

當前無可用鏈路，退出并等待下一個發送周期

else

統計未發送數據包數量R1與所有鏈路剩余擁塞窗口數量R2。

if R1 < R2

貪心選擇最先完成傳輸任務的鏈路

else

優先選擇傳輸速率最大的鏈路

Until（鏈路選擇結束）

具體流程如圖3所示，首先選取所有的可用鏈路，并統計未發生的數據包數量R1和當前剩余的擁塞窗口R2，如果 R1>R2 時，此時優先選擇發送速率大的鏈路分配數據，盡可能快的將數據傳遞到對端；若 R1≤R2 ,則說明此時鏈路的擁塞窗口可能填充不滿，所以為了盡量避免尾延遲，需要優先選擇可以提前完成傳輸任務的鏈路。

5.實驗

5.1實驗設置

為了驗證SCTC傳輸調度算法的性能，通過VMware虛擬機平臺搭建了實驗環境；其中服務端主機安裝了搭載PROGMP編程模型的MPTCP內核，客戶端安裝IETF官網發布的Linux-MPTCP。實驗環境中的主機操作系統均為ubuntu 18.04，配置多個網卡。實驗過程中通過VMware網卡設置功能修改client端網卡的RTT、帶寬等網絡參數模擬各類網絡狀況，并與linux-mpTCP中集成的minRtt、Round Robin(RR)和 Opportunity Redundant(OR)三種調度算法進行性能對比。實驗架構模型圖如圖4所示。

5.2實驗結果分析

首先進行文件下載場景下的性能測試。該試驗共進行四組實驗，分別下載不同大小的文件，將SCTC與linux-MPTCP集成的三種傳輸調度算法進行下載時間的比較，同時為了確定網卡性能差異性帶來的影響，先將一個網卡的帶寬設置為1M，將另一個網卡的帶寬值由1M逐漸變為10M，圖5的橫坐標表示的就是第二個網卡的帶寬值。可以看出，隨著第二塊網卡的帶寬逐漸增大，文件的下載時間前期是逐漸減少的，但隨著鏈路之間網絡性能差異越來越大，下載時間后面會小幅度的增加。本文中所提出SCTC算法在實驗中表現良好，通過圖5可以看出該算法更適用于中等大小的文件，對于64K這樣足夠小文件和4M這樣的大文件傳輸調度算法對總的下載時間影響較小，總體來說相比于linux-MPTCP默認的MinRtt調度算法性能提升了約24%，與RR和OR比起來也有不少的提升。

接著測試傳輸調度算法在子流網絡環境差異較大的情況下加載網絡頁面的性能。客戶端設置了三個網卡，帶寬分別為1M、5M和10M。將故宮官網首頁部署服務器端，共包含53個網絡文件，客戶端瀏覽器加載網頁時，將一直保持與服務器的網絡連接，持續下載網絡文件。圖6左圖描述了從請求網頁到頁面完全加載的時間，SCTC較其他三種傳輸調度算法加載時間減少約25%；圖6右圖顯示了網頁內全部網絡文件從瀏覽器請求到完成加載的時間CDF圖，SCTC傳輸調度算法較其他三種傳輸調度算法提前加載96.7%的網絡文件。結果顯示SCTC可以較好的應對網頁加載的場景。

最后測試調度算法在網絡差異較大的環境下播放dash視頻時可以達到的碼率以及對應的分辨率。實驗環境中，客戶端配備了三個網卡，帶寬分別為1M、5M和10M，同時使用ffmpeg工具將測試視頻分別轉碼為360P、480P、720P、1080P和1080P（60幀）的視頻段，并使用開源的dash.js播放器進行播放。實驗結果如表3所示，SCTC傳輸調度算法相較與其他三種調度算法，在網絡差異較大的環境下可以將播放視頻的分辨率穩定在720P，碼率為1310kbps，性能較minRtt調度算法性能提高了56%，測試結果表明SCTC傳輸調度算法可以有效的應對視頻流這樣的突發流量。

表3 Dash視頻播放測試

6.總結

本文中提出了一種新的MPTCP傳輸調度算法，首先通過一些實驗證實了各鏈路網絡的差異性與動態性對傳輸性能的影響。之后通過公式推導，將SCTC傳輸調度算法分為兩個算法模塊：可以優先選擇傳輸速率快的鏈路傳輸數據，以達到快速降低傳輸延遲的目的；在數據量較少時貪心的選擇最先完成的鏈路，可以避免尾延遲對傳輸性能的影響。最后通過進行仿真實驗測試該算法在文件下載、網頁加載和視頻播放等常見場景下的性能，并與現有的三種傳輸調度算法進行了對比，結果表明SCTC傳輸調度算法性能較好，可以降低傳輸延遲。