基于线性规划的MPQUIC调度算法

黄培纪 蒋艳 陈斌 李静 董苹苹 张连明

摘  要： 基于MPQUIC协议优化多路径调度算法，可进一步增强多路径聚合带来的性能提升。因此提出一个基于MPQUIC的调度算法。在数据传输之前，该算法通过线性规划合理地分配不同路径上的数据传输量，在尽量减小路径之间的传输完成时间差距的同时，最小化整体的传输完成时间。基于Mininet虚拟网络环境仿真平台，模拟了不同网络环境进行数据传输，实验结果表明，该算法的表现优于minRTT、ECF、BLEST算法。

关键词： QUIC； MPQUIC； 多路径调度； 线性规划

中图分类号：TP393.2          文献标识码：A     文章编号：1006-8228（2023）06-38-05

MPQUIC scheduling algorithm based on linear programming

Huang Peiji， Jiang Yan， Chen Bin， Li Jing， Dong Pingping， Zhang Lianming

（College of Information Science and Engineering， Hunan Normal University， Changsha， Hunan 410081， China）

Abstract： In order to enhance the performance gains from multipath aggregation and optimize the multipath scheduling algorithm based on the MPQUIC， a scheduling algorithm based on MPQUIC is proposed. Before starting the data transfer， the amount of data to be transferred on each path is reasonably allocated by linear programming. It not only minimizes the transmission completion time， but also minimizes the transmission completion time gap between different paths. The data transmission in different network environments is simulated based on Mininet， and the results show that this algorithm outperforms the minRTT， ECF， and BLEST algorithms.

Key words： QUIC; MPQUIC; multipath scheduling; linear programming

0 引言

近年來，随着互联网的快速发展，互联网承载的数据传输量越来越多，用户对体验质量的要求也逐步提高。另外，现在的笔记本电脑和智能手机都可以利用多个网络接口（例如Wi-Fi、4G/5G）进行网络通信[1]。然而，当前广泛使用的传输层控制协议（TCP， Transmission Control Protocol）较为臃肿与僵化，且只能使用其中一个网络接口进行通信，这愈发难以满足业务的要求与用户体验高质量的需求。因此，轻巧灵活的快速UDP互联网连接协议（QUIC， Quick UDP Internet Connections）与多路径传输协议研究成为热点[2]。

QUIC是一个由Google提出的、类似TCP的传输层协议[3]，底层使用UDP协议进行通信。但QUIC无法有效地同时利用多条网络路径进行数据传输，为此，De Coninck等人[4]在QUIC的基础上提出了多路径QUIC（MPQUIC， Multipath QUIC）。MPQUIC允许传输层的一条连接对应物理层的多条路径，以此来实现多条路径带宽的聚合，减小数据传输所需要的时间。在多路径数据传输中，能否合理地使用多条路径极大地影响着多路径传输的性能。为此，需要设计一个有效的、合理的调度算法，路径调度算法决定着数据包会在哪一条路径上进行传输。

综上所述，本文在De Coninck等人所提出的MPQUIC基础上，考虑不同路径之间存在的差异，提出一个基于线性规划的路径调度算法。算法通过减少不同路径间的传输完成时间差异，避免因为某一条路径传输完成时间过长而导致整体的传输完成时间过长，从而充分使用所有的可用路径，减少数据传输时间。

1 背景知识

1.1 QUIC

QUIC由Google首次公开提出于2012年的互联网工程任务组（IETF， Internet Engineering Task Force）讨论会议上。随后，QUIC的标准化工作交由IETF接管，并发布了正式的QUIC标准。

相比于TCP，QUIC具有很多优点。例如，TCP每次建立连接时需要2-RTT来进行三次握手，而QUIC在大部分的情况下可以做到0-RTT建立连接并开启数据传输。QUIC当前默认的拥塞控制算法是Cubic，由于QUIC是部署在用户空间，可以根据需求灵活地选取合适的拥塞控制算法，但这对于部署在系统内核中的TCP来说是很难做到的。另外，TCP是依据四元组惟一标识一个连接，而QUIC是依据连接ID来惟一标识一个连接，当端口、IP等发生改变时，QUIC并不需要重新建立连接。所以，QUIC相比于TCP具备部署方便、高效与灵活等特性，更加符合当前业务和用户体验的要求。

