基于BPNN端到端时延预测的多路传输调度
2022-02-15苏旭东衷璐洁
苏旭东,衷璐洁
(首都师范大学 信息工程学院,北京 100048)
0 引 言
MPTCP(MultiPath TCP)是一种基于多接口的传输控制协议,允许在多条链路同时传输数据,旨在提高吞吐量的同时更充分地利用网络资源。在移动网络环境下,带宽、延迟、丢包率等网络参数动态变化,终端的移动性会引发网络链路间的频繁切换,造成数据包不能按序到达接收端,引起数据包乱序问题。乱序数据包在接收端缓冲区滞留等待,严重时会导致接收端缓存阻塞,造成网络延迟,降低网络吞吐量。在该问题背景下,如何针对移动异构网络特点,减少数据包乱序发生可能,实现高效移动多路传输调度具有重要意义。对此,本文提出一种基于BP神经网络(back propagation neural network,BPNN)端到端(传输)时延预测的移动多路传输调度方法,综合考虑链路丢包率、RTT、吞吐量等性能参数,通过BP神经网络的训练与学习,提取输入性能参数与端到端时延间的有效规则,在更准确预测端到端时延的基础上,对路径拥塞状况进行计算评估,并基于路径综合评估结果实施数据包调度,以使数据包尽可能按序到达接收端,进而有效避免缓冲区阻塞,实现负载均衡,提高多路传输网络吞吐量。
1 相关工作
MPTCP数据调度:Ke等[1]利用自定义的排序算法对路径状态信息进行排序,之后基于排序结果实现数据包的传输。黄辉等[2]提出一种将RTT与丢包率相结合,运用综合效用函数作为评估指标的数据调度机制。Luo等[3]提出一种基于强化学习DQN的数据调度算法,通过强化模型完成路径的选择判断,并借助路径奖惩值计算实现路径选择的更新。
基于端到端时延的调度:Xue等[4]通过计算在接收端不发生乱序的前提下应为每条路径分配的数据包个数,为各路径分配DSN连续的数据包。王振朝等[5]利用路径带宽、往返时延和拥塞窗口预测数据包到达时间,并以此为基础完成数据包的分发。Dong等[6]根据子流是否丢包对端到端时延采用不同的计算方法进行估算。Froemmgen等[7]通过主动探测未使用的子流并根据传统TCP时间戳选项得到的端到端时延来调度数据包。
数据包乱序减少:Han等[8]通过预测数据包到达时间,将数据包调度到最早到达时间的子流上,以保证数据包到达的顺序。Shi等[9]选择慢路径发送序列号较大的数据包。Kim等[10]通过估算无序数据包数量及传输所需的缓冲区大小来减少数据包乱序的发生可能。Ling等[11]对路径阻塞时延进行评估,选择不易造成阻塞的子流集进行数据传输。
2 基于BP神经网络端到端时延预测的多路传输调度
基于BP神经网络端到端时延预测的多路传输调度(multipath scheduling based on BP neural network EET prediction,MSBPEET)通过综合考虑丢包率、吞吐量、RTT等路径性能参数,构建BP神经网络对数据包在各路径上的端到端时延实施预测,随后选择时延小且拥塞状况良好的路径进行传输,以使数据包在尽可能短的时间内按顺序到达接收端。方法总体框架如图1所示,包括:(Ⅰ)RTT预测;(Ⅱ)基于BP神经网络的端到端时延预测;(Ⅲ)子流拥塞状况评估;(Ⅳ)网络状态综合评估及有效路径集排序调度4个部分。其中:RTT预测部分将RTT及RTT高频变化分别建模为常量信号和噪声,然后结合卡尔曼滤波,对当前RTT测量值进行评估和纠正;基于BP神经网络的端到端时延预测部分主要通过BP神经网络的构建、训练和学习完成对端到端时延的更准确预测;子流拥塞状况评估部分主要完成对各个子流的拥塞状况评估;网络状态综合评估及有效路径集排序调度部分主要负责在对路径完成综合评估后,选择最优路径进行数据包调度。
图1 基于BP神经网络端到端时延预测的多路传输调度
2.1 RTT预测
RTT是路径质量评估的重要参数。在本文中,RTT作为BP神经网络的输入,其预测准确性将直接影响端到端时延预测的准确性。在路径参数高度动态变化的移动无线网络环境下,为进一步提高RTT预测的准确性,本文采用卡尔曼滤波方法,利用前一时刻的RTT与当前时刻RTT的测量值来更新对RTT的预测估计,进而获得当前时刻RTT更准确的估计值。
首先将RTT及RTT高频变化分别建模为常量信号及噪声,如式(1)和式(2)所示
RTTk=RTTk-1+wk
(1)
RTT′k=RTTk+vk
(2)
其中,RTTk和RTTk-1分别表示当前时刻k和上一时刻k-1的RTT;wk表示过程噪声,服从高斯分布;RTT′k表示当前时刻RTT的测量值;vk是测量噪声,服从高斯分布。RTT卡尔曼滤波预测过程如下:
(1)初始化测量噪声R、 过程噪声Q和误差协方差P;
(2)对任一MPTCP子流j,若子流j收到ACK或发生超时,获取子流j当前时刻RTT测量值RTTk及上一时刻最优RTT估计值RTT(k-1|k-1)。 初次预测时,将子流j上一时刻的RTT测量值RTTk-1视作上一时刻的最优RTT估计值,然后转步骤(3)~步骤(7)。
时间更新阶段:
(3)计算当前时刻RTT的预测值,记作RTT(k|k-1), 如式(3)所示
RTT(k|k-1)=RTT(k-1|k-1)
(3)
(4)计算当前时刻误差协方差的预测值,记作P(k|k-1), 如式(4)所示
P(k|k-1)=P(k-1|k-1)+Q
(4)
其中,P(k-1|k-1) 为上一时刻误差估计协方差;Q为过程噪声,服从高斯分布。
评估更新阶段:
(5)根据当前时刻误差估计协方差更新卡尔曼增益Kk, 如式(5)所示
Kk=P(k|k-1)(P(k|k-1)+R)-1
(5)
其中,R为测量噪声,服从高斯分布。
(6)根据卡尔曼增益Kk和当前时刻RTT预测值RTT(k|k-1) 及当前时刻RTT测量值RTTk计算当前时刻最优RTT估计值,如式(6)所示
RTT(k|k)=RTT(k|k-1)+Kk(RTTk-RTT(k|k-1)
(6)
(7)根据当前时刻误差估计协方差P(k|k-1) 和卡尔曼增益Kk更新误差估计协方差P(k|k), 如式(7)所示
P(k|k)=(1-Kk)P(k|k-1)
(7)
(8)最终输出经卡尔曼滤波处理后的RTT(k|k), 即为子流j当前时刻的最优RTT估计值,将其作为端到端时延预测BP神经网络的输入之一。
2.2 基于BP神经网络的端到端时延预测
端到端时延预测的准确性对减少数据包乱序发生具有重要的指导意义。影响链路端到端时延的主要因素包括链路丢包率、吞吐量、RTT等,为实现端到端时延的更准确预测,本文提出构建服务于端到端时延预测的BP神经网络模型,以RTT、丢包率、吞吐量等端到端时延特征参数为输入,端到端时延为期望输出,对设计的多层BP神经网络实施训练,使其通过训练和学习,提高端到端时延预测的准确性。
基于BP神经网络的端到端时延预测主要分为BP神经网络端到端时延预测模型构建和端到端时延预测两部分。其中模型构建部分主要负责构建基于BP神经网络的端到端时延预测模型,通过实验收集的数据样本集对设计的多层BP神经网络模型进行训练,并实施优化,提高端到端时延预测的准确性。
模型构建部分主要由样本数据获取、BP神经网络构建与训练和训练优化3个部分组成。图2给出了这3个部分的组成示意。当应用层有数据传输需求时,端到端时延预测部分将在BP神经网络端到端时延预测模型的基础上,以链路丢包率、吞吐量、RTT等参数为输入,获得链路端到端时延的预测输出。
图2 基于BP神经网络的端到端时延预测模型
2.2.1 样本数据获取
(1)计算、获取丢包率Loss、 吞吐量Th及RTT。 其中RTT由RTT预测部分获取,丢包率Loss、 吞吐量Th的计算方法如式(8)和式(9)所示
(8)
(9)
其中,Cwndpre表示拥塞窗口收缩之前的值,Cwnd表示当前时刻的拥塞窗口值。
(2)计算端到端传输时延EET, 计算方法如式(10)所示[12]
EET=Tr-Ts-Te
(10)
在式(10)中,Tr表示接收端发送SACK的时间;Ts表示发送端发送数据包的时间;Te表示接收端从接收到数据包到发送SACK的间隔时间。
(3)对训练数据和测试数据进行划分。为避免过拟合问题,将经由(1)获取到的样本集划分为训练集和测试集,并设置训练集占比85%,验证集占比15%。考虑到不同维度间的样本数据差距及同维度样本数据间的相差范围,在训练前采用Min-max方法[13]对数据进行归一化处理,将数据映射至区间[-1,1],以减少数据波动对神经网络训练时间及收敛效果的影响。
2.2.2 BP神经网络构建与训练
(1)设置权重、阈值、学习速率、训练最大迭次数等相关参数。初始化权重和阈值在[-1,1]之间。对于学习速率,从较大学习速率开始训练,然后逐渐减小速率,直至损失值不再发散。训练最大迭代次数设置为50 000。在多次试算的基础上,兼顾网络稳定性及训练时长考虑,具体参数设置见表1。
表1 参数设置
(2)输入、输出层神经元个数选择。输入层神经元分别为Th、RTT、Loss,输出层神经元为EET。相应地,输入层神经元个数I设为3,输出层神经元个数J设为1。
(3)隐含层层数和节点数设置。通过获取的样本集,对设置不同隐含层数和节点数的BP神经网络进行训练测试,根据不同神经元个数训练的均方误差来确定隐含层层数和节点数。隐含层节点个数K参考式(11)及测试结果综合选定
(11)
在式(11)中,J为输出层节点个数,I为输入层节点个数,a为1~10间的常数。
(4)随机选取第m个输入样本及其对应的期望输出,将输入样本作为正向传播输入,其中第m个输入样本如式(12)所示,其对应的期望输出如式(13)所示
xi(m)=(Th(m),Loss(m),RTT(m))
(12)
H(m)=EET(m)
(13)
(5)判断训练样本是否用尽,若否,转步骤(6)~步骤(7);否则转步骤(8)。
(6)前向计算各p隐含层及输出层神经元的输入和输出。
1)输入层神经元Th、RTT、Loss计算隐含层输出值Dk(m), 计算方法如式(14)~式(16)所示,其中k表示隐含层节点;i表示输入层节点;I为输入层节点数;xi(m) 表示输入层输入;oi(m) 表示输入层输出;wik表示输入层到隐含层的神经元权值;dk(m) 表示隐含层输入;Bk表示输入层到隐含层的阈值;f为输入层和隐含层激活函数,为正切S形函数(tansig)
oi(m)=f(xi(m))
(14)
(15)
Dk(m)=f(dk(m))
(16)
2)将隐含层神经元的输出值传递给输出层
(17)
Y(m)=g(y(m))
(18)
在式(17)和式(18)中,k表示隐含层节点;K为隐含层节点数;wk表示隐含层到输出层的神经元权值;B表示隐含层到输出层的阈值;y(m) 为输出层输入;Y(m) 为输出层输出。g为输出层激活函数,为线性函数。
(7)误差反向传播,调整连接权值和阈值。计算神经网络输出Y(m) 与期望值H(m) 之间的误差,如式(19)所示
(19)
之后运用梯度下降法,通过反向传播不断调整各层神经元的权值和阈值,使误差函数沿着负梯度方向下降,输出值不断接近实际值。
(8)计算网络全局误差,如式(20)所示
(20)
其中,M代表样本数,H(m),Y(m) 分别代表第m个样本的神经网络输出与期望值。
(9)判断网络全局误差是否满足要求,若满足,预测过程结束;否则查看是否达到设定的迭代次数上限,若已达到,预测过程结束,否则转步骤(4)~步骤(7)。
2.2.3 训练优化
针对权值在学习过程中发生震荡、收敛速度慢等问题,使用动量BP和学习速率可变的BP方法,不断调整各层神经元的权值和阈值,以减小误差,提高BP神经网络的收敛速度。