车载异构网络中基于前向时延的多径传输路径调度优化

赵海涛，陈跃，张唐伟，朱奇星，朱洪波

（1.南京邮电大学教育部泛在网络健康服务系统工程研究中心，江苏 南京 210003；2.南京邮电大学通信与信息工程学院，江苏 南京 210003）

1 引言

近年来，随着工业技术和互联网技术的不断发展，硬件设备成本大大降低，网络设备普及越来越广，越来越多的终端设备装有多个网络接口，同时，装备在车辆上的网络接口也越来越复杂多样。新一代的车载网络可以实现移动过程中车辆之间的通信，以及低速移动或者静止时车辆与路边基础设施之间的通信，这些能为车辆提供安全消息传输、智能交通信息业务、多媒体数字业务等。异构网络中，多径传输技术可以同时利用多个网络的资源进行传输，聚合多个网络的传输能力[1-3]，有效提高吞吐量和资源利用率，实现负载均衡。多径传输中也面临很多问题，因为在异构网络中，为了使用多个路径进行数据传输，需要一个分组调度器，它的职责是决定通过哪条路径发送哪个数据分组。另一方面，为了获得更高的可靠性，数据传输时需要按照它们在发送方传输的相同顺序而在接收方传送数据分组（到上层应用程序）。然而，不同的路径具有不同的特性，如分组丢失率、带宽、往返时间等，不同路径发送的数据到达接收端时会发生乱序，这就需要对数据分组重新排序。这些无序分组会被累积在有限的接收缓冲器中，有可能导致缓冲区阻塞并影响车辆之间的通信性能。所以，需要设计一种有效的路径调度优化方法来避免较少的重新排序工作，防止多径传输的性能降低。

2 研究现状

多径传输可在协议栈的多个层实现，不同层的解决方案针对不同的问题，同时受该层特性的影响。因为应用层可以很好地适应应用的特性，所以可以实现更好的业务优化，但会增加应用层的复杂度。网络层对更高层透明，且对现有的基础设施兼容性好，但数据分组乱序会造成TCP（transmission control protocol）性能下降。由于链路层可以获取信道的信息，因此可以更好地适应信道的动态变化，但链路层的解决方案不适应于端到端传播。传输层的解决方案可以兼顾不同层的优缺点。本文主要针对传输层多径传输技术进行研究，并对数据分组乱序问题提出解决方案来提高传输性能和资源利用率。

基于数据调度可以解决数据分组乱序问题，文献[4]提出一种基于强化学习深度Q 网络的数据调度算法，该算法先收集各条路径的信息，依据路径的传输效果对各条路径进行奖惩，动态地估计各条路径的传输能力，将数据尽可能地分配到传输能力强的路径上，但会严重降低网络利用率。文献[5]针对路径时延对接收端乱序的影响，提出了一种基于时延约束的主动数据调度算法，该算法的核心思想是当路径时延小于设定的阈值时，则认为路径可用。但是该算法忽略了分组丢失率和带宽在实际网络中与乱序的制衡关系，而且也不能保证可用路径是全部路径中相互时延差最小的路径集合。文献[6]提出了一种多路径数据调度传输解决方案，该方案将单个数据流分成不同路径上的多个单独流，并在接收主机上将它们组合在一起，但在接收主机上组合时可能会出现拼接错误。文献[7]提出了一种改进的数据调度算法，在计算中加入分组丢失率这个参数，对各个路径的传输数据大小进行建模，通过仿真结果可知，该算法提高了吞吐量，但其不能适应网络的动态变化。文献[8]提出了Kim-2012 算法，该算法通过发送完数据分组并收到该数据分组的确认后，然后基于往返时间（RTT,round-trip time）在每条路径上调度数据分组。该算法使用固定的时间（）作为前向时延的估计，如图1 所示，但是，由于前向时延和后向时延不对称，因此这不是一个好的估计。

图1 前向时延和后向时延说明