1.2 MPQUIC

在多路径TCP（MPTCP， Multipath TCP）协议的启发下，De Coninck等人将多路径传输机制引入到QUIC中，提出了MPQUIC协议，其具体框架如图1所示。MPQUIC可以同时使用客户端和服务器之间的多条路径，加快数据传输速率，同时还能灵活切换数据的传输路径，保证良好的传输性能，增强故障排除能力。

在多路径传输协议中，合理的路径调度算法和良好的数据管理机制是获得优良性能的关键[5]。在路径调度方面，MPQUIC可以直接从路径管理器中获取全局视图，全局视图中记录着所有的可用路径与其具体信息，可以用来检测性能不佳或中断的路径，以便加快数据传输过程中的路径切换[6]。当存在多条可用路径时，发送方需要选择一条合适的路径来传输数据包，而这种选择是由路径调度算法所决定的。

1.3 线性规划

线性规划是运筹学中数学规划的一个重要分支，并且，由George Dantzig于1947年提出的求解线性规划的单纯形法使得线性规划在理论上趋于成熟。在实践中，线性规划是现代管理中经常使用的基本方法之一，并且可以通过使用计算机去处理具有数千个约束和决策变量的线性规划问题。

线性规划问题是在一组线性约束下寻找线性目标函数的最大值或最小值，其目标函数和约束都是线性函数，且目标函数能够找到最大值或最小值。对于线性规划问题的解，满足定义的约束的解称为可行解，使目标函数最大化或最小化的可行解称为最优解，所有可行解的集合称为问题的可行域。

2 相关工作

随着多路径传输协议的不断发展，路径的异构性会大大削减多路径传输性能这一问题引起研究者的广泛关注。路径的异构性指的是多条路径的带宽、时延等存在差异，这个差异增加了数据乱序到达的可能性，从而降低了多路径数据传输的性能[2]。为此，众多研究者在MPTCP或MPQUIC的基础上，提出了不同的路径调度算法。

MPQUIC默认的调度算法是minRTT[4]，它按照往返时延（RTT， Round-Trip Time）从小到大的顺序循环路径传输数据，并没有考虑路径的带宽和异构性，容易导致传输时间变长。Wang等人[7]提出了一种基于优先级的移动HTTP/2流调度算法。调度算法根据流的大小和依赖树的信息，基于加权轮询（WRR， Weighted Round Robin）算法计算流传输的顺序，然后以独占方式传输每个流。虽然与默认的循环机制相比，该方法减少了阻塞时间，但它过于依赖HTTP/2依赖树。不管传输路径是否空闲，当被依赖流尚未发送时，依赖该流的其他流只能等待，导致资源浪费和传输时间增加。

Lim等人[8]提出了最早完成优先（ECF， The Earliest Completion First）算法，利用路径的RTT、带宽和连接级发送缓冲区大小等相关信息，基于MPTCP提出了新的路径调度算法。在存在路径异质性的情况下，ECF能够有效利用所有可用路径，特别是对Web网页浏览、流媒体视频传输时，有更好的表现。Ferlin等人提出了[9]发送窗口阻塞估计调度（BLEST， Blocking Estimation-based MPTCP Scheduler）算法，旨在最小化异构网络中的队头阻塞，从而通过减少虚假重发的数量来增加带宽聚合的能力。虽说ECF与BLEST各有千秋，但它们的提出都是基于MPTCP，而TCP协议并不会考虑到不同被传输的数据流之间的关系，例如流的优先级、流之间的依赖等。

为了能够更充分利用多路径资源，更进一步提高MPQUIC的性能，本文提出了一个线性规划调度算法（LPS， Linear Programming Scheduler）。LPS使用线性规划算法来分配数据流在不同路径上所传输的数据量，在最小化不同路径上完成数据传输所需的时间差距的同时，减小整体的传输完成时间。

3 LPS算法

3.1 LPS概述

LPS是一个基于MPQUIC的路径调度算法，旨在减小多路径数据传输的完成时间。算法通过分析数据流与路径的信息，将打包好的数据流合理分配到不同的路径上进行传输，避免出现大量数据集中在某一条路径上进行传输的情况，尽可能使得不同路径上的数据同时完成传输并最小化数据传输完成时间。

