基于时延差控制的有效吞吐量提高方法

2018-03-16李加成欧晗琪

计算机工程与设计 2018年2期

陶洋，李加成，欧晗琪

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

0 引言

随着互联网和相关技术的快速发展，网络终端可使用的接入技术越来越多，如3G、4G、WIFI、蓝牙等。多路径并行传输(concurrent multipath transfer，CMT)就是在这样的环境下发展而来。现有研究成果多集中在数据包重传策略、数据包丢失恢复及数据包的路径选择上。文献[1]提出一种优化的数据包重传路径选择方案，通过采用最小时延路径重传策略，提高了发生数据包重传情况下的有效吞吐量；文献[2]中提出一种多路径传输协议MPLOT(multi-path loss-tolerant)，可以在高丢包率的异构无线网络中提高多路径并行传输的实际吞吐量；文献[3,4]通过路径的实时状态来建立路径质量模型，然后根据质量模型的评价结果，来决定分组在哪条链路上传输；文献[5,6]通过卡尔曼滤波算法及其改进算法对各条路径的带宽、时延进行准确的估计，从而降低了接收端数据乱序的程度。

从以上分析可以看出，现有的相关研究虽然能够有效提高多路径并行传输的有效吞吐量，但也存在着一些问题，无法使多路径并行传输系统在异构网络环境中达到最优的性能。文献[7]进行了大量的仿真实验得出结论，多路径并行传输系统在异构网络环境下性能低于预期的原因包括：不正确的端到端往返时延(round-trip time，RTT)估计和路径间的不对称性等。不正确的RTT估计使得数据包分流、数据包重传等算法的执行结果出现误差，而路径间的不对称性则是导致传输过程中出现数据包乱序、有效吞吐量降低的根本原因之一。本文将分别针对这两个因素，针对SCTP-CMT协议，提出基于卡尔曼滤波的传播时延估计算法和基于时延差控制的有效吞吐量优化方法。

1 基于卡尔曼滤波的端到端时延估计

1.1 时延估计的重要性

在异构无线网络环境中，多路径并行传输系统中使用的传输链路往往属于不同的接入网络，链路之间具有非对称性，不同链路之间在时延、带宽、丢包率等参数上存在较大差异，限制了多路径并行传输系统的吞吐性能。此外，无线网络带宽低、时延抖动大和丢包率高等特点，同样会对多路径并行传输系统的吞吐性能造成不利影响。为了避免这些不利的影响，需要对不同链路上的时延、带宽、丢包率等参数进行准确估计，并根据估计的结果对传输策略进行自适应的调整。

SCTP协议中保留了TCP协议所使用的平滑的往返时延估计算法(smoothed RTT，SRTT)，式(1)为SRTT的计算公式，其中一般取经验值1/8。每当发送端接收到一个SACK报文，就对SRTT的值进行一次更新。在SCTP-CMT协议中，对于多路径并行传输中使用到的每一条并发路径分别维护一个SRTT的值

SRTT=(1-α)SRTTlast+αRTTnew

(1)

文献[8]中通过实验发现，在不同路径间时延差异较大的异构网络环境中，SRTT估计算法的准确性并不高，特别是对于时延较小的路径，SRTT的估计值有可能是实际往返时延的6倍甚至更多。原因在于SRTT估计的是较长一段时间内端到端往返时延的加权平均值，其更新速度远远无法跟上异构网络中传播时延的变化频率。错误的时延估计将会影响到拥塞控制算法、数据重传算法、数据分流算法的性能，从而间接影响了多路径并行传输系统的有效吞吐量。因此，对异构网络中各链路上的传播时延进行准确估计是提高多路径并行传输有效吞吐量的前提。

1.2 基于卡尔曼滤波的时延估计算法研究

卡尔曼滤波算法可以对离散系统的状态进行最优估计，该算法假设离散系统可表示成线性随机微分方程的形式

X(k)=AX(k-1)+BU(k-1)+W(k-1)

(2)

而系统状态的测量值可以描述为

Z(k)=HX(k)+V(k)

(3)

式(2)和式(3)中，X(k)、X(k-1)分别表示k、k-1时刻系统的状态，U(k-1)是k-1时刻系统的控制量。A、B均为系统的系数，若目标系统是多模型系统，则A和B是矩阵的形式。Z(k)是k时刻系统状态的测量值，H是测量系统的参数，若是多测量系统，则同理H是矩阵的形式。W(k-1)是系统过程的噪声，而V(k)表示测量的噪声，两者均为高斯白噪声，方差分别是Q和R。卡尔曼滤波器对于任何满足以上条件的系统来说都是最优的信息处理器，可以估算出系统的最优化输出。

