一种适用于地空通信的负载分布算法*

余 翔，刘 晗，段思睿，陈宇博

(重庆邮电大学 通信与信息工程学院，重庆 400065)

0 引 言

日益增加的航空旅客通信业务对航空通信质量提出了更高的要求[1]。据估计，在未来几年内民航的乘客人次将从2020年的69 312万增长到2025年的122 152万。为了满足乘客的需求，未来航空通信要求具有高吞吐量和低时延的传输能力。多路径传输协议是一种适用于有线互联网和异构无线网络的并发传输协议，能够在具有多终端的通信网络上实现数据并发传输。采用多路径传输不仅可以保证吞吐量性能的提升，也能保证在恶劣环境下的通信质量。

多路径网络的流量分配一直是一个重要且活跃的研究领域[2-3]，而现有的分配策略可以分为基于流和数据包的流量分割方法。基于分组数据包的模型通常根据信道状态信息、分组延迟约束等将分组的数据包发送到不同的路径上。尽管调度策略减少了单个路径上的排队延迟，但也可能导致严重的数据包重新排序问题，从而导致较大的端到端延迟。为了解决端到端时延问题，Wu等人[4]提出了一种旨在通过将多个并行路径聚合为单个虚拟路径来最小化总数据包延迟的多路径负载分布(Sub-packet Based Multipath Load Distribution，SPLMD)模型，从而减少包延迟的变化和接收端包重新排序的风险，同时用一个混合的M/M/1模型估计了每条路径的排队延迟，并分割流量以最小化延迟变化的成本。Raiciu等人[5]提出了一种基于机会调度的调度器，对每个路径分配与流量分配关联的权重，可以在保持每条路径传输字节比例的同时，向多个路径发送数据包。而目前应用最广泛的多路径TCP协议(Multipath TCP，MPTCP)也是通过分割流的方式对多路径网络流量进行分配。Li等人[6]提出了一种基于系统编码的多路径TCP(Multipath TCP with Systematic Coding，SC-MPTCP)方案，该方案引入线性系统编码来解决在接收缓冲区限制下容忍路径异构的问题。Chen等人[7]对蜂窝和WiFi网络上的MPTCP的性能进行了测量研究，以调查路径多样性对应用级别度量的影响。Le等人[8]也提出了一种基于转发延迟的数据包调度(Forward-Delay-Based Packet Scheduling，FDPS)算法，通过发送方估计的转发延迟和吞吐量差异为并发路径分派数据包。

本文考虑到地空通信信道的不对称性，提出了一种拥塞感知负载分布(Congestion-aware Load Distribution，CALD)算法。该算法针对在地空通信场景下的高丢包、高时延特性重新估计了传输损失率，同时分别预估了各子路径的拥塞窗口大小，解决了统一的拥塞控制窗口不适用于非对称路径传输的问题。

1 系统模型及问题公式

1.1 系统模型

所提MPTCP解决方案系统模型如图1所示。本文研究了多个可用接入网络与MPTCP的端到端通信问题，所提出的CALD方案旨在端到端延迟约束下更好地调度非对称路径上传输的子流。当数据到达本地服务器，服务器将接收到的数据划分为多个子流，将每个子流划分为多个数据包，并暂存在多个可用通信路径的发送缓存区中。系统框架中的主要决策模块在本地服务器端实现，远端服务器端负责数据的接收重组。

图1 子流分配系统模型

本文考虑一个地空异构覆盖网络，并在其中部署了具有多个端到端通信路径的代理服务器。为了实现端到端的通信，可以通过将源IP和目的IP进行绑定来构造。由于构造的可用通信路径不相交，不具有共享瓶颈链路，即每个通信路径都可被认为是与其他路径无关的独立传输路径。因此，可以假设每个通信路径的可用容量、损失率以及RTT往返时延等物理特性是相互独立的[9-10]。

基于独立的端到端通信路径特性，设可用带宽为μp，其表示端到端感知到的带宽变化情况，具体数值可以通过发送缓存区内的数据和往返时延来计算。往返时间RTTp，代表发送数据包到接收到ACK确认消息的总时间。