LPS的传输调度过程如图2所示。当服务器与客户端建立连接时，服务器的路径管理器可以获得每条路径的属性以及要传输的数据流，例如带宽、拥塞窗口（CWND）、RTT、流的大小等。LPS按照RTT对可用路径进行升序排序，并按优先级对流进行降序排序，再根据线性规划算法在路径上预先分配数据传输量。接下来，根据算法预先分配的结果，服务器使用MPQUIC协议将数据包发送给客户端。最后，当接收到数据时，客户端将ACK帧发送至服务器，以表示数据已被接收，并且服务器更新其CWND。

3.2 问题建模

为了形式化该问题，首先假设有n条可用路径和m个流，并按照优先级对流进行降序排序。设Ri表示可用路径i的RTT，Bi表示可用路径i的带宽，Sj表示流j的大小，其中[i∈[1，n] ， j∈[1，m]]。如果流j通过可用路径i传输了大小为Cij的数据，则称流j调度在可用路径i上的数据比例为Xij，其计算过程如公式⑴所示。

[Xij=CijSj]  ⑴

为了降低计算难度，我们简單将可用路径i完成数据传输所需的时间假设为Ti，其计算过程如公式⑵。

[Ti=j=1mCijBi+Ri]  ⑵

只有当所有的路径都完成了数据的传输后，本次传输才能结束，且耗时为[T=max（T1，T2，T3，...，Tn）]。所以，想要提高用户体验，减少数据加载等待时间，则需最小化传输耗时T。

3.3 解决方案

为了能够最小化T，我们使用线性规划计算所有流的调度比例Xij。求解线性规划问题是需要在可行域中寻找最优解，假设D是传输时间的上限，我们给出两个约束函数，如公式⑶、公式⑷。

[Ti≤D， 1≤i≤n]  ⑶

[i=1nCijBi≤D ， 1≤j≤m]  ⑷

另外，如果D设置得不合理，则得出的解不会是最优解。在LPS中，D被设置为：

[D=max（j=1mSjB1+R1 ， ... ， j=1mSjBn+Rn）]  ⑸

然而这两个约束没有考虑路径之间的RTT异质性。如果仅使用这两个约束，流j将优先在具有高带宽的路径上传输。这样就有可能导致大部分的数据都在高带宽高RTT的路径上传输，此时，若存在低带宽低RTT的路径的话，那这条路径资源就不会被充分利用，导致最终传输完成时间仍然居高不下。所以，为了能够得到最优解，需要将可用路径的RTT引入到约束中进行计算，同时尽量缩减不同路径的传输时间差距，使得每一条路径都能够被充分利用。根据上述描述，为了缩减不同路径的传输时间差距，给出第三个约束函数，如公式⑹。

