基于權(quán)重的MPTCP數(shù)據(jù)調(diào)度算法設(shè)計(jì)

黃輝

摘要：并行多路傳輸技術(shù)通過聚合多條鏈路的帶寬資源可以提高傳輸吞吐量，越來越受到學(xué)術(shù)界和工業(yè)界的關(guān)注。多路徑TCP（MPTCP）是其中最具代表性的研究成果之一，因其是在TCP的基礎(chǔ)上拓展而來，保持了對TCP的兼容性，能夠比較容易地部署到現(xiàn)有網(wǎng)絡(luò)中。然而，MPTCP默認(rèn)的數(shù)據(jù)調(diào)度機(jī)制在異構(gòu)網(wǎng)絡(luò)環(huán)境下導(dǎo)致傳輸性能下降。針對此問題，本文提出一種基于權(quán)重的數(shù)據(jù)調(diào)度算法，充分考慮子流之間的差異性。仿真結(jié)果顯示所提算法優(yōu)于傳統(tǒng)的數(shù)據(jù)調(diào)度算法，能夠較好的適應(yīng)網(wǎng)絡(luò)環(huán)境變化。

關(guān)鍵詞：計(jì)算機(jī)網(wǎng)絡(luò)；并行多路傳輸；MPTCP；數(shù)據(jù)調(diào)度算法

中圖分類號：TP393.0

文獻(xiàn)標(biāo)識碼：A

DOI： 10.3969/j.1S S11.1003-6970.2016.02.019

引言

近年來，隨著工業(yè)技術(shù)和互聯(lián)網(wǎng)技術(shù)的不斷進(jìn)步，硬件設(shè)備的制造成本大大降低的同時(shí)，網(wǎng)絡(luò)設(shè)備普及范圍也越來越廣?，F(xiàn)在越來越多的終端裝備了多個(gè)網(wǎng)絡(luò)接口卡（NIC），通過將這些接口資源同時(shí)利用起來并行的傳輸數(shù)據(jù)，可以大大的提高傳輸吞吐量，因此，網(wǎng)絡(luò)傳輸越來越受到一些學(xué)者的關(guān)注。目前，比較有代表性的研究成果包括CMT_SCTP和MPTCP其中，CMT-SCTP是在SCTP基礎(chǔ)上拓展而來，而MPTCP則是在TCP基礎(chǔ)上拓展而來。截至目前為止，TCP依然是互聯(lián)網(wǎng)中占據(jù)主導(dǎo)地位的傳輸協(xié)議，由于MPTCP對現(xiàn)有網(wǎng)絡(luò)的兼容性更好，使其具備了天然的部署優(yōu)勢，而CMT-SCTP同現(xiàn)有網(wǎng)絡(luò)設(shè)施和協(xié)議的兼容性問題，阻礙了其在工業(yè)界的進(jìn)一步發(fā)展。

盡管并行多路傳輸理論上可以極大的提高傳輸吞吐量，但是在異構(gòu)網(wǎng)絡(luò)環(huán)境下，并行多路傳輸?shù)男阅軈s大不如預(yù)期，有時(shí)甚至比單路徑傳輸還低。這其中的主要問題來自并行多路傳輸協(xié)議本身采用的是輪詢（Round Robin）調(diào)度算法，該算法對具備差異性的路徑等同對待，加劇了接收端的隊(duì)首阻塞（Head-Of-LineBlocking），使得質(zhì)量較差的路徑影響了質(zhì)量較好的路徑的傳輸性能。為了解決這個(gè)問題，董貝貝等作者提出了基于傳輸時(shí)間和發(fā)送間隔的調(diào)度算法（RSFSA），利用馬爾科夫模型預(yù)測數(shù)據(jù)包達(dá)到時(shí)間。Paasch等作者設(shè)計(jì)了一個(gè)通用的模塊化的調(diào)度器框架用于研究調(diào)度決策的不同對傳輸性能的影響。CMT-QA通過評估路徑質(zhì)量，在預(yù)測數(shù)據(jù)到達(dá)接收端的時(shí)間基礎(chǔ)上調(diào)度，有效的提高了傳輸吞吐量。

