趙歡歡

摘要：CMT中多條路徑同時(shí)進(jìn)行數(shù)據(jù)傳輸，在接收端存在數(shù)據(jù)亂序問題，該文改進(jìn)的數(shù)據(jù)調(diào)度算法，能協(xié)調(diào)每條路徑的RTT和CWND，計(jì)算出每條路徑分配的次數(shù)，以及每次分配數(shù)據(jù)的數(shù)據(jù)包序號(hào)，有效地解決了接收端數(shù)據(jù)亂序問題，使接收端的數(shù)據(jù)按序到達(dá)，避免接收緩沖區(qū)溢出。同時(shí)，使所有待發(fā)送數(shù)據(jù)的路徑在一個(gè)最長路徑RTT內(nèi)，盡可能多的發(fā)送數(shù)據(jù)，有效提高網(wǎng)絡(luò)效率。

關(guān)鍵詞：CMT；SCTP；時(shí)延；擁塞窗口

中圖分類號(hào)：TP311 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2015）24-0010-03

Based on Parallel Multipath Transmission Delay of the Data Transmission Scheduling Algorithm Improvement

ZHAO Huan-huan

（College of Information Technology Engineering， Tianjin University of Technology and Education， Tianjin 300222， China）

Abstract： CMT agreement multiple paths at the same time for data transmission， data out-of-order problems at the receiving end， the paper improved data scheduling algorithm， can coordinate each path RTT and the CWND， calculate the number of each path allocation， as well as the distribution of each data packet sequence number， effectively solve the problem receiving end out-of-order data， the data at the receiving end arrived in order， avoid the receive buffer overflow.At the same time， the effective use of all the sent data path， within a longest path RTT， each path can be as much as possible to send data， effectively improve the efficiency of the network.

Key words： Concurrent Multipath Transfer（CMT）；Stream Control Transmission Protocol（SCTP）；time delay； congestion window

隨著現(xiàn)代通訊技術(shù)的快速發(fā)展，越來越多的網(wǎng)絡(luò)終端有多接口接入能力[1]，比如：交換機(jī)、集線器、路由器、網(wǎng)卡等，也讓網(wǎng)絡(luò)終端能夠同時(shí)接入多種網(wǎng)絡(luò)[2]。傳輸層最基礎(chǔ)的協(xié)議TCP（Transmission Control Protocol）和UDP（User Datagram Protocol），不支持多端口接入功能，只能為多宿主主機(jī)提供一種網(wǎng)絡(luò)接入方式。

由SIGTRAN工作組2011年制定的SCTP（Stream Control Transmission Protocol，流控制傳輸協(xié)議）[3][4]，有效地結(jié)合了傳輸層的另外兩種主流協(xié)議TCP和UDP的主要優(yōu)勢，并且SCTP還具有多宿主特性（Multi-homing）與多流特性（Multi-streaming）。SCTP工作原理是：在兩臺(tái)主機(jī)的多條路徑中，選取一條路徑作為主路徑（Primary Path）進(jìn)行數(shù)據(jù)傳輸，其他路徑作為備用路徑；當(dāng)主路徑失效時(shí)，SCTP才從備用路徑中選取一條路徑，作為新的主路徑來傳輸數(shù)據(jù)。但是SCTP 不能同時(shí)使用多條路徑進(jìn)行數(shù)據(jù)傳輸，也就是說，SCTP沒有并行多路徑傳輸功能。

為了實(shí)現(xiàn)多路徑并行傳輸功能，在SCTP協(xié)議基礎(chǔ)上，Delaware大學(xué)協(xié)議工程實(shí)驗(yàn)室，提出了CMT（Concurrent Multipath Transfer，多路徑并行傳輸協(xié)議）[5]。CMT具有多路并行傳輸能力，讓兩個(gè)主機(jī)之間的多條鏈路同時(shí)進(jìn)行數(shù)據(jù)傳輸，能適應(yīng)主機(jī)的多接口接入能力，實(shí)現(xiàn)了多接口設(shè)備之間的并行多路傳輸，有效提高了數(shù)據(jù)傳輸效率。

