葉寧，董蘋蘋，段桂華，王建新

?

基于數(shù)據(jù)流特性的MPTCP數(shù)據(jù)流調(diào)度算法研究

葉寧1，董蘋蘋2，段桂華1，王建新1

(1. 中南大學(xué) 信息科學(xué)與工程學(xué)院，湖南 長沙，410083；2. 湖南師范大學(xué) 計算機(jī)教學(xué)部，湖南 長沙，410081 )

基于廣域網(wǎng)中使用MPTCP協(xié)議進(jìn)行數(shù)據(jù)傳輸時，由于短流的傳輸數(shù)據(jù)量小，每條子流的擁塞窗口在其生命周期內(nèi)保持很小的狀態(tài)，這使得1個數(shù)據(jù)包的丟失也可能導(dǎo)致超時現(xiàn)象發(fā)生，從而增大數(shù)據(jù)流的完成時間，為此，提出一種根據(jù)MPTCP數(shù)據(jù)流特性進(jìn)行MPTCP數(shù)據(jù)流調(diào)度的算法MPTCP-FSFSm(multi-path TCP flow scheduling based on flow size)。首先，MPTCP-FSFS算法根據(jù)MPTCP數(shù)據(jù)流需要發(fā)送的數(shù)據(jù)量將MPTCP數(shù)據(jù)流分類；然后，發(fā)送端根據(jù)當(dāng)前每條路徑往返時延進(jìn)行MPTCP數(shù)據(jù)流調(diào)度：對于短流，選擇往返時延最小的若干條路徑進(jìn)行數(shù)據(jù)流傳輸；對于長流，使用所有的路徑進(jìn)行數(shù)據(jù)流傳輸。研究結(jié)果表明：與MPTCP相比，MPTCP-FSFS在保證長流吞吐率的基礎(chǔ)上，能夠明顯降低短流的數(shù)據(jù)流完成時間，同時提高數(shù)據(jù)流平均吞吐率。

MPTCP；數(shù)據(jù)流特性；路徑往返時延；數(shù)據(jù)流調(diào)度

隨著互聯(lián)網(wǎng)的迅速發(fā)展，互聯(lián)網(wǎng)上傳輸?shù)臄?shù)據(jù)量越來越多。據(jù)文獻(xiàn)[1]，網(wǎng)絡(luò)中99%的數(shù)據(jù)流小于 100 MB，但90%的數(shù)據(jù)流量由100 MB到1 GB之間的數(shù)據(jù)流提供，呈現(xiàn)短流數(shù)目多但是傳輸?shù)臄?shù)據(jù)量小的特性。實時分析[2?3]和在線交互式應(yīng)用如網(wǎng)頁搜索和查詢業(yè)務(wù)、各種社交網(wǎng)站和在線零售業(yè)務(wù)等，經(jīng)常產(chǎn)生大量短流，考慮到用戶體驗感，短流的完成時間要盡可能小，即短流對于數(shù)據(jù)流完成時間(flow completion time, FCT)敏感。然而，網(wǎng)絡(luò)中傳輸?shù)拇罅繑?shù)據(jù)由長流提供，長流對于吞吐率(throughput)的要求高。當(dāng)所有流使用TCP 協(xié)議時，如果短流與長流競爭，由于隊列堆積，會導(dǎo)致短流完成時間長，同時長流不能將擁塞轉(zhuǎn)移，導(dǎo)致吞吐率低且網(wǎng)絡(luò)的利用率低。另外，在當(dāng)前互聯(lián)網(wǎng)中，具有多條并行接入通道的多宿主主機(jī)越來越多，多宿主主機(jī)配置多塊網(wǎng)卡，因此，多宿主主機(jī)之間可以建立多條可用路徑。為了充分利用多條路徑的發(fā)送能力并且最大化資源使用率，IETF(Internet Engineering Task Force Internet，互聯(lián)網(wǎng)工程任務(wù)組)提出了MPTCP(multi-path TCP)[4?5]。在完全兼容傳統(tǒng)TCP的基礎(chǔ)上，MPTCP 能同時利用多個網(wǎng)絡(luò)接口建立多條子流進(jìn)行數(shù)據(jù)傳輸[6]，提升網(wǎng)絡(luò)吞吐率。KHEIRKHAH等[7]發(fā)現(xiàn)在MPTCP協(xié)議中，使用多條子流進(jìn)行長流數(shù)據(jù)傳輸，可以提高長流的吞吐率，但傳輸短流時數(shù)據(jù)流完成時間長。為了減少短流的完成時間，同時保證長流的吞吐率，國內(nèi)外學(xué)者研究與設(shè)計了相關(guān)的MPTCP數(shù)據(jù)流調(diào)度算法，如SARWAR等[8?12]對MPTCP數(shù)據(jù)流數(shù)據(jù)調(diào)度進(jìn)行了改進(jìn)，但都是針對單條MPTCP數(shù)據(jù)流內(nèi)部數(shù)據(jù)的調(diào)度算法。KHEIRKHAH等[7]提出了一種算法MMPTCP，對于所有的數(shù)據(jù)流，初始時使用Packet Scatter協(xié)議進(jìn)行數(shù)據(jù)傳輸，當(dāng)傳輸數(shù)據(jù)量達(dá)到100 KB時，若數(shù)據(jù)流依舊有數(shù)據(jù)發(fā)送，則將該數(shù)據(jù)流當(dāng)作長流，并進(jìn)行傳輸協(xié)議切換，使用MPTCP協(xié)議進(jìn)行數(shù)據(jù)傳輸。MMPTCP與MPTCP相比減少了短流的數(shù)據(jù)流完成時間，但傳輸長流時需要進(jìn)行協(xié)議轉(zhuǎn)換。WANG等[13]對路徑進(jìn)行劃分，短流路徑只傳輸短流，長流路徑只傳輸長流，路徑可根據(jù)長、短流的數(shù)目變化動態(tài)調(diào)節(jié)，但對于長流沒有考慮負(fù)載均衡，多條長流可能調(diào)度到同一路徑導(dǎo)致長流吞吐率低。針對這些問題，本文作者提出一種基于傳輸?shù)臄?shù)據(jù)流特性進(jìn)行數(shù)據(jù)流調(diào)度的算法MPTCP-FSFS(multi-path TCP flow scheduling based on flow size)，發(fā)送端根據(jù)每條數(shù)據(jù)流需發(fā)送的數(shù)據(jù)量將數(shù)據(jù)流進(jìn)行分類，根據(jù)數(shù)據(jù)流所屬類別選擇路徑對數(shù)據(jù)流進(jìn)行調(diào)度，并通過NS3[14?15]網(wǎng)絡(luò)模擬平臺進(jìn)行仿真。

