一种基于强化学习的CDN流量调度系统设计方法

林春莺

(集美大学理学院，福建 厦门 361021)

0 引言

内容分发网络(content delivery network，CDN)是一种在服务提供方和消费方之间，通过架设节点或者服务器，让用户就近获取所需的内容，从而达到缓解网络拥塞，提高用户访问网站响应速度的目的。基于这种服务结构，如何有效管理不同服务的资源调度分配，保证高质量的服务是一个需要深入研究的问题。特别是当资源处于超负荷运转或网络波动时，如何通过调度来及时选择合适的替代资源，是保证服务质量的关键。传统业界的调度方式一般采用基于规则的方式[1],即，先收集大量服务器资源的指标(比如负载情况、网络情况、物理位置、服务冗余度等)，再统计评价指标，最后以此来制定规则。但指标量越大则导致调度规则越复杂，使修改和维护成本更高，灵活性更差，同时调度策略往往只考虑服务质量，而没有考虑现实的成本问题。

近年来强化学习(reinforcement learning,RL)[2]因其强大的探索能力和自主学习能力，在游戏[3]、机器人控制[4]、交通控制[5]等领域都有广泛的应用。在资源调度策略领域，文献[6]利用Q值强化学习，将虚拟机资源调度描述成马尔科夫决策过程，并设计了动作的奖励函数，实现虚拟机的资源调度策略；文献[7]将深度强化学习的思路应用到微电网在线优化调度过程中；文献[8]应用强化学习算法求解置换流水车间调度问题；文献[9]提出DeepRM模型，将资源调度系统的状态信息建模成图像形式，将获取的图像信息输入到卷积神经网络中，通过卷积神经网络对图像信息进行快速特征提取，用强化学习的方法对神经网络中的参数进行迭代更新，形成最终的策略；文献[10]使用分析集群状态和机器状态的两层深度强化学习模型来共同完成对集群资源和能耗的管理工作。这些应用都是将现实问题转化为强化学习问题，通过训练智能体(agent)以及定义符合领域知识的环境反馈，进行动态灵活的学习。

为了解决CDN资源调度中存在的复杂规则问题，同时综合考虑服务质量和成本，本文拟结合强化学习的优势，对CDN资源调度问题进行重新定义，提出一种基于深度强化学习的CDN资源调度系统设计方法，以避免人为指定调度规则带来的不准确、维护困难以及成本波动等问题。

1 系统设计

1.1 总体框架设计

本文提出的基于深度强化学习的流量调度系统的设计内容，主要包括调度的智能告警触发模块、综合质量和成本的调度评估模块、强化学习模块。其工作原理主要为：1)采集节点和服务器相关指标以及故障数据，构建基于马尔可夫模型的智能报警网络，产生流量调度的增量带宽需求；2)对节点和服务器的带宽情况、服务能力、用户覆盖情况、响应时间等进行综合考虑，建立质量评估模型(强化学习环境的奖励函数的组成部分)；3)对节点和服务器的计费类型、计费系数等进行综合考虑，建立成本评估模型(强化学习环境的奖励函数的组成部分)；4)针对增量带宽需求，结合质量和成本评估奖励函数，在线上受限环境(model-free)或者虚拟环境(model-base)中进行迭代学习，建立深度强化学习模型；5)在全网环境部署模型后，根据调度产生的数据不断进行在线学习，完善调度系统。

1.2 故障报警网络设计

建立故障报警网络是为了能及时发现出现服务质量的节点或服务器，触发流量调度。本研究通过采集近期故障报警历史数据，建立基于马尔科夫链的异常检测算法，进行智能告警。主要有：1)采集故障报警历史数据。历史数据指因监控服务器而产生的从底层机器指标(CPU、请求数、响应时间)到高层机器指标(客户投诉)报警的时间序列。2)对故障报警历史数据进行离散化，设立低、中、高三个告警级别，从而建立不同告警级别前后相连的马尔科夫链。3)基于报警马尔可夫链，建立故障报警网络。当发生低级别机器指标报警时，根据网络内各个报警级别间的转化关系及概率，预测高级别报警产生的概率，若概率较高，则会以较大概率触发调度。

1.3 基于Stacking模型的质量评估模型

