面向时延敏感服务的多路径传输调度算法

◎青岛大学计算机科学技术学院◎冯飞宇◎陈飞◎

为了解决多路径传输控制协议（MultiPath TCP，MPTCP）子流任务完成时间不同步、整体传输延迟过大的问题。文章围绕多路径中的链路差异性设计了一种优化传输调度算法。通过实时监控多路径的链路状况和待发送数据流，将优化调度方案分为两部分，当多路径链路带宽被充分利用时采用传输速率优先，多条路径并发的传输数据；当多路径链路带宽未被充分利用时采用最快完成链路优先，以缓解子流完成时间不同步的问题。仿真结果显示，在文件下载、网页加载和视频播放等场景下，该算法性能比默认的最小往返延迟优先（MinRtt）算法综合提升了25%，可以降低传输延迟。

1.引言

传统的TCP网络架构只允许设备利用一个网络接口建立网络连接，这导致了大量的网络带宽资源没有被充分利用。为此，Multi-Connectivity的解决方案是通过在两个网络设备的网卡之间建立多条通讯链路，实现数据的聚合和分离[17]。其中MPTCP网络协议是由IETF研发的位于传输层的实现，是目前使用最广泛的多路径网络协议解决方案[1]。MPTCP允许设备利用其携带的多个网卡接口与对端设备建立多条网络连接进行数据传输任务，目前该协议应用于多种实际场景，如：配备wifi和LTE的智能移动终端[2][3]和数据中心中同时具有多条网络链路的主机等[4]。MPTCP还可以与传统TCP兼容且无需更改现有的上层应用[5]，是目前最成熟的多路径传输协议。

传输调度机制作为MPTCP中的一个重要组件，负责调度分配应用层需要发送的数据，其通过传输调度算法将数据包分配给可用的子流进行传输。作为传输调度机制核心的传输调度算法是决定MPTCP性能的主要因素之一[12]。但由于链路之间RTT、丢包率和拥塞窗口等网络参数的差异性，会对传输调度算法性能造成很大的影响，甚至会出现性能比使用一条最佳TCP连接还要差的现象[6][11][13]。

目前MPTCP默认的数据调度算法是MinRTT，该方法将优先选择RTT最小且存在拥塞窗口的链路以实现降低传输延迟的目的[7]。但由于终端设备的不同网络接口普遍存在异构性，网络状态也是动态变化的，直观的选择RTT最小的链路并不一定获得最佳的传输效率和系统资源利用率，具体体现在以下两方面：首先，RTT并不能完全反映当前网络的拥塞状况[14]，盲目选择RTT小的链路分配传输任务很容易闲置其他拥有大量带宽资源的链路，而且易造成较大的尾延迟。其次，虽然MinRTT可以结合机会重传和惩罚机制避免丢包以降低网络波动造成的影响[11]，但其无法适应网络中类似视频流等突发流量的场景[6]。

目前传输调度算法的设计主要存在以下两个问题：（1）调度算法选用的网络参数无法完全描述当前网络状况，链路传输完成时间存在较大的尾延迟，进而影响总传输延迟；（2）调度算法易受网络波动的影响，无法适应类似视频流这样的突发流量。

针对以上问题，本文以协调多链路的总体传输延迟为主要目标，解决了传输链路尾延迟较大的问题，较好的应对传输流量的突变，设计了不限制设备网络接口数量的同步完成传输调度算法（synchronous completion transmission scheduling，SCTC），通过尽可能同步各链路传输任务完成时间以实现低延迟传输。

2.相关工作介绍

虽然目前仍没有完善的调度算法，但已经有很多工作针对不同的性能优化目标提出了一些改进的调度算法。目前MPTCP调度器研究工作的性能优化目标主要分为：降低总的传输延迟、提高数据传输的吞吐量等。

