基于传输时延的CMT数据调度算法改进

赵欢欢

摘要：CMT中多条路径同时进行数据传输，在接收端存在数据乱序问题，该文改进的数据调度算法，能协调每条路径的RTT和CWND，计算出每条路径分配的次数，以及每次分配数据的数据包序号，有效地解决了接收端数据乱序问题，使接收端的数据按序到达，避免接收缓冲区溢出。同时，使所有待发送数据的路径在一个最长路径RTT内，尽可能多的发送数据，有效提高网络效率。

关键词：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

随着现代通讯技术的快速发展，越来越多的网络终端有多接口接入能力[1]，比如：交换机、集线器、路由器、网卡等，也让网络终端能够同时接入多种网络[2]。传输层最基础的协议TCP（Transmission Control Protocol）和UDP（User Datagram Protocol），不支持多端口接入功能，只能为多宿主主机提供一种网络接入方式。

由SIGTRAN工作组2011年制定的SCTP（Stream Control Transmission Protocol，流控制传输协议）[3][4]，有效地结合了传输层的另外两种主流协议TCP和UDP的主要优势，并且SCTP还具有多宿主特性（Multi-homing）与多流特性（Multi-streaming）。SCTP工作原理是：在两台主机的多条路径中，选取一条路径作为主路径（Primary Path）进行数据传输，其他路径作为备用路径；当主路径失效时，SCTP才从备用路径中选取一条路径，作为新的主路径来传输数据。但是SCTP 不能同时使用多条路径进行数据传输，也就是说，SCTP没有并行多路径传输功能。

为了实现多路径并行传输功能，在SCTP协议基础上，Delaware大学协议工程实验室，提出了CMT（Concurrent Multipath Transfer，多路径并行传输协议）[5]。CMT具有多路并行传输能力，让两个主机之间的多条链路同时进行数据传输，能适应主机的多接口接入能力，实现了多接口设备之间的并行多路传输，有效提高了数据传输效率。

本文将以CMT协议为基础，结合每条路径的传输时延和拥塞窗口，进行数据包的分配，得出新的数据调度算法。解决了接收端数据乱序问题，避免接收缓冲区溢出，使每条路径能尽可能多的发送数据，有效提高网络效率。

1 相关研究

目前，针对CMT的研究主要集中在传输延迟、流量分配、路径选择、重传策略等。文献[6]结合带宽估算的改进算法和基于网络拥塞控制算法进行改进，得到了拥塞控制算法TCP-AHN，在网络吞吐量、拥塞窗口值、重传次数方面优于传统方法，提高了网络性能。文献[7]在无线环境下，对时间敏感度和数据重要性分析，提出了基于多流优先级的并行多路传输方案，即优先级数据调度算法，根据路径质量对路径分发数据，数据传输性能有所提高。文献[8]分析影响路径传输的各种因素，在CMT工作原理基础上，给出了差异化路径性能评估模型，提出基于乱序反馈的差异化路径评估方案，通过乱序反馈来调节每条路径的数据分配量，有效减少乱序包，提高吞吐量。文献[9]根据拥塞大小和发送队列信息对网络性能评估，动态调整每条路径的数据传输量，合理的分配传输任务，使各路径的平均时延相等，从而缩短数据包在接受缓冲区的排队等待时延，减少乱序包数量。文献[10]结合优先级和带宽，提出一种优先级和带宽结合的分组调度算法，在每次调度时以一定概率调度各个优先级分组，当队列有大量分组没有被调度时，能够相应提高调度概率。文献[11]为每条路径设置了独立的发送缓存和接受缓存，多条路径是同时进行数据传输的，结合通信路径的实际传输时延来分配数据量，这种数据分配算法，虽然为发送端数据包排了序号，但是没有具体给出每条路径每次发送数据包的序号，这样的话，在接收端会出现数据乱序问题。

本文改进了文献[11]的数据调度算法，对数据乱序问题作出了解决方案，提出新的数据调度算法，结合每条路径的RTT和CWND，确定了各条路径每次传输的数据包序号，使接收端到达的数据是按序的，这样数据能很快封装传输到上一层，不占用接收缓冲区内存，有效的提高网络传输效率。

2 数据调度算法

模拟的仿真模型，两个主机A和B都是多接口设备，A是发送方，B是接收方。假设主机A有三个接口，分别为A1、A2、A3；主机B有三个接口，分别为B1、B2、B3。主机A和B之间有三条传输路径，A1和B1之间的路径是路径1，即P1；A2和B2之间的路径是路径2，即P2；A3和B3之间的路径是路径3，即P3。网络拓扑图如图1所示：

共有三条路径进行数据传输，依据每条路径往返时延RTT从小到大排序，即R={R1、R2、R3}，得到时延最短的为P1，依次给路径命名为P2 、P3。设定三条路径的拥塞窗口分别为CWND1 = 3 、CWND2 = 2 、CWND3 = 4 ，往返时延分别为R1 = 10 、R2 = 11 、R3 = 40 。

1）计算路径1的分配次数，[R3R1]次，即[R3R1=4010=4]，得到的时间点为{R1、2R1、3R1、4R1 }，其中R1=10、2R1=20、3R1=30、4R1=40。

