黃培紀(jì) 蔣艷 陳斌 李靜 董蘋蘋 張連明

摘? 要： 基于MPQUIC協(xié)議優(yōu)化多路徑調(diào)度算法，可進(jìn)一步增強(qiáng)多路徑聚合帶來的性能提升。因此提出一個基于MPQUIC的調(diào)度算法。在數(shù)據(jù)傳輸之前，該算法通過線性規(guī)劃合理地分配不同路徑上的數(shù)據(jù)傳輸量，在盡量減小路徑之間的傳輸完成時間差距的同時，最小化整體的傳輸完成時間?；贛ininet虛擬網(wǎng)絡(luò)環(huán)境仿真平臺，模擬了不同網(wǎng)絡(luò)環(huán)境進(jìn)行數(shù)據(jù)傳輸，實驗結(jié)果表明，該算法的表現(xiàn)優(yōu)于minRTT、ECF、BLEST算法。

關(guān)鍵詞： QUIC； MPQUIC； 多路徑調(diào)度； 線性規(guī)劃

中圖分類號：TP393.2? ? ? ? ? 文獻(xiàn)標(biāo)識碼：A? ? ?文章編號：1006-8228（2023）06-38-05

MPQUIC scheduling algorithm based on linear programming

Huang Peiji， Jiang Yan， Chen Bin， Li Jing， Dong Pingping， Zhang Lianming

（College of Information Science and Engineering， Hunan Normal University， Changsha， Hunan 410081， China）

Abstract： In order to enhance the performance gains from multipath aggregation and optimize the multipath scheduling algorithm based on the MPQUIC， a scheduling algorithm based on MPQUIC is proposed. Before starting the data transfer， the amount of data to be transferred on each path is reasonably allocated by linear programming. It not only minimizes the transmission completion time， but also minimizes the transmission completion time gap between different paths. The data transmission in different network environments is simulated based on Mininet， and the results show that this algorithm outperforms the minRTT， ECF， and BLEST algorithms.

Key words： QUIC; MPQUIC; multipath scheduling; linear programming

0 引言

近年來，隨著互聯(lián)網(wǎng)的快速發(fā)展，互聯(lián)網(wǎng)承載的數(shù)據(jù)傳輸量越來越多，用戶對體驗質(zhì)量的要求也逐步提高。另外，現(xiàn)在的筆記本電腦和智能手機(jī)都可以利用多個網(wǎng)絡(luò)接口（例如Wi-Fi、4G/5G）進(jìn)行網(wǎng)絡(luò)通信[1]。然而，當(dāng)前廣泛使用的傳輸層控制協(xié)議（TCP， Transmission Control Protocol）較為臃腫與僵化，且只能使用其中一個網(wǎng)絡(luò)接口進(jìn)行通信，這愈發(fā)難以滿足業(yè)務(wù)的要求與用戶體驗高質(zhì)量的需求。因此，輕巧靈活的快速UDP互聯(lián)網(wǎng)連接協(xié)議（QUIC， Quick UDP Internet Connections）與多路徑傳輸協(xié)議研究成為熱點[2]。

QUIC是一個由Google提出的、類似TCP的傳輸層協(xié)議[3]，底層使用UDP協(xié)議進(jìn)行通信。但QUIC無法有效地同時利用多條網(wǎng)絡(luò)路徑進(jìn)行數(shù)據(jù)傳輸，為此，De Coninck等人[4]在QUIC的基礎(chǔ)上提出了多路徑QUIC（MPQUIC， Multipath QUIC）。MPQUIC允許傳輸層的一條連接對應(yīng)物理層的多條路徑，以此來實現(xiàn)多條路徑帶寬的聚合，減小數(shù)據(jù)傳輸所需要的時間。在多路徑數(shù)據(jù)傳輸中，能否合理地使用多條路徑極大地影響著多路徑傳輸?shù)男阅?。為此，需要設(shè)計一個有效的、合理的調(diào)度算法，路徑調(diào)度算法決定著數(shù)據(jù)包會在哪一條路徑上進(jìn)行傳輸。

綜上所述，本文在De Coninck等人所提出的MPQUIC基礎(chǔ)上，考慮不同路徑之間存在的差異，提出一個基于線性規(guī)劃的路徑調(diào)度算法。算法通過減少不同路徑間的傳輸完成時間差異，避免因為某一條路徑傳輸完成時間過長而導(dǎo)致整體的傳輸完成時間過長，從而充分使用所有的可用路徑，減少數(shù)據(jù)傳輸時間。

1 背景知識

1.1 QUIC