[|Ti-Tk|≤L ， 1≤k

其中，L指的是一个较小的值，用于限制两个路径传输完成时间之间的差距。若L过小，则可能不存在可行域；但若L过大，则会影响算法的效果。在LPS中的初始值被设定为5ms，若不存在可行域，则往上递增5ms，直至存在可行域。

在公式⑹的约束下，所有路径的传输完成时间都较为相近，故我们将线性规划的最小化目标函数设置为：

[mini=1nTi] ⑺

在求解出Xij后，计算数据流在不同路径上传输的数据量Cij。在可用路径i上，优先级越大的流会越早被传输。最后，根据预先分配好的数据量，将数据流调度到不同的路径上进行传输。

4 性能测试

在本节中，基于Golang语言实现了LPS，并在不同的网络状态下进行文件传输，将其传输完成时间与minRTT、ECF、BLEST这三个调度算法进行对比。

接下来本文将评估一个大小为1024KB的文件在不同路径状态下的完成时间。为了模拟不同的网络状态，本文参考MPQUIC的实验装置[4]，将该网络拓扑设计为：两条独立的传输路径与基于这两条路径进行Web对象传输的客户端和服务器组成，拓扑图如图1所示。且在多个虚拟机上基于Mininet设置了不同的仿真网络环境，分别模拟时延异构、带宽异构、时延与带宽异构对多路径数据传输的影响。在这些仿真网络环境上，使用不同的路径调度算法进行数据传输，并记录客户端从启动到完成所有数据传输所消耗的时间，最后对多次实验后所记录的时间取均值。

4.1 时延异构

为了模拟时延异构，本文首先将两条路径的带宽固定为1Mbps，将路径1的RTT设置为1ms，并将路径2的RTT从1ms不断增加到400ms，以增加两条路径之间的RTT异构性。每种算法的结果如图3所示。

从实验结果可以看出，在时延异构性较小的时候，不同的调度算法下的传输时间差距较小。在时延异构性逐渐增大的时候，LPS调度算法的传输完成时间最少，BLEST与ECF调度算法的表現略优于minRTT调度算法。

4.2 带宽异构

为了模拟带宽异构，本文将两条路径的RTT固定为1ms，将路径1的带宽设置为1Mbps，将路径2的带宽从1Mbps不断增加到100Mbps，以增加两条路径之间的带宽异构性。实验结果如图4所示。

从实验结果可以看出，在路径带宽异构性逐渐增大时，相比于其他三种调度算法，LPS在带宽异构性大的时候表现较为优异。而带宽异构性较小的时候，四种调度算法表现差距较小。

4.3 时延与带宽异构

最后，为了同时模拟时延异构与带宽异构，本文将路径1的带宽与时延固定为1Mbps与1ms，路径2的带宽与时延分别设置为20Mbps、40Mbps、60Mbps与100ms、200ms，以同时增加路径的时延异构性与带宽异构性。实验结果如图5所示。

从实验结果可以看出，路径的时延异构性与带宽异构性同时增大时，LPS仍然保持优越的性能，且BLEST与ECF调度算法的表现略优于minRTT调度算法。

5 结论

本文为充分发挥多路径的效率，提高传输速率，在MPQUIC的基础上提出了LPS算法。LPS通过线性规划来调度多条路径上的数据传输，在试图平衡每条路径上的传输完成时间的同时，最小化整体的传输完成时间。最后基于仿真平台进行实验，验证了该方法的有效性。但对传输时间的计算较为简单，与真实的传输时间相比存在一定的偏差，且没有考虑到网络的波动情况。因此，如何更精准地计算传输完成时间、如何更合理地将线性规划应用在路径调度上，还有待进一步的研究。

参考文献（References）：

[1] Zeng H， Cui L， Tso F P， et al. Optimizing multipath QUIC

transmission over heterogeneous paths[J]. Computer Networks，2022，215：109198

[2] 张思惬.无线网络中传输控制新技术研究[D].硕士，西安

电子科技大学，2019

[3] Lee S， Yoo J. Reinforcement Learning Based Multipath

QUIC Scheduler for Multimedia Streaming[J].Sensors，2022，22（17）：6333

[4] De Coninck Q， Bonaventure O. Multipath QUIC： Design

and Evaluation[C]//Proceedings of the 13th international conference on emerging networking experiments and technologies，2017：160-166

[5] Dong E， Xu M， Fu X， et al. A loss aware MPTCP scheduler

for highly lossy networks[J]. Computer Networks，2019，157：146-158

[6] Schmidt T， Deutschmann J， Hielscher K S， et al. POSTER：

Revisiting Multipath QUIC Experiments and Comparing them with more recent Multipath TCP Implementations[C]//2021 IEEE International Symposium on Local and Metropolitan Area Networks （LANMAN）. IEEE，2021：1-2

[7] Wang J， Gao Y， Xu C. A multipath QUIC scheduler for

mobile HTTP/2[C]//Proceedings of the 3rd Asia-Pacific Workshop on Networking 2019，2019：43-49

[8] Lim Y， Nahum E M， Towsley D， et al. ECF： An MPTCP

path scheduler to manage heterogeneous paths[C]//Proceedings of the 13th international conference on emerging networking experiments and technologies，2017：147-159

[9] Ferlin S， Alay ?， Mehani O， et al. BLEST： Blocking

estimation-based MPTCP scheduler for heterogeneous networks[C]//2016 IFIP networking conference （IFIP networking） and workshops. IEEE，2016：431-439