低延迟是数据传输性能的一个关键指标，是传输调度算法的优化主要方向。MinRTT是目前linux-MPTCP内核中默认的调度算法，该算法将优先选择RTT最小且存在拥塞窗口的链路以实现降低传输延迟的目的[7]，但RTT反映不了网络的真实状况，由于子链路的异构性，会出现拥塞堵塞等降低网络资源使用率的现象；REMP[10]中所有子流冗余的发送相同数据，以带宽换取低延迟和鲁棒性，网络中往往会存在大量无用的冗余数据，增加了网络的负载，带宽有效利用率低；DEMS[8]通过同步两个子流的完成时间来实现低延迟传输，同时通过添加适量的冗余数据以适应网络波动，该算法的限制在于MPTCP连接只支持两条子流，同时会占用接收端大量的缓存空间，只适用于中小型文件（小于8M）[8][9]；DAPS[15]根据每个链路的实时传输时间选择要在每个路径上传输的分组序列，以有序接收，降低缓存占有率，降低应用层提取数据的延迟，但受链路差异性影响，无法对网络变化做出快速反应。

在一些高带宽需求应用场景，例如视频流媒体，吞吐量成为影响用户服务质量的重要因素。ECF[6]通过通过计算慢路径与快路径的传输完成时间来选择链路，提高快链路的使用效率，从而提高吞吐量，但该算法的复杂度随链路数量增加而指数增加，且易受网络波动的影响。文献[14]中提出的调度算法，在MinRTT的基础上加入了链路拥塞状况的考虑，通过分配与链路可用容量成比例的数据包，尽可能避免拥塞来提高吞吐量，但对于可用容量的计算会因为网络变化出现误差。BLEST[16]则通过检测发送窗口是否阻塞，最大限度地减少异构网络中的LOL阻塞问题，从而减少重传数量提高吞吐量。

3.多路径传输性能分析

为了验证MPTCP的可靠性，在VMware平台安装IEFT发布的Linux-MPTCP操作系统，配置了三个网络接口，使用MPTCP默认的三种传输调度算法MinRtt、Round Robin(RR)和Opportunity Redundant(OR)进行文件传输速率测试，并于传统TCP传输进行比较。实验中设计了两种实验场景，在链路差异较小的情况，三个网络接口的带宽分别为：10M，9M，8M；链路差异较大的场景下，网络接口的带宽为：10M，5M，1M；TCP实验组网络接口带宽固定为10M。每组实验做五次，并取实验结果平均值作为最终的结果。

实验结果显示传统TCP的平均传输速率为1.1M/s，而MPTCP的传输速率随链路的差异大小而变化。如表1所示，在链路差异较小的情况下，MPTCP传输速率可以达到传统TCP的250%；而在链路差异较大的情况下，MPTCP的传输性能只有传统TCP的53%。可见网络环境的差异性对于MPTCP的传输性能影响很大。

表1 MPTCP与TCP下载性能对比

接下来通过动态的加载网卡实验来表现网络环境差异性与动态性的综合影响，该实验初始时只有一个网卡投入使用，之后每隔10秒多加载一块网卡，最多同时加载三块，实验结果如图1所示。在链路差异较小的情况下动态的加载网卡，整体的网络传输速率呈线性的上升；而当链路差异较大时，动态的加载网卡对传输性能提升有限，而且随着网卡数量的逐渐增加，传输性能反而大幅下降。

图1 网络接口动态加载

4.问题模型与解决方案

为了能够在异构网络中降低传输延迟，我们进行以下建模分析。

参数列表 说明n 未发送的数据包数量n′ 可能造成尾延迟的数据包数量m可用链路数量i当前链路i cwndi 链路i当前可用的拥塞窗口rtti 链路i当前的往返延迟

表2 参数说明

每轮的发送周期以当前时刻未发送的数据包作为接下来需要传输调度的数据。假设一个周期内存在n个数据包需要发送，终端设备拥有m条可用链路，每条链路的拥塞窗口大小为cwndi，每条链路的往返时延为rtti，传输调度算法需要设计合理的调度算法来给每条链路分配数据包，使得传输任务总延迟T最低。假设一个周期内，每条链路需要发送的数据包数量为si，则每条链路的传输完成时间ti可以通过公式（1）的分段函数求出。在实际传输过程中，未填充满拥塞窗口的数据传输仍会耗时一个rtt，所以需要合理的给子流分配数据包，尽可能的同步子流的完成时间，提高每条链路的使用效率，减少每个周期传输任务的完成时间。即在求解ti的时候需要尽可能的满足si%cwndi=0 的条件。（1）

通过对以上问题的建模，可以得到： （2）