1 問題分析

網(wǎng)絡(luò)中存在大量對延時敏感的實時交互式應(yīng)用，如網(wǎng)頁瀏覽、各種社交平臺和在線購物等，這些應(yīng)用經(jīng)常產(chǎn)生大量的短流。短流的特點(diǎn)是傳輸?shù)臄?shù)據(jù)量小，對數(shù)據(jù)流完成時間敏感。然而，網(wǎng)絡(luò)中傳輸?shù)拇蟛糠至髁慷际怯砷L流產(chǎn)生的，長流對吞吐率要求高。同時，網(wǎng)絡(luò)設(shè)備配置多塊網(wǎng)卡已經(jīng)越來越普遍化，多宿主主機(jī)之間可以建立多條可達(dá)路徑進(jìn)行數(shù)據(jù)傳輸，硬件上支持MPTCP協(xié)議的部署。

1.1 TCP協(xié)議

在長流與短流共存的網(wǎng)絡(luò)中，當(dāng)所有的數(shù)據(jù)流均使用TCP協(xié)議時，每條數(shù)據(jù)流選擇1條可達(dá)路徑進(jìn)行TCP連接傳輸數(shù)據(jù)。對于長流，每條長流只占據(jù)1條鏈路建立TCP連接并且傳輸所有數(shù)據(jù)，當(dāng)某條長流傳輸路徑出現(xiàn)擁塞時，即使其余路徑空閑，該長流也無法使用空閑路徑的發(fā)送能力，導(dǎo)致長流的吞吐率下降，同時網(wǎng)絡(luò)的利用率低。對于短流，由于長流占據(jù)大量的帶寬使得使用該路徑傳輸?shù)亩塘髋抨犙訒r增大，此外，當(dāng)多條數(shù)據(jù)流同時調(diào)度到同一條可達(dá)路徑進(jìn)行數(shù)據(jù)傳輸時，交換機(jī)或者路由器緩存會溢出，出現(xiàn)丟包，使得TCP流出現(xiàn)重傳或者超時現(xiàn)象[16?17]，導(dǎo)致短流的數(shù)據(jù)流完成時間增大。

1.2 MPTCP協(xié)議

針對TCP協(xié)議對多網(wǎng)卡設(shè)備的利用率不足的問題，IETF提出了MPTCP (multi-path TCP)。MPTCP協(xié)議是對TCP協(xié)議的擴(kuò)展，可以通過多個網(wǎng)絡(luò)接口為1條數(shù)據(jù)流建立多條子流連接，每條子流有自己獨(dú)立的擁塞控制窗口，從而提高網(wǎng)絡(luò)吞吐率。RAICIU等[18]通過研究發(fā)現(xiàn)MPTCP協(xié)議對長流是有利的，但傳輸短流時短流的完成時間長。圖1所示為發(fā)送端通過5條路徑并發(fā)30條MPTCP數(shù)據(jù)流傳輸?shù)浇邮斩藭r的實驗結(jié)果，每條路徑初始往返時延為20 ms，帶寬為 100 MB/s，丟包率為0.2%，每條路徑存在1條TCP背景長流。其中，圖1(a)所示為實驗測試發(fā)送30條80 KB的TCP數(shù)據(jù)流時，數(shù)據(jù)流使用不同路徑數(shù)目時短流的平均完成時間。由圖1(a)可見：短流的平均數(shù)據(jù)流完成時間隨著路徑數(shù)目增大而增大，即使用MPTCP協(xié)議傳輸短流時效果比使用TCP協(xié)議傳輸短流的效果差。圖1(b)所示為并發(fā)30條5 MB的數(shù)據(jù)流時的吞吐率期望值，可見長流的吞吐率隨著路徑數(shù)目增大而增大。

(a) 短流平均完成時間；(b) 長流吞吐率期望值

