面向异构网络的多路径数据重传研究∗

戴卓臣 陆江东

（第二军医大学 上海 200433）

1 引言

随着互联网和相关技术的快速发展，网络终端可使用的接入技术越来越多，如3G、4G、WIFI、蓝牙等［1～3］。多路径并行传输（CMT）就是在这样的环境下发展而来。现有研究成果多集中在数据包重传策略、数据包丢失恢复及数据包的路径选择上［4］。现有重传算法可以分为单一因素考虑重传以及多因素考虑重传。单一因素重传主要包含五种经典的基本重传算法，对丢包率、拥塞窗口大小、时延等单一因素进行判断［5］，来选择重传路径。还有相关学者综合多种因素考虑重传，并设计出TRX-CLS重传算法［6］。该算法分别对 largest cwnd、largest ssthresh、lowest rate path依次判断，选出最合适的重传信道。现有研究成果都是基于现有路径网络态进行决策，并没有涉及异构网络状态［7-9］。而异构网络状态在重传路径的选择决策上起到非常重要的作用。RTX-LR重传策略基于最小丢包率、最小超时记录吋间、最小重传间隔确定重传信道［10］。但是仍然存在不足，该算法首先对活跃路径中的丢包率进行判断，选择丢包率小的路径，但是丢包率小并不能保证数据包一定能尽快到达接收端。此外，当现有的网络信息不足以选择重传路径时，RTX-LR重传算法会对路径的异构信息进行判断，选择异构记录良好的那条［11］。然而，作为一个异构记录指标，最小的超时时间也并不能保证数据包最快到达接收端，只能表明曾经最优。同时，在多变的异构网络环境下，该算法不能很好地适应路径性能发生突变的情况，因此本文在该算法的基础之上，做进一步的改进研究。

2 数据重传

2.1 异构网络环境

在异构网络环境下进行并行传输，应该首先保证重传数据包能尽快到达接收端，以减少接收端缓冲区阻塞。由于RTX_LR重传算法在考虑重传时采用的是异构最小超时时间［12］，但是只能表明该条链路曾经具有最小的超时时间，因此并不能保证数据包一定最快到达接收端［13］。假设某条路径Pi最开始有最小的超时重传时间，但是后来超时严重，因此在这种场景下，还是选择原路径Pi作为重传路径，显然是不合理的。

具体如图1所示，假设发端和接收端有3条可用路径，调度模块按照调度策略将数据块按序依次分发到这3条路径上。图中灰色标识的数据包表示在传输过程中发生了丢包，并需要对该数据包进行重传，重传时间在图中已经被标识。按照RTX_LR重传算法，当丢包率相同时，该算法会选择异构最小的重传时延的路径B进行重传，图中可知选择路径B进行重传是不合理的。因此本文提出了面向异构网络的多路径数据重传算法。该算法将对最小重传时延、min｛max｛路径重传超时时间｝｝、最小丢包率依次进行判断，最终确定要选择的重传路径。

图1 RTX_LR重传算法不足示意图

2.2 重传模型建立

根据异构网络环境下多路径并行传输中重传算法的设计原则，即保证重传的数据包快速准确地到达接收端，避免接收端缓存阻塞，以提高重传效率［14］。本文提出的MDRA算法，首先对丢包类型进行判断，若是快重传，则在源路径上进行重传即可。若为超时重传，则需要选择其他路径进行重传。首先扫描除源路径之外的活跃路径，若无，则从源路径上重传［15］，若存在，则先计算各活跃路径的重传时延期望值，然后选择最具有最小期望值的路径作为重传路径，如果当前路径不唯一，则判断这些路径的max｛路径重传时间｝，选择最小的作为重传路径。若仍然无法判断，则选择路径丢包率小的作为重传路径。如果仍然不唯一，则在其中随机选择一条作为重传路径，算法结束。

数据包超时重传时间的计算与丢包率 p、端到端时延RTTs/2、超时计时器设定的超时重传时间t，其值为RTO以及重传次数有关。为了便于分析，假设数据包在重传期间没有发生拥塞。那么，数据包经过一次重传后，能成功到达接收端的概率为1-p［16］。设Ti为经过i次超时重传到达接收端并确认的时间。那么，第一次超时重传到达接收端的时间满足：

同理可知，经过两次超时重传和三次超时重传到达接收端所需要的时间为

假设最大超时重传次数为3，超过3次就不再对该数据包进行重传。因此，数据包成功到达接收端的期望值为

其中，pi为第i次超时重传后，数据包成功到达接收端的概率，可以得到：

将式（5）代入式（4），可以得出每条路径传输该数据包的重传时延期望值。然后进行比较，选出期望值最小的路径作为重传路径。同时，MDRA算法将会为每条路径做一个记录，这个记录存储着该路径从建立开始到现在，数据块的最大超时重传时间tmax。若多条路径具有最小重传期望，则从中选择具有最小的tmax作为重传路径，若仍然无法判断，则对丢包率进行判断，仍然无法判断的则从其中随机选择一条。

2.3 算法流程及伪代码

算法步骤具体如下：

Step1：发端发现数据包丢失，首先判断重传类别，若是快重传，则在源路径上重传，进入Step6，否则，进入Step2；

Step2：扫描路径，计算各路径的超时重传期望值，选择期望值最小的路径作为重传路径；