考慮到MPTCP對現(xiàn)有網(wǎng)絡(luò)的兼容性更好，本文基于MPTCP，提出了一種基于權(quán)重的數(shù)據(jù)調(diào)度算法，提取子流質(zhì)量相關(guān)的特征作為數(shù)據(jù)調(diào)度的關(guān)鍵指標(biāo)。本文的第一部分，簡要的介紹一下MPTCP比較有代表性的數(shù)據(jù)調(diào)度算法和主要存在的問題，第二部分詳細(xì)的敘述基于權(quán)重的數(shù)據(jù)調(diào)度算法的設(shè)計(jì)，第三部分通過基于NS-2的仿真驗(yàn)證所設(shè)計(jì)的算法的有效性，并同現(xiàn)有方案比較，第四部分對本文的工作進(jìn)行總結(jié)。

1 MPTCP相關(guān)數(shù)據(jù)調(diào)度算法

互聯(lián)網(wǎng)工程任務(wù)組（IETF）于2011年和2013年在工程任務(wù)組MPTCP中提出了一系列的草案標(biāo)志著MPTCP標(biāo)準(zhǔn)化的開始。影響MPTCP性能的因素有很多，其中很重要的一個(gè)就是數(shù)據(jù)調(diào)度算法的設(shè)計(jì)。數(shù)據(jù)調(diào)度的主要任務(wù)是將數(shù)據(jù)合理的分發(fā)到子路徑上使得數(shù)據(jù)盡可能的按序到達(dá)接收方以減少接收端的隊(duì)首阻塞（Head-Of-Line Blocking）。隊(duì)首阻塞主要是由于數(shù)據(jù)亂序到達(dá)接收方造成的，序列號靠前的數(shù)據(jù)比序列號靠后的數(shù)據(jù)更晚到達(dá)接收端，接收端不得不緩存這些序列號靠后的數(shù)據(jù)，直到所有的序列號比它靠前的數(shù)據(jù)都接收到，才能往上層遞交該數(shù)據(jù)，這就導(dǎo)致了較大的遞交時(shí)延，嚴(yán)重影響了使用戶體驗(yàn)。

MPTCP默認(rèn)采用的是輪洵（Round Robin）數(shù)據(jù)調(diào)度機(jī)制，該機(jī)制順序的遍歷所有的路徑，把一條路徑的可用窗口發(fā)送滿后，就選擇下一條路徑發(fā)送，如果所有的路徑都遍歷了一遍，則從第一條開始重新開始發(fā)送數(shù)據(jù)。該機(jī)制可以在路徑差異不大的場景下比較好的工作，但是現(xiàn)實(shí)網(wǎng)絡(luò)中，異構(gòu)網(wǎng)絡(luò)環(huán)境大量廣泛存在，路徑之間的差異性往往很明顯，這就使得MPTCP的傳輸性能大大的降低，嚴(yán)重的影響了MPTCP并行多路徑傳輸?shù)膬?yōu)勢。

Paasch等作者在其發(fā)表在2014 ACM SIGCOMMworkshop上的文章中，提出了基于最小雙向傳輸時(shí)延（RTT）的數(shù)據(jù)調(diào)度機(jī)制，該機(jī)制在有數(shù)據(jù)需要發(fā)送時(shí)，總是選擇RTT最小的一條路徑，直到該路徑的發(fā)送窗口滿了不能再發(fā)送更多的數(shù)據(jù)為止，然后選擇RTT次小的路徑發(fā)送，不斷地重復(fù)該過程。雖然采用最小RTT作為選擇路徑的指標(biāo)，可以保證數(shù)據(jù)包盡可能快的到達(dá)接收端，但是該機(jī)制忽略了其他可能會影響傳輸?shù)囊恍┮蛩?，比如鏈路的質(zhì)量以及窗口的大小等。本文期望通過提取更多與傳輸相關(guān)的參數(shù)，提供一個(gè)更加全面、有效的調(diào)度策略，從而提高M(jìn)PTCP在不同場景下的傳輸性能。

