廖彬彬 张广兴 刁祖龙 谢高岗
(∗中国科学院计算技术研究所 北京100190)
(∗∗中国科学院大学 北京100190)
(∗∗∗中国科学院计算机网络信息中心 北京100190)
多路径传输控制协议[1](multi-path transport control protocol,MPTCP)自2013 年由互联网工程任务组(Internet Engineering Task Force,IETF)标准化以来,已经受到了工业界和学术界的广泛关注和研究。由于其固有的多链路带宽聚合能力和单链路故障恢复能力,MPTCP 已经被应用于加速众多的数据交互场景(如文件传输、Web 浏览和视频推流等)。尤其在移动互联网的背景下,内核装载MPTCP 的移动设备可以同时利用WiFi和蜂窝无线网络来提高移动应用程序的网络服务健壮性和传输质量保障[2]。
影响MPTCP 整体性能的一个重要因素是其数据包调度程序的设计和实现,它需要根据特定的策略在有效的传输控制协议(transport control protocol,TCP)子流上分配合适的数据包数量。已有的研究表明,错误的数据包调度决策将会导致MPTCP 严重的性能问题[3-4]。尤其在多变的无线网络环境中,由于TCP 子流的状态特别容易遭受网络拥塞和数据包随机丢失的影响[5],MPTCP 连接上的多条TCP子流之间的性能差异变得十分巨大。而这种网络的异构性主要表现为分发到较快子流上的数据包必须等待较慢子流上的数据包,这便造成了发送端数据的队头阻塞现象(head-of-line blocking,HoL)和接收端的数据包的乱序队列问题(out-of-order queue size,OQS)。因此,如何最小化接收端的数据包OQS 成为提升MPTCP 整体性能的关键[6-7]。
实际上,当MPTCP 所有的子流都相对正常或异构性不太明显时,设计一个合理的数据包调度器便能够实现多子流的正常传输,并缓解MPTCP 的队头阻塞与乱序问题。然而,如果存在某些TCP 子流在网络质量上具有很高的多样性时(如剧烈的丢包损耗、网络拥塞或延迟抖动等),仅依靠调度器是无法适应这种异构网络的剧烈变化,并实现数据包的快速恢复的。而使用网络编码的方法可以根据TCP子流的网络状态实现超时或丢包的0-RTT 快速恢复[8]。因此,在进行数据包调度之前增加一个网络编码的过程[9-10],可以使得MPTCP 不仅能够在相对稳定的网络环境中获得可观的性能提升,而且还能快速地适应网络的剧烈变化。
然而,基于网络编码的数据包调度系统将主要面临如下两个挑战。首先数据包的编码率需要随着MPTCP 所有TCP 子流网络状态的相对变化而改变,例如,当所有的子流都比较稳定时使用较低的编码率,而当部分子流出现明显的拥塞或丢包时则需要提升数据包的编码率。其次,数据包调度器也需要通过衡量所有TCP 子流的相对差异来确定分配编码后的数据包到每条子流的数量。也就是说,无论是网络编码器还是数据包调度器都需要根据所有TCP 子流的网络状态来决定其采取的动作。然而,决定TCP 子流状态的因素众多(如丢包率、拥塞窗口、时延抖动等),这将导致MPTCP 多TCP 子流组成的状态空间十分巨大。而且这些因素随着时间的变化可能是线性的也可能是非线性的,甚至可能不符合任何数学分布规律。因此基于数学建模的方法来人工拟合一个函数模型以匹配MPTCP 的子流状态到其对应的全局最优编码和调度动作几乎是不可能的。
近年来,由于不用假设状态空间的分布情况,使用深度神经网络作为函数的估计器来拟合高维度状态空间到连续动作空间的匹配关系已经变得十分常见[11-12]。尤其在众多复杂多变的计算机网络环境中(如数据包分类[13]、自适应比特率流[14]和数据中心流调度[15]等),基于深度神经网络的强化学习方法(deep reinforcement learning,DRL)已经取得了令人惊讶的效果。受到这些实例的启发,本文尝试训练一个深度增强的MPTCP 动态编码调度系统动态多路径编码调度器(dynamic multi-path encoding scheduler,DMES),来自适应MPTCP 多子流异构网络环境下的状态变化,并将MPTCP 的多子流实时状态输入转化为当前状态下的数据包编码比率和分配比率,从而最大化接收端的OQS 定义的反馈函数。最后通过梯度下降的方法训练DMES 的深度神经网络直到收敛。实验结果表明,在剧烈异构的动态网络环境中,DMES 将接收端的OQS 降低到24.6%以上,并且能够在平均有效吞吐量提升18.3%的同时将MPTCP 的应用延迟降低12.2%左右。
本文共分为5 节,其中第1 节为引言部分,对本文研究背景和主要研究内容进行介绍;第2 节为相关工作,主要介绍已有的MPTCP 数据包调度方法、网络编码技术以及深度强化学习方法;第3 节首先分析已有方法的不足之处,然后提出基于深度强化学习的MPTCP 动态网络编码调度系统;第4 节介绍了实验布置及说明,并给出了对应的实验结果;第5节对本文主要成果和未来工作进行总结和说明。
在现有的多路径传输系统中,网络的异构性是其数据包调度程序设计的难点。因为在性能差异较大的多条路径之间传输数据将不可避免地导致OQS 问题。而这种OQS 乱序排队将直接导致整个MPTCP 连接的时延上升和吞吐量下降[2,4]。作为MPTCP 的默认调度器,MinRTT 仅考虑多条路径间的往返时间(round-trip time,RTT)异构性,并向RTT 最小的子流中发送更多的数据包。而当前的BLEST[16]、STMS[6]和ECF[17]调度器不仅考虑RTT的差异,同时将不同路径间的拥塞窗口、吞吐量、inflight 缓存以及发送队列等TCP 层的属性差异放到一个数学模型中,以向质量更好的TCP 子流中预先分配定量计算的数据包数量,从而缓解网络异构性导致的乱序问题。
但是已有的研究表明,这类数学的方法为了简化建模的过程,通常假设了特定的网络环境,如MPTCP 只建立2 条子流、不存在主机或网络缓存的限制、子流的丢包率忽略不计等,以大幅缩小TCP子流的状态空间,使得调度器只需要简单地使用TCP 层的几个属性就能拟合函数来计算每条子流需要分配的数据包数量[7,18],但这也导致了基于数学建模的方法往往只能在有限类型的网络环境中优化特定的MPTCP 性能指标,却无法自适应更加复杂的网络环境。
在高丢包或高拥塞的动态网络中[19],由于TCP子流频繁的数据包重传和重排序,将导致剧烈的网络异构性。这使得仅优化数据包调度器已经无法实现MPTCP 的带宽聚合和故障恢复能力[20]。有一些解决方案尝试通过优化MPTCP 的拥塞控制算法,以弥补由于拥塞丢包而导致的性能下降[21-22]。但是,高丢包和高延迟的网络环境很多时候并不是由于网络拥塞导致的。尤其在无线网络中,信号衰减、噪声干扰、链路切换等情况将导致大量的无线随机丢包[2,20]。在无线网络上引入网络编码,已被证实能够极大地降低丢包概率和减少重传,从而提高TCP子流的吞吐量[8-10]。
为了实现多路径的容错传输,MPLOT[23]采用固定比率的编码方案来减少数据包的恢复延迟,以提高无线自组织网络的质量。但是当多条路径的质量急剧变化时,固定速率编码的性能将变得不佳[9]。因为编码的过程需要时间代价,而编码的冗余程度也需要消耗额外的网络带宽。不同的网络环境显然需要不同的编码率,例如在网络完全没有丢包时可以不使用编码,而在所有的路径都存在严重的丢包时使用全冗余编码能够极大地保障网络的可用性。FMPTCP[10]率先提出了使用喷泉码来实现多路径TCP 的动态编码机制,而MPTCP-dFEC[9]则基于前向纠错码(FEC)实现MPTCP 数据传输的动态前向纠错。但与之前的数据包调度器设计类似,这两种编码机制都仅基于TCP 子流的几个属性来建立一个启发式的数学模型以适应一些特定的网络场景。更准确地说,FMCTP 仅使用拥塞窗口、丢包率和RTT 来调整码率,而MPTCP-dFEC 则使用丢包率和RTT 来调整FEC 的编码率。相较于喷泉码,FEC 编解码的复杂度更低,而且数据恢复能力也相差无几。因此FEC 更常用于延迟敏感的网络编码调度中。
增强学习的变种有很多,其中主要包括Q-learning[24]、Sarsa[25]、Deep Q network(DQN)[11]、以及Actor-Critic[26]等。在任意的时间步骤t,一个标准的增强学习系统需要训练Agent 智能体与未知的环境之间进行交互,智能体根据环境当前的状态st执行动作at,以最大化自定义的反馈函数rt。对于状态空间较小的问题,Q-learning 和Sarsa 可以通过映射表的方式,将每个状态st采用动作at时得到的反馈rt的值存储到Q值表中,在训练的过程中不断更新Q值表以最大化rt直到收敛。考虑到很多问题的复杂性,使用简单的Q表已经无法存储巨大的状态空间。因此使用深度神经网络作为函数估计器映射状态空间st和动作空间at的Q值被引入到DQN 中。
但是,DQN 只能处理离散和低维的动作空间,而很多任务的动作空间,如MPTCP 数据包的编码率和分配率,都是连续的值。考虑到Policy Gradient(PG[27])的方法常被用到处理连续的控制动作,因此基于Actor-Critic 的深度确定性策略梯度下降(deep deterministic policy gradient,DDPG[12])算法通过整合DQN 和PG,被广泛应用于处理高维状态空间下的连续动作控制。考虑到MPTCP 的多子流网络状态空间的复杂性和编码调度动作的连续性,为了建立适应各种异构环境下的动态编码调度模型,只有使用DDPG 的Actor-Critic 深度神经网络才能够将所有可能的TCP 子流状态st估计到其对应的数据包编码率和分配率at的函数模型,并最大化MPTCP 整体性能定义的反馈函数rt。
由于MPTCP 的编码器与调度器用于解决不同的传输问题,因此现有MPTCP 系统中的编码和调度模块是分开实现的。但是数据包在经过编码后一定会经过调度器模块的分配,因此编码器和调度器又是强耦合在一起的。如图1 所示,在设计DMES 动态网络编码调度系统之前,本文首先基于多路径协同滑动调度器(slide together multi-path scheduler,STMS[6])使用带TC 模块[28]的无线接入设备构建了一个网络可控的MPTCP 实验平台,并对已有的编码器、调度器以及两者的组合进行测试分析,以评估当前技术在动态异构网络环境下的性能瓶颈。为了模拟动态复杂的网络环境,每条MPTCP 连接将建立n=3条TCP 子流,并根据表1 中每个Case 在RTT、丢包率和可用带宽的值域范围内,使用TC 模块随机地设置这3 条TCP 子流的网络质量。而且通过对每个Case 进行10 组多路径传输实验,分析MPTCP已有的编码器 MPTCP-dFEC (dFEC)、FMPTCP(FMP),目前性能最佳的调度器ECF 以及它们的组合在各种网络环境设置下的平均OQS 情况。
图1 实验台拓扑图
表1 子流数不变时的网络质量参数
由图2 可以看出,相比于现有的编码器,调度器ECF 能够更好地解决Case 1、2 和3 中RTT 和可用带宽异构性导致的OQS。而编码器dFEC 和FMP能够更好地解决Case 4、5 和6 中高丢包网络导致的异构性。FMP 在高丢包的Case 6 中表现得比dFEC 更好,但是在丢包相对较小的Case 2 中,dFEC却有更好的性能,这是因为喷泉码的高丢包恢复能力是以编解码开销为代价的。对于Case 5 中既高延迟抖动又高丢包率的环境,编码器组合调度器的性能有一定的提升,但是仅比单独使用编码器时的平均OQS 降低3%左右。这是因为现有的编码器和调度器都只是根据一部分的TCP 状态属性各自建立线性数学模型,并不能适应非线性变化的多路径网络环境。而这种简单的组合更不能很好地适应动态复杂的网络环境。
图2 不同方法在异构网络环境下的平均OQS
基于数学建模的方法估计MPTCP 的数据包编码率和分配率是积累了人类有限的测量经验在特定网络环境下的应用,因此缺乏对各种网络异构性的泛化能力和自适应性。它们不仅只选取部分的TCP状态属性作为输入,而且还会假设MPTCP 不会同时动态维持太多的TCP 子流。但在真实场景中,MPTCP 建立的TCP 子流数目却是动态变化的,子流的状态空间也由很多属性参数共同决定,而且参数之间还存在各种联系。因此使用深度增强神经网络(DNN)作为函数模型的估计器,能够在不需要假设MPTCP 网络环境的前提下,将TCP 子流的全部属性组成状态空间输入到DNN 中,以训练出一个将所有可能出现的“状态到动作”的匹配关系都考虑进去的泛化模型。
因此在本节中,DMES 首先使用TCP 层的属性参数设计MPTCP 的状态空间,并通过Transformmer神经网络解决这些参数之间的相关性和TCP 子流数目的动态性,以输出一个定长矩阵作为DNN 的输入。而DMES 作用在TCP 子流上的动作空间则默认使用MPTCP 数据包的编码率与分配率。然后根据MPTCP 的设计原理,引入一个新的flag-bit 位来返回DMES 系统的反馈值。最后根据这些定义详细地说明DMES 的流程。
2.2.1 MPTCP 状态空间设计
状态空间:每个时刻DMES 系统输入的状态空间,实际上是MPTCP 当前网络环境的一次快照。对于任意的时刻t,系统智能体需要输入的状态空间可以表示为st=(st1,st2,…sti…stn),sti(1 ≤i≤n) 是第i条子流TCP 层的全部属性参数,可以用一个元组表示为sti=(dti,cti,bti,lti,wti,kti),其中,dti表示TCP 子流i的往返时延(RTT)、cti表示TCP 子流i的拥塞窗口(congestion window,CWND)、bti表示TCP 子流i的数据包交付速率(packet delivery rate,PDR)、lti表示TCP 子流i的数据包丢失率(PLR)、wti表示TCP 子流i的接收窗口(RWND)、kti表示TCP 子流i的MPTCP 连接级别的数据包确认数量(Data ACKed)。
使用MPTCP 的子流加入选项(MP_JOIN option)和子流关闭选项(RST option),MPTCP 的客户端和服务器间能够动态地维持n条存活的TCP 子流。而每个时刻的状态st由MPTCP 当前存活的TCP 子流构成,这将会导致状态st的长度是随机变化的。但矛盾的是神经网络的输入层却是固定长度的。考虑到基于多头注意力模型的Transformer 神经网络[29]可以将变长的输入转换为定长的Matrix,同时还能将输入属性间的相关性附加到输出的Matrix 中。因此可以将变长的状态空间st经过Transformer 神经网络转换为定长的Matrix 后喂给DMES的神经网络输入层。这不仅能够解决状态空间的动态性问题,而且还能解决属性间的相关性对神经网络模型复杂度的影响。
2.2.2 动作空间与反馈函数设计
动作空间:在任意的时刻,DMES 根据TCP 子流的网络状态空间对即将发送的数据包首先需要进行编码动作然后进行调度动作。现有的编码算法中,基于异或的前向纠错码(FEC)不仅复杂度低而且数据恢复能力强,因此被广泛应用于TCP-IR[8]、QUIC[30]和MPQUIC[31]等网络协议的数据包编码恢复中。2.1 节中的对照实验也表明,在大多数情况下,动态FEC 能够在MPTCP 中取得更好的性能。如图3 所示,对于任意一个动态的FEC 编码模块(m,k),其中k表示应用层的源数据包数量,而m是编码后的总数据包数量,m-k则是冗余的奇偶校验数据包数量。这些奇偶校验数据包使得MPTCP 的接收端只需要接收任意k个编码数据包,就能恢复应用层的k个源数据包。因此,在任意的时刻t根据所有TCP 子流组成的状态空间st,数据包的编码率可以表示为et=(m-k)/k。而对于编码后的m个数据包,MPTCP 的调度器需要确定分配到每条TCP 子流i上的数据包数量为xti。如果MPTCP 总共维持了n条子流,则分配到子流i的比率表示为pti=xti/m,而且pt1+pt2+…pti…+ptn=1。由于编码和调度强耦合在一起,因此用一个集合将DMES的动作空间表示为at=(et,pt1,pt2,…,pti,…,ptn)。
图3 基于异或的FEC 的编码率
反馈函数:根据MPTCP 的设计原则,应用层的延迟和有效吞吐量是当前MPTCP 连接的主要QoS指标。越来越多的研究表明,影响QoS 的根本原因是MPTCP 接收端的OQS 大小,以及其衍生出来的发送端的HoL 问题。因此,在设计DMES 的反馈函数rt时需要最小化接收端的OQS。由于DMES 运行在MPTCP 的发送端队列与TCP 子流之间,这使得接收端的OQS 大小需要随着连接级别的Data ACK数据包从接收端返回到发送端。如图4所示,在每个Data ACK 数据包的数据序列信号字段(data sequence signal option,DSS)新增一个Q-bit 信号位[7]来返回接收端OQS。为了使得OQS 越小越好,DMES 的反馈函数定义为rt=1/OQS。
图4 DATA ACK 的Q-bit 标志位
2.2.3 DMES 系统设计
根据上述定义,可以发现MPTCP 动态编码调度系统的状态空间st与动作空间at都是高维度且连续变化的。因此如图5 所示,本文使用基于Actor-Critic 的DDPG 深度神经网络来估计st、at以及rt之间的函数关系模型。DDPG 共维持了4 个深度神经网络(DNNs)作为函数模型的估计器。其中,2个DNNs 是Actor 深度神经网络和Critic 深度神经网络,分别用θμ和θQ表示其神经网络的参数。Actor网络也被称为策略函数网络,用来估计当前观测到的状态st与需要采取的最佳动作at间的函数关系为at=μ(st;θμ)。Critic 网络也被称为值函数网络,用来估计对于任意的“状态-动作”对(st,at)的反馈函数的值为rt=Q(st,at;θQ)。如图5 所示,深度强化学习通过min-batches 的方式从“回放缓存”[32]中找到某个时刻t到下一时刻t+1 的状态转换元组(st,at,st+1,at+1),并根据偏导数式(1)和式(2),以SGD(θμ)和SGD(θQ)的随机梯度下降方式训练Actor 和Critic 表示的神经网络:
图5 基于深度强化学习的MPTCP 编码调度系统
而另外2 个神经网络为目标Actor 网络θ μ’和目标Critic 网络θQ’,主要用来输出每个时刻用来计算损失函数的目标值yi:
这2 个目标网络的参数θ μ’和θQ’则是使用跟踪参数τ<<1从θ μ和θQ缓慢更新而来:
最终的DMES 训练算法如算法1 所示,将主要由式(1)、(2)、(4)、(5)更新完成。在算法训练开始时,需要随机初始化Actor-Critic 网络的θ μ和θQ值。目标神经网络的参数θ μ’和θQ’也从初始化的参数复制而来。为了对状态转换进行最小采样(mini-batches)采样,因此初始化“重放缓存”为R。为了实现对连续的动作空间的探索过程,需要为每个动作的探索初始化一个噪声参数N[12]。最后将MPTCP 的子流初始状态空间s’放入R中。初始化完成之后,DMES 将进入一个无限循环直到收敛。对于每个Data ACK 的返回时刻t,DMES 的智能体将“探索噪声N”和Actor 神经网络的输出组成状态st的匹配动作,即at=μ(st;θ μ) +Nt。然后,at中的码率et和比率pt将会被应用到MPTCP 发送端的编码器和调度器上。而在t时刻应用at导致的反馈值rt(即OQS),将在t+1 时刻由Data ACK 返回,并与状态st+1组成(st,at,rt,st+1)存储到回放缓存R中。而Actor-Critic 神经网络的更新,则是通过从R中mini-batchesN个状态转换元组(st,at,rt,st+1),并使用式(1)和(2)进行随机梯度下降更新参数θ μ和θQ。而目标Actor-Critic 神经网络θ μ’和θQ’的更新则是通过式(4)和(5)完成。
为了让MPTCP 的对端都支持动态的FEC 编码,需要在MPTCP 的握手报文中新增FEC_CABLE选项进行对端的FEC-enabled协商。由于MPTCP是内核空间的程序,而基于Tensorflow[33]的Actor-Critc 深度神经网络是用户空间的程序,因此DMES使用系统调用函数getsockopt()从内核空间中周期性地获取MPTCP 的TCP 子流状态空间st,并通过系统调用函数setsockopt()来执行Actor-Critic 神经网络在不同的状态st下输出的MPTCP 动作空间at,以最小化rt中MPTCP 接收端的OQS 队列。
在训练DMES 时,需要使用6 层叠加的多头注意力(multi-head attention)模型组成Transformer 神经网络,每个注意力模型的输入是一个512 维的矩阵。与此同时,Actor 神经网络和Critic 神经网络由2 个全连接的48 ×48 的神经网络隐藏层和神经网络输出层组成,并使用rectified linear 函数作为隐藏层的激励函数,以及hyperbolic tangent 函数作为输出层的激励函数[34]。根据Adam 方法[35],将更新Actor 网络和Critic 网络的学习率分别设置为10-4和10-5。为了模拟动态复杂的网络环境,本节继续使用第2.1 节中的可控实验床,具体的参数设置如表2 所示,且每种Case 进行20 组多路径传输实验。
表2 子流数变化时的网络质量参数
(1)乱序队列
如图6 所示,本小节首先分析了各种异构网络环境下的MPTCP 乱序队列分布情况。实验结果表明,相比于其他的方法DMES 在所有的Case 中的OQS 都是最小的。且在多子流高丢包的环境中,将MPTCP 的平均OQS 最高降低20%以上。因为深度神经网络将编码器和调度器完美融合到一起,不仅能够基于调度的方式自适应轻微网络异构性而且能够通过编码恢复的方式极大地降低剧烈网络异构性导致的接收端乱序队列数量。
图6 不同方法在动态异构网络下的OQS 分布情况
为了更加清楚地描述实验结果,本小节分析了在不同的丢包率和TCP 子流数量下的MPTCP 接收端的平均OQS 情况。如图7(a)所示,与其他的设计方法相比,在15%~20%的高丢包环境中,DMES最高能够将平均OQS 降低17.4% 左右,若此时MPTCP 同时建立了8 条TCP 子流,如图7(b)所示,DMES 将平均OQS 降低到24.6%以上。
图7 不同方法在不同丢包和子流下的平均OQS
(2)应用延迟
由于接收端的乱序直接导致了数据包的延迟交付。因此传输实验中测量了MPTCP 连接级别的平均应用延迟。如图8 所示,在子流数目较少且丢包不高的Case 1 中进行多路径传输实验时,由于ECF+dFEC 和DMES 几乎没有编码开销而且能够通过调度器适应网络的异构性,因此它们的应用延迟明显低于存在编码开销的dFEC 和FMP。当在Case 3和Case 4 中的丢包率达到10%~15%时,相比于ECF 调度器,DMES 却能够自适应地编码,因此将应用延迟降低大约6.3%左右。最后在子流的数量为6~8 条且丢包率达到15%~ 20% 的Case 6 中,DMES 能够将平均应用延迟最高降低12.2%以上。
图8 不同方法在动态异构网络下的平均应用延迟
(3)有效吞吐量
MPTCP 连接的吞吐量是TCP 子流共同作用的结果。但由乱序到达的报文必须按序交付给应用层,使得MPTCP 的有效吞吐量并不是TCP 子流吞吐量的简单叠加。因此,通过测量应用程序的实时吞吐量作为MPTCP 的有效吞吐量。如图9 所示,在丢包率较低的Case 1 和Case 2 中,相较于ECF 调度器,DMES 的有效吞吐量提升了7.4%左右。而在丢包率较高的Case 6 中,相比于ECF、FMP 和dFEC 的设计方法,DMES 的有效吞吐量提升能够分别达到18.3%、14.7%和15.2%左右。与此同时,当子流的数目较多时MPTCP 的网络虽然变得更加复杂,但DMES 的有效吞吐量提升却更加明显。
图9 不同方法在动态异构网络下的平均有效吞吐量
本文通过分析现有的编码器、调度器以及两者的组合在动态多变的异构网络环境中的表现情况,发现了编码器组合调度器在剧烈的异构网络中的性能提升空间。并通过使用深度强化神经网络作为函数模型的估计器,利用Transformer 神经网络处理MPTCP 连接动态TCP 子流的全部属性,以匹配出编码器和调度器当前最佳的编码动作和调度动作,从而最大化MPTCP 整体传输性能。实验结果表明,本文提出的方法能够实现编码器和调度器能力的完美融合,从而更加适应动态复杂的多路径网络环境。
未来工作将尝试基于深度强化学习的多路径动态编码调度思想应用到用户态的多路径传输协议中,以减少内核态与用户态的交互开销,同时采用更多真实环境下的多路径数据传输实验以增加系统的稳定性。