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

葉寧，董蘋(píng)蘋(píng)，段桂華，王建新

?

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

葉寧1，董蘋(píng)蘋(píng)2，段桂華1，王建新1

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

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

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

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

1 問(wèn)題分析

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

1.1 TCP協(xié)議

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

1.2 MPTCP協(xié)議

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

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

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

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

2 算法設(shè)計(jì)

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

表1 符號(hào)含義

2.1 MPTCP-FSFS

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

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

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

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

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

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

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

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

2.2 數(shù)據(jù)流分類(lèi)

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

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

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

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

3 性能評(píng)估

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

3.1 實(shí)驗(yàn)設(shè)計(jì)

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

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

為了模擬真實(shí)的廣域網(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è)置符合真實(shí)的網(wǎng)絡(luò)流量模型。

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

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

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

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

3.2.1 短流平均完成時(shí)間

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

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

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

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

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

3.2.2 長(zhǎng)流平均吞吐率

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

圖3 長(zhǎng)流平均吞吐率

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

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

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

3.3 路徑數(shù)目變化

本組實(shí)驗(yàn)設(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ù)目變化時(shí)，根據(jù)每條路徑上平均傳輸?shù)臄?shù)據(jù)流數(shù)目變化即路徑的負(fù)載變化，測(cè)試不同路徑數(shù)目下調(diào)度算法的性能。

3.3.1 短流平均完成時(shí)間

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

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

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

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

3.3.2 長(zhǎng)流平均吞吐率

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

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

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

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

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

4 結(jié)論

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

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

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

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

(編輯 陳燦華)