由于该模型目标函数t 是非线性的，随着数据包数量的增加，目标函数图像呈阶梯状。又由于决策变量s和链路的窗口cwnd、时延rtt为离散的整数，所以该问题是混合整数非线性规划问题，是非凸优化问题[18]。这类问题通常是NP的，无法在多项式时间内求解出最优解，可以使用近似算法得到近似解。

4.1多路径并发传输

首先多路径并发传输模块作为SCTC算法的一部分，在发送缓冲区数据较大时调用，此时各链路可以充分利用带宽资源。该部分按照链路的数据传输速率来为每条链路分配数据包，其中cwndi可以表示链路的实际网络负载能力，rtti表示链路的往返时延，用来代表链路的实际网络传输能力。该调度算法在终端需要发送数据的时候调用，分配的数据即为当前发送缓冲区的数据，该调度算法根据各链路的传输速率的比例分配传输任务，尽量实现各子流完成时间同步。在传输过程中产生新的发送请求则等待当前传输任务都结束后执行，传输调度算法默认每个发送周期内网络参数不变。伪代码如下所示。

Repeat

筛选出当前所有拥有拥塞窗口的链路集合sbfCandidates

if sbfCandidates is NULL

当前无可用链路，退出并等待下一个发送周期

else

Until（链路选择结束）

图2 尾延迟

在每个发送周期内，该模块首先筛选出当前所有的具备拥塞窗口的可用链路，之后计算的各个子流的传输速率并优先选择传输速率大的链路分配传输任务。这个方法可以在一定程度上缓解链路异构性带来的影响，但该方法通过公式（1）计算得到的子流完成时间差异仍比较大。如图2所示，T′为理想的完成时间线，即n个数据包按照MPTCP所有链路的传输能力之和计算所需要花费的时间，但一般情况下很难实现绝对同步的情况；T为执行该调度算法完成传输任务的实际完成时间线，可以按照公式（1）计算，各链路最后一次都会传输少量的剩余数据。T-T′为尾延迟。可以分析得到尾延迟现象的原因是快速链路的使用效率较低，慢链路上负载了较多的数据传输任务，且尾延迟现象会随着链路差异性的增加，越来越明显。

4.2尾延迟处理

图3 SCTC链路选择流程

为了尽可能避免尾延迟现象对整体传输延迟的影响，需要进一步完善传输调度算法SCTC。由于模型（2）是NP的，无法在有限时间内求出最优解，所以为了能够尽可能的同步子流的完成时间，SCTC在造成尾延迟的部分数据通过贪心算法来获得次优解。

在多路径并发传输阶段每条链路进行数据传输的数据量是其拥塞窗口的整数倍，各子流完成所分配的数据传输任务所需要的时间为如公式（3）所示：

结合公式（1）与公式（3），子流的完成时间满足等式（4），当si刚好为子流拥塞窗口的整数倍时，不存在造成尾延迟的数据，所以其传输任务完成时间等于公式（1）计算所得时间；如果si不是子流拥塞窗口的整数倍，则此时其完成时间与公式（1）计算所得相差一个rtti的时间，传输调度算法所要做的正是优化由于子流链路属性差异性使得最后一次传输造成子流完成时间的不同步，以减少总的传输时间。（4）

SCTC用n′表示剩余未分配的数据包。通过公式（5）可求得n′。如果多路径并发传输阶段T′=T，则n′=0，各子流的传输完成时间完美同步，不需要优化；若每条链路在最后一次传输时其拥塞窗口都只差一个数据包塞满时，此时n′获得最大值，是最坏情况，不存在优化空间。n′取值范围如公式（6）所示。

图4 实验架构

图5 不同带宽下文件下载实验

图6 网页对象加载实验

经过上面的分析，尾延迟是由于快速链路的使用效率低造成的，所以分配最后的n′个数据包时，优先选择可以提前完成任务的链路k，贪心规则为：

其中ti为链路i当前任务的完成时间，rtti为链路i的往返时延。

传输速率优先模块分配数据时，会出现数据无法完整的填充子流拥塞窗口的现象，剩下的数据虽然很少，但仍需要一个rtt的传输时间，所以使用传输速率优先模块的传输时间为T=t′i+rttmax；而做了尾延迟处理的SCTC传输完成时间是T′=Min(t′i+rtti)，可得出T′≤T。SCTC算法伪代码与流程图如下所示：

Repeat

筛选出当前所有拥有拥塞窗口的链路集合sbfCandidates

if sbfCandidates is NULL