2 基于權(quán)重的MPTCP數(shù)據(jù)調(diào)度算法設(shè)計(jì)

MPTCP是在TCP基礎(chǔ)上拓展而來的，因而MPTCP繼承了很多TCP的思想。比如，MPTCP的子流就可以看作是一個(gè)普通的TCP連接，只不過所有的子流（子流層）會接受來自MPTCP核心（數(shù)據(jù)層）的調(diào)度管理，在子流層和數(shù)據(jù)層之間通過構(gòu)建數(shù)據(jù)映射機(jī)制來管理和同步兩層之間的序列號。先來看一下子流層的情況，TCP連接的吞吐量理論上滿足如下公式：

其中，RTT是TCP連接的雙向傳輸時(shí)延，而D是丟包率。由此可以看出一個(gè)TCP連接的吞吐量不僅僅取決于RTT的值，同時(shí)還與丟包率有關(guān)。無線網(wǎng)絡(luò)環(huán)境下，這種效果更加的明顯，因?yàn)樵跓o線網(wǎng)絡(luò)環(huán)境下，鏈路的丟包率往往較大。本文將RTT和丟包率結(jié)合在一起，作為數(shù)據(jù)調(diào)度機(jī)制評估指標(biāo)。從公式（l）可以看出，吞吐量的大小與路徑的RTT成反比，與丟包率的開方成反比：

經(jīng)過上面的分析得出，MPTCP中的子流的吞吐量也應(yīng)該滿足公式（2）的成比例關(guān)系。由此，我們定義每一條子流的質(zhì)量：

其中，i對應(yīng)MPTCP子流的編號，我們假設(shè)這里處理的是無線網(wǎng)絡(luò)環(huán)境的場景，因此，丟包率不為0，并記P=√p。RTT*和pi分別表示RTT和P的歸一化值。根據(jù)RTT和P在具體網(wǎng)絡(luò)環(huán)境下對傳輸影響的重要程度，加權(quán)求和得到子流的質(zhì)量QSi。QSi的值越小，說明子流的質(zhì)量越好。加權(quán)因子a和β將根據(jù)RTT和P的抖動(dòng)程度分配權(quán)重。一種衡量抖動(dòng)的方法是，分別計(jì)算RTT和P的標(biāo)準(zhǔn)差，比較標(biāo)準(zhǔn)差同平均值的偏離程度的百分比，然后根據(jù)RTT和P兩個(gè)量的偏離程度占比來分配a和β權(quán)重，可以根據(jù)需要對加權(quán)因子進(jìn)行偏好設(shè)置，a和β默認(rèn)值為0.5，并滿足a與β和為1。歸一化值可以通過如下方式計(jì)算：

其中，max_RTT和min_RTT分別是所有子流中RTT的最大值和最小值；同樣的，max_p和min_p分別是所有子流中P的最大值和最小值。

在此基礎(chǔ)上提出我們的算法，具體調(diào)度流程如圖1所示：

（l）在調(diào)度開始前，更新所有的相關(guān)變量，包括每一條子流的質(zhì)量QSi；

（2）然后以每一條子流的質(zhì)量QSi作為子流的權(quán)重進(jìn)行排序；

（3）從發(fā)送窗口還有剩余的子流中選擇QSi最好的一條子流發(fā)送數(shù)據(jù)；

（4）檢查是否所有子流都處理過了，如果沒有，跳轉(zhuǎn)到3）；

（5）一輪調(diào)度結(jié)束。

3 仿真驗(yàn)證和結(jié)果分析

