基于線性規(guī)劃的MPQUIC調(diào)度算法

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

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

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

中圖分類(lèi)號(hào)：TP393.2? ? ? ? ? 文獻(xiàn)標(biāo)識(shí)碼：A? ? ?文章編號(hào)：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 引言

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

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

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

1 背景知識(shí)

1.1 QUIC

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

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

1.2 MPQUIC

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

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

1.3 線性規(guī)劃

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

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

2 相關(guān)工作

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

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

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

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

3 LPS算法

3.1 LPS概述

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

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

3.2 問(wèn)題建模

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

[Xij=CijSj]? ⑴

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

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

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

3.3 解決方案

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

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

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

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

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

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

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

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

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

[mini=1nTi] ⑺

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

4 性能測(cè)試

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

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

4.1 時(shí)延異構(gòu)

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

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

4.2 帶寬異構(gòu)

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

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

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

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

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

5 結(jié)論

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