MPTCP可以提升長流的吞吐量，但傳輸短流效果差，其原因在于：對于長流，數(shù)據(jù)流使用MPTCP協(xié)議可以為1條數(shù)據(jù)流建立多條子流進(jìn)行數(shù)據(jù)傳輸，提高了吞吐率；對于短流，由于傳輸?shù)臄?shù)據(jù)量少，使用MPTCP協(xié)議傳輸短流時，在該數(shù)據(jù)流生命周期內(nèi)，每條子流的擁塞控制窗口都保持在一個很小的狀態(tài)，當(dāng)子流發(fā)生丟包時，很容易出現(xiàn)超時現(xiàn)象[7](因為不能收到3個重復(fù)ACK數(shù)據(jù)包，導(dǎo)致不能進(jìn)入快速重傳階段)，使得短流的數(shù)據(jù)流完成時間大大增多。

綜上所述，在多宿主主機(jī)之間進(jìn)行數(shù)據(jù)流傳輸時，使用TCP協(xié)議進(jìn)行數(shù)據(jù)傳輸或者使用MPTCP協(xié)議建立多條子流進(jìn)行數(shù)據(jù)傳輸都存在不足之處。TCP協(xié)議對于短流傳輸是有利的，但傳輸長流時吞吐率低并且鏈路利用率低。使用MPTCP協(xié)議傳輸長流時優(yōu)勢明顯，但傳輸短流平均完成時間長。因此，本文結(jié)合TCP協(xié)議對于傳輸短流的優(yōu)勢以及MPTCP協(xié)議對于傳輸長流的優(yōu)勢，設(shè)計基于數(shù)據(jù)流特性的MPTCP數(shù)據(jù)流調(diào)度算法MPTCP-FSFS。

2 算法設(shè)計

MPTCP-FSFS算法是基于MPTCP協(xié)議的，所有的數(shù)據(jù)流都使用MPTCP協(xié)議作為傳輸層協(xié)議。文中，使用的符號及含義見表1。

表1 符號含義

2.1 MPTCP-FSFS

MPTCP-FSFS的核心思想是：根據(jù)MPTCP數(shù)據(jù)流需發(fā)送的數(shù)據(jù)量決定該數(shù)據(jù)流使用的路徑以及建立的子流數(shù)目，短流使用往返時延最小的若干條路徑建立子流進(jìn)行數(shù)據(jù)傳輸，長流使用所有路徑建立子流進(jìn)行數(shù)據(jù)傳輸。

首先，根據(jù)數(shù)據(jù)流需要發(fā)送的數(shù)據(jù)量將數(shù)據(jù)流分為4類，分類方法如表2所示。

表2 數(shù)據(jù)流分類

MPTCP-FSFS調(diào)度算法的思想是：使用TCP協(xié)議傳輸短流時的數(shù)據(jù)流完成時間比使用MPTCP協(xié)議傳輸短流時數(shù)據(jù)流完成時間少，但MPTCP協(xié)議在傳輸長流時長流的吞吐率比使用TCP協(xié)議時要高，根據(jù)數(shù)據(jù)流傳輸數(shù)據(jù)量不同，決定數(shù)據(jù)流調(diào)度的路徑，這樣就可以充分利用TCP對于傳輸短流的優(yōu)勢和MPTCP對于傳輸長流的優(yōu)勢。

首先，對于每條數(shù)據(jù)流，根據(jù)數(shù)據(jù)流傳輸數(shù)據(jù)量進(jìn)行分類。如表3所示，每條數(shù)據(jù)流根據(jù)傳輸數(shù)據(jù)量所屬的區(qū)間分在不同的類別，在MPTCP-FSFS算法中將數(shù)據(jù)流分為4類。

表3 數(shù)據(jù)流分類算法

表4 MPTCP-FSFS調(diào)度算法

然后，根據(jù)數(shù)據(jù)流所屬的類別進(jìn)行路徑選擇，MPTCP-FSFS調(diào)度算法將屬于0，1和2的數(shù)據(jù)流都當(dāng)作短流，將屬于3的數(shù)據(jù)流當(dāng)作長流。對于短流，總是選取當(dāng)前所有路徑中往返時延最小的1條或多條路徑進(jìn)行數(shù)據(jù)傳輸，這樣從理論上可以實現(xiàn)短流平均完成時間最小。對于長流，使用所有可用路徑進(jìn)行數(shù)據(jù)流傳輸，每條數(shù)據(jù)流建立多條子流進(jìn)行數(shù)據(jù)傳輸，提高長流的吞吐率。

2.2 數(shù)據(jù)流分類

