基于傳輸時延的CMT數(shù)據(jù)調(diào)度算法改進

趙歡歡

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

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

中圖分類號：TP311 文獻標識碼：A 文章編號：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)絡終端有多接口接入能力[1]，比如：交換機、集線器、路由器、網(wǎng)卡等，也讓網(wǎng)絡終端能夠同時接入多種網(wǎng)絡[2]。傳輸層最基礎的協(xié)議TCP（Transmission Control Protocol）和UDP（User Datagram Protocol），不支持多端口接入功能，只能為多宿主主機提供一種網(wǎng)絡接入方式。

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

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

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

1 相關(guān)研究

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

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

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

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

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

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

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

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

4）[R=R1、2R1、3R1、4R1R2、2R2、3R2R3]，把得到的所有時間點進行從小到大排序，得到結(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時間內(nèi)，由路徑1進行傳輸，P1分配的數(shù)據(jù)包序號為1、2、3。在R2時間內(nèi)，由路徑2進行傳輸，P2分配的數(shù)據(jù)包序號為4、5。在2R1時間內(nèi)，由路徑1進行傳輸，P1分配的數(shù)據(jù)包序號為6、7、8。在2R2時間內(nèi)，由路徑2進行傳輸，P2分配的數(shù)據(jù)包序號為9、10。在3R1時間內(nèi)，由路徑1進行傳輸，P1分配的數(shù)據(jù)包序號為11、12、13。在3R2時間內(nèi)，由路徑2進行傳輸，P2分配的數(shù)據(jù)包序號為14、15。在4R1時間內(nèi)，由路徑1進行傳輸，P1分配的數(shù)據(jù)包序號為16、17、18。在R3時間內(nèi)，由路徑3進行傳輸，P3分配的數(shù)據(jù)包序號為19、20、21、22。

6）接著確定發(fā)送順序，每條路徑第一次發(fā)送的數(shù)據(jù)包率先發(fā)送，即R1 、R2 、R3時間點的數(shù)據(jù)包先發(fā)送。其余時間點的其余數(shù)據(jù)包，按照剩下時間點排序發(fā)送。所得數(shù)據(jù)包發(fā)送順序為{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ù)包序號，具體的表述方法，如圖2所示：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 結(jié)束語

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

參考文獻：

[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)絡擁塞識別控制算法[J].計算機工程與設計，2015，36（3）：581-592.

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

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

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

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

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