本文利用卡尔曼滤波思想对端到端时延进行估计。从较长一段时间来看，多路径并行传输系统各条链路上的端到端传输时延是一个相对稳定的值，因此假设端到端传输时延是一个常量信号与一个高频变化的分量之和，该高频分量是一个高斯白噪声，则端到端时延可以用下面的式子表示

X(k)=X(k-1)+W(k-1)

(4)

Z(k)=X(k)+V(k)

(5)

其中，X(k)和Z(k)分别表示端到端时延的真实值和通过SACK报文测量得到的测量值。W(k)代表端到端时延的高频噪声分量，满足方差为Q的高斯分布，即W(k)～N(0,Q)。V(k)表示端到端时延测量值的噪声，满足方差为R的高斯分布，即V(k)～N(0,R)。

基于卡尔曼滤波的时延估计算法可以划分为两个不断循环的阶段：更新时延估计值(预测状态)和更新估计误差(修正状态)，两个阶段之间的状态转移过程如图1所示。

图1 基于卡尔曼滤波的端到端时延估计

卡尔曼滤波算法的两个阶段可以分别用以下两组公式描述：

更新时延估计值

X(k|k-1)=X(k-1|k-1)

(6)

P(k|k-1)=P(k-1|k-1)+Q

(7)

更新估计误差

(8)

X(k|k)=X(k|k-1)+Kg(k)(Z(k)-X(k|k-1))

(9)

P(k|k)=(1-Kg(k))P(k|k-1)

(10)

以上就是基于卡尔曼滤波的端到端时延估计算法的基本原理，在实际运用时，取最新的时延测量值作为时延估计初值X(0|0)，并输入估计误差的初值P(0|0)(可以取任意非零值)，算法就能够自动循环运行，完成对端到端时延的预测。根据式(6)可以得到当前时刻的时延先验估计值，该估计值被用于下节中的拥塞控制算法中。每当接收到一个SACK应答报文则对当前时延估计值进行修正，并计算得出时延的最优估计值，作为下一轮时延估计的依据。

2 基于时延差控制的拥塞控制算法

2.1 SCTP-CMT有效吞吐量分析

SCTP-CMT协议聚合不同的网络资源，并进行统一管理，从而达到聚合不同网络的可用带宽，提升业务QoS的目的[9,10]。然而，该协议并不适合于异构无线网络环境。在异构网络中，由于路径间的不对称性导致不同路径上的端到端传输时延差异巨大，在不同路径上并行传输的数据包将无法按照发送时的顺序有序地到达接收端，从而引起数据包乱序现象。只有当较小TSN的数据包全部到达后，才递交到上层应用，严重影响了网络吞吐量性能[11]。特别的，对于实时视频会议等对数据实时性要求较高的业务，即使最终数据包能够成功递交给上层应用，数据包内的数据也可能已经超过了有效期限而被应用丢弃，这将使得多路径并行传输系统的有效吞吐性能进一步恶化。

本文定义SCTP-CMT有效吞吐量为：单位时间内由传输层递交到应用层的数据包数量，即

(11)

下面将以一个最简单的、只具有两条并发路径的多路径传输场景为例进行分析，进一步说明不同路径间的时延差和SCTP-CMT系统有效吞吐量之间的关系。具体参数说明如下：

τi是指数据包在各链路上的发送间隔，其中i为链路编号(i=1,2)。

di是指路径i上的传播时延，且d1

Δd是指路径1和2的传播时延差，Δd=|d2-d1|。

T是指接收到一个完整的有序的数据块所经历的时间。

S是指在时间T内共接收到有序数据块的大小。

假设总共有4个传输序列号TSN连续的数据包等待发送，数据包的TSN分别为1、2、3和4。其中有3个数据包被分配到路径1上进行传输，剩下的一个数据包通过路径2传输。传输开始后，数据包1和数据包2分别由路径1与路径2发送出去，考虑以下两种情形：

(1)当Δd>τ1时，如图2(a)所示，当在路径2上发送的数据包到达接收端时，接收端才会将排序好的数据包递交到上层应用，此时接收该有序数据块所花费的时间T=Δd，故

(12)

(2)当Δd≤τ1时，数据包发送情况如图2(b)所示。由于SCTP规定接收端完整地接收到一个有序数据块后向发送端发送SACK应答报文，发送端接收到该报文后开始下一轮的数据发送，故这种情况下接收端接收到一个完整有序数据块所花费的时间可以近似地用路径2上的数据包发送间隔代替，故