數(shù)據(jù)流分類方法見表2。在廣域網(wǎng)中，傳輸?shù)臄?shù)據(jù)流量近似呈帕累托分布，即傳輸數(shù)據(jù)量小的數(shù)據(jù)流占據(jù)總數(shù)據(jù)流的絕大多數(shù)，但傳輸?shù)臄?shù)據(jù)量大部分由長流提供。從圖1(a)可知：當(dāng)傳輸數(shù)據(jù)量小于100 KB時，使用1條路徑傳輸數(shù)據(jù)流相比于使用多條路徑建立多條子流傳輸?shù)臄?shù)據(jù)流完成時間更小。這是由于數(shù)據(jù)流傳輸?shù)臄?shù)據(jù)量小，使用多條路徑建立多條子流進(jìn)行數(shù)據(jù)傳輸時每條子流的擁塞窗口在生命周期內(nèi)保持在很小的狀態(tài)，即使出現(xiàn)1個數(shù)據(jù)包丟失也可能會導(dǎo)致超時現(xiàn)象發(fā)生，從而導(dǎo)致數(shù)據(jù)流完成時間長。因此，本文將傳輸數(shù)據(jù)量在(0,100) KB區(qū)間的數(shù)據(jù)流劃分到類別0中。隨著數(shù)據(jù)流傳輸數(shù)據(jù)量增大，使用MPTCP協(xié)議建立多條子流進(jìn)行數(shù)據(jù)流傳輸?shù)膬?yōu)勢顯現(xiàn)。本文將在(100,300) KB區(qū)間的數(shù)據(jù)流劃分到類別1中，將在(300,800) KB區(qū)間的數(shù)據(jù)流劃分到類別2中。將數(shù)據(jù)流需傳輸?shù)臄?shù)據(jù)量大于800 KB的數(shù)據(jù)流當(dāng)作長流，劃分到類別3中。

2.3 數(shù)據(jù)流調(diào)度

對于每條數(shù)據(jù)流，根據(jù)傳輸數(shù)據(jù)量將數(shù)據(jù)流分為4類。對屬于每個類別的數(shù)據(jù)流，根據(jù)傳輸?shù)臄?shù)據(jù)量不同，選擇合適的路徑進(jìn)行數(shù)據(jù)流調(diào)度。

根據(jù)圖1(a)，由于使用1條子流進(jìn)行數(shù)據(jù)流傳輸時，數(shù)據(jù)流平均完成時間比使用多條路徑建立多條子流進(jìn)行數(shù)據(jù)流傳輸時完成時間要小，所以，對于1條數(shù)據(jù)流，當(dāng)該數(shù)據(jù)流屬于0時，使用當(dāng)前所有路徑中往返時延最小的路徑進(jìn)行數(shù)據(jù)傳輸，這樣，可以實現(xiàn)使用最短的時間完成時間敏感的短流傳輸。對于屬于1的數(shù)據(jù)流，本文使用往返時延最小的2條路徑進(jìn)行數(shù)據(jù)流傳輸。對于屬于2的數(shù)據(jù)流，使用往返時延最小的3條路徑進(jìn)行數(shù)據(jù)流傳輸。對于屬于3的數(shù)據(jù)流，本文將該類型數(shù)據(jù)流當(dāng)作是長流，從圖1(b)可知：MPTCP對于長流而言是有利的，可以大大提高長流的吞吐率。所以，對于長流，使用所有的路徑建立子流進(jìn)行數(shù)據(jù)傳輸。

3 性能評估

實驗基于NS3網(wǎng)絡(luò)模擬平臺實現(xiàn)，性能評價指標(biāo)包括短流的數(shù)據(jù)流完成時間(flow completion time, FCT)、長流平均吞吐率(mean throughput)和數(shù)據(jù)流平均吞吐率 (mean throughput)。

3.1 實驗設(shè)計

實驗設(shè)置發(fā)送端與接收端之間建立條路徑，在[5,20]的范圍內(nèi)變化；路徑帶寬設(shè)置為100 MB/s，往返時延在[20,200] ms范圍內(nèi)變化[19]，路由器設(shè)置丟包策略為Droptail[20]。MPTCP協(xié)議的擁塞控制算法設(shè)置為RTT_compensator[21]。設(shè)置MPTCP數(shù)據(jù)流緩沖為

式中：B為第條路徑的帶寬；max為所有路徑中最大的路徑往返時延。每條路徑分別引入5條FTP長 流[22]，其余協(xié)議參數(shù)均按照NS3的默認(rèn)值進(jìn)行設(shè)置。所有實驗仿真運(yùn)行時間至少為100 s，忽略仿真時間前5 s的統(tǒng)計數(shù)據(jù)。

為了模擬真實的廣域網(wǎng)環(huán)境，發(fā)送的數(shù)據(jù)流分布根據(jù)文獻(xiàn)[23]中方法生成。設(shè)置網(wǎng)絡(luò)中總的數(shù)據(jù)流到達(dá)速率服從泊松分布，平均到達(dá)速率從50條/s變化到2 000條/s，該設(shè)置符合真實的網(wǎng)絡(luò)流量模型。

本實驗將需傳輸數(shù)據(jù)量小于等于800 KB的數(shù)據(jù)流當(dāng)作短流，以數(shù)據(jù)流完成時間(FCT)作為性能測試指標(biāo)；將需傳輸數(shù)據(jù)量大于800 KB的數(shù)據(jù)流當(dāng)作長流，以數(shù)據(jù)流吞吐率(throughput)作為性能測試指標(biāo)。

在實驗結(jié)果圖中，MPTCP-FSFS表示數(shù)據(jù)流使用MPTCP-FSFS調(diào)度算法時的實驗結(jié)果，MPTCP表示使用MPTCP協(xié)議并利用條路徑建立多條子流時的實驗結(jié)果，TCP表示所有數(shù)據(jù)流使用TCP協(xié)議時的實驗結(jié)果。

3.2 數(shù)據(jù)流到達(dá)速率的變化