(1)

首先，假设传输的总数据流为Sm，划分的子流可以表示为

(2)

(3)

(4)

由公式(4)可以得到路径p的状态转移矩阵为

(5)

(6)

由公式(5)、(6)可得，可以将路径p的第i个数据包错误的概率重写为

(7)

(8)

由于地空通信之间的移动性和长距离传输会造成长时间的链路中断和每次RTT时延不定的问题，可能会出现在规定时间内并不能收到ACK的情况，因此本文用逾期损失来衡量这种ACK的逾期情况。文献[12]中提到Sarkar等人提出逾期损失可以用M/G/1排队模型来近似，因此，单个路径上的端到端延迟遵循指数分布[13],可以建模为

(9)

式中：w表示数据包的到达率，可用平均时延w=1/E(Dp)来表示。因此公式(9)改写为

(10)

式中：T为约束逾期时间，E(Dp)表示端到端的平均时延。由于E(Dp)是一个基于大量端到端延时的统计数据集的估计值，因此Wu等人在文献[14]中提出了一个估计模型：

(11)

(12)

有效损失率可以表示为信道损失的数据包和数据包过期的总损失比，可表示为

(13)

基于有效损失率，估计总路径的聚合流量为

(14)

正如文献[15-17]所述，为了消除可用地空通信路径之间的较大延迟差异，将最小化端到端时延作为最优子流分配的一个约束条件。为了便于求解，本文将上述对通信路径p的线性约束优化问题转化成一个最大化实时流量Si的线性约束问题。

(15)

1.2 路径状态估计

为了有效地利用地空通信网络中可用的信道资源，更准确地对各个路径上的子流进行调度，准确地估计每个通信路径的状态是相当重要的。为了得到有效带宽参数，本文采用文献[18]中的方案进行估计，通信路径的可用带宽可被表征为

(16)

式中：wp代表当前时刻的拥塞窗口大小，而RTTp代表往返时延。由于在低质量的通信路径中，统一的拥塞控制很可能会导致性能下降，因此本文分别估计了各路径的拥塞窗口大小。由于MPTCP的特点是要求对TCP是友好的，因此本文采用文献[19]中研究人员模拟的对单条TCP拥塞窗口的平均大小作为通信路径p的拥塞窗口估计值。在本文中wp可以被表征如下

(17)

2 基于信道状态感知的负载分布策略

本文基于实用理论的流量分配方案，使用连续分段线性方法去最大化目标函数的输出结果[20]。由于此方案倾向于给具有更高质量和传输能力的通信路径分配更大的流量，因此极易导致地空异构通信网络中的流量负载分布不平衡。为了缓解严重的流量负载不平衡问题，本文引入了一个负载不平衡参数Lp来表示路径p的负载水平，并表示为

(18)

式中：μp·(1-πp)表示为当前路径p的无损带宽。如果Lp的值明显高于设定的阈值TLV[21],则路径p将过载。为了更快地达到收敛条件，将初始子流设置为无损带宽的比值，即

(19)

同时，将路径p上每次迭代的变化率设置为ΔSp，则下一次子流的分配情况可以表示为Sp+ΔSp。为了计算每次迭代的变化率，根据文献[22]中提出的链路增长算法来对每次的增量进行估计：

(20)

从而可以估计每条路径迭代后的有效增量为

(21)

基于信道状态估计的渐进式流率分配(Subflow Allocation)算法如下：

输入： {μp,ξp}p∈∈P,TLV=1.2,D=max(Dp),ΔSp=0.05Sp。

输出：S=max{Sp}p∈P。

1 for each elementpin available setPdo

2 InitializeSp,RTTp,E(Dp),Lp,wp

3 while(Sp≤μp·(1-πp))&&(Lp≤TLV)&&(E(Dp)≤D)do

4Sp=Sp+ΔSp

5 Update the elementLp,wp,RTTp,D=E(Dp)

6 end

7 Reset the above parameterSp,RTTp,E(Dp),Lp

8 while(Sp≤μp·(1-πp))&&(Lp≤TLV)&&(E(Dp)≤D) do