本文將以CMT協(xié)議為基礎(chǔ)，結(jié)合每條路徑的傳輸時(shí)延和擁塞窗口，進(jìn)行數(shù)據(jù)包的分配，得出新的數(shù)據(jù)調(diào)度算法。解決了接收端數(shù)據(jù)亂序問題，避免接收緩沖區(qū)溢出，使每條路徑能盡可能多的發(fā)送數(shù)據(jù)，有效提高網(wǎng)絡(luò)效率。

1 相關(guān)研究

目前，針對CMT的研究主要集中在傳輸延遲、流量分配、路徑選擇、重傳策略等。文獻(xiàn)[6]結(jié)合帶寬估算的改進(jìn)算法和基于網(wǎng)絡(luò)擁塞控制算法進(jìn)行改進(jìn)，得到了擁塞控制算法TCP-AHN，在網(wǎng)絡(luò)吞吐量、擁塞窗口值、重傳次數(shù)方面優(yōu)于傳統(tǒng)方法，提高了網(wǎng)絡(luò)性能。文獻(xiàn)[7]在無線環(huán)境下，對時(shí)間敏感度和數(shù)據(jù)重要性分析，提出了基于多流優(yōu)先級的并行多路傳輸方案，即優(yōu)先級數(shù)據(jù)調(diào)度算法，根據(jù)路徑質(zhì)量對路徑分發(fā)數(shù)據(jù)，數(shù)據(jù)傳輸性能有所提高。文獻(xiàn)[8]分析影響路徑傳輸?shù)母鞣N因素，在CMT工作原理基礎(chǔ)上，給出了差異化路徑性能評估模型，提出基于亂序反饋的差異化路徑評估方案，通過亂序反饋來調(diào)節(jié)每條路徑的數(shù)據(jù)分配量，有效減少亂序包，提高吞吐量。文獻(xiàn)[9]根據(jù)擁塞大小和發(fā)送隊(duì)列信息對網(wǎng)絡(luò)性能評估，動(dòng)態(tài)調(diào)整每條路徑的數(shù)據(jù)傳輸量，合理的分配傳輸任務(wù)，使各路徑的平均時(shí)延相等，從而縮短數(shù)據(jù)包在接受緩沖區(qū)的排隊(duì)等待時(shí)延，減少亂序包數(shù)量。文獻(xiàn)[10]結(jié)合優(yōu)先級和帶寬，提出一種優(yōu)先級和帶寬結(jié)合的分組調(diào)度算法，在每次調(diào)度時(shí)以一定概率調(diào)度各個(gè)優(yōu)先級分組，當(dāng)隊(duì)列有大量分組沒有被調(diào)度時(shí)，能夠相應(yīng)提高調(diào)度概率。文獻(xiàn)[11]為每條路徑設(shè)置了獨(dú)立的發(fā)送緩存和接受緩存，多條路徑是同時(shí)進(jìn)行數(shù)據(jù)傳輸?shù)?，結(jié)合通信路徑的實(shí)際傳輸時(shí)延來分配數(shù)據(jù)量，這種數(shù)據(jù)分配算法，雖然為發(fā)送端數(shù)據(jù)包排了序號(hào)，但是沒有具體給出每條路徑每次發(fā)送數(shù)據(jù)包的序號(hào)，這樣的話，在接收端會(huì)出現(xiàn)數(shù)據(jù)亂序問題。

本文改進(jìn)了文獻(xiàn)[11]的數(shù)據(jù)調(diào)度算法，對數(shù)據(jù)亂序問題作出了解決方案，提出新的數(shù)據(jù)調(diào)度算法，結(jié)合每條路徑的RTT和CWND，確定了各條路徑每次傳輸?shù)臄?shù)據(jù)包序號(hào)，使接收端到達(dá)的數(shù)據(jù)是按序的，這樣數(shù)據(jù)能很快封裝傳輸?shù)缴弦粚?，不占用接收緩沖區(qū)內(nèi)存，有效的提高網(wǎng)絡(luò)傳輸效率。