Step3：若具有最小超时重传期望值的路径不唯一，则从中选择具有min{tmax}的路径作为重传路径；

Step4：若选择出的min{tmax}路径仍然不唯一，则从中选择具有最小丢包率的路径进行重传；

Step5：若所选的路径最小丢包率仍然无法判断，则在其中随机选择一条路径作为重传路径；

Step6：算法结束。

MDRA重传算法具体设计如图2所示。

图2 MDRA重传算法

MDRA重传算法伪代码如下：

3 实验仿真

3.1 实验环境

仿真试验的具体网络拓扑如图3所示，发送端和接收端均有两个接口，分别接入两个网络中进行并行传输，这两条链路的具体参数如表1所示。

图3 MDRA重传算法仿真拓扑结构

表1 链路参数设置

这样设置的目的是，对于重传算法而言，丢包率占有非常重要的作用，为了分析丢包率对重传算法的影响，故仿真中一条路径的丢包率为固定值1%，而另一条路径丢包率从1%～10%逐步增加，递增间隔设置为0.01。通过这种仿真场景，就可以分析出丢包率差异对重传算法的影响。R1、R2、R3和R4为四个路由器。瓶颈链路的队列长度设定为100个数据包，链路的排队模型为DropTail。应用层协议使用FTP协议，为了评估协议在较长的一段时间内的有效吞吐量性能，仿真中使用FTP协议传输一个足够大的文件来模拟数据传输的过程，仿真时长设定为100s。

3.2 结果分析

根据上述的拓扑结构，本文得出如下的仿真结果，如图4～6所示，分别展示了不同接收缓存RB（Receive Buffer）下，三种重传算法的性能趋势。其中，MDRA算法是指本文所提出的基于记录的综合参数算法设计；RTX_LR是基于最小丢包率、最小超时重传时间、最小重传间隔来确定重传路径；RTX_LOSSRATE是基于最小丢包率的经典重传算法，其思想是选择丢包率最小的路径作为重传路径。RB=128KB下的仿真结果如图4所示。

图4 当RB=128KB时吞吐量对比图

图4中，可以看出本文提出的算法明显优于其他两种重传算法，大概高出5.5%左右。并且还可以得出，随着路径2丢包率的提高，两条链路的差异性也随之变大，网络整体吞吐量性能趋势不断下降，但利用本文提出的MDRA算法比其他两种重传算法可以获得更好的吞吐量。RB=64KB下的仿真结果如图5所示。

图5 当RB=64KB时吞吐量对比图

从图5可以看出，接收端缓存减小对吞吐量性能非常明显。因为差异化的路径在并行传输时，会造成接收端数据的乱序，已接收的乱序数据会暂存在接收端缓存当中，等待乱序数据包的到达，因此在缓存受限的情况下，若超时重传的数据包迟迟不能到达接收端，势必会导致接收端缓存阻塞，严重影响路径的传输性能。同时从图5中看出，当RB减小时，三种算法的吞吐量均有所减少，但本文提出的算法相较于其他两种算法，吞吐量性能提高了7.5%左右。RB=64KB下的仿真结果如图6所示。

图6 RB=32KB时吞吐量对比图

类似地，图6中吞吐量的仿真结果，可知，本文提出的算法明显高于其他两种算法，性能提高9%左右。由此可知，当RB越小，则MDRA算法所带来的性能提升越明显。

为了更加清楚地论证本文所提算法的优越性，本文将对三种重传算法在三种不同的RB下的平均吞吐量进行比较。平均吞吐量是指在一定丢包率范围内的平均吞吐量。基于以上的仿真结果，本文丢包率的取值范围为1%～10%。具体统计结果如表2所示。

从表2可以看出，在不同的接收端缓存下，MDRA算法的平均吞吐量性能均优于其他两种算法，并且可以得出当RB=128KB时，MDRA算法的平均吞吐量比RTX_LR高了大概2.5%；当RB=64KB时，提高了约8%；当RB=32KB时，提高了约为12%。因此，可以得知，RB越小，则MDRA算法表现越优秀。

表2 三种重传算法平均吞吐量

为了找到吞吐量性能提高的原因，本文对接收端乱序数据包的个数做了统计。依然利用图3仿真拓扑结果，RB设置为64KB，仿真时间为30s，应用层依然采用FTP文本。链路1、2的丢包率采保留原来的设置。得到仿真结果如图7所示。

图7 三种重传算法乱序包个数比较

从图7中可知，接收端乱序数据包个数随着丢包率增大而增大。但本文MDRA算法相较于其他两种算法，乱序包个数有明显的减少。由此可知，MDRA算法可以有效减少接收端乱序数据包的个数，最终提升网络的吞吐量性能。

4 结语

针对本文以吞吐量性能为目标，对差异化网络环境下数据重传策略进行了分析研究，并提出了基于记录的综合参数数据重传算法，该算法分别对最小超时重传时延、min｛max｛路径重传时间｝｝、最小丢包率依次进行判断，最终确定要选择的重传路径。保证了重传数据包最快地到达接收端，降低接收端缓存阻塞，提高多路径传输系统整体吞吐性能。通过NS-2仿真实验证明，在异构网络环境下，相较于默认的重传算法，本文所提出的基于综合参数重传算法可以有效提高重传效率，减少接收端缓存阻塞，一定程度上提高了网络的吞吐性能。