本組實驗在發(fā)送端與接收端之間建立10條可達(dá)路徑時，網(wǎng)絡(luò)中總的數(shù)據(jù)流平均到達(dá)速率服從泊松分布，在其余條件不變時，數(shù)據(jù)流的平均到達(dá)速率從 50條/s變化到2 000條/s(若每條路徑分配相同數(shù)目的數(shù)據(jù)流，則每條路徑的數(shù)據(jù)流平均到達(dá)速率從5條/s變化到200條/s)，測試不同數(shù)據(jù)流到達(dá)速率場景下調(diào)度算法的性能。

3.2.1 短流平均完成時間

圖2所示為短流的平均數(shù)據(jù)流完成時間實驗結(jié)果。由圖2可見：對于屬于0~2的數(shù)據(jù)流，使用MPTCP-FSFS調(diào)度算法進(jìn)行數(shù)據(jù)流調(diào)度時，總是選取當(dāng)前時刻路徑往返時延最小的1~3條路徑進(jìn)行數(shù)據(jù)流調(diào)度，數(shù)據(jù)流平均完成時間最小。實驗中，當(dāng)網(wǎng)絡(luò)中總數(shù)據(jù)流平均到達(dá)速率介于50條/s到1 000條/s時，平均每條路徑上傳輸?shù)臄?shù)據(jù)流數(shù)目少，即路徑負(fù)載低。由圖2(a)可見：當(dāng)使用MPTCP時，將建立多條子流進(jìn)行數(shù)據(jù)流傳輸，由于路徑負(fù)載低，數(shù)據(jù)流發(fā)生丟包的概率低，數(shù)據(jù)流平均完成時間相比于TCP更低。由于存在路徑差異性，使用MPTCP時，數(shù)據(jù)流可能選擇路徑往返時延大的路徑建立主子流進(jìn)行傳輸，導(dǎo)致數(shù)據(jù)流平均完成時間比MPTCP-FSFS的高。隨著數(shù)據(jù)流到達(dá)速率增大，每條路徑負(fù)載加大，路徑擁塞導(dǎo)致丟包的概率增大。當(dāng)數(shù)據(jù)流使用MPTCP時，由于傳輸?shù)臄?shù)據(jù)量少，在其生命周期內(nèi)子流的擁塞窗口都保持在很小的狀態(tài)，丟包導(dǎo)致超時現(xiàn)象產(chǎn)生的概率高；同時，由于路徑存在差異性，導(dǎo)致數(shù)據(jù)流的平均完成時間最長。當(dāng)數(shù)據(jù)流使用TCP協(xié)議時，由于路徑差異性導(dǎo)致數(shù)據(jù)流平均完成時間與使用MPTCP-FSFS調(diào)度算法時的平均完成時間相比更大。實驗結(jié)果顯示：當(dāng)屬于0的數(shù)據(jù)流使用MPTCP-FSFS調(diào)度算法進(jìn)行數(shù)據(jù)流調(diào)度時，與MPTCP相比，數(shù)據(jù)流平均完成時間減少31.88%以上，與TCP相比減少25.12%以上。

數(shù)據(jù)流類別：(a) G0；(b) G1；(c) G2

由圖2(b)可見：對于屬于1的數(shù)據(jù)流，使用MPTCP建立多條子流進(jìn)行數(shù)據(jù)流傳輸，且當(dāng)網(wǎng)絡(luò)負(fù)載較小時，與TCP相比，數(shù)據(jù)流使用多條子流進(jìn)行傳輸優(yōu)勢顯現(xiàn)，數(shù)據(jù)流平均完成時間更低。隨著數(shù)據(jù)流到達(dá)速率增大，網(wǎng)絡(luò)負(fù)載加大，由于丟包導(dǎo)致超時，從而使得數(shù)據(jù)流平均完成時間增大。結(jié)果顯示，當(dāng)屬于1的數(shù)據(jù)流使用MPTCP-FSFS調(diào)度算法進(jìn)行數(shù)據(jù)流調(diào)度時，與MPTCP相比，數(shù)據(jù)流平均完成時間減少23.69%以上，與TCP相比減少21.15%以上。

由圖2(c)可見：對于屬于2的數(shù)據(jù)流，使用MPTCP-FSFS與MPTCP時，由于數(shù)據(jù)流建立多條子流進(jìn)行傳輸，與TCP相比，數(shù)據(jù)流平均完成時間更少。當(dāng)數(shù)據(jù)流使用MPTCP時，由于鏈路差異性導(dǎo)致數(shù)據(jù)流平均完成時間相比于數(shù)據(jù)流使用MPTCP-FSFS調(diào)度算法時更長。實驗結(jié)果表明：屬于2的數(shù)據(jù)流使用MPTCP-FSFS調(diào)度算法進(jìn)行數(shù)據(jù)流調(diào)度時，與MPTCP相比，數(shù)據(jù)流平均完成時間減少10.79%以上，與TCP相比減少16.90%以上。

數(shù)據(jù)流使用MPTCP-FSFS調(diào)度算法時，對于每條數(shù)據(jù)流，總是使用當(dāng)前時刻路徑往返時延最小的若干條路徑進(jìn)行數(shù)據(jù)流傳輸，與MPTCP和TCP相比，短流平均完成時間均明顯降低。