基于路径调度可以解决数据分组乱序问题，文献[9]针对目前多路径并行传输过程中由于传输路径质量的差异导致网络传输性能整体下降的问题，提出一种多路径并行传输的路径动态决策（CMT-DS,concurrent multipath transfer-dynamic selection）方法。该方法考虑到路径传输质量对网络吞吐量的影响，通过测量时延、抖动、分组丢失率和缓存占用比这4 个路径传输属性，拟合成路径质量的关联函数，根据该关联函数对路径进行动态选择，从而实现动态选择路径的功能，以达到最理想的传输效果，但在室外环境或路径更多时效果明显降低。文献[10]提出2 种新颖的基于块估计调度程序和最短传输时间优先的调度技术，仿真结果表明，该技术可以降低交互时延，但对提高吞吐量效果不显著。文献[11]提出根据应用程序的工作量动态调整路径解决方案，该方案首先利用TCP 建模的思想来估计正在调度的路径上的等待时间以及同时在其他路径上发送的数据量，然后以减少完成的目标为目的，定期确定用于某些应用程序的路径集，但其实现起来较复杂。文献[12]提出一种基于FIFO（first input first output）的车道拥堵缓解策略，仿真实验表明，分批策略可以使滑行流出量增加25%以上，但该方法的实时性还有待验证。文献[13]提出一种调度多条路径的方法，该方法先估计乱序的数据分组，提前预测缓冲区阻塞，并阻止在性能差的路径上传输数据分组。但该方法选择路径时仅考虑分组丢失率和带宽，因此，选择路径时会出现偏差。文献[14]提出一种无线多跳网络环境下并行多径传输中的公平机制，使用Q 学习机制来获得网络中的动态信息，根据所获得的动态信息来选择最佳路径，以获得更高的带宽利用率并提高网络公平性指数，从而有效均衡流量并提高服务质量，但准确率还有待提高。文献[15]提出一种基于MPSCTP（multipath stream control transmission protocal）的优化分流技术，并提出使用一种时延不敏感的优化的启发式算法来研究多路径选择的策略，提高了对MPSCTP 中确认损耗的敏感性，从而提高了网络利用率，并为终端用户提供更好的服务质量，但是其内存空间占用较大，在实际应用中不够方便。

针对上述在解决多径传输中数据分组乱序的问题，本文提出了车载异构网络中基于前向时延的多径传输路径调度优化方案。该方案根据前向路径之间的估计时延和带宽差异来调度分组，可以减少重新排序工作，从而提高系统吞吐量。

3 基于前向时延的路径调度算法

3.1 估计前向时延差异

本文规定前向时延为从发送方到接收方的时延，后向时延为从接收方到发送方的时延。前向时延加后向时延就是往返时间（RTT）（如图1 所示）。因为发送器和接收器的时钟一般存在差异，所以估计前向时延在实际中并不是微不足道的。然而，从本节证明中可以看出，即使发送器和接收器的时钟存在差异，也可以估计得到路径之间的前向时延差异。

时延差计算如图2 所示，发送方通过2 条不同的路径向接收方发送2 个分组。S 代表发送方，R代表接收方，发送方在时间经路径1 将分组1 发送到接收方，分组1 的到达时间为，发送方在时间将分组2 经路径2 发送到接收方，分组2 的到达时间为。然后利用式(1)算出2 个数据分组的发送时间差Δs，利用式(2)得到2 个数据分组的接收时间差Δr，令ΔT=clkS-clkR 为发送方和接收方之间的时钟差，通过式(3)算出数据分组1 的前向时延。同理，利用式(4)算出数据分组2 的前向时延。最后通过式(5)得到2 条路径之间的前向时延差。

图2 时延差计算

3.2 调度数据分组

本节首先需要找到前向时延最短的路径。其中P={P1,P2,…,PN}是MPTCP 传输数据路径的集合，前向时延最短的pi可以由图3 中的算法确定。

该算法的主要思想是首先输入一条路径pi，然后依次计算该路径与其他所有路径pj之间的前向时延差Δpi pj，2 条路径之间的差异必须是一个非正数，最后计算得到最大的Sum 值对应的路径就是本文要找的路径pi。

得到前向时延最短的路径后，发送方就将调度数据分组。仿真实验时假设发送方使用子流之间共享的缓冲区，并且应用层的数据足够大来填充缓冲区。将发送缓冲区中的数据分区为数据分组，每个数据分组的大小等于TCP 路径的MSS（maximum segment size）。然后，利用本文提出的算法调度程序在前向时延小的路径上发送序列号低的数据分组。当决定选择路径i上的子流来传输数据之前，算法调度程序将先根据式(6)计算出数值idxi，然后缓冲区中idxi处对应的数据分组就将被传输。

图3 系统算法流程

其中，xi代表路径i的平均传输能力（B/s），MSS代表消息段大小，代表路径i的归一化速率，因此，乘积可以被解释为路径i和i*之间的“带宽−时延乘积差”。因此，在数据分组到达路径i之前，路径i*上有足够的空间来发送分组，在路径i上发送的分组应该在式(6)计算得出的分组之后。在发送一个数据分组之后，较大的idxi对应的数据分组将被移位送到缓冲区，如图4 所示。本文的分组调度算法原理是生成的数据分组先被存储在发送缓冲器中，然后只有当用于发送数据的窗口打开时才被分配给子流。

图4 根据前向时延差异分配数据分组

4 仿真结果与分析

本节评估了FDPS（forward delay-based packet scheduling）算法的性能，并与MPTCP[6]、FIFO[12]（具有最低RTT 的先进先出）和Kim-2012[15]的性能进行比较，重点比较的是重新排序缓冲区占用密度（RBD,reorder-buffer-occupancy density）和吞吐量这2 个参数。通过仿真得到不同参数下4 种算法的RBD 和吞吐量并进行比较。