(13)

图2 具有两条并发路径的多路径传输场景

通过上述分析比较得知，当两条路径的传输的时延差越大，接收端重排序的时间就越长，递交给上层应用就越慢，因此网络的有效吞吐量就越小。同时，若路径间时延差越大，传输过程中的数据包乱序越严重，增加了数据包的重排序时延，降低了传输的有效吞吐量。因此，我们可以通过在发送端对数据包发送速率进行调节，均衡不同路径上的负载，间接地调控并发路径间的最大时延差，减轻数据包乱序，提高多路径并行传输系统的吞吐量。

2.2 基于时延差控制的拥塞控制算法研究

在多路径并行传输过程中，可以通过调整发送端拥塞窗口的大小，将网络负载由高负载链路向低负载链路转移，减轻高负载链路的拥塞程度，从而减小不同链路上的最大时延差[12]。本文将根据这一结论对SCTP协议的拥塞控制算法进行改进。本文主要对拥塞控制部分的算法进行改进，保留了SCTP协议慢启动、拥塞避免和快速重传阶段的拥塞控制算法。

定义时延系数θ为通过卡尔曼滤波法获得的端到端时延估计值中最大值与最小值之比，即

(14)

在每次接收到SACK分组后，调用卡尔曼滤波算法进行新一轮的端到端时延估计，并根据最近时刻的时延先验估计值更新时延系数θ。定义两个阈值θ0和θmax，满足0<θ0<θmax。当θ>θ0时，表示当前不同路径上时延差距较大，有可能会导致数据乱序现象的发生；当θ>θmax表示当前路径时延差异非常大，传输过程中数据乱序现象严重，很有可能会导致接收端缓存阻塞。当时延系数θ大于θ0或θmax时，需要对发送端拥塞窗口进行调整。此时，发送端即使没有收到包含同一TSN丢失信息的SACK分组或数据包超时消息，也会根据时延系数θ的大小来调整最大传输时延路径的拥塞窗口。本算法的具体描述如下：

(1)使用卡尔曼滤波算法更新时延估计值后，本策略开始执行；

(2)根据最新的时延估计值，更新时延系数θ；

(3)若θ>θ0，查找当前传输时延估计值最大的路径Pi；否则，算法终止；

(4)若0<θ0<θmax，则将Pi上的拥塞窗口cwndi减小为

(15)

(5)若θ>θmax，则将Pi上的拥塞窗口cwndi减小为

(16)

(6)比较减小后的cwndi和该路径的慢启动阈值SSthreshi，如果cwndi

图3 基于时延差控制的拥塞控制算法伪代码

在本算法中，当θ0<θ<θmax和θ>θmax时，分别采取不同的拥塞窗口控制策略，原因在于：θ0<θ<θmax时，传输过程中可能会发生数据包乱序，但是并没有到达十分严重的地步，因此通过调整拥塞窗口的大小，有效避免了因拥塞窗口减小过快而引起的系统吞吐量性能大幅度下降；而θ>θmax时，由于很可能会引发接收端缓存阻塞，必须迅速减小发送端拥塞窗口的大小，以减慢数据包发送速率。此外，当调整后cwndi的值过小时，令SSthreshi=cwndi是为了保证执行完本算法后，链路依然处于拥塞避免阶段，以避免由于减小cwnd使链路处于慢启动阶段，从而cwnd将会快速增加并恢复到调整前的大小。

在执行完上述算法之后，端到端时延最大的路径上的拥塞窗口cwnd将会被减小，导致减小后的cwnd值加上目前已经收到SACK确认的最大TSN序列号之和小于已经被发送出去的最大TSN，这将使得该路径上发生暂时性的阻塞，无法发送新的数据包。设阻塞的时长为ΔT，则最坏情况下ΔT的大小可以通过式(17)进行计算

ΔT=(cwndi-cwndi/θ)×τi

(17)

例如，θ=4，τi=2 ms，cwndi=100，则ΔT的值为150ms。经过150ms后，该路径将结束暂时性阻塞，重新开始发送数据包。虽然在该时间段内时延最大的路径会暂时性的阻塞，然而整个多路径传输的有效吞吐量将得到大幅度的提高，对于整个多路径并行传输系统来说总体上的传输性能还是获得了提高的。