当前无可用链路，退出并等待下一个发送周期

else

统计未发送数据包数量R1与所有链路剩余拥塞窗口数量R2。

if R1 < R2

贪心选择最先完成传输任务的链路

else

优先选择传输速率最大的链路

Until（链路选择结束）

具体流程如图3所示，首先选取所有的可用链路，并统计未发生的数据包数量R1和当前剩余的拥塞窗口R2，如果 R1>R2 时，此时优先选择发送速率大的链路分配数据，尽可能快的将数据传递到对端；若 R1≤R2 ,则说明此时链路的拥塞窗口可能填充不满，所以为了尽量避免尾延迟，需要优先选择可以提前完成传输任务的链路。

5.实验

5.1实验设置

为了验证SCTC传输调度算法的性能，通过VMware虚拟机平台搭建了实验环境；其中服务端主机安装了搭载PROGMP编程模型的MPTCP内核，客户端安装IETF官网发布的Linux-MPTCP。实验环境中的主机操作系统均为ubuntu 18.04，配置多个网卡。实验过程中通过VMware网卡设置功能修改client端网卡的RTT、带宽等网络参数模拟各类网络状况，并与linux-mpTCP中集成的minRtt、Round Robin(RR)和 Opportunity Redundant(OR)三种调度算法进行性能对比。实验架构模型图如图4所示。

5.2实验结果分析

首先进行文件下载场景下的性能测试。该试验共进行四组实验，分别下载不同大小的文件，将SCTC与linux-MPTCP集成的三种传输调度算法进行下载时间的比较，同时为了确定网卡性能差异性带来的影响，先将一个网卡的带宽设置为1M，将另一个网卡的带宽值由1M逐渐变为10M，图5的横坐标表示的就是第二个网卡的带宽值。可以看出，随着第二块网卡的带宽逐渐增大，文件的下载时间前期是逐渐减少的，但随着链路之间网络性能差异越来越大，下载时间后面会小幅度的增加。本文中所提出SCTC算法在实验中表现良好，通过图5可以看出该算法更适用于中等大小的文件，对于64K这样足够小文件和4M这样的大文件传输调度算法对总的下载时间影响较小，总体来说相比于linux-MPTCP默认的MinRtt调度算法性能提升了约24%，与RR和OR比起来也有不少的提升。

接着测试传输调度算法在子流网络环境差异较大的情况下加载网络页面的性能。客户端设置了三个网卡，带宽分别为1M、5M和10M。将故宫官网首页部署服务器端，共包含53个网络文件，客户端浏览器加载网页时，将一直保持与服务器的网络连接，持续下载网络文件。图6左图描述了从请求网页到页面完全加载的时间，SCTC较其他三种传输调度算法加载时间减少约25%；图6右图显示了网页内全部网络文件从浏览器请求到完成加载的时间CDF图，SCTC传输调度算法较其他三种传输调度算法提前加载96.7%的网络文件。结果显示SCTC可以较好的应对网页加载的场景。

最后测试调度算法在网络差异较大的环境下播放dash视频时可以达到的码率以及对应的分辨率。实验环境中，客户端配备了三个网卡，带宽分别为1M、5M和10M，同时使用ffmpeg工具将测试视频分别转码为360P、480P、720P、1080P和1080P（60帧）的视频段，并使用开源的dash.js播放器进行播放。实验结果如表3所示，SCTC传输调度算法相较与其他三种调度算法，在网络差异较大的环境下可以将播放视频的分辨率稳定在720P，码率为1310kbps，性能较minRtt调度算法性能提高了56%，测试结果表明SCTC传输调度算法可以有效的应对视频流这样的突发流量。

表3 Dash视频播放测试

6.总结

本文中提出了一种新的MPTCP传输调度算法，首先通过一些实验证实了各链路网络的差异性与动态性对传输性能的影响。之后通过公式推导，将SCTC传输调度算法分为两个算法模块：可以优先选择传输速率快的链路传输数据，以达到快速降低传输延迟的目的；在数据量较少时贪心的选择最先完成的链路，可以避免尾延迟对传输性能的影响。最后通过进行仿真实验测试该算法在文件下载、网页加载和视频播放等常见场景下的性能，并与现有的三种传输调度算法进行了对比，结果表明SCTC传输调度算法性能较好，可以降低传输延迟。