本文的评估基于图5 所示的拓扑结构，并在NS-3 上进行了模拟。表1 给出了各种网络条件下模拟实验的参数。

图5 仿真路径拓扑

表1 仿真参数

4.1 双路径传输

本文假设数据流在没有后台流量的2 个单独的路径上传输。表1 是仿真参数，表2 是仿真时2 条路径的基本参数。如图6 所示，本文首先按照表1调整好实验参数，然后规定路径A 带宽为5 Mbit/s，时延为10 ms；路径B 带宽为5 Mbit/s，带宽为10 ms。通过图6 可以看出，即使2 条路径相同，所有算法仍然会发生无序分组现象。但是，4 种算法的性能仍有很大的差异，FIFO 和MPTCP 的表现是最差的，Kim-2012 的性能稍微比前两者表现得要好。与其他算法相比，FDPS 获得了最佳性能，其RBD 集中在零点附近。

接下来，在条件2 下进行仿真，结果如图7 所示。规定路径A 的带宽为5 Mbit/s，时延为10 ms；路径B 的带宽为5 Mbit/s，时延为25 ms，可以看到，此次仿真路径B 的时延增加。FIFO 和MPTCP算法的RBD 比图6 中的性能显著降低。在这种情况下，Kim-2012 依然比FIFO 和MPTCP 表现得要好，但是从图7 中可以看出FDPS 的性能仍然是最好的，其RBD 依然集中在零点附近。

图8 是在条件3 下进行的仿真。规定路径A 的带宽为4 Mbit/s，时延为10 ms；路径2 的带宽为8 Mbit/s，时延为30 ms。此次仿真是在具有不同时延和带宽的2 条路径上进行的。从图8 中可以看出，Kim-2012的性能比FIFO 和MPTCP 的性能表现得要好，但FDPS 的表现还是最好的，FDPS 的分组重新排序密度密集地集中在零点附近，而其他的则比较分散。

表2 仿真时2 条路径的基本参数

4.2 具有后台流量的双路径传输

实际上，网络中的TCP 流经常与其他前向或后向流共享带宽，为了评估在此类路径上发送数据分组时数据分组调度算法的效率，本文进行了具有后台流量的双路径传输仿真实验，此实验路径参数按表2 中的条件2 进行配置。从图9 可以看出，因为后台流使RTT 估算的精确度降低，所以所有算法性能都大大降低，且MPTCP 和Kim-2012 的表现差于FIFO，因为前两者对时变更敏感，但FDPS 的性能表现仍然是最好的。

4.3 3 条路径传输

图10 是本文在具有后台流量3 条相同的路径上进行的仿真实验。可以看到，所有算法性能都变差了。这表明，当并发路径数增加时，重新排序问题变得更加严重，但是，在这种情况下，FDPS 仍然表现最佳。

4.4 吞吐量比较

图6 条件1 下没有后台流量的双路径传输仿真实验

图7 条件2 下没有后台流量的双路径传输仿真实验

图9 具有后台流量的双路径传输仿真实验

图10 具有后台流量3 条路径传输仿真实验

图11 是相同条件下4 种算法的吞吐量仿真。从图11 中可以看出，MPTCP 吞吐量在刚开始时上升的趋势很快，但很快就开始下降然后趋于平缓，并且趋于平缓后MPTCP 吞吐量表现是最差的，另外，Kim-2012 和MPTCP、FIFO 的曲线走势基本相同，但Kim-2012 的吞吐量总体比FIFO 和MPTCP 表现得要好，FDPS 的吞吐量曲线是走势最好的，刚开始上升很快，一段时间后趋于平缓后，代表FDPS 吞吐量的曲线依然在其他3 条曲线的上方。综合4.1～4.3 节考虑分析，因为相同条件下FDPS 始终获得最优的重新排序缓冲区占用密度，数据分组乱序造成缓冲区拥塞的可能性最低，从而系统性能处于最优状态，所以FDPS 获得了最优的吞吐量表现。

5 结束语

本文针对多径传输中数据分组乱序问题，提出了一种基于前向时延的多径传输路径调度优化算法，所提算法在不同条件仿真实验中始终获得最佳的缓冲器占用率，这表明在各种网络条件下所提算法的性能表现都很稳定。在本文的模拟中，使用不限大小的重新排序缓冲区，因为本文希望捕获接收器上的所有数据分组以进行正确的RBD 和吞吐量测量。由于所提算法与其他算法相比都得到了最佳的重新排序缓冲器占用率，因此如果使用所提算法，则有限重新排序缓冲器大小的影响将是最小的，可以降低乱序问题提高吞吐量。针对本文中在数据分组调度方面仍然存在的问题，下一步的工作计划是设计更加合理的数据调度算法，进一步提升多路径传输性能。

图11 相同条件下4 种算法的吞吐量仿真