2）计算路径2的分配次数，[R3R2]次，即[R3R2=4011=3.6=3]，得到的时间点为{R2、2R2、3R2}，其中R2=11、2R2=22、3R2=33。

3）计算路径3的分配次数为1次，得到的时间点为{R3}，其中R3=40。

4）[R=R1、2R1、3R1、4R1R2、2R2、3R2R3]，把得到的所有时间点进行从小到大排序，得到结果为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时间内，由路径1进行传输，P1分配的数据包序号为1、2、3。在R2时间内，由路径2进行传输，P2分配的数据包序号为4、5。在2R1时间内，由路径1进行传输，P1分配的数据包序号为6、7、8。在2R2时间内，由路径2进行传输，P2分配的数据包序号为9、10。在3R1时间内，由路径1进行传输，P1分配的数据包序号为11、12、13。在3R2时间内，由路径2进行传输，P2分配的数据包序号为14、15。在4R1时间内，由路径1进行传输，P1分配的数据包序号为16、17、18。在R3时间内，由路径3进行传输，P3分配的数据包序号为19、20、21、22。

6）接着确定发送顺序，每条路径第一次发送的数据包率先发送，即R1 、R2 、R3时间点的数据包先发送。其余时间点的其余数据包，按照剩下时间点排序发送。所得数据包发送顺序为{1、2、3， 4、5， 19、20、21、22， 6、7、8， 9、10， 11、12、13， 14、15， 16、17、18}。

发送方发送数据包序号，具体的表述方法，如图2所示：

在接收端，R1=10时，数据包1、2、3到达接收缓冲区；R2=11时，数据包4、5到达接收缓冲区；2R1=20时，数据包6、7、8到达接收缓冲区；2R2=22时，数据包9、10到达接收缓冲区；3R1=30时，数据包11、12、13到达接收缓冲区；3R2=33时，数据包14、15到达接收缓冲区；4R1=40时，数据包16、17、18到达接收缓冲区；R3=40时，数据包19、20、21、22到达接收缓冲区。数据包的接收情况，如图3所示：

实际的网络环境中，假设有m条路径进行数据传输，依据每条路径的RTT进行从小到大排序，得到的结果为{R1、R2 、R3、…、Rm-1、Rm}，依次对应的路径分别为{P1、P2 、P3、…、Pm-1、Pm}，设定m条路径的拥塞窗口分别为{CWND1、CWND2 、CWND3、…、CWNDm-1、CWNDm}。

若待发送的总数据量为b0，判断是否给第m条路径发送数据，需满足如下条件，则给m条路径分数据

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

否则，判断是否给第m-1条路径分配数据，方法如公式所示。以此类推，直到把所有待发送的数据分配完。

1）计算路径1的分配次数，[RmR1]次，得到的时间点为[R1、2R1、……RmR1R1]。

2）计算路径2的分配次数，[RmR2]次，得到的时间点为[R2、2R2、……RmR2R2]。

3）计算路径3的分配次数，[RmR3]次，得到的时间点为[R3、2R3、……RmR3R3]。

4）经过多次分配后，计算路径m-1的分配次数，[RmRm-1]次，得到的时间点为[Rm-1、2Rm-1、……RmRm-1Rm-1]。

5）路径m经过1次分配，得到时间点为{Rm}。

6）将得到的所有时间点R，组成一个集合，得到从小到大的一个排序，若时间点大小一样，则以路径级数低的，优先排在前面。

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

7）结合每条路径的CWND，以及步骤（6）时间点的排序，分别给每条路径按时间点的大小顺序分配数据包序号，每条路径的数据包个数就是CWND的大小。

8）将每一条路径第一次发送的数据包序号提出来，按照顺序依次发送。其余的数据包按照（7）的顺序发送。

这种数据调度方法，有效避免数据乱序，接收缓冲区的数据按序到达，避免接收缓冲区溢出。同时，有效利用了所有待发送数据的路径，在一个最长路径RTT内，每条路径能尽可能多的发送数据，有效提高网络效率。

4 结束语

由于CMT没有考虑，一个时间段内每条路径发送数据包的次数，以及每次发送数据的数据包序号，这会引起链路质量好的利用效率低，并且接收端产生数据包乱序问题。本文的数据调度算法，结合传输时延和拥塞窗口，对是否有m条路径进行了计算，还给出了每条路径传输次数，以及每次传输的数据包序号，这些改进，减轻了接收缓冲区负担，避免了接收端数据包乱序，有效地提高了网络传输效率。

参考文献：

[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的网络拥塞识别控制算法[J].计算机工程与设计，2015，36（3）：581-592.

[7] 唐曼.无线环境下基于多流优先级的并行多路传输[J].SOFTWARE，2014，35（10）：46-50.

[8] 杜文峰，吴真.基于乱序反馈的差异化路径并发传输模型数据分配算法[J].计算机科学，2015，42（3）：60-64.

[9] 余东平，张剑峰，王聪，李宁.多路并行传输中数据调度算法的优化[J].计算机应用，2014，34（5）：1227-1231.

[10] 江明，刘锋.一种优先级与带宽需求相结合的分组调度算法[J].太赫兹科学与电子信息学报，2015，13（1）：46-51.

[11] 杜文峰，吴真，赖力潜.传输延迟感知的多路径并发差异化路径数据分配算法[J].通信学报，2013，34（4）：149-157.