QUIC由Google首次公開提出于2012年的互聯(lián)網(wǎng)工程任務(wù)組（IETF， Internet Engineering Task Force）討論會議上。隨后，QUIC的標(biāo)準(zhǔn)化工作交由IETF接管，并發(fā)布了正式的QUIC標(biāo)準(zhǔn)。

相比于TCP，QUIC具有很多優(yōu)點。例如，TCP每次建立連接時需要2-RTT來進(jìn)行三次握手，而QUIC在大部分的情況下可以做到0-RTT建立連接并開啟數(shù)據(jù)傳輸。QUIC當(dāng)前默認(rèn)的擁塞控制算法是Cubic，由于QUIC是部署在用戶空間，可以根據(jù)需求靈活地選取合適的擁塞控制算法，但這對于部署在系統(tǒng)內(nèi)核中的TCP來說是很難做到的。另外，TCP是依據(jù)四元組惟一標(biāo)識一個連接，而QUIC是依據(jù)連接ID來惟一標(biāo)識一個連接，當(dāng)端口、IP等發(fā)生改變時，QUIC并不需要重新建立連接。所以，QUIC相比于TCP具備部署方便、高效與靈活等特性，更加符合當(dāng)前業(yè)務(wù)和用戶體驗的要求。

1.2 MPQUIC

在多路徑TCP（MPTCP， Multipath TCP）協(xié)議的啟發(fā)下，De Coninck等人將多路徑傳輸機(jī)制引入到QUIC中，提出了MPQUIC協(xié)議，其具體框架如圖1所示。MPQUIC可以同時使用客戶端和服務(wù)器之間的多條路徑，加快數(shù)據(jù)傳輸速率，同時還能靈活切換數(shù)據(jù)的傳輸路徑，保證良好的傳輸性能，增強(qiáng)故障排除能力。

在多路徑傳輸協(xié)議中，合理的路徑調(diào)度算法和良好的數(shù)據(jù)管理機(jī)制是獲得優(yōu)良性能的關(guān)鍵[5]。在路徑調(diào)度方面，MPQUIC可以直接從路徑管理器中獲取全局視圖，全局視圖中記錄著所有的可用路徑與其具體信息，可以用來檢測性能不佳或中斷的路徑，以便加快數(shù)據(jù)傳輸過程中的路徑切換[6]。當(dāng)存在多條可用路徑時，發(fā)送方需要選擇一條合適的路徑來傳輸數(shù)據(jù)包，而這種選擇是由路徑調(diào)度算法所決定的。

1.3 線性規(guī)劃

線性規(guī)劃是運(yùn)籌學(xué)中數(shù)學(xué)規(guī)劃的一個重要分支，并且，由George Dantzig于1947年提出的求解線性規(guī)劃的單純形法使得線性規(guī)劃在理論上趨于成熟。在實踐中，線性規(guī)劃是現(xiàn)代管理中經(jīng)常使用的基本方法之一，并且可以通過使用計算機(jī)去處理具有數(shù)千個約束和決策變量的線性規(guī)劃問題。

線性規(guī)劃問題是在一組線性約束下尋找線性目標(biāo)函數(shù)的最大值或最小值，其目標(biāo)函數(shù)和約束都是線性函數(shù)，且目標(biāo)函數(shù)能夠找到最大值或最小值。對于線性規(guī)劃問題的解，滿足定義的約束的解稱為可行解，使目標(biāo)函數(shù)最大化或最小化的可行解稱為最優(yōu)解，所有可行解的集合稱為問題的可行域。

2 相關(guān)工作

隨著多路徑傳輸協(xié)議的不斷發(fā)展，路徑的異構(gòu)性會大大削減多路徑傳輸性能這一問題引起研究者的廣泛關(guān)注。路徑的異構(gòu)性指的是多條路徑的帶寬、時延等存在差異，這個差異增加了數(shù)據(jù)亂序到達(dá)的可能性，從而降低了多路徑數(shù)據(jù)傳輸?shù)男阅躘2]。為此，眾多研究者在MPTCP或MPQUIC的基礎(chǔ)上，提出了不同的路徑調(diào)度算法。