在基于强化学习的调度系统中，当调度系统生成一个动作时，需要环境给出奖励来指导整个学习过程。本研究为强化学习提供服务质量的奖励函数。当一个带宽增量需求提出时，虽然机器的承载带宽可承载，但是由于业务特性不同，对机器的CPU、内存等要求是不同的，若不加以区分就会造成机器资源耗竭，影响服务质量。因此，本研究提出基于Stacking模型的服务质量评估模块，用来预测加量后机器资源的CPU使用率，并以此作为机器负载的判断标准。过程步骤如下：

1)采集训练数据：采集线上机器资源的业务属性(带宽量、http请求数)和机器属性(内存大小、磁盘类型、CPU核数、CPU主频大小)作为输入特征，采集机器资源的多核CPU实时使用率均值为预测值，同时统计不同业务特征每1 Mibit/s带宽对应增加的http请求。

2)数据集划分：将历史n天数据作为训练集，第n+1天数据作为测试集，并采用滑动窗口方式在时间轴上将数据集不断划分。

3)基模型训练：先使用Xgboost、RandomForest、Lightgbm算法作为基模型，采用K折交叉验证方式对每种模型进行训练，然后每种基模型训练后会得到K个子模型以及对训练集样本的CPU使用率预测结果，再保存每种基模型的各个子模型。

4)模型融合：用K-NearestNeighbor(KNN)进行模型融合，将步骤3)中每种基模型下的子模型对应训练集的CPU使用率预测结果作为KNN模型的输入特征，将训练集真实CPU使用率作为KNN模型的输出，设置训练模型近邻个数为5(见图1左边部分)。

5)预测阶段：假设要给机器资源加量500 Mibit/s带宽量，实时采集当前机器的业务属性(带宽量、http请求数)和机器属性(内存大小、磁盘类型、CPU核数、CPU主频大小)，在此基础上将增量的500 Mibit/s按照统计系统换算成http请求数加到当前值中，带宽量也加500 Mibit/s，训练好的模型对增量后的特征进行预测，得到CPU使用率，如图1所示。

1.4 深度强化学习调度模型设计

本文所要解决的CDN资源调度问题为服务的增量需求问题。当客户请求访问增加，导致当前服务的机器资源负载增加，出现服务响应时间变长，服务质量降低，此时需要为当前的客户请求增加额外的机器资源。其调度结构如图2所示。其中：增量需求包含带宽增量(如需要增加300 Mibit/s)和地理属性(如福建)两个重要属性；服务器资源是有额定带宽上限的机器资源，可用资源池为机器剩余的可用带宽，不同的机器资源有不同的价格系数，代表了机器的成本因素；调度策略为强化学习的智能体(agent)结构，调度策略的目标是既要满足带宽增量的要求，又要兼顾服务质量和成本的均衡。

1.4.1 问题建模

与传统的机器学习相比，强化学习更注重与环境的交互，通过不断与环境交互获得奖励学习，以此得到最佳的动作(如图3所示)。

本文将CDN增量需求的调度问题转化为基于有限的马尔科夫决策过程。这种过程可以用一个五元组表示(S,A,Pa(st,st+1),Ra(st,st+1),γ)。其中：S为状态集合；A是动作集合；Pa(st,st+1)为在时刻t的状态st经过执行动作a可以在t+1时刻转换到状态st+1的转换概率；Ra(st,st+1)为执行动作a所产生的奖励值；γ为折扣因子，值处于[0,1]区间，用来表示奖励值对累积奖励值的影响权重。对于本文要解决的CDN增量需求的调度问题，动作A为将可用资源池中服务器资源分配给某个增量需求；状态S为分配后增量需求满足情况和资源的剩余情况；而奖励R为分配后CDN服务产生的服务质量和成本。本文设计的强化学习的目标就是学习最佳的策略(h)，能使整个任务过程的累积奖励值最大。

本文采用Q学习方法中的动作评价函数Q(s,a)来描述在状态s时agent选择动作a后所得到的最大累积奖励。在agent训练过程中，总是选择Q最大值的动作：

Q(st,at)=r(st,at)+γmaxQ(st+1,at+1)。

1.4.2 策略设计

本文采用基于卷积网络的DQN(deep Q-network)[11]算法来训练agent智能体。DQN算法使用参数为θ的深度卷积神经网络作为动作值函数的网络模型，用模型Q(s,a,θ)来模拟最佳Q(s,a)。在训练过程中，该网络模型生成每个动作的Q值，采用递增的ε-greedy策略来选择动作，生成一系列的状态、动作和奖励值。DQN训练模型如图4所示。