2 數(shù)據(jù)調(diào)度算法

模擬的仿真模型，兩個(gè)主機(jī)A和B都是多接口設(shè)備，A是發(fā)送方，B是接收方。假設(shè)主機(jī)A有三個(gè)接口，分別為A1、A2、A3；主機(jī)B有三個(gè)接口，分別為B1、B2、B3。主機(jī)A和B之間有三條傳輸路徑，A1和B1之間的路徑是路徑1，即P1；A2和B2之間的路徑是路徑2，即P2；A3和B3之間的路徑是路徑3，即P3。網(wǎng)絡(luò)拓?fù)鋱D如圖1所示：

共有三條路徑進(jìn)行數(shù)據(jù)傳輸，依據(jù)每條路徑往返時(shí)延RTT從小到大排序，即R={R1、R2、R3}，得到時(shí)延最短的為P1，依次給路徑命名為P2 、P3。設(shè)定三條路徑的擁塞窗口分別為CWND1 = 3 、CWND2 = 2 、CWND3 = 4 ，往返時(shí)延分別為R1 = 10 、R2 = 11 、R3 = 40 。

1）計(jì)算路徑1的分配次數(shù)，[R3R1]次，即[R3R1=4010=4]，得到的時(shí)間點(diǎn)為{R1、2R1、3R1、4R1 }，其中R1=10、2R1=20、3R1=30、4R1=40。

2）計(jì)算路徑2的分配次數(shù)，[R3R2]次，即[R3R2=4011=3.6=3]，得到的時(shí)間點(diǎn)為{R2、2R2、3R2}，其中R2=11、2R2=22、3R2=33。

3）計(jì)算路徑3的分配次數(shù)為1次，得到的時(shí)間點(diǎn)為{R3}，其中R3=40。

4）[R=R1、2R1、3R1、4R1R2、2R2、3R2R3]，把得到的所有時(shí)間點(diǎn)進(jìn)行從小到大排序，得到結(jié)果為R={R1、R2、2R1、2R2、3R1、3R2、4R1 、R3}，即R={R1=10、R2=11、2R1=20、2R2=22、3R1=30、3R2=33、4R1=40 、R3=40}。

5）在R1時(shí)間內(nèi)，由路徑1進(jìn)行傳輸，P1分配的數(shù)據(jù)包序號(hào)為1、2、3。在R2時(shí)間內(nèi)，由路徑2進(jìn)行傳輸，P2分配的數(shù)據(jù)包序號(hào)為4、5。在2R1時(shí)間內(nèi)，由路徑1進(jìn)行傳輸，P1分配的數(shù)據(jù)包序號(hào)為6、7、8。在2R2時(shí)間內(nèi)，由路徑2進(jìn)行傳輸，P2分配的數(shù)據(jù)包序號(hào)為9、10。在3R1時(shí)間內(nèi)，由路徑1進(jìn)行傳輸，P1分配的數(shù)據(jù)包序號(hào)為11、12、13。在3R2時(shí)間內(nèi)，由路徑2進(jìn)行傳輸，P2分配的數(shù)據(jù)包序號(hào)為14、15。在4R1時(shí)間內(nèi)，由路徑1進(jìn)行傳輸，P1分配的數(shù)據(jù)包序號(hào)為16、17、18。在R3時(shí)間內(nèi)，由路徑3進(jìn)行傳輸，P3分配的數(shù)據(jù)包序號(hào)為19、20、21、22。

6）接著確定發(fā)送順序，每條路徑第一次發(fā)送的數(shù)據(jù)包率先發(fā)送，即R1 、R2 、R3時(shí)間點(diǎn)的數(shù)據(jù)包先發(fā)送。其余時(shí)間點(diǎn)的其余數(shù)據(jù)包，按照剩下時(shí)間點(diǎn)排序發(fā)送。所得數(shù)據(jù)包發(fā)送順序?yàn)閧1、2、3， 4、5， 19、20、21、22， 6、7、8， 9、10， 11、12、13， 14、15， 16、17、18}。