9Sp=Sp-ΔSp

10 Update the elementLp,wp,RTTp,D=E(Dp)

11 end

12 Determine the allocation vector of the subflow

13 end

14 Specific inter-path allocation:

15 find another avilable pathp′

16 if(Sp′≤μp′·(1-πp′))&&(Lp′≤TLV)&&(E(Dp′)≤D)

do

17Sp′=Sp′-ΔSp′orSp′=Sp′+ΔSp′

18 end

19 end

由于初始子流Sp被设置为无损带宽的比值，并不是从原点开始计算，可能会导致初值分配权重过高的问题,因此在算法中采用前向与后向迭代同时进行来解决此问题，得到最终的子流分配结果。本文按照所提算法的分配结果对接收到的流进行分配，并在下一节给出实验结果。

3 数据仿真及分析

基于shdowsock搭建了一个多路径端到端实验平台。本地服务器端和远端服务器端被映射到本地网络中的实际计算机中，并配置了多条可用通信路径。本文通过绑定本地服务器端和远端服务器端的多对IP地址构建了端到端通信网络。如图2所示，发送端输入的流量可以途经通信网络中所有可用路径到达接收端。

图2 端到端测试系统架构

3.1 参数设置

本次实验主要从吞吐量和端到端时延两个指标来衡量算法的性能。为了评估可用通信路径对整个网络吞吐量等性能的影响，对不同的路径的流量分布进行了实验(p=2,3,4,5)。实验中每条通信路径的参数设置如表1所示。本文使用地空通信链路仿真器对每条路径进行参数设定，分别模拟了并在远端服务器端实时统计流量分配情况。同时为了获得可靠的结果，重复每一组模拟实验10次，最后给出了一个平均结果。对于单一时间的结果，本文对TLV值进行了仿真分析。在图3中通过调整TLV值观察得到不同的端到端时延，进而得出最优的TLV值，给出了更具代表性的一组仿真结果。

表1 多通信路径参数

图3 最优负载均衡值TLV

3.2 数值分析

本文将得到的仿真结果与DEAM、ADMIT、EMTCP 以及MPTCP多路径协议中的子流分配算法进行了对比。首先,设置可用路径p=2，统计传输数据流分别为4 Mb、5.25 Mb、6.5 Mb、7.75 Mb下的数据包重传结果。本文统计了总的包重传数量，并在图4中展示了不同数据流下数据包的重传次数。从图中可以看出，由于MPTCP对于TCP应该是友好的，因此在引入预估的单条通信路径所对应的TCP平均拥塞窗口作为判定路径质量的一个标准后，数据包重传数量明显降低。

图4 数据包重传数量

同时，本文在远端服务器端统计了从数据包发送到数据重组后的端到端时延。如图5所示，本文所提算法展示了更低的端到端时延，其性能随可用通信路径和传输数据流的增加而提升。这是由于本文更加准确地估计了通信路径的一个质量情况，给质量较好的通信路径分配了较大的子流,因此链路拥塞情况得到了明显的改善，从而降低了端到端时延，并减少了连续的损失。图6表示一段时间内的平均损失率的变化。

图5 平均端到端时延

图6 平均丢包率

此外，由于本文在算法中使用最优链路增长算法对每次迭代的增量进行估计，使得每次分配的子流量与对应的信道状态的变化情况成正相关，从而更加准确地分配了通信路径所对应子流的数据量，因此更好地缓解了链路的拥塞情况，得到了较高吞吐量。图7和图8分别展示了吞吐量随可用路径数量的变化情况和随时间的变化情况。

图7 平均吞吐量

图8 瞬时吞吐量

4 结束语

本文提出了一种拥塞感知负载分布算法，通过预估MPTCP通信路径的一个拥塞窗口变化情况，映射到多路径的拥塞感知负载分布模型中；同时将每次的路径增量与通信路径的变化情况对应，预估对应的最优链路增长值，从而有效降低了端到端时延，提高了多路径传输的总吞吐量。

未来的工作中，将继续考虑改进地空通信的拥塞控制，并将路径传播能耗纳入到相关变量中进行综合研究。