MPQUIC默認(rèn)的調(diào)度算法是minRTT[4]，它按照往返時延（RTT， Round-Trip Time）從小到大的順序循環(huán)路徑傳輸數(shù)據(jù)，并沒有考慮路徑的帶寬和異構(gòu)性，容易導(dǎo)致傳輸時間變長。Wang等人[7]提出了一種基于優(yōu)先級的移動HTTP/2流調(diào)度算法。調(diào)度算法根據(jù)流的大小和依賴樹的信息，基于加權(quán)輪詢（WRR， Weighted Round Robin）算法計算流傳輸?shù)捻樞?，然后以獨占方式傳輸每個流。雖然與默認(rèn)的循環(huán)機(jī)制相比，該方法減少了阻塞時間，但它過于依賴HTTP/2依賴樹。不管傳輸路徑是否空閑，當(dāng)被依賴流尚未發(fā)送時，依賴該流的其他流只能等待，導(dǎo)致資源浪費(fèi)和傳輸時間增加。

Lim等人[8]提出了最早完成優(yōu)先（ECF， The Earliest Completion First）算法，利用路徑的RTT、帶寬和連接級發(fā)送緩沖區(qū)大小等相關(guān)信息，基于MPTCP提出了新的路徑調(diào)度算法。在存在路徑異質(zhì)性的情況下，ECF能夠有效利用所有可用路徑，特別是對Web網(wǎng)頁瀏覽、流媒體視頻傳輸時，有更好的表現(xiàn)。Ferlin等人提出了[9]發(fā)送窗口阻塞估計調(diào)度（BLEST， Blocking Estimation-based MPTCP Scheduler）算法，旨在最小化異構(gòu)網(wǎng)絡(luò)中的隊頭阻塞，從而通過減少虛假重發(fā)的數(shù)量來增加帶寬聚合的能力。雖說ECF與BLEST各有千秋，但它們的提出都是基于MPTCP，而TCP協(xié)議并不會考慮到不同被傳輸?shù)臄?shù)據(jù)流之間的關(guān)系，例如流的優(yōu)先級、流之間的依賴等。

為了能夠更充分利用多路徑資源，更進(jìn)一步提高M(jìn)PQUIC的性能，本文提出了一個線性規(guī)劃調(diào)度算法（LPS， Linear Programming Scheduler）。LPS使用線性規(guī)劃算法來分配數(shù)據(jù)流在不同路徑上所傳輸?shù)臄?shù)據(jù)量，在最小化不同路徑上完成數(shù)據(jù)傳輸所需的時間差距的同時，減小整體的傳輸完成時間。

3 LPS算法

3.1 LPS概述

LPS是一個基于MPQUIC的路徑調(diào)度算法，旨在減小多路徑數(shù)據(jù)傳輸?shù)耐瓿蓵r間。算法通過分析數(shù)據(jù)流與路徑的信息，將打包好的數(shù)據(jù)流合理分配到不同的路徑上進(jìn)行傳輸，避免出現(xiàn)大量數(shù)據(jù)集中在某一條路徑上進(jìn)行傳輸?shù)那闆r，盡可能使得不同路徑上的數(shù)據(jù)同時完成傳輸并最小化數(shù)據(jù)傳輸完成時間。

LPS的傳輸調(diào)度過程如圖2所示。當(dāng)服務(wù)器與客戶端建立連接時，服務(wù)器的路徑管理器可以獲得每條路徑的屬性以及要傳輸?shù)臄?shù)據(jù)流，例如帶寬、擁塞窗口（CWND）、RTT、流的大小等。LPS按照RTT對可用路徑進(jìn)行升序排序，并按優(yōu)先級對流進(jìn)行降序排序，再根據(jù)線性規(guī)劃算法在路徑上預(yù)先分配數(shù)據(jù)傳輸量。接下來，根據(jù)算法預(yù)先分配的結(jié)果，服務(wù)器使用MPQUIC協(xié)議將數(shù)據(jù)包發(fā)送給客戶端。最后，當(dāng)接收到數(shù)據(jù)時，客戶端將ACK幀發(fā)送至服務(wù)器，以表示數(shù)據(jù)已被接收，并且服務(wù)器更新其CWND。

3.2 問題建模

為了形式化該問題，首先假設(shè)有n條可用路徑和m個流，并按照優(yōu)先級對流進(jìn)行降序排序。設(shè)Ri表示可用路徑i的RTT，Bi表示可用路徑i的帶寬，Sj表示流j的大小，其中[i∈[1，n] ， j∈[1，m]]。如果流j通過可用路徑i傳輸了大小為Cij的數(shù)據(jù)，則稱流j調(diào)度在可用路徑i上的數(shù)據(jù)比例為Xij，其計算過程如公式⑴所示。

[Xij=CijSj]? ⑴

為了降低計算難度，我們簡單將可用路徑i完成數(shù)據(jù)傳輸所需的時間假設(shè)為Ti，其計算過程如公式⑵。

[Ti=j=1mCijBi+Ri]? ⑵