發(fā)送方發(fā)送數(shù)據(jù)包序號(hào)，具體的表述方法，如圖2所示：

在接收端，R1=10時(shí)，數(shù)據(jù)包1、2、3到達(dá)接收緩沖區(qū)；R2=11時(shí)，數(shù)據(jù)包4、5到達(dá)接收緩沖區(qū)；2R1=20時(shí)，數(shù)據(jù)包6、7、8到達(dá)接收緩沖區(qū)；2R2=22時(shí)，數(shù)據(jù)包9、10到達(dá)接收緩沖區(qū)；3R1=30時(shí)，數(shù)據(jù)包11、12、13到達(dá)接收緩沖區(qū)；3R2=33時(shí)，數(shù)據(jù)包14、15到達(dá)接收緩沖區(qū)；4R1=40時(shí)，數(shù)據(jù)包16、17、18到達(dá)接收緩沖區(qū)；R3=40時(shí)，數(shù)據(jù)包19、20、21、22到達(dá)接收緩沖區(qū)。數(shù)據(jù)包的接收情況，如圖3所示：

實(shí)際的網(wǎng)絡(luò)環(huán)境中，假設(shè)有m條路徑進(jìn)行數(shù)據(jù)傳輸，依據(jù)每條路徑的RTT進(jìn)行從小到大排序，得到的結(jié)果為{R1、R2 、R3、…、Rm-1、Rm}，依次對應(yīng)的路徑分別為{P1、P2 、P3、…、Pm-1、Pm}，設(shè)定m條路徑的擁塞窗口分別為{CWND1、CWND2 、CWND3、…、CWNDm-1、CWNDm}。

若待發(fā)送的總數(shù)據(jù)量為b0，判斷是否給第m條路徑發(fā)送數(shù)據(jù)，需滿足如下條件，則給m條路徑分?jǐn)?shù)據(jù)

[b0≥RmR1×CWND1+RmR2×CWND2+……+RmRm-1×CWNDm-1+CWNDm]

否則，判斷是否給第m-1條路徑分配數(shù)據(jù)，方法如公式所示。以此類推，直到把所有待發(fā)送的數(shù)據(jù)分配完。

1）計(jì)算路徑1的分配次數(shù)，[RmR1]次，得到的時(shí)間點(diǎn)為[R1、2R1、……RmR1R1]。

2）計(jì)算路徑2的分配次數(shù)，[RmR2]次，得到的時(shí)間點(diǎn)為[R2、2R2、……RmR2R2]。

3）計(jì)算路徑3的分配次數(shù)，[RmR3]次，得到的時(shí)間點(diǎn)為[R3、2R3、……RmR3R3]。

4）經(jīng)過多次分配后，計(jì)算路徑m-1的分配次數(shù)，[RmRm-1]次，得到的時(shí)間點(diǎn)為[Rm-1、2Rm-1、……RmRm-1Rm-1]。

5）路徑m經(jīng)過1次分配，得到時(shí)間點(diǎn)為{Rm}。

6）將得到的所有時(shí)間點(diǎn)R，組成一個(gè)集合，得到從小到大的一個(gè)排序，若時(shí)間點(diǎn)大小一樣，則以路徑級數(shù)低的，優(yōu)先排在前面。

[R=R1、2R1、……RmR1R1R2、2R2、……RmR2R2…………Rm-1、2Rm-1、……RmRm-1Rm-1Rm]

7）結(jié)合每條路徑的CWND，以及步驟（6）時(shí)間點(diǎn)的排序，分別給每條路徑按時(shí)間點(diǎn)的大小順序分配數(shù)據(jù)包序號(hào)，每條路徑的數(shù)據(jù)包個(gè)數(shù)就是CWND的大小。