本文基于主流網(wǎng)絡(luò)仿真器NS-2進(jìn)行算法的驗(yàn)證和性能評估。本文的主要比較對象是傳統(tǒng)的MPTCP和基于最小RTT優(yōu)先的數(shù)據(jù)調(diào)度算法。首先，將MPTCP的實(shí)現(xiàn)方案添加到NS-2中。然后，將我們的調(diào)度算法和比較對象實(shí)現(xiàn)到現(xiàn)有的MPTCP中，本文評估主要指標(biāo)是吞吐量。

3.1 仿真場景配置

如圖2所示是本文采用的三路徑拓?fù)浣Y(jié)構(gòu)，發(fā)送方和接收方都裝備了多個(gè)網(wǎng)絡(luò)接口卡。路徑1的帶寬值設(shè)置為2Mbps，時(shí)延設(shè)置為80ms，隊(duì)列大小設(shè)置為50個(gè)數(shù)據(jù)包，路徑2的帶寬值設(shè)置為384kbps，時(shí)延設(shè)置為lOOms，隊(duì)列大小設(shè)置為80個(gè)數(shù)據(jù)包，路徑3的帶寬值設(shè)置為IOMbps，時(shí)延設(shè)置為50ms，隊(duì)列大小設(shè)置為50個(gè)數(shù)據(jù)包。三條路徑的鏈路丟包率都在0-l%之間動(dòng)態(tài)變化。上層分別搭載的是FTP應(yīng)用和CBR應(yīng)用（比特率為2Mbps）。仿真時(shí)間設(shè)置為500秒，其他未給出的仿真參數(shù)采用默認(rèn)值。

3.2 結(jié)果分析

如圖3所示，本文比較了傳統(tǒng)的MPTCP輪詢調(diào)度的策略和基于最小RTT優(yōu)先的調(diào)度策略。主要的評估指標(biāo)是吞吐量。分別做了兩組實(shí)驗(yàn)，一組上層搭載的是FTP應(yīng)用程序，而另一組搭載的CBR應(yīng)用程序，比特率為2Mbps，然后分別比較其吞吐量的變化情況。

如圖3左圖所示，采用最小RTT優(yōu)先和基于權(quán)重的調(diào)度策略在丟包率變化過程中，都比傳統(tǒng)的輪詢調(diào)度策略有了較大的提高，在丟包率較小的時(shí)候基于權(quán)重的調(diào)度策略和基于最小RTT優(yōu)先的性能差距較小，但是隨著丟包率的增加，基于權(quán)重的調(diào)度策略表現(xiàn)了更好的性能，這主要?dú)w功于基于權(quán)重的調(diào)度策略同時(shí)考慮了RTT和丟包率的影響。

如圖3右圖所示，在支持CBR方面，在丟包率較低的時(shí)候，這幾種機(jī)制都能夠很好的支持上層應(yīng)用，但是在丟包率增大之后，傳統(tǒng)的MPTCP還是落后于其他的兩種方案。但是與支持FTP不同的是，基于最小RTT優(yōu)先的調(diào)度策略和基于權(quán)重的調(diào)度策略的差距變大了，也就是說在對CBR應(yīng)用的支持上，基于權(quán)重的調(diào)度策略發(fā)揮了更好的性能。主要原因在于基于最小RTT優(yōu)先的調(diào)度策略在鏈條帶寬足夠但是可能鏈路質(zhì)量較差時(shí)，依然會被選為發(fā)送路徑，造成了性能的下降，而基于權(quán)重的調(diào)度策略可以避免這種調(diào)度結(jié)果的發(fā)生。

4 結(jié)論

本文提出了一種基于權(quán)重的MPTCP數(shù)據(jù)調(diào)度算法，通過將影響調(diào)度策略的RTT和丟包率信息都納入調(diào)度決策中，增強(qiáng)了傳輸方案適應(yīng)多變環(huán)境的能力。通過同傳統(tǒng)的MPTCP輪詢調(diào)度策略和基于最小RTT優(yōu)先的調(diào)度策略的分析和比較，顯示了基于權(quán)重的調(diào)度策略的優(yōu)勢。