只有當(dāng)所有的路徑都完成了數(shù)據(jù)的傳輸后，本次傳輸才能結(jié)束，且耗時為[T=max（T1，T2，T3，...，Tn）]。所以，想要提高用戶體驗，減少數(shù)據(jù)加載等待時間，則需最小化傳輸耗時T。

3.3 解決方案

為了能夠最小化T，我們使用線性規(guī)劃計算所有流的調(diào)度比例Xij。求解線性規(guī)劃問題是需要在可行域中尋找最優(yōu)解，假設(shè)D是傳輸時間的上限，我們給出兩個約束函數(shù)，如公式⑶、公式⑷。

[Ti≤D， 1≤i≤n]? ⑶

[i=1nCijBi≤D ， 1≤j≤m]? ⑷

另外，如果D設(shè)置得不合理，則得出的解不會是最優(yōu)解。在LPS中，D被設(shè)置為：

[D=max（j=1mSjB1+R1 ， ... ， j=1mSjBn+Rn）]? ⑸

然而這兩個約束沒有考慮路徑之間的RTT異質(zhì)性。如果僅使用這兩個約束，流j將優(yōu)先在具有高帶寬的路徑上傳輸。這樣就有可能導(dǎo)致大部分的數(shù)據(jù)都在高帶寬高RTT的路徑上傳輸，此時，若存在低帶寬低RTT的路徑的話，那這條路徑資源就不會被充分利用，導(dǎo)致最終傳輸完成時間仍然居高不下。所以，為了能夠得到最優(yōu)解，需要將可用路徑的RTT引入到約束中進(jìn)行計算，同時盡量縮減不同路徑的傳輸時間差距，使得每一條路徑都能夠被充分利用。根據(jù)上述描述，為了縮減不同路徑的傳輸時間差距，給出第三個約束函數(shù)，如公式⑹。

[|Ti-Tk|≤L ， 1≤k

其中，L指的是一個較小的值，用于限制兩個路徑傳輸完成時間之間的差距。若L過小，則可能不存在可行域；但若L過大，則會影響算法的效果。在LPS中的初始值被設(shè)定為5ms，若不存在可行域，則往上遞增5ms，直至存在可行域。

在公式⑹的約束下，所有路徑的傳輸完成時間都較為相近，故我們將線性規(guī)劃的最小化目標(biāo)函數(shù)設(shè)置為：

[mini=1nTi] ⑺

在求解出Xij后，計算數(shù)據(jù)流在不同路徑上傳輸?shù)臄?shù)據(jù)量Cij。在可用路徑i上，優(yōu)先級越大的流會越早被傳輸。最后，根據(jù)預(yù)先分配好的數(shù)據(jù)量，將數(shù)據(jù)流調(diào)度到不同的路徑上進(jìn)行傳輸。

4 性能測試

在本節(jié)中，基于Golang語言實現(xiàn)了LPS，并在不同的網(wǎng)絡(luò)狀態(tài)下進(jìn)行文件傳輸，將其傳輸完成時間與minRTT、ECF、BLEST這三個調(diào)度算法進(jìn)行對比。

接下來本文將評估一個大小為1024KB的文件在不同路徑狀態(tài)下的完成時間。為了模擬不同的網(wǎng)絡(luò)狀態(tài)，本文參考MPQUIC的實驗裝置[4]，將該網(wǎng)絡(luò)拓?fù)湓O(shè)計為：兩條獨立的傳輸路徑與基于這兩條路徑進(jìn)行Web對象傳輸?shù)目蛻舳撕头?wù)器組成，拓?fù)鋱D如圖1所示。且在多個虛擬機(jī)上基于Mininet設(shè)置了不同的仿真網(wǎng)絡(luò)環(huán)境，分別模擬時延異構(gòu)、帶寬異構(gòu)、時延與帶寬異構(gòu)對多路徑數(shù)據(jù)傳輸?shù)挠绊憽Ｔ谶@些仿真網(wǎng)絡(luò)環(huán)境上，使用不同的路徑調(diào)度算法進(jìn)行數(shù)據(jù)傳輸，并記錄客戶端從啟動到完成所有數(shù)據(jù)傳輸所消耗的時間，最后對多次實驗后所記錄的時間取均值。

4.1 時延異構(gòu)

為了模擬時延異構(gòu)，本文首先將兩條路徑的帶寬固定為1Mbps，將路徑1的RTT設(shè)置為1ms，并將路徑2的RTT從1ms不斷增加到400ms，以增加兩條路徑之間的RTT異構(gòu)性。每種算法的結(jié)果如圖3所示。