DQN采用均方误差作为深度网络的损失函数，公式为Li(θi)=E[(r+γmaxa′Q(s′,a′;θi)-Q(s,a;θi))2]。其中：γ为折扣因子；θi为第i次迭代的网络参数；s′,a′为下一个状态和动作。

DQN采用mini-batch方式的随机下降法来实现对目标损失函数的优化。每产生一个动作a和环境交互后，神经网络都会进行一次迭代学习，同时更新参数，直到收敛。

1.4.3 状态空间

策略中状态空间包含可用的机器资源池和增量带宽需求。由问题定义可知，资源池和增量需求都是以数值属性带宽量(如500 Mibit/s)表示，这样动作设计(分配资源)时只能整个分配或者不分配，使资源分配方式受限。所以在状态空间设计时，需将资源和需求量拆分成更小的单元(如100 Mibit/s)。如图5所示，左边为5个带宽需求，有颜色的部分代表最小单元带宽，第一个需求为增强500 Mibit/s；右边为当前资源池中每台机器可用带宽资源，同样有颜色的表示最小带宽单元，第一个带宽资源为700 Mibit/s。将有颜色的部分用1表示，空白的地方用0表示，就可以将资源状态转换为图像矩阵的形式，作为DQN深度卷积网络的输入，从而提取重要特征。由于DQN神经网络需要保持输入的固定大小，状态空间设计时，设定固定M个需求，而对于剩余的需求则可以放在等待队列。

1.4.4 动作空间

策略中的动作空间为将资源分配给带宽需求的动作集合。设策略中包括M个带宽需求，N个机器资源，则总的状态空间数量为N×M+1个，{0,1,2,3,…,N×M-1,φ},φ表示空动作，不做分配。在每次迭代时，调度器将资源分配给合适的带宽需求，并更新系统中的资源状态，直到所有的带宽需求都分配完或者所有的资源都分配完才中止迭代。

1.4.5 奖励函数

本策略中针对CDN资源调度问题，兼顾质量和成本的目标，设计了一个基于模型的评估函数。当一个机器资源分配给一个带宽需求时，除了要满足需求的带宽，还要使机器资源在地理位置上尽可能相同，这样才能保证就近访问，提高响应时间。另外，还需要考虑加量后机器资源是否会出现高机器负载。虽然机器资源带宽是允许承接设定的带宽量，但由于业务特性不同，使用CPU资源不同，即使同样的带宽量产生的负载也会不同，如网页和流媒体的CPU资源使用率就完全不同。服务成本要求尽可能选择价格系数小的机器资源。

因此，策略中的奖励函数可以表示成：r=(m×g×l)/p。其中:m表示满足带宽的比例，可以在分配后计算;g表示地理位置的匹配程度，可以根据带宽需求的地理属性和机器资源的地理属性匹配情况，按照不同层级设定不同的比例(如同城为1，同省为0.8，同大区为0.5，跨大区为-0.5,跨国为-1)；l表示加量后负载情况；p为价格系数，是机器资源的固有属性。

对于如何判断加量后会不会产生机器负载问题，本策略先采用Stacking质量评估模型进行预测，得到增量带宽后的CPU使用率；再根据CPU使用率的不同等级设置不同的分数，如>90%为-1，[80%，90%]为0.2，[50%，80%]为0.6，<50%为1。

1.5 深度强化学习调度模型训练

1.5.1 训练参数

在DQN网络训练中，为使agent 在训练前期对最优策略的探索力度增加，采用递增的ε-greedy策略来选择动作。设ε的初始值为0.5，最大值为0.9，增幅为0.001；折扣因子为0.95；经验池规模为30 000；迭代次数为1000;采用Mini-batch 训练方法，设batch-size为32；采用随机梯度下降方法更新Q网络参数，优化器为Adam，学习率为0.001。每C个训练回合后将当前Q网络的参数值复制给目标Q′网络，并更新一次目标网络参数。

1.5.2 受限环境调度系统

CDN是一个复杂的内容分发网络，在训练本文提出的基于强化学习的CDN流量调度系统时，需要在不影响现有网络基础上构造一个可行的环境。受限环境(model-free)调度系统是指系统的学习过程、调度过程都是在真实的环境下进行，同样，接收到的结果反馈也来自于真实的环境。model-free调度系统结构图见图6。