在上述算法中，θ0和θmax这两个阈值的选择会对算法性能带来重要的影响，如果阈值选择过大，会使得算法执行的频率跟不上时延差的变化速度，导致路径端到端时延差变大时得不到及时的调控，算法达不到预期的效果；如果阈值选择过小，会使得拥塞窗口cwnd在短时间内频繁变化，提高了链路的抖动性。阈值θ0定义为当θ>θ0时，表示当前不同路径上时延差距较大，有可能会导致数据乱序现象的发生，记d(i)为数据包i在网络传输过程中经历的传播时延；T(i)为数据包i离开发送端的时刻，T(i)=R(i)+S(i)，其中R(i)为数据包i到达发送端的时刻，S(i)为数据包i经历的发送时延；记ΔT(i)为数据包i-1与数据包i离开发送端的时间间隔由式(18)得知，在多路径并行传输系统中，数据包i有序传输需要满足数据包i与i-1在发送端的发送间隔大于等于所有并发路径上的最大传输时延差，如式(19)所示

d(i)≥d(i-1)-(T(i)-T(i-1))=d(i-1)-ΔT(i)

(18)

ΔT(i)≥dmax-dmin

(19)

由于数据包i的发送路径与所采用的数据分流策略有关，因此为了保证满足数据包有序传输约束条件，要求所有路径上的发送间隔都要满足式(18)，因此有

(20)

而阈值θmax的定义是，当θ>θmax表示当前路径时延差异非常大，传输过程中数据乱序现象严重，很有可能会导致接收端缓存阻塞，因此将接收端的缓冲区大小作为θmax计算的参考标准，记接收端缓冲区中能够容纳的数据包个数为NBuffer，通过式(21)可以计算出θmax

(21)

3 仿真实验分析

3.1 仿真环境及参数设置

仿真实验的拓扑设置采用异构无线网络中常见的两种链路：HSDPA链路和WLAN链路。具体网络拓扑如图4所示，其中并发链路1模拟的是高速下行链路分组接入网(highspeeddownlinkpackagesaccess，HSDPA)，而并发链路2模拟的是无线局域网(wirelesslocalareanetwork，WLAN)，WLAN链路的平均时延、丢包率和带宽分别为40ms、2.7%和3Mbps；HSDPA分别为80ms、0.8%和1Mbps。发送端和接收端均有两个接口，分别接入HSDPA和WLAN网络中进行并行传输。R1、R2、R3和R4为4个路由器。瓶颈链路的队列长度设定为50个数据包，链路的排队模型为DropTail。

图4 仿真拓扑结构

应用层协议使用FTP协议，且选择一个足够大的文本作为输入流，仿真时长设定为30s。发送端每次接收到SACK应答报文后，使用本文提出的基于卡尔曼滤波的端到端时延估计算法，对各条传输路径上的端到端时延估计值进行更新。然后，使用基于时延差控制的拥塞控制算法计算出当前时刻的时延系数θ，当θ的值过大时，对时延最大的链路上的拥塞控制窗口cwnd进行调整。卡尔曼滤波算法中的参数设置为：Q=1，R=0.8，P0=1；数据包到达率设置为150 Packet/s，接收缓存大小为64 KB，SACK时延设置为200 ms，其它参数设置为默认值。仿真过程中，每0.1 s记录一次两条链路上的传播时延以及它们之间的时延差。每收到50个连续TSN数据包时，计算一次吞吐量，并记录当前缓冲区占用情况。每当接收端收到50个具有连续TSN的数据包时，计算一次有效吞吐量，并记录下当前接收缓存的占用情况。

3.2 仿真结果分析

本文利用接收缓存的大小来表示当获得K个连续传输序列号的数据包时所需要的存储大小，该值与接收到的数据包乱序程度成正比。仿真结果如图5和图6所示，图5是为SCTP-CMT、CMT-PF与本文提出的SCTP-CDD接收端缓存占用情况的比较，图6是三者有效吞吐量的对比。

图5 接收端缓存占用情况对比

图6 有效吞吐量对比

从图5中可以看出，在整个传输过程中，3种算法都只有在极少数时刻接收端缓存中是空的，在其余时刻接收端缓存中都存在乱序分组，这说明数据乱序现象时无法完全消除的，只能通过对协议的优化尽可能地减少数据乱序现象的发生。SCTP-CMT和CMT-PF在传输过程中，大部分时候接收端缓存中都存放有5个到8个的乱序数据包，最多时甚至会存放有10个乱序的数据包，可以看出，由于异构网络中链路的不对称性，导致这两种算法存在明显的数据乱序现象。相对的，本文所提出的SCTP-CDD算法的缓存占用情况要明显优于另外两种算法。使用SCTP-CDD算法时，接收端缓存的占用率有了明显的降低，大部分时候接收端缓存中只有一个，最多时也不超过3个乱序的数据包，说明数据包在达到接收端后都能够及时地提交给上层应用程序进行处理。可见，使用SCTP-CDD进行多路径并行传输能够大大减轻数据包乱序现象。