8）將每一條路徑第一次發(fā)送的數(shù)據(jù)包序號(hào)提出來，按照順序依次發(fā)送。其余的數(shù)據(jù)包按照（7）的順序發(fā)送。

這種數(shù)據(jù)調(diào)度方法，有效避免數(shù)據(jù)亂序，接收緩沖區(qū)的數(shù)據(jù)按序到達(dá)，避免接收緩沖區(qū)溢出。同時(shí)，有效利用了所有待發(fā)送數(shù)據(jù)的路徑，在一個(gè)最長路徑RTT內(nèi)，每條路徑能盡可能多的發(fā)送數(shù)據(jù)，有效提高網(wǎng)絡(luò)效率。

4 結(jié)束語

由于CMT沒有考慮，一個(gè)時(shí)間段內(nèi)每條路徑發(fā)送數(shù)據(jù)包的次數(shù)，以及每次發(fā)送數(shù)據(jù)的數(shù)據(jù)包序號(hào)，這會(huì)引起鏈路質(zhì)量好的利用效率低，并且接收端產(chǎn)生數(shù)據(jù)包亂序問題。本文的數(shù)據(jù)調(diào)度算法，結(jié)合傳輸時(shí)延和擁塞窗口，對是否有m條路徑進(jìn)行了計(jì)算，還給出了每條路徑傳輸次數(shù)，以及每次傳輸?shù)臄?shù)據(jù)包序號(hào)，這些改進(jìn)，減輕了接收緩沖區(qū)負(fù)擔(dān)，避免了接收端數(shù)據(jù)包亂序，有效地提高了網(wǎng)絡(luò)傳輸效率。

參考文獻(xiàn)：

[1] Alpcan T，Singh J P，Basar T. Robust rate control for heterogeneous network access in multihomed environments [J]. IEEE Trans. on Mobile Computing ， 2009，8（1）：41-45.

[2] Report from the IAB workshop on routing and addressing [S]. IETF RFC 4984，2007.

[3] Y. Hung， H. Sieh， R. Sivakumar. A transport layer approach for achieving aggregate bandwidths on multihomed mobile hosts[J]. In Proc. ACM/IEEE MOBICOM. Atlanta， Georgia， USA. September 2002：83-94.

[4] M. Zhang， J. Lai， A. Krishnamurthy， et a1. A transport layer approach for improving end-to-end performance and robustness using redundant paths[C]. Usenix Annual Technical Conference. Boston， MS， USA. June 2004.

[5] Iyengar J R， Amer P D ，Stewart R. Concurrent multipath transfer using SCTP multihoming over independent end-to-end paths[J]. IEEE/ACM Trans. On Networking ，2006，14（5）：951-964.

[6] 陶洋，王婭，杜軍恒.MANETs中基于TCP的網(wǎng)絡(luò)擁塞識(shí)別控制算法[J].計(jì)算機(jī)工程與設(shè)計(jì)，2015，36（3）：581-592.

[7] 唐曼.無線環(huán)境下基于多流優(yōu)先級的并行多路傳輸[J].SOFTWARE，2014，35（10）：46-50.

[8] 杜文峰，吳真.基于亂序反饋的差異化路徑并發(fā)傳輸模型數(shù)據(jù)分配算法[J].計(jì)算機(jī)科學(xué)，2015，42（3）：60-64.

[9] 余東平，張劍峰，王聰，李寧.多路并行傳輸中數(shù)據(jù)調(diào)度算法的優(yōu)化[J].計(jì)算機(jī)應(yīng)用，2014，34（5）：1227-1231.

[10] 江明，劉鋒.一種優(yōu)先級與帶寬需求相結(jié)合的分組調(diào)度算法[J].太赫茲科學(xué)與電子信息學(xué)報(bào)，2015，13（1）：46-51.

[11] 杜文峰，吳真，賴力潛.傳輸延遲感知的多路徑并發(fā)差異化路徑數(shù)據(jù)分配算法[J].通信學(xué)報(bào)，2013，34（4）：149-157.