近些年来,以5G和Wifi6为代表的无线通信技术发展迅速,并已经在全世界实现了大规模部署。此外,智能手机等移动设备不断迭代更新,其网络通信能力也持续演进,使得应用同时利用多个不同网卡在多条不同物理链路上(如5G和WiFi)传输数据成为可能。加之新兴应用对于带宽的需求与日俱增,多路径传输技术得到了广泛关注。
多路径传输基于不同的传输层协议,主要分为多路径TCP(Multipath TCP,MPTCP)[1]和多路径QUIC (Multipath QUIC,MPQUIC) [2-4] 两类。MPTCP是传输层使用最广泛的多路径技术,并已经得到了商用智能手机操作系统如iOS[5]和Android[6]的支持。然而,TCP本身存在固有弊端,例如其实现在内核级别,难以与应用层进行结合,且对于应用提供商而言难以进行针对性的性能优化。为解决这一问题,MPQUIC利用了QUIC传输协议[7-8]的用户空间特性,可以方便地集成并部署到应用中。
概述
多路径传输领域的学术研究,在过去主要针对MPTCP开展。MPQUIC的部分核心设计仍沿用MPTCP,不过其基于QUIC和易与应用结合的特性,使其能够针对不同应用(如点播视频、短视频、低时延实时视频等)进行深入优化。
多路径的研究内容主要包括[9]:数据包调度、多路径(耦合)拥塞控制、子流/路径管理、能耗[27]、安全性等。其中,数据包调度是多路径设计最核心的部分之一。数据包调度器负责确定每个数据包应该由哪个路径(子流)进行发送,致力于解决两个关键问题[10-11]:
- 多路径队首阻塞(Head-of-Line blocking):由在慢子流分配过多数据引起,由于多路径传输需保证按序交付,快子流必须等待慢子流数据包到达,从而导致整体传输性能下降;
- 接收缓冲区(窗口)限制:由数据包乱序到达引起,慢子流的数据包占据了接收缓冲区,导致发送窗口被阻塞,影响快子流的充分利用。
本文重点梳理多路径传输中数据包调度机制的设计空间与发展历程。
设计空间
多路径数据包调度器可以分为四类:(相关综述可以参见:[9][29-32])
(1) 简单调度器
- 轮询(Round-Robin,RR):没有优先级,按照轮询的顺序将数据包填满各子流的发送窗口
- 不足:忽略外部因素(拥塞、丢包等)对子流传输的影响,无法保证数据包按序到达
- 最小往返时延优先(Lowest-RTT-First,LowRTT/MinRTT)[10]:将子流按RTT大小确定优先级,按优先级排序将数据包依次填满子流的发送窗口
- 优势:让路径质量好的子流承载更多的数据包,有一定负载均衡的效果
- 不足:无法保证数据包按序到达,存在多路径HoL阻塞和接收窗口限制等问题
- 机会性重传和惩罚(opportunistic retransmission and penalization,RP)[11]:为了补偿不同路径上的时延差异以缓解HoL阻塞,机会重传会在其他可用子流重传(重注入)引发HoL的数据包,惩罚机制会将阻塞的子流的拥塞窗口减半以限制其使用
- 不足:惩罚机制会减少聚合带宽
- 缓冲区膨胀缓解(bufferbloat mitigation,BM)[12]:通过限制传输的数据量(拥塞窗口减半)来排空网络缓冲区中的队列,从而降低RTT
- 不足:随机作用,不总是有效,会反复触发拥塞
- ReMP[13]:为了提高可靠性,将数据包冗余发送到所有子流上
- 不足:会产生额外的开销
- eMPTCP[14]:在路径管理和数据包调度中考虑多路径的功耗
- 不足:主要针对功耗进行设计,没有考虑性能提升
MPTCP默认调度器用的是MinRTT[10]+RP[11],也包含RR与ReMP[13]。
(2) 基于路径质量估计的调度器
如BLEST[21],ECF[22],MuSher[25]等
(3) 基于路径时延差的调度器
如DEMS[23],STMS[24],RAVEN[26]等
(4) 基于机器学习的调度器
如ReLes[27],Peekaboo[28]等
其中,第二、三类和第四类的大部分工作,其设计思想可以统一归为“乱序发生,按序到达”。
乱序发送,按序到达
目前主流的数据包调度器采用乱序发送,按序到达的思想:并非将连续的数据包分别分配到快子流和慢子流上(如MinRTT[10]),而是为快子流提前预留一部分数据包(超出其拥塞窗口,以便下一个RTT发送),以尽可能多地利用快子流进行传输,从而提高多路径传输整体的聚合带宽。其核心思想如下图所示[24]:
代表性研究工作的发展过程为:
- Westwood SCTP[15]:根据RTT与可用带宽估计值,估计不同路径上数据包的到达时间,据此对每条传输路径进行性能排序,并按降序选择路径传输数据包
- 不足:当不同路径之间存在显着不同的时延时效果不佳
- FPS(Forward Prediction Scheduling)[16]:估计传输路径上数据包的到达时间以及其他路径(非传输路径)上的数据传送时间,实现所有路径上的数据同时到达
- 不足:没有考虑丢包的影响[9]
- F2P-DPS(Fine-grained Forward Prediction based Dynamic Packet Scheduling)[17]
- DAPS(Delay Aware Packet Scheduling)[18-19]:有两个版本
- [18] :在接收buffer受限的环境下,为了减少接收buffer的阻塞时间,基于子流的转发时延倒数和CWND来确定各子流分配的数据包数量,按照时延从小到大的顺序依次为各子流分配数据包,确保在各子流转发时延的最小公倍数(LCM)内,所有数据包按序到达
- [19]:针对只有两个子流的场景设计,是原始算法[18]的简化及实践扩展,提出了最大接收buffer阻塞时间的分析模型
- 不足:若子流时延的差异较大(LCM较大),则调度时间(周期)较长,无法及时对网络变化做出反应;使用所有可以发送的子流,即使某个子流的贡献非常低(慢路径);没有考虑使用重注入(重传)[21]
- OTIAS(Out-of-order Transmission for In-order Arrival Scheduling)[20]:
- 不足:没有考虑拥塞窗口的可用性,可能会导致不必要的重传[21-22]
- BLEST(BLocking ESTimation)[21]:为了避免慢子流数据包阻塞发送窗口,使用RTT和CWND等参数计算快子流(在一个慢子流的RTT内)可以发送的数据包数量,通过减少不必要的重传次数来最小化HoL阻塞
- 不足:会导致部分子流(如空闲的快子流[22])未充分利用,从而延长较大文件的下载时间
- ECF(Earliest Completion First)[22]:利用RTT、带宽(拥塞窗口大小)、发送缓冲区等信息估计数据包传输时间,当无待发数据(发送缓冲区为空)时视情况等待可用快子流(而非直接使用慢子流发送),尽可能提高快子流的利用率,从而提升聚合吞吐量
- 不足:在多数时间里,大象流的发送缓冲区都是满的,ECF只有在流即将结束时(尾部数据包)才能起到调度作用。 此外,ECF在计算流完成时间(FCT)时没有考虑单向延迟,因此无法实现准确的有序到达[24]
- DEMS(DEcoupled Multipath Scheduler)[23]:感知数据块边界,快子流从前向后发送,慢子流从后向前发送,以此将子流解耦,通过估计RTT(单向时延,OWD)和带宽来实现快慢子流传输的同时完成,并根据网络情况重注入数据包
- 不足:需要一个巨大的缓冲区来存储整个块[24];主要针对两个子流进行设计,多路径扩展性不佳[26]
- STMS(Slide Together Multipath Scheduler)[24]:为了解决链路及接收端缓冲区受限时多路径聚合带宽下降的问题,根据数据包被ACK的情况,来动态调节快慢子流间数据包序列号的间隔(gap),以充分利用快子流并实现数据包的按序到达
- 不足:调节gap的过程偏启发式,可能不是最优策略
参考文献
- Ford A, Raiciu C, Handley M, et al. TCP extensions for multipath operation with multiple addresses[R]. 2013.
- Olivier Bonaventure. Apple uses Multipath TCP[EB/OL]. [2018-12-15]. http://blog.multipath-tcp.org/blog/html/2018/12/15/apple_and_multipath_tcp.html.
- Olivier Bonaventure. In Korean, Multipath TCP is pronounced GIGA Path[EB/OL]. [2015-07-24]. http://blog.multipath-tcp.org/blog/html/2015/07/24/korea.html.
- 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.
- Viernickel T, Froemmgen A, Rizk A, et al. Multipath QUIC: A deployable multipath transport protocol[C]//2018 IEEE International Conference on Communications (ICC). IEEE, 2018: 1-7.
- Liu Y, Ma Y, De Coninck Q, et al. Multipath Extension for QUIC[R]. 2023.
- Iyengar J, Thomson M. QUIC: A UDP-based multiplexed and secure transport[M]//RFC 9000. Fremont, CA, USA: Internet Engineering Task Force (IETF), 2021.
- Langley A, Riddoch A, Wilk A, et al. The quic transport protocol: Design and internet-scale deployment[C]//Proceedings of the conference of the ACM special interest group on data communication. 2017: 183-196.
- 薛开平, 陈珂, 倪丹, 等. 基于 MPTCP 的多路径传输优化技术综述[J]. 计算机研究与发展, 2016, 53(11): 2512-2529.
- Paasch C, Ferlin S, Alay O, et al. Experimental evaluation of multipath TCP schedulers[C]//Proceedings of the 2014 ACM SIGCOMM workshop on Capacity sharing workshop. 2014: 27-32.
- Raiciu C, Paasch C, Barre S, et al. How hard can it be? designing and implementing a deployable multipath {TCP}[C]//9th USENIX symposium on networked systems design and implementation (NSDI 12). 2012: 399-412.
- Ferlin-Oliveira S, Dreibholz T, Alay Ö. Tackling the challenge of bufferbloat in multi-path transport over heterogeneous wireless networks[C]//2014 IEEE 22nd International Symposium of Quality of Service (IWQoS). IEEE, 2014: 123-128.
- Frommgen A, Erbshäußer T, Buchmann A, et al. ReMP TCP: Low latency multipath TCP[C]//2016 IEEE international conference on communications (ICC). IEEE, 2016: 1-7.
- Lim Y, Chen Y C, Nahum E M, et al. Design, implementation, and evaluation of energy-aware multi-path TCP[C]//Proceedings of the 11th ACM Conference on Emerging Networking Experiments and Technologies. 2015: 1-13.
- Casetti C, Gaiotto W. Westwood SCTP: load balancing over multipaths using bandwidth-aware source scheduling[C]//IEEE 60th Vehicular Technology Conference, 2004. VTC2004-Fall. 2004. IEEE, 2004, 4: 3025-3029.
- Mirani F H, Boukhatem N, Tran M A. A data-scheduling mechanism for multi-homed mobile terminals with disparate link latencies[C]//2010 IEEE 72nd Vehicular Technology Conference-Fall. IEEE, 2010: 1-5.
- Ni D, Xue K, Hong P, et al. Fine-grained forward prediction based dynamic packet scheduling mechanism for multipath TCP in lossy networks[C]//2014 23rd international conference on computer communication and networks (ICCCN). IEEE, 2014: 1-7.
- Sarwar G, Boreli R, Lochin E, et al. Mitigating receiver’s buffer blocking by delay aware packet scheduling in multipath data transfer[C]//2013 27th international conference on advanced information networking and applications workshops. IEEE, 2013: 1119-1124.
- Kuhn N, Lochin E, Mifdaoui A, et al. DAPS: Intelligent delay-aware packet scheduling for multipath transport[C]//2014 IEEE international conference on communications (ICC). IEEE, 2014: 1222-1227.
- Yang F, Wang Q, Amer P D. Out-of-order transmission for in-order arrival scheduling for multipath TCP[C]//2014 28th international conference on advanced information networking and applications workshops. IEEE, 2014: 749-752.
- 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.
- 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.
- Guo Y E, Nikravesh A, Mao Z M, et al. Accelerating multipath transport through balanced subflow completion[C]//Proceedings of the 23rd Annual International Conference on Mobile Computing and Networking. 2017: 141-153.
- Shi H, Cui Y, Wang X, et al. {STMS}: Improving {MPTCP} throughput under heterogeneous networks[C]//2018 USENIX Annual Technical Conference (USENIX ATC 18). 2018: 719-730.
- Saha S K, Aggarwal S, Pathak R, et al. MuSher: An agile multipath-TCP scheduler for dual-band 802.11 ad/AC wireless LANs[C]//The 25th Annual International Conference on Mobile Computing and Networking. 2019: 1-16.
- Lee H J, Flinn J, Tonshal B. RAVEN: Improving interactive latency for the connected car[C]//Proceedings of the 24th Annual International Conference on Mobile Computing and Networking. 2018: 557-572.
- Zhang H, Li W, Gao S, et al. ReLeS: A neural adaptive multipath scheduler based on deep reinforcement learning[C]//IEEE INFOCOM 2019-IEEE Conference on Computer Communications. IEEE, 2019: 1648-1656.
- Wu H, Alay Ö, Brunstrom A, et al. Peekaboo: Learning-based multipath scheduling for dynamic heterogeneous environments[J]. IEEE Journal on Selected Areas in Communications, 2020, 38(10): 2295-2310.
- Polese M, Chiariotti F, Bonetto E, et al. A survey on recent advances in transport layer protocols[J]. IEEE Communications Surveys & Tutorials, 2019, 21(4): 3584-3608.
- Kimura B Y L, Lima D C S F, Loureiro A A F. Packet scheduling in multipath TCP: Fundamentals, lessons, and opportunities[J]. IEEE Systems Journal, 2020, 15(1): 1445-1457.
- Chao L, Wu C, Yoshinaga T, et al. A brief review of multipath tcp for vehicular networks[J]. Sensors, 2021, 21(8): 2793.
- Asiri M Y. A Survey of Multipath TCP Scheduling Schemes: Open Challenges and Potential Enablers[J]. 2021.