从图6中可以看出，在异构网络环境下，SCTP-CMT和CMT-PF的聚合吞吐量较低，大部分时候维持在1.5 Mbps到2.5 Mbps之间，在某些时刻甚至仅仅等于慢路径(HSDPA，1 Mbps)的带宽；而本文所提出的SCTP-CDD的有效吞吐量相比另外两种算法有了明显的提高，大部分时候的有效吞吐量都保持在3 Mbps以上，且有效吞吐量的抖动范围有了明显减小。仿真结果说明SCTP-CDD能够充分利用异构网络的带宽资源，发挥出多路径并行传输的聚合不同链路带宽的优势。

4 结束语

针对因为数据包乱序导致的多路径并行传输系统性能下降的问题，提出了一种多路径并行传输有效吞吐量优化算法SCTP-CDD，该算法通过卡尔曼滤波法对多路径并行传输中各条路径上的传输时延进行估计，然后根据时延估计值对拥塞窗口cwnd进行调整，以平衡各条路径的负载，减小并发路径间的最大时延差，从而达到减少数据包乱序，提高有效吞吐量的目的。NS-2仿真实验表明，所提优化算法能够有效减小并发路径间的最大时延差，减少乱序数据包的数量，优化多路径并行传输系统的有效吞吐量。

[1]Raiciu C,Paasch C,Barre S,et al.How hard can it be?Designing and implementing a deployable multipath TCP[C]//NSDI San José,2012.

[2]Sharma V,Kar K,Ramakrishnan KK,et al.A transport protocol to exploit multipath diversity in wireless networks[J].IEEE/ACM Transactions on Networking,2012,20(4):1024-1039.

[3]Changqiao Xu,Tianjiao Liu,Jianfeng Guan,et al.CMT-QA:Quality-aware adaptive concurrent multipath data transfer

in heterogeneous wireless networks[J].IEEE Transactions on Mobile Computing,2013,12(11):2193-2205.

[4]Wen Li,Wenbo Wang,Xiaojun Jing,et al.Kalman filter based bandwidth and round trip time estimation for concurrent multipath transfer performance optimization in SCTP[C]//Proccedings of the 4th International Conference on Computer Engineering and Networks,2014:1225-1233.

[5]LI Wen,WANG Wenbo,JING Xiaojun,et al.CMT performance optimization algorithm based on union prediction of bandwidth and round trip time[J].Journal of Beijing University of Posts and Telecommunications,2015,37(1):133-142(in Chinese).[李文,王文博,景晓军,等.基于带宽与往返时延联合预测的多路径并行传输性能优化算法[J].工程科学学报,2015,37(1):133-142.]

[6]Zhang X,Nguyen TMT,Pujolle G.Kalman filter based band-width estimation and predictive flow distribution for concurrent multipath transfer in wireless networks[C]//Proceedings of the 3th IEEE International Conference on Network Infrastructure and Digital Content,2012.

[7]Sarwar G,Boreli R,Lochin E,et al.Performance evaluation of multipath transport protocol in heterogeneous network environments[C]//International Symposium on Communications and Information Technologies.Gold Coast:IEEE,2012:985-990.

[8]Zhou D,Song W,Shi M.Goodput improvement for multipath TCP by congestion window adaptation in multi-radio devices[C]//IEEE Consumer Communications and Networking Conference.IEEE,2013:508-514.

[9]Du WF,Wu Z,Lai LQ.Delay-sensitive data allocation scheme for CMT over diversity paths[J].Journal of China Institute of Communication,2013,34(4):149-157.

[10]DU Wenfeng,LAI Liqian,WU Zhen.Transmission delay prediction based data allocation scheme for concurrent multipath transfer[J].Journal of Software,2015,26(8):2041-2055(in Chinese).[杜文峰,赖力潜,吴真.基于传输时延预测的多路径并发传输数据分配算法[J].软件学报,2015,26(8):2041-2055.]

[11]Leung KC,Lai C,Li VOK,et al.A packet-reordering solution to wireless losses in transmission control protocol[J].Wireless Networks,2013,19(7):1577-1593.

[12]Xu CQ,Liu TJ,Guan JF,et al.CMT-QA:Quality-aware adaptive concurrent multipath data transfer in heterogeneous wireless networks[J].IEEE Transactions on Mobile Computing,2013,12(11):2193-2205.