本文构建CDN受限环境的目的在于从CDN全网环境中规划出一个小范围的环境，使得深度强化学习模型在训练和验证期间的一系列试错行为产生的负面影响，被控制在一个较小的范围，避免给全网的服务质量和成本带来波动。该受限环境可以根据物理位置、运营商或者不同等级的用户等进行划分。

本文提出的设计方法分成CDN受限环境下的训练阶段和CDN全网环境下的应用阶段。

在训练阶段，若出现触发调度的情况，则设置CDN受限环境下资源配置情况为模型输入状态，模型会基于当前网络中的参数，输出替代资源的挑选概率或者分数，并根据一定策略选择替代资源，然后评估系统对替代资源的服务情况进行评估并反馈给模型，模型接收到反馈信号后，根据反向传播算法，调整网络参数，使后续调度能够朝着全局最优的方向进行。

当训练达到一定迭代次数或者结束条件时，会生成性能较好的调度模型。该调度模型会应用到CDN全网环境上，在后续的运行过程中仍然持续进行在线学习。若发生触发调度的情况时，模型会根据学习的结果选择可能对未来产生正面影响的替代资源进行服务，同时评估系统会对替代资源的选择进行评估，调度模型根据反馈信号进行参数调整。

1.5.3 虚拟环境调度系统

虚拟环境(model-based)调度系统是指系统的学习过程是在虚拟环境中完成，而调度过程是在真实环境中进行。虚拟环境调度系统结构图如图7所示。

CDN虚拟环境是指根据线上CDN全网环境虚拟出的一个环境。该环境支持调度系统与其进行交互，且支持根据调度结果，模拟线上CDN全网环境对其的响应。其评估系统的工作方式和原理与受限环境调度系统一样，但由于是虚拟环境，调度触发条件中的故障报警功能可以用简单的元胞自动机进行模拟。

基于CDN虚拟全网环境来训练模型有两点优势：

1)线上真实环境需要等待调度触发条件出现，才能进行调度，评估调度结果，累积训练数据。在这样的情况下让模型的性能收敛，可能需要一个比较长的时间周期。如果是在虚拟环境中，可以通过元胞自动机进行触发条件模拟，相较于真实环境下能有千倍甚至万倍的效率对模型进行训练，大大缩短训练时间周期。

2)CDN受限环境是为了减小模型在训练期间的试错行为对线上服务质量和成本带来的负面影响，而规划出的CDN全网环境的一个子集。该子集环境虽然能够将负面影响限制在一个较小的范围内，但是却不能完全消除影响。另外，由于是一个CDN的子集环境，在该环境上产生的用于模型训练的数据是一个局部数据集，可能与CDN全网环境产生的全局数据集不是来自同一个分布，可能会导致深度强化学习模型出现过拟合现象，而不能很好地泛化到全网环境。而CDN虚拟环境则解决了以上两个问题，一方面，它在虚拟环境中的任何操作都不会对真实环境造成影响；另一方面，虚拟环境是模拟真实的全局环境，避免了数据层面的局限性。

2 仿真实验结果分析

在阿里云申请了全球10个机房节点资源，20台服务器设备，对本文算法进行实验仿真。

首先，训练Stacking质量评估模型。实验定义ABS(实际CPU-预测CPU)<5表示模型预测准确，模型预测精度=模型预测准确数量/样本总数。预测结果显示，CPU的精度整体可以达到95%。从在线运行结果(见图8)可知，21:03实际带宽2.57 Gibit/s，预期加量700 Mibit/s，模型判断不能加量；21:12实际带宽3.15Gibit/s，机器的健康值为0.7，加量导致机负载超负荷。由实验可知，质量评估模型能有效评估加量后的机器质量情况，能够为强化学习提供有效的奖励反馈。

图9显示了强化学习训练过程不同迭代的奖励值。由图9可知，随着迭代的增加，智能体agent完成调度任务所获得的奖励值不断增长直至收敛。

在线上部署强化学习过程中，对比开启强化学习调度前后的效果(见图10)，发现本算法在不同产品线上不仅能满足合适的带宽要求，而且机器的服务质量也有明显的提升。

在带宽调度上，线上实验结果表明强化学习模型可以有效地控制节点跑高。如图11所示，节点跑高后1 min内开始降量。

最后对比了基于规则调度系统和深度强化学习调度系统在不同场景中的调度耗时。由表1可见，深度强化学习调度系统提升效果明显。

表1 调度耗时对比图Fig.1 Time consuming comparison of scheduling