從實驗結(jié)果可以看出，在時延異構(gòu)性較小的時候，不同的調(diào)度算法下的傳輸時間差距較小。在時延異構(gòu)性逐漸增大的時候，LPS調(diào)度算法的傳輸完成時間最少，BLEST與ECF調(diào)度算法的表現(xiàn)略優(yōu)于minRTT調(diào)度算法。

4.2 帶寬異構(gòu)

為了模擬帶寬異構(gòu)，本文將兩條路徑的RTT固定為1ms，將路徑1的帶寬設(shè)置為1Mbps，將路徑2的帶寬從1Mbps不斷增加到100Mbps，以增加兩條路徑之間的帶寬異構(gòu)性。實驗結(jié)果如圖4所示。

從實驗結(jié)果可以看出，在路徑帶寬異構(gòu)性逐漸增大時，相比于其他三種調(diào)度算法，LPS在帶寬異構(gòu)性大的時候表現(xiàn)較為優(yōu)異。而帶寬異構(gòu)性較小的時候，四種調(diào)度算法表現(xiàn)差距較小。

4.3 時延與帶寬異構(gòu)

最后，為了同時模擬時延異構(gòu)與帶寬異構(gòu)，本文將路徑1的帶寬與時延固定為1Mbps與1ms，路徑2的帶寬與時延分別設(shè)置為20Mbps、40Mbps、60Mbps與100ms、200ms，以同時增加路徑的時延異構(gòu)性與帶寬異構(gòu)性。實驗結(jié)果如圖5所示。

從實驗結(jié)果可以看出，路徑的時延異構(gòu)性與帶寬異構(gòu)性同時增大時，LPS仍然保持優(yōu)越的性能，且BLEST與ECF調(diào)度算法的表現(xiàn)略優(yōu)于minRTT調(diào)度算法。

5 結(jié)論

本文為充分發(fā)揮多路徑的效率，提高傳輸速率，在MPQUIC的基礎(chǔ)上提出了LPS算法。LPS通過線性規(guī)劃來調(diào)度多條路徑上的數(shù)據(jù)傳輸，在試圖平衡每條路徑上的傳輸完成時間的同時，最小化整體的傳輸完成時間。最后基于仿真平臺進(jìn)行實驗，驗證了該方法的有效性。但對傳輸時間的計算較為簡單，與真實的傳輸時間相比存在一定的偏差，且沒有考慮到網(wǎng)絡(luò)的波動情況。因此，如何更精準(zhǔn)地計算傳輸完成時間、如何更合理地將線性規(guī)劃應(yīng)用在路徑調(diào)度上，還有待進(jìn)一步的研究。

參考文獻(xiàn)（References）：

[1] Zeng H， Cui L， Tso F P， et al. Optimizing multipath QUIC

transmission over heterogeneous paths[J]. Computer Networks，2022，215：109198

[2] 張思愜.無線網(wǎng)絡(luò)中傳輸控制新技術(shù)研究[D].碩士，西安

電子科技大學(xué)，2019

[3] Lee S， Yoo J. Reinforcement Learning Based Multipath

QUIC Scheduler for Multimedia Streaming[J].Sensors，2022，22（17）：6333

[4] De Coninck Q， Bonaventure O. Multipath QUIC： Design

and Evaluation[C]//Proceedings of the 13th international conference on emerging networking experiments and technologies，2017：160-166

[5] Dong E， Xu M， Fu X， et al. A loss aware MPTCP scheduler

for highly lossy networks[J]. Computer Networks，2019，157：146-158

[6] Schmidt T， Deutschmann J， Hielscher K S， et al. POSTER：

Revisiting Multipath QUIC Experiments and Comparing them with more recent Multipath TCP Implementations[C]//2021 IEEE International Symposium on Local and Metropolitan Area Networks （LANMAN）. IEEE，2021：1-2

[7] Wang J， Gao Y， Xu C. A multipath QUIC scheduler for

mobile HTTP/2[C]//Proceedings of the 3rd Asia-Pacific Workshop on Networking 2019，2019：43-49

[8] Lim Y， Nahum E M， Towsley D， et al. ECF： An MPTCP

path scheduler to manage heterogeneous paths[C]//Proceedings of the 13th international conference on emerging networking experiments and technologies，2017：147-159

[9] Ferlin S， Alay ?， Mehani O， et al. BLEST： Blocking

estimation-based MPTCP scheduler for heterogeneous networks[C]//2016 IFIP networking conference （IFIP networking） and workshops. IEEE，2016：431-439