3.2.2 長流平均吞吐率

圖3所示為長流平均吞吐率實驗結(jié)果。當(dāng)網(wǎng)絡(luò)負(fù)載低、數(shù)據(jù)流使用MPTCP-FSFS調(diào)度算法時，與TCP相比，長流平均吞吐率明顯更高，增長幅度在76.15%以上。與MPTCP相比，由于MPTCP-FSFS調(diào)度算法中短流占用路徑往返時延小的若干條路徑帶寬，導(dǎo)致長流的平均吞吐率有所降低，但由于短流傳輸?shù)臄?shù)據(jù)量小，降低的幅度最大不超過3.49%。當(dāng)網(wǎng)絡(luò)負(fù)載較高時，由于網(wǎng)絡(luò)擁塞，數(shù)據(jù)流使用MPTCP-FSFS，MPTCP和TCP時長流吞吐率接近。

圖3 長流平均吞吐率

3.2.3 數(shù)據(jù)流平均吞吐率

圖4所示為數(shù)據(jù)流平均吞吐率。根據(jù)前面的分析可知：使用MPTCP-FSFS調(diào)度算法進(jìn)行數(shù)據(jù)流調(diào)度時，與MPTCP相比，長流的平均吞吐率略下降，但短流的平均吞吐率增幅更大，并且在實驗中99%的數(shù)據(jù)流為短流；與TCP相比，短流的數(shù)據(jù)流平均完成時間更少，長流的吞吐率更高，因此，數(shù)據(jù)流平均吞吐率更高。實驗結(jié)果表明：數(shù)據(jù)流使用MPTCP-FSFS調(diào)度算法進(jìn)行調(diào)度時，與MPTCP相比，數(shù)據(jù)流平均吞吐率增大39.57%以上，與TCP相比增大30.82%以上。

圖4 數(shù)據(jù)流平均吞吐率

3.3 路徑數(shù)目變化

本組實驗設(shè)置網(wǎng)絡(luò)中總的數(shù)據(jù)流平均到達(dá)速率服從泊松分布，平均數(shù)據(jù)流到達(dá)速率不變，設(shè)置為1 000條/s，路徑數(shù)目由5變化到20。由于網(wǎng)絡(luò)中總的數(shù)據(jù)流平均到達(dá)速率不變，當(dāng)傳輸路徑數(shù)目變化時，根據(jù)每條路徑上平均傳輸?shù)臄?shù)據(jù)流數(shù)目變化即路徑的負(fù)載變化，測試不同路徑數(shù)目下調(diào)度算法的性能。

3.3.1 短流平均完成時間

圖5所示為短流的平均數(shù)據(jù)流完成時間。從圖5(a)可見：當(dāng)數(shù)據(jù)流屬于0時，隨著路徑數(shù)目增大，每條路徑上傳輸?shù)臄?shù)據(jù)流數(shù)目減少，即路徑負(fù)載降低，路徑擁塞概率降低，排隊時延減少，導(dǎo)致數(shù)據(jù)流平均完成時間減少。當(dāng)數(shù)據(jù)流使用MPTCP-FSFS調(diào)度算法時，數(shù)據(jù)流平均完成時間最??；當(dāng)路徑數(shù)目為5時，使用MPTCP時數(shù)據(jù)流平均完成時間最多。這是由于路徑擁塞導(dǎo)致丟包發(fā)生概率高，數(shù)據(jù)流使用MPTCP協(xié)議建立多條子流進(jìn)行數(shù)據(jù)流傳輸時，數(shù)據(jù)流傳輸?shù)臄?shù)據(jù)量少，容易導(dǎo)致數(shù)據(jù)流即使只丟失1個數(shù)據(jù)包也會出現(xiàn)超時現(xiàn)象，從而導(dǎo)致數(shù)據(jù)流平均完成時間最多。隨著路徑數(shù)目增大，路徑負(fù)載降低，數(shù)據(jù)流使用MPTCP-FSFS和MPTCP建立多條子流進(jìn)行數(shù)據(jù)傳輸時，與數(shù)據(jù)流使用TCP協(xié)議相比短流平均完成時間更少。實驗結(jié)果表明：屬于0的數(shù)據(jù)流使用MPTCP-FSFS調(diào)度算法進(jìn)行數(shù)據(jù)流調(diào)度時，相比于MPTCP，數(shù)據(jù)流平均完成時間減少31.67%以上，相比于TCP減少了23.32%以上。

從圖5(b)可見：當(dāng)數(shù)據(jù)流屬于1，使用MPTCP- FSFS調(diào)度算法進(jìn)行數(shù)據(jù)流調(diào)度時，數(shù)據(jù)流使用當(dāng)前時刻所有路徑中路徑往返時延最小的2條路徑建立2條子流進(jìn)行數(shù)據(jù)流傳輸，數(shù)據(jù)流的平均完成時間最少。實驗結(jié)果表明：與MPTCP相比，數(shù)據(jù)流的平均完成時間減少23.41%以上，與TCP相比減少20.81%以上。

從圖5(c)可見：當(dāng)數(shù)據(jù)流屬于G，使用MPTCP- FSFS和MPTCP時，與TCP相比，由于數(shù)據(jù)流使用多條子流進(jìn)行傳輸，數(shù)據(jù)流平均完成時間更少。數(shù)據(jù)流使用MPTCP-FSFS調(diào)度算法時，總是使用當(dāng)前時刻路徑往返時延最小的3條路徑建立3條子流進(jìn)行傳輸，數(shù)據(jù)流平均完成時間最少。實驗結(jié)果表明：與MPTCP相比，數(shù)據(jù)流平均完成時間減少11.05%以上，與TCP相比減少18.10%以上。

(a) G0；(b) G1；(c) G2

3.3.2 長流平均吞吐率

圖6所示為長流平均吞吐率。從圖6可見：隨著路徑數(shù)目增大，每條路徑上傳輸?shù)拈L流數(shù)目減少，數(shù)據(jù)流使用MPTCP協(xié)議進(jìn)行傳輸時，長流的吞吐率相比于數(shù)據(jù)流使用TCP協(xié)議時優(yōu)勢明顯，長流吞吐率均比數(shù)據(jù)流使用TCP協(xié)議作為傳輸層協(xié)議時的高；當(dāng)數(shù)據(jù)流使用MPTCP-FSFS調(diào)度算法時，由于短流占據(jù)路徑往返時延小的路徑帶寬，長流的吞吐率相比于MPTCP略有下降。實驗結(jié)果表明：吞吐率下降不超過2.16%，但與TCP相比提高7.81%以上。

圖6 不同路徑數(shù)目時長流平均吞吐率

3.3.3 數(shù)據(jù)流平均吞吐率

圖7所示為數(shù)據(jù)流平均吞吐率。從圖7可見：隨著路徑數(shù)目增大，每條路徑上傳輸?shù)钠骄鶖?shù)據(jù)流數(shù)量減少，即負(fù)載減小，數(shù)據(jù)流由于路徑擁塞導(dǎo)致丟包的概率減少，排隊時延減少，數(shù)據(jù)流平均吞吐率增大；當(dāng)數(shù)據(jù)流使用MPTCP-FSFS調(diào)度算法時，短流的平均完成時間最少，長流吞吐率與MPTCP的長流吞吐率相比相差不超過2.16%，并且短流數(shù)目占總的數(shù)據(jù)流絕大多數(shù)，數(shù)據(jù)流平均吞吐率最高；當(dāng)使用MPTCP建立多條子流進(jìn)行數(shù)據(jù)流傳輸且路徑數(shù)為5時，由于網(wǎng)絡(luò)擁塞導(dǎo)致短流的平均數(shù)據(jù)流完成時間長，并且短流從數(shù)量上而言最多，導(dǎo)致數(shù)據(jù)流平均吞吐率最低；隨著路徑數(shù)目增大，路徑負(fù)載降低，數(shù)據(jù)流使用MPTCP-FSFS和MPTCP相比于TCP短流平均完成時間更少，長流吞吐率更高，數(shù)據(jù)流平均吞吐率比TCP的高。實驗結(jié)果表明：當(dāng)數(shù)據(jù)流使用MPTCP-FSFS調(diào)度算法時，與MPTCP相比，數(shù)據(jù)流的平均吞吐率增大42.47%以上，與TCP相比增大34.08%以上。

圖7 不同路徑數(shù)目時數(shù)據(jù)流平均吞吐率

4 結(jié)論

1) 針對MPTCP協(xié)議傳輸長流時吞吐率高但傳輸短流時數(shù)據(jù)流完成時間長，而TCP協(xié)議傳輸短流時數(shù)據(jù)流完成時間少但傳輸長流吞吐率低的特點(diǎn)，提出MPTCP-FSFS調(diào)度算法。

2)結(jié)合MPTCP協(xié)議對于傳輸長流的優(yōu)勢以及TCP協(xié)議對于傳輸短流的優(yōu)勢，根據(jù)數(shù)據(jù)流傳輸?shù)臄?shù)據(jù)量進(jìn)行數(shù)據(jù)流分類，在進(jìn)行短流調(diào)度時根據(jù)短流所屬的類別選擇當(dāng)前往返時延最小的若干條路徑進(jìn)行數(shù)據(jù)流調(diào)度，在保證長流吞吐率的基礎(chǔ)上，大大減少了短流的數(shù)據(jù)流完成時間，并且數(shù)據(jù)流平均吞吐率提高。

[1] GREENBERG A, HAMILTON J, JAIN N, et al. VL2: a scalable and flexible data center network[C]// Proceedings of ACM SIGCOMM. Barcelona, Spain: ACM, 2011: 51?62.

[2] ENGLE C, LUPHER A, XIN R, et al. Shark: fast data analysis using coarse-grained distributed memory[C]// Proceedings of the 2012 ACM SIGMOD International Conference on Management of Data. Scottsdale, Arizona, 2012: 689?692.

[3] MELNIK S, GUBAREV A, LONG J, et al. Dremel: interactive analysis of web-scale datasets[J]. Communications of the ACM, 2011, 54(6): 114?123.

[4] RFC 6182, Architectural guidelines for multipath TCP development[S].

[5] RFC 6897, Multipath TCP (MPTCP) application interface considerations[S].

[6] RFC 6824, TCP extension for multipath operation with multiple address[S].

[7] KHEIRKHAH M, WAKEMAN I, PARISIS G. MMPTCP: a multipath transport protocol for data centers[C]// IEEE INFOCOM. San Francisco, California, 2016: 1?9.

[8] SARWAR G, BORELI R, LOCHIN E, et al. Mitigating receiver’s buffer blocking by delay aware packet scheduling in multipath data transfer[C]// IEEE WAINA. Barcelona, Spain, 2013: 1119?1124.

[9] KUHN N, LOCHIN E, MIFDAOUI A, et al. DAPS: intelligent delay-aware packet scheduling for multipath transport[C]// IEEE International Conference on Communications. Sydney, Australia, 2014: 1222?1227.

[10] YANG Fan, WANG Qi, AMER P. Out-of-order transmission for in-order arrival scheduling for multipath TCP[C]// IEEE WAINA. Victoria, Canada, 2014: 749?752.

[11] FERLIN S, ALAY O, MEHANI O, et al. BLEST: blocking estimation-based MPTCP scheduler for heterogeneous networks[C]// IFIP Networking Conference. Trondheim, Norway, 2016: 431?439.

[12] CHAN M, TSENG C, YEN L. Jitter-aware packet scheduler for concurrent multipath transmission in heterogeneous wireless networks[C]// IEEE WCNC. San Francisco, California, 2016: 1?7.

[13] WANG Wei, SUN Yi, SALAMATIAN K, et al. Adaptive path isolation for elephant and mice flows by exploiting path diversity in data centers[J]. IEEE Transactions on Network and Service Management, 2016, 13(1): 5?18.

[14] CHIHANI B, DENIS C. A multipath TCP model for ns-3 simulator[C]// Workshop on ns-3 Held in Conjunction with SIMUTools 2011. Barceloan, Spain, 2011: 1?6.

[15] KHEIRKHAH M. Multipath-TCP in ns-3[EB/OL]. [2015?04?03]. http://dx.doi.org/10.5281/zenodo.32691/.

[16] FALL K, STEVENS W. TCP/IP illustrated volume 1 : the protocols[M]. 2nd ed. Boston: Addison-Wesley Professional, 2012: 727?803.

[17] ALIZADEH M, GREENBERG A, MALTZ D, et al. Data center TCP (DCTCP)[C]// Proceeding of ACM SIGCOMM. New Delhi, India: ACM, 2010: 63?74.

[18] RAICIU C, BARRE S, PLUNTKE C, et al. Improving datacenter performance and robustness with multipath TCP[C]// Proceeding of ACM SIGCOMM. Barcelona, Spain: ACM, 2011: 266?277.

[19] JIANG Hao, DOVROLIS C. Passive estimation of TCP round trip times[J]. ACM Computer Communications Review, 2002, 32(3): 7?18.

[20] RASTOGI S, ZAHEER H. Comparison analysis of different queuing mechanisms Droptail, RED and NLRED[J]. Social Network Analysis and Mining, 2016, 6(1): 70?76.

[21] WISCHIK D, RAICIU C, GREENHALGH A, et al. Design implementation and evaluation of congestion control for multipath TCP[C]// Proceedings of the USENIX Symposium on Networked Systems Design and Implementation(NSDI). Berkeley, California, 2011: 99?112.

[22] WANG Jianxin, CHEN Jie, ZHANG Shigeng, et al. An explicit congestion control protocol based on bandwidth estimation[C]// Global Communication Conference. Huston, American, 2011: 1?5.

[23] PLONKA D. Internet traffic flow size analysis[EB/OL]. [2002?10?05]. http://net.doit.wisc.edu/data/flow/size/.

Research on MPTCP flows scheduling algorithm based on flow characteristics

YE Ning1, DONG Pingping2, DUAN Guihua1, WANG Jianxin1

(1. School of Information Science and Engineering, Central South University, Changsha 410083, China;2. Department of Computer Education, Hunan Normal University, Changsha 410081, China)

When MPTCP protocol is used as the transmission layer protocol for short flows in the WAN, the congestion window of each subflow keeps small over its lifetime due to the small amount of data to be transmitted, and in this condition, even the loss of one packet may result in timeout, and thus makes the completion time of short flows become long. In order to solve this problem, the MPTCP-FSFS (multi-path TCP flow scheduling based on flow size) algorithm was presented, which scheduled MPTCP data flows based on the characteristics of MPTCP data flows. Firstly, the MPTCP-FSFS algorithm classified the MPTCP flows based on the amount of data to be sent. Then, the sender scheduled MPTCP flows according to the round-trip delay of each path. For short flows, several paths with the smallest RTT were selected for data transmission. For long flows, all the paths were used for transmission. The results show that compared with MPTCP, MPTCP-FSFS can reduce the completion time of short flows and improve the mean throughput of flows, which ensures long flows throughput simultaneously.

MPTCP; flow characteristics; path round-trip delay; flow scheduling

10.11817/j.issn.1672-7207.2018.07.016

TP393.2

A

1672?7207(2018)07?1691?09

2017?10?09；

2017?11?22

國家自然科學(xué)基金資助項目(61502539，61572530，61602171，61402542) (Projects(61502539, 61572530, 61602171, 61402542) supported by the National Natural Science Foundation of China)

段桂華，博士，副教授，從事計算機(jī)網(wǎng)絡(luò)、網(wǎng)絡(luò)安全研究；E-mail: duangh@csu.edu.cn

(編輯 陳燦華)