面向延迟敏感应用的基于机器学习的预占式 SDN负载均衡

摘要

软件定义网络（SDN）是实现5G和多接入边缘计算 网络可扩展性的关键使能技术。为了在分布式SDN控制器之间 平衡负载，已有研究提出迁移数据平面组件的方法。与大多数 以往采用反应式机制的工作不同，我们提出一种预先行的S DN控制平面负载均衡方法，以支持需要低延迟通信的网络流。
首先，我们对SDN控制器的负载进行预测，以防止负载不平衡， 并提前规划数据平面迁移。其次，我们在满足延迟约束的前提 下优化迁移操作，以实现更优的负载均衡。具体而言，在第一步中，我们基于自回归积分滑动平均（ARIMA）和长短期记忆 （LSTM）方法构建了两个预测模型，用于预测SDN控制器的 负载。随后，我们对这两个模型进行了对比研究，并计算了它 们的准确性和预测误差。结果表明，在长期预测中，LSTM模型 的预测误差比ARIMA模型低55%，性能更优。在第二步中，为 在延迟约束下选择需要迁移的数据平面组件及其目标位置，我 们将该问题建模为一个非线性二元规划问题，证明其具有NP完 全性，并提出一种强化学习算法来求解该问题。仿真结果表明， 所提出的算法性能接近最优，且优于现有文献中的最新基准算 法。

索引词

负载均衡，机器学习，迁移，多接入边缘计算，预测，强化学习，软件定义网络。

一、引言

A DISTRIBUTED 软件定义网络控制平面的分布式架构是 解决当前集中式架构问题的合适方案，尤其是在大规模网络 中[1]。具体而言，分布式架构在控制平面为移动应用提供了 高可扩展性和更高的处理能力，同时避免了交通拥塞和高
稿件收到日期2020年5月30日；修订于2020年9月27日；接受于2020年 11月2日。出版日期2020年11月18日；当前版本日期2021年1月22日。本文 的审稿由T.原教授协调。(通讯作者：苏迈娅·谢尔科伊。)阿卜杜拉希姆·法 拉利就职于加拿大魁北克省舍布鲁克J1K2R1舍布鲁克大学电气与计算机工 程系（电子邮件：abder‐rahime.filali@usherbrooke.ca）。祖拜尔·姆 利卡就职于加拿大魁北克省舍布鲁克J1K2R1舍布鲁克大学工程学院（电子 邮件：mlika.zoubeir@gmail.com）。苏迈娅·谢尔科伊就职于加拿大魁 北克省舍布鲁克J1K2R1舍布鲁克大学电气与计算机工程系、工程学院（电 子邮件：soumaya.cherkaoui@usherbrooke.ca）。阿卜杜勒‐阿提夫·科 班就职于摩洛哥拉巴特BP713穆罕默德五世大学高等理工学院（电子邮件： abdellatif.kobbane@um5.ac.ma）。数字对象标识符 10.1109/TVT.2020.3038918

图1.分布式软件定义网络移动网络架构。

延迟和单点故障（即瓶颈）问题[2]。在分布式控制平面 架构中，如图1所示，网络被水平划分为若干个互不重叠 的区域，称为控制域，每个控制域由一个单独的控制器管 理。这种分布式架构目前与现有和新兴技术的多项标准相 结合，特别是网络功能虚拟化（NFV）、服务功能链（ SFC）和多接入边缘计算（MEC）[3]。此外，它也是 5G网络的关键组成部分[4]。作为所有这些技术的一部分， 分布式SDN架构确实有能力持续保障数据平面中目标应用 所需的性能，尤其是延迟敏感型应用[5],[6]。然而，这 种架构引发了负载分配问题，可能严重影响控制平面的可 扩展性，并降低其资源（例如控制器处理能力）的利用效 率[8]。在应用程序数量庞大且流量波动持续存在的大规 模网络中，每个控制器都需要尽可能快速地处理和响应来 自数据平面组件的成千上万条请求。因此，这种动态网络 流量可能导致控制器之间的负载不平衡，即某些控制器会 过载，而其他控制器则会欠载。当某个控制器过载时，其 对数据平面组件请求的响应时间将增加。因此，必须在 SDN控制器之间进行负载均衡，以最小化延迟并高效利用 控制平面资源。
数据平面组件迁移是一种广泛用于在控制器之间平衡负载 的高效解决方案[9]。
0018‐9545©2020年电气与电子工程师协会。允许个人使用，但重新发布/分发需要电气与电子工程师协会的许 可。更多信息请见https://www.ieee.org/publications/rights/index.html。
授权使用的范围限于：中央密歇根大学。下载时间：2021年5月14日16:17:20UTC，来源：IEEEXplore。适用限制条款。
本文档由funstory.ai的开源PDF翻译库BabelDOCv0.5.10(http://yadt.io)翻译，本仓库正在积极的建设当中，欢迎star和关注。

15948 IEEE车辆技术汇刊，第69卷，第12期，2020年12月

事实上，当控制器上的负载不均衡时，一些数据平面组件 会从过载控制器迁移到欠载控制器，从而在控制器之间公 平地平衡负载。数据平面组件的迁移操作通过四阶段机制 [10]来改变其控制域。尽管数据平面组件迁移是实现控制 平面负载均衡的关键使能技术，但它带来了若干挑战，例 如迁移应在何处发生（即确定过载和欠载控制器），以及 应迁移哪个数据平面组件。为了应对这些挑战，近年来已 提出了大量算法和方案[11]–[21]。然而，我们发现这些研 究中存在两个重要的研究空白。首先，它们均提出的是针 对数据平面组件迁移的反应式机制。反应式机制在检测到 控制器过载后才触发迁移操作，导致该控制器在一段时间 内处于拥塞状态，从而使其响应时间在此期间增加。其次， 迁移操作的成本尚未以延迟来定义，这可能降低迁移效率。
本文旨在针对边缘端延迟敏感应用，预先实现控制器 之间的负载均衡。为此，为了填补上述研究空白，我们： （1）提出一种长期预测模型，用于预测控制器的负载； （2）通过优化负载均衡与基于SDN控制器响应时间的迁 移操作成本之间的权衡，解决分布式SDN架构中的负载均 衡问题。长期预测能够检测控制平面中的负载不平衡情况， 从而通过提前规划迁移操作实现主动响应。该主动机制不 仅可防止控制器过载，还能仔细选择应迁移的数据平面组 件及其迁移目标位置。因此，我们将面向延迟敏感应用的 SDN负载均衡问题（LBDSA）建模为一个优化程序，其目 标是通过迁移操作最小化负载均衡因子与迁移操作成本的 组合。由于该主动机制以及LBDSA模型的设计，延迟敏感 应用的需求得以满足。
总之，本工作的创新性主要体现在两个方面。第一部 分是对自回归积分滑动平均（ARIMA）[22]——一种传统 随机模型——与机器学习预测模型——长短期记忆（ LSTM）[23]——进行的对比研究。第二部分是定义了 LBDSA问题，并提出了一种强化学习算法来解决该问题。
本工作的主要贡献总结如下： 1)我们构建并评估了两个预测模型，一个基于 ARIMA，另一个基于LSTM。2)我们提供了性能分析， 比较ARIMA和LSTM模型在短期和长期SDN控制器负 载预测上的准确性。3)我们将LBDSA建模为非线性二 进制规划，并研究其NP完全性。
4)由于LBDSA的NP完全性，求得其最优解在计算上是 昂贵的。因此，我们提出了一种基于著名“赢留输变” （WSLS）学习策略[24],[25]的强化学习算法，称为 2WSLS。
5)我们将2WSLS的性能与最优解以及两种先进的软件 定义网络负载均衡算法[17]和[11]进行了比较。结果 表明，2WSLS接近最优，并且优于基准算法。
本文的其余部分组织如下。第二节讨论了基于数据平 面组件迁移操作的软件定义网络控制平面负载均衡方面的 近期研究工作。第三节介绍了ARIMA和LSTM预测模型。
第四节构建了用于长期预测的ARIMA和LSTM模型，并 对所获得的模型进行了评估。第五节比较了所构建模型在 短期和长期预测准确性方面的性能。第六节和第七节分别 提出了软件定义网络负载均衡优化的系统模型，以及 LBDSA的数学规划建模及其NP‐完全性。第八节介绍了所 提出的2WSLS学习算法，并解释其操作过程。第九节重 点阐述了2WSLS的性能并讨论了所获得的结果。最后， 第十节对全文进行总结。

II.相关工作

本节介绍的研究工作可分为两类：(i)不考虑与数据 平面组件迁移操作相关的任何成本[11]–[16] ；(ii)考虑 数据平面组件迁移成本[17]–[20]。
在[11],中，作者提出了一种基于控制器实际响应时 间的负载均衡机制。他们还利用该响应时间定义一个适当 的阈值，以判断控制器是否过载。过载控制器同时将最重 的交换机迁移到欠载控制器。然而，由于迁移操作是同时 进行的，所提出的机制可能会增加控制流量开销。[12]的 作者使用负载多样性因子（即负载之比）来识别过载控制 器和欠载控制器。当多样性由过载控制器引起时，应将其 控制域中的一些交换机进行迁移；而当其由欠载控制器引 起时，则应将其控制下的所有交换机都进行迁移。为解决 此交换机迁移问题，他们采用了一个非合作博弈，其中参 与方为接收迁移的控制器。在[13],中，采用了一种改进版 的匈牙利算法来实现交换机到控制器的分配。在分配过程 中，所提出的算法考虑了交换机与控制器之间的往返时间 以及控制器的当前负载。文献[14]以两阶段方式解决交换 机‐控制器分配问题。第一阶段，基于流路径，使用贪心集 合覆盖算法形成最少数量的控制域，这些控制域包含了路 径上的大多数交换机。所得的分配结果在第二阶段被联盟 博弈策略用于改善控制器之间的负载均衡。在此阶段，交 换机可以
授权使用的范围限于：中央密歇根大学。于2021年5月14日协调世界时16:17:20从IEEEXplore下载。限制适用。
菲拉利等：面向延迟敏感应用的基于机器学习的抢占式SDN负载均衡 15949
改变其联盟以达到纳什均衡。然而，所提出的方法导致了 更多的迁移操作。为了解决长期范围内的动态控制器‐交换 机分配问题，文献[15]中的作者使用随机固定时间范围 控制（RFHC）框架将其分解为一系列单一时隙分配问题。
在每个时隙中，给定每个交换机的请求速率，采用两阶段 算法将交换机分配给控制器。在第一阶段，分配问题被建 模为多对一匹配博弈。在第二阶段，将第一阶段得到的结 果作为输入用于联盟博弈，以实现纳什均衡。为了最大化 控制器与交换机之间流建立的效率，文献[16]中的作者定 义了一个关于控制器部署和控制器‐交换机分配的长期优化 问题。控制器的部署规划考虑了未来可能发生的交换机迁 移操作。在控制器部署完成后，可以通过从过载控制器中 选择负载最高的交换机来执行交换机迁移操作。总之，文 献[11]–[16]中的研究在评估迁移操作的有效性时未考虑 任何迁移成本。
[17]的作者通过执行两种类型的交换机移动来处理交 换机迁移问题。他们提出了一种启发式算法，利用移位操 作和交换操作将交换机从过载控制器迁移到欠载控制器。
移位操作是指交换机的传统迁移操作，而交换操作是指两 个交换机通过迁移操作交换其主控制器。交换机迁移的成 本取决于（i）参与迁移操作的控制器之间的延迟，以及 （ii）被迁移交换机与参与迁移操作的控制器之间的延迟。
当无法执行移位操作时，交换操作在控制器之间的负载均 衡方面非常有用。然而，执行交换操作会大幅增加迁移在 时间和控制平面开销方面的成本。[18]的作者定义了一个 负载多样性因子，用于将控制器划分为过载控制器和欠载 控制器。两个控制器之间的负载多样性因子是它们负载的 比值，当该比值超过预设阈值时，便执行交换机迁移。过 载控制器选择迁移那些对其具有较大延迟且资源消耗较少 的交换机。目标控制器的选择旨在最大化迁移效率，迁移 效率定义为负载均衡变化量与迁移成本的比值。类似地， [19]的作者也使用相同的负载多样性因子，但在计算控制 器负载时考虑了同步和路由开销。在[20],中，采用了一 种称为逼近理想解的排序方法（TOPSIS）的多准则决策 方法来选择目标控制器。这些准则基于资源消耗和跳数距 离。此外，他们还使用一种概率模型，选择资源消耗较低 的交换机进行迁移。在[18]–[20],中，迁移操作的成本主要 由控制流量开销中增加的负载定义，而未考虑该迁移操作 所需的时间，这可能会降低迁移效率。

III.软件定义网络控制器负载预测模型

在本节中，我们定义了本文所考虑的SDN控制器负载 以及时序的基本概念。然后，我们回顾了使用ARIMA和 LSTM模型进行预测所需的核心数学基础。

A.软件定义网络控制器负载

在时间 t，SDN控制器的负载记为 L(t)，可以定义为 来自以下部分的请求总和：(i)受管的数据平面组件，(ii) 其他SDN控制器，或(iii)能与此控制器通信的任何网络实 体。在本研究中，我们认为由数据平面组件发送的请求是 SDN控制器最主要的部分[26],，特别是OpenFlow协议 的 Packet_In消息。
为了预测分布式控制平面架构中每个SDN控制器的负 载，我们假设存在一个对网络具有全局视图的根控制器 [27]。实际上，该根控制器与其他控制器相连，但不管理 任何数据平面组件。在这种架构中，所有控制器都会向根 控制器更新其控制域状态。因此，根控制器掌握每个控制 器的全部信息，包括它们的负载历史。基于SDN控制器的 负载历史，根控制器可以对每个控制器的负载进行预测。

B.时间序列和预测

时间序列是在一段时间内通常以固定时间间隔测量得 到的数据点（即观测值）的有序序列。顺序的重要性在于 观测值之间可能存在依赖关系，因此改变顺序可能会改变 数据的含义。在本例中，我们研究的是单个变量，即软件 定义网络控制器负载L(t)。因此，所研究的时间序列称为 单变量时间序列。此外，控制器负载每秒测量一次，因此 它是一个离散时间序列。将SDN控制器负载作为时间序列 进行分析的主要优势在于能够预测其未来值。预测的目标 是以零误差或尽可能小的误差对未来情况进行预报。为此， 必须使用时间序列数据训练合适的预测模型，并且应拟合 模型的参数以从数据中提取模式。根据所研究问题的不同， 预测可以针对短期或长期前景进行。就我们的研究目的而 言，即预测控制平面中的任何负载不平衡情况，以便提前 调度数据平面组件迁移操作，长期预测是合适的模型。

C.多步负载预测

我们通过负载预测的目标是检测控制平面中的任何负 载不平衡。因此，可以提前调度数据平面组件的迁移操作。
为了执行有效的迁移操作，需要完成多项任务，例如选择 数据平面组件
授权使用的权限限制为：中央密歇根大学。于2021年5月14日协调世界时16:17:20从IEEEXplore下载。限制适用。
15950 IEEE车辆技术汇刊，第69卷，第12期，2020年12月
迁移及其新的控制域。因此，长期预测是合适的模型，能 够仔细选择哪些数据平面组件需要迁移以及迁移应发生在 何处。长期预测指的是对SDN控制器负载进行多步预测。
在本研究中，我们采用多输入多输出（MIMO）策略来预 测SDN控制器负载的多个步骤。MIMO策略使用相同的过 去观测值，通过同一个拟合模型一次性预测整个预测序列。
设 L(t+ w)为第 w步（即在时间 t+ w）预测的SDN控制
器负载，则序列{L(t+ 1) L(t+ 2)…, L(t+ w)}的预测可由
F(L(t)…, L(t −p+ 1))定义，其中 F是向量值函数， p是
观测数量。

D.使用ARIMA和LSTM进行负载预测

为了研究时间序列模型在实现更高精度预测和更低预 测误差方面的有效性，我们的研究旨在比较一种传统随机 模型和一种机器学习模型，即ARIMA和LSTM。我们选 择ARIMA作为随机预测模型代表的主要原因是：我们的 数据集具有非平稳性，且ARIMA被认为是线性模型中最 通用的模型。作为机器学习模型的代表，我们选择 LSTM基于多个原因：我们的数据可能具有非线性特征， 是动态的，并且在不同时段可能存在高自相关性。此外， LSTM能够长期保留并训练数据的特征。此外，ARI MA和LSTM已在不同的预测领域被广泛使用[28],[29]。
1)使用ARIMA进行负载预测：在自回归积分移动平 均（ARIMA）模型中，变量的未来值被认为是若干过去 值（即观测值）和随机误差的线性组合。在时间序列分析 和预测应用中，ARIMA模型是自回归（AR）模型、移动 平均（MA）模型以及AR与MA组合（ARMA）模型的一 般形式。实际上，阶数为 p的自回归模型，记作AR(p)， 其基本思想是：在时刻 t的时间序列当前值L(t)——在本例 中即SDN控制器负载——可以表示为 p个过去值的线性组 合，并加上一个随机误差 E(t)。而阶数为 q的移动平均模 型，记作MA(q)，则不使用预测变量的过去观测值，而是 利用先前的误差作为未来结果的预测因子。ARMA(p, q)模 型将上述两个模型结合起来，形式如下： L(t)= E(t)
+∑ p
i=1 φ i B i L(t)+∑ q j =1 θ j BjE(t)，其中 φ i和 θ j 是模型 的参数， E(t)是具有零均值和恒定方差的随机误差。
B i ∗ L(t)= L(t − i)是后移算子。
ARMA模型只能用于平稳时间序列。然而，在许多情 况下，时间序列的统计特性（例如均值、方差）会随着时 间变化，使其成为非平稳的。因此，ARIMA模型对 ARMA模型进行了推广，以涵盖非平稳时间序列的情况。
非平稳时间序列变得不可预测，无法建模或预测。因此，
处理平稳时间序列更容易，因为它们可以被分析和预测。
在ARIMA(p, d, q)模型中，非平稳时间序列可以通过差分 过程转化为平稳序列。ARIMA(p, d, q)模型的表达式为
(1 −∑p i=1 φiBi)(1 − B)dL(t)=(1+∑q j=1 θjBj)E(t),其 中 d是差分阶数，且(1 − B)dL(t)= L(t) − L(t − d)。

2)使用LSTM进行负载预测：

作为循环神经网络（ RNN）的一种，LSTM网络具有强大的能力，能够记住先 前阶段的信息，从而在延长的时间范围内进行预测。事实 上，这类网络的核心思想是在对当前输入生成预测时，使 模型能够感知之前的阶段。因此，需要记住先前状态，这 使得网络能够在预测下一步时学习并利用序列观测。
LSTM网络的特殊性在于能够有选择性地记忆长序列中的 模式。LSTM网络由一组称为细胞的记忆块组成，这些记 忆块通过三个门——输入门、遗忘门和输出门——来实现 信息的过滤、删除和添加。遗忘门用于决定是否丢弃来自 前一个细胞的信息。输入门负责决定当前输入和隐藏状态 的哪一部分应被记忆。输出门则充当过滤器，确定将从细 胞中输出什么信息。

IV.预测模型的构建

本节介绍本研究中所用数据集的来源及其在被预测模 型使用前的准备过程。接下来，我们描述构建ARIMA和 LSTM模型的过程，并对得到的模型进行评估。

A.仿真设置

所有仿真和实验，包括数据集生成、ARIMA和LSTM建 模、训练过程及预测，均在一台配备IntelCorei7‐8750H处 理器、16GB内存和NVIDIAGeForceGTX1070显卡的笔 记本电脑上进行。本工作所使用的软件环境包括Keras版本 2.2.4与TensorFlow1.14.0后端。

B.数据集描述与准备

本工作所使用的数据集是SDN控制器负载，即数据平面 组件向控制器发送的请求数量的总和。为了获取此类数据， 我们使用Mininet模拟器创建了一个SDN网络。我们采用 RYU[30]作为SDN控制器，并使用OpenFlow协议版本1.3 作为数据平面组件与SDN控制器之间的南向接口。在数据平 面组件方面，我们使用了支持OpenFlow协议的虚拟交换机。
我们构建了一个包含38个虚拟交换机的数据平面层。这些虚 拟交换机随机连接，每个交换机连接3台主机。为避免网络架 构依赖性，在实验过程中定期并随机地更改交换机之间的连 接，从而生成不同的数据平面拓扑结构
授权使用的范围限于：中央密歇根大学。于2021年5月14日协调世界时16:17:20从IEEEXplore下载。限制适用。
菲拉利等：面向延迟敏感应用的基于机器学习的抢占式SDN负载均衡 15951
数据集的生成周期。为了模拟真实网络中的动态流量，我 们使用Iperf生成UDP和TCP流量，使用D‐ITG生成器产 生VoIP和DNS流量，并使用Wget生成HTTP流量。此外， 生成的VoIP和DNS流量分别遵循指数分布和均匀分布。
这些设置使得构建的网络中产生的流量具有动态性。所有 这些流量均由随机选择的主机生成。在执行流量生成器持 续6小时的同时，捕获SDN控制器与虚拟交换机之间交换 的消息。然后对捕获的流量进行过滤，仅保留SDN控制器 接收到的请求（例如 P acket_In messages）。
数据集准备对于实现更好的预测性能至关重要。首先， 我们通过用序列数据的平均值替换异常值来处理噪声和不 一致数据。由于SDN控制器的处理能力由其每秒可处理的 数据包数量定义，因此获取的流量每秒采样一次。因此， 我们的数据被转换为时间序列，时间步长等于1秒。时间序 列中的每个值代表对SDN控制器负载的一次观测。然后， 在保持观测值时间顺序的前提下，将数据划分为两个部分： 训练集和测试集。训练数据用于通过调整模型参数来拟合 模型。测试数据用于在训练阶段之后评估所获得的模型， 且不参与学习阶段。我们的数据量足够大，因此使用80% 作为训练数据、20%作为测试数据，可使两个子集都具有 高度代表性。

C.ARIMA建模

ARIMA模型记为ARIMA(p, d, q)，由差分I(d)、自回 归AR(p)和移动平均MA(q)组件组成，其中 d是使时间序 列平稳所需的差分次数； p是模型中包含的滞后观测个 数； q是预测方程中滞后预测误差的个数。为了构建有效 的预测模型，必须仔细确定三个参数 d、 p和 q。

1)差分阶数：

对时间序列进行差分的目的是使其平 稳（即时间序列的性质不依赖于时间）。为了研究平稳性 并确定合适的差分阶数，我们分析了自相关函数（ACF）。
如果ACF图迅速趋近于零，则该时间序列被认为是平稳的； 而非平稳时间序列的ACF则缓慢地趋于零。在图2中，我 们观察到原始时间序列的ACF在大量滞后阶数上呈现正自 相关（超过10个滞后），因此该时间序列需要进行差分处 理。此外，如果滞后1阶的自相关过于负，小于−0.5，则 说明该时间序列被过度差分。因此，观察一阶差分后的 ACF图（见图3），滞后1阶自相关大于 −0.5，表明该时 间序列未被过度差分。因此，该时间序列的最优差分阶数 为 d= 1。为了消除残差中的所有自相关痕迹，应添加自 回归项和移动平均项。

图2.原始序列的自相关函数。

图3.一阶差分的自相关函数

2)自回归和移动平均阶数：为我们的时间序列构建 ARIMA模型的下一步是确定自回归阶数 p和移动平均阶数 q。ARIMA模型选择需要在准备好的数据集上拟合多个模 型（即评估若干模型的性能），然后从中选择最佳模型。
如果一个模型在训练数据集上的性能良好且复杂度较低， 则认为其为最佳模型。我们可以使用偏自相关函数（ PACF）和ACF来大致判断平稳时间序列中去除自相关所 需的自回归项和移动平均项的数量。然而，仅通过检查 PACF和ACF图可能无法准确识别最优的AR和MA阶数。
为了获得最优的ARIMA模型，我们采用Akaike信息准则
（AIC）方法来选择AR和MA阶数。AIC是一种有效的方 法，用于选择拟合效果好但参数数量少（即本例中的 p和 q） 的模型，其表达式为 AIC= 2K −2ln(L)，其中 K表示模 型中的参数数量（例如p、 q阶数）， L表示数据的似然性。
由于我们之前已确定差分阶数为 d= 1，因此我们改变 p
和 q的值以寻找最小的AIC结果。表I总结了所得到的结果。
因此，最优模型为ARIMA(4,1,3)。

表IAIC结 果

模型的残差误差。)

图4.拟合ARIMA(4,1,3)模型的残差误差。

模型的残差误差密度)

图5.拟合ARIMA(4,1,3)模型的残差误差密度

图6.残差误差的自相关函数

3)所得ARIMA模型的评估：为使用时间序列构建一 个合适的ARIMA模型，此前所有步骤，即识别差分阶数、 自回归阶数和移动平均阶数，旨在构建一个有效且简洁的 模型。为了评估所得模型，即ARIMA(4,1,3)，我们检查了 残差图以确保不存在任何模式。图4和图5分别展示了残差 误差图和密度图。残差误差似乎呈平稳状态，即围绕零均 值波动，且密度图显示为高斯分布
授权使用的权限限制为：中央密歇根大学。于2021年5月14日16:17:20协调世界时从IEEEXplore下载。限制适用。
15952 IEEE车辆技术汇刊，第69卷，第12期，2020年12月
均值为零。图6描绘了残差误差的ACF图，其中我们可以 观察到所有自相关系数均在阈值范围内，即残差之间无自 相关性。因此，拟合ARIMA(4,1,3)模型是极佳的。

表IILSTM网络保留的超参数

D.LSTM网络建模

为了选择能够高精度进行预测的LSTM网络，需要对 多个超参数进行调优，例如隐藏层数量、每层神经元数量、 损失函数、优化器以及先前观测值数量。超参数调优过程 旨在找到最佳超参数组合以获得更好性能。在对LSTM网 络的超参数进行调优之前，我们首先对时间序列进行差分 使其平稳。根据ARIMA模型的构建过程，进行一阶差分足 以使时间序列达到平稳。然后，我们将时间序列值转换为 缩放到0和1之间的范围。数据缩放非常重要，因为它可以 避免大输入值减慢LSTM网络的学习和收敛速度。为了在 训练数据集上对拟合模型进行无偏评估，我们使用了验证 数据集。模型参考验证数据集来验证其性能，而不是从中 学习。
在本研究中，我们采用了随机搜索方法来为构建的 LSTM模型寻找最优解。根据该方法，使用超参数的随机 组合作为训练LSTM模型的输入。采用随机搜索方法可以 明确控制所使用的参数以及尝试组合的数量。在训练和调 整了多组组合后，保留的LSTM模型最重要的超参数总结 于表II中。

V.预测性能评估

为了比较ARIMA和LSTM在短期和长期预测方面的 性能，我们在本节中介绍了用于评估所研究模型的指标。
然后，我们展示各模型的预测结果，并比较它们在SDN控 制器负载预测中的性能。

A.评估指标

为了评估两种预测模型（即ARIMA和LSTM）在准确 性方面的性能，我们使用了均方根误差（RMSE）、决定
系数R 2、平均绝对误差（MAE）和平均绝对百分比误差 （MAPE）作为评估指标。对于每一步w（即在时间 t+ w）。
在RMSE公式中，误差被平方后再取均值，这会惩罚大误
差。 R 2实际值与预测值之间相关性的平方。
授权使用的范围限于：中央密歇根大学。下载时间：2021年5月14日16:17:20UTC，来源：IEEEXplore。适用限制条款。
菲拉利等：面向延迟敏感应用的基于机器学习的抢占式SDN负载均衡 15953
t+ 1。(b)t+ 15。(c)t+ 30。)

图7 SDN个控制器负载的ARIMA和LSTM模型在不同步长下的预测结果。(a)t+ 1。(b)t+ 15。(c)t+ 30。

表IIIARIMA和LSTM的平均绝对误差与平均绝对 百分比误差得分

平均绝对误差是所有预测绝对误差的均值，它是一个线性 评分，意味着所有个体差异在平均值中被同等加权。平均 绝对百分比误差以百分比形式衡量模型的准确性。

B.预测结果

使用ARIMA和LSTM模型，我们进行了多步预测。
实验包括对未来1到30秒的控制器负载进行预测。如前所 述，我们使用了20%的数据集（即测试数据集）来比较 ARIMA和LSTM在预测准确性方面的表现。
图7a、7b和7c分别展示了步长为1、15和30时SDN控 制器负载的预测结果。从图7a可以看出，两种模型在短期 预测t+1中均表现出良好的预测性能。事实上，ARIMA和 LSTM在步长t+1的预测结果均紧密跟随实际（即真实值） 的SDN控制器负载，呈现出相似的模式。一方面，在步长 t+1中，ARIMA的预测结果略优于LSTM，MAPE和 MAE的差异分别为4.91%和13.78；另一方面，根据表III， LSTM模型在步长t+15和t+30上的MAE和MAPE得分最低。
我们可以注意到，LSTM模型能够较好地捕捉SDN控制器 负载波动的一些峰值，如图7b和图7c所示。在第30步时， ARIMA模型预测的百分比误差（即MAPE）达到了 99.99%，而LSTM模型的MAPE仅为45%。由于这一55 %的差距，LSTM在长期预测中的性能明显优于ARIMA模 型。此外，ARIMA模型在三个步长t+1、t+15和t+30的预 测结果大致具有相同的轮廓，这可以解释为ARIMA模型 始终倾向于跟随均值。

图8.从t+1到t+30的ARIMA和LSTM的均方根误差。

图9.从t+1到t+30的ARIMA和LSTM的 R2。

此外，为了比较ARIMA和LSTM模型的准确性，从步 骤t+1到步骤t+30绘制了均方根误差（RMSE）分数和决定 系数 R2。图8显示，RMSE分数随着预测步数的增加而呈 比例上升。事实上，当对更远的未来阶段进行预测时， ARIMA和LSTM这两个模型的预测结果误差变得更高。然 而，在长期预测方面，LSTM模型的结果优于ARIMA模型，

图10.迁移操作期间数据平面组件、初始控制器和最终控制器之间交换的消息 [10]。

在t+30时RMSE分数相差400.31；而ARIMA在短期预测中
仍然略好。类似地，我们在图9中绘制并分析了 R 2分数。
R 2的取值范围为0到1之间，当 R 2接近0时表示预测结果
较差，当R 2接近1时表示预测结果较好。从图9可以看出，
随着预测步数的增加，两个模型的 R 2分数均趋于下降至
0。然而，ARIMA模型的 R 2从第18步开始迅速降至0，而
LSTM模型的 R 2在步骤t+30时仍保持在0.35。
使用预定义的评估指标，我们比较了ARIMA和 LSTM在短期和长期预测SDN控制器负载方面的准确性。
当预测到分布式SDN控制平面中出现负载不平衡时，我们 需要审慎选择要迁移的数据平面组件以及
授权使用的范围限制为：中央密歇根大学。于2021年5月14日16:17:20协调世界时从IEEEXplore下载。适用限制。
15954 IEEE车辆技术汇刊，第69卷，第12期，2020年12月
迁移应在何处发生，以保证高效的迁移操作。因此，下一 步是合理设计一种基于迁移的模型，在考虑迁移成本的同 时实现控制器之间的负载均衡。

VI.系统模型

A.控制器响应时间

我们考虑一种由有限个SDN控制器 C=
{c1, c2, c3,…, cn},（其中 |C| = n）组成的分布式SDN控制 平面架构。每个控制器 ck具有有限的处理能力 αk，定义 为单位时间内可处理的请求数量，并用
α={α1, α2, α3,…, αn}表示控制器的处理能力集合。数
据平面包含一组有限的数据平面组件S={s1, s2, s3,…, sm},
（其中 |S| = m）。在分布式控制平面架构中，每个控制 器管理一个数据平面组件的子集。因此，我们将控制器与 数据平面组件之间的关联定义为一个二元矩阵 Xn×m，其中 当且仅当 ck管理数据平面组件 si时， xki= 1成立。如前
所述，SDN控制器的负载是数据平面组件发送的Packet_In
消息数量的总和。因此，第 kth个控制器的负载可计算为
Lk=∑ m i=1 xki ∗ li,，其中 li表示 si发送的请求数量。
为了计算控制器的响应时间，我们考虑以下假设：
（i）请求数量的到达过程遵循泊松分布（即Packet_
Inmessages），而到达间隔时间服从指数分布；（ii）在 SDN控制器内，请求的处理时间（即服务时间）相互独立， 且与到达过程独立，并服从指数分布。因此，SDN控制器 可被建模为一个M/M/1排队系统。通过应用利特尔定律， 我们按如下方式计算控制器 ck的响应时间：
Tr k = 1
αk − Lk
. (1)
为了满足延迟敏感应用的需求，控制器的响应时间应 与这些应用程序所需的延迟相适应。因此，每个控制器的 响应时间不得超过阈值Tth。
由(1)可知，控制器 ck的响应时间 T r k 与其负载 L k成正 比。因此，在控制平面中进行负载均衡可维持控制器之间 在响应时间上的公平性。为了衡量负载在控制器之间的分 配公平性，我们定义负载均衡因子LB如下：
LB=
n
∑
k=1
n
∑
k ′ >k
∣ ∣ T r k − T r k ′
∣ ∣ .
(2)
在(2)中，响应时间之间的差异越小，控制平面中的负载 均衡程度就越高。

B.迁移协议

在迁移操作中，当数据平面组件 si从控制器 ck迁移到 控制器 ck′时，前者称为初始控制器，后者称为最终控制器。
为了确保迁移操作期间 si、 ck和 ck′的正常运行，应实施 一种迁移协议[10]，该协议包含四个阶段，如图10所示： （i）将最终控制器的角色更改为对等；（ii）插入并删除 虚拟流；（iii）使用屏障刷新待处理请求；（iv）将最终 控制器的角色更改为主控。第一阶段是将最终控制器的角 色从从属更改为对等。为此，最终控制器需要响应两条接 收到的消息，第一条由初始控制器发送（即开始迁移）， 第二条是由迁移的数据平面组件发送的异步消息（即对对 等角色的回复消息）。在此阶段结束时，最终控制器向初 始控制器发送一条消息，表明其已准备好进行迁移操作。
因此，在第二阶段，初始控制器作为对最终控制器最后一 条消息的响应，向迁移的数据平面组件连续发送两条消息 （即流表修改添加命令和屏障请求消息）。接下来，在接 收到屏障回复消息后，初始控制器移除由流表修改命令添 加的流表项。在第三阶段，初始控制器在第二阶段接收到 流删除消息后，向迁移的数据平面组件发送另一条屏障消 息作为连续命令。该消息被控制器用于确保所有先前的请 求在脱离其作为主控控制器的管理之前已被数据平面组件 处理完毕。然后，在接收到屏障回复消息后，初始控制器 向最终控制器发送一条消息，指示迁移结束。最后，在第 四阶段，最终控制器通过向迁移的数据平面组件发送角色 请求消息，将其角色从对等更改为主控。
通过分析初始控制器和最终控制器在四阶段迁移协议中的行为， 我们可以注意到，初始控制器在接收到四条消息后应响应四次，而 最终控制器在接收到三条消息后应响应三次。
授权使用的范围限于：中央密歇根大学。于2021年5月14日协调世界时16:17:20从IEEEXplore下载。限制适用。
菲拉利等：面向延迟敏感应用的基于机器学习的抢占式SDN负载均衡 15955
初始控制器的四个响应分别是：(i)流表修改添加命令和屏 障请求消息，(ii)流表删除命令，(iii)屏障请求消息，以 及(iv)迁移结束。最终控制器的三个响应分别是：(i)准 备迁移，(ii)角色请求消息至对等，以及(iii)角色请求消 息至主控。

C.迁移成本

我们用Xinitial n×m表示初始关联矩阵，用 Xfinal n×m表示执
行迁移操作后的最终关联矩阵。 Xinitial n×m与Xfinal n×m之间的
逻辑异或操作定义了二进制迁移矩阵 Mn×m，即 Mn×m=
Xinital n×m ⊕ Xfinal n×m ，其中 mki= 1当且仅当 ck是 si的初始 控制器或最终控制器。
为了表示参与迁移操作的控制器作为初始控制器，我们
定义二进制矩阵 Minitial
n×m=Mn×m • Xinital
n×m，其中• 是与操
作符，且 minitial ki= 1 当且仅当 ck是 si的初始控制器。类
似地，我们定义M final
n×m= Mn×m • Xfinal n×m 来表示作为最终控
制器参与迁移的控制器，其中mfinal ki= 1 当且仅当 ck 是 si 的最终控制器。
使用基于OpenFlow的迁移机制，数据平面组件的迁 移操作通过该组件、初始控制器和最终控制器之间交换一 组消息来完成，如图10所示。因此，我们将数据平面组件 的迁移成本定义为交换所有这些消息所需的时间。完成迁 移操作所需的时间取决于这些消息的传输延迟、初始控制 器的响应时间、最终控制器的响应时间以及数据平面组件 的响应时间。由于控制器的响应时间通常远大于传输延迟 和数据平面组件的响应时间[31][32],，我们假设迁移操作 的成本仅取决于初始控制器和最终控制器的响应时间。因 此，迁移 si的成本可定义如下：
Tmi =
n
∑
k=1
4 ∗ Tr k ∗ m initial ki +
n
∑
k ′ =1
3 ∗ Tr k ′ ∗ m final k ′ i
. (3)
在(3)中，第一个总和计算了初始控制器迁移si所需的 响应时间，第二个总和计算了最终控制器所需的响应时间。
由于初始控制器在接收到四条消息后应响应四次，而最终 控制器在接收到三条消息后应响应三次（见第VI‐B节）， 因此我们将初始控制器的响应时间乘以4，将最终控制器
的响应时间乘以3。此外，我们将总迁移成本T m定义如下：
T m =
m
∑
i= 1
T m i (4)
执行大量迁移操作会增加迁移成本，从而影响控制器性 能。由于我们
正在研究边缘处延迟敏感型应用的软件定义网络负载均衡问 题，显著的迁移成本会严重影响这些应用程序提供的服务。
因此，LBSDA的目标是通过迁移操作最小化负载均衡因子， 但不会以增加迁移成本为代价。为了最优地解决LBDSA问题， 我们将在下一节中将其表述为一个优化问题。

VII.问题P的表述与NP难性

A.问题建模

为了优化负载均衡和迁移成本，我们通过引入权重因 子 ω ∈[0, 1]，将两个目标 LB和Tm转化为加权总和。因 此，LBDSA可以表述如下：
minimize
X,M ω × LB+(1 − ω)× Tm (5a)
subject to
n
∑
k=1
xki= 1, ∀i ∈{1, 2, 3,…, m} (5b)
Lk< αk, ∀k ∈{1, 2, 3,…, n} (5c) Trk ≤ Tth, ∀k ∈{1, 2, 3,…, n} (5d) xki, mki, m initial ki , mfinal ki ∈{0, 1}. (5e)
方程(5a)描述了两个目标的加权总和。约束条件 (5b)确保每个数据平面组件必须恰好分配给一个控制器。
约束条件(5c)保证每个控制器的负载不应超过其处理能力。
约束条件(5d)指出每个控制器的响应时间不能超过与延 迟敏感应用程序所需的延迟相关的定义阈值 Tth。约束条 件(5e)列出了优化变量。
由于(1)的非线性，LBDSA是一个非线性二进制规划问题。

B.NP难性

我们将此处的LBDSA问题(5)表示为 P。为了证明 P是
NP完全的，我们(i)考虑该问题的一个决策版本，(ii)证明 P
属于非确定性多项式时间类（NP），以及(iii)在多项式时间 内将划分问题[34]归约到 P。在[35],中，已有研究通过从 划分问题的归约来证明SDN控制平面中类似负载均衡问题的 NP完全性。由于我们的问题与[35],中的问题不同，因此我 们不能直接推断我们的问题是NP难的。从[35]的问题到我 们问题的归约可能是可行的，但由于两个问题具有不同的目 标和约束，这种归约并不明显。为了给出一个简单的证明， 我们使用划分问题来证明我们问题的NP难性。
定义1.划分问题：划分问题是一个决策问题，定义如 下：给定一个整数集合 S，任务是判断 S是否可以被划分
为两个子集 S 1和 S 2，使得 S 1中所有元素之和等于 S 2中所
有元素之和，即 S 1 ∪ S 2 = S和∑s 1 ∈ S 1
s 1 =∑s 2 ∈ S 2
s 2。
定理1：问题P是NP完全的.
授权使用的范围限于：中央密歇根大学。于2021年5月14日协调世界时16:17:20从IEEEXplore下载。限制适用。
15956 IEEE车辆技术汇刊，第69卷，第12期，2020年12月
证明：我们通过限制来证明该定理，即证明 P的一个 受限版本是NP完全的。首先，我们证明 P属于问题P。这 是正确的，因为已知数据平面组件与控制器之间的关联矩 阵Xn×m，就可以在多项式时间内验证控制器的处理能力 （α）未被超出，且控制器的响应时间（Tr）不超过定义 的阈值（Tth）。
划分问题可以另述如下：给定一个有限集 S，且每个 元素 s ∈ S表示一个负载值 load（s） ∈N，是否存在一个 子集 S′ ⊆ S，使得∑s∈S′ load（s）=∑s∈S\S′ load（s）？
P的受限版本构造如下。设 C={c1, c2}, ω= 1和 α1= α2。
每个 si表示一个元素s ∈ S，并具有请求数量（即负载） li= load(si)。然后，给定划分问题的一个“是”解 S1和 S2， 我们可以构造一个关联矩阵 Xn×m作为 P的解，具体如下：对 所有 i ∈ S1， x1i= 1；对所有 i ∈ S2， x2i= 1。我们得到
∑m i=1 x1i × li=∑ m i=1 x2i × li,，因此 L1= L2。由于我们选择
α1= α2，则 Tr1 = Tr2。因此，我们得到一个解 xki ∈{0, 1},
∀i ∈{1, 2,…, m}和 ∀ k ∈{1, 2}，满足 LB= 0。反过来的推导
可以类似完成。由于划分问题是NP完全的，该归约在多项式时 间内完成，且P属于NP，这证明了 P是NP完全的，从而证明了 该定理。
我们证明了LBDSA是NP完全的，因此在大规模网络 中很难最优地求解。为了解决这一问题，我们采用机器学 习工具以计算高效的方式执行数据平面组件与SDN控制器 之间的关联任务。特别是，我们使用强化学习(RL)来高效 地获得LBDSA的关联解。在下一节中，我们将描述所提出 的强化学习算法。

VIII.强化学习算法

在强化学习中，智能体与其环境进行交互，其目标是 基于先前经验做出次优决策。智能体面临的主要挑战是在 利用与探索之间找到平衡：利用是指根据当前信息做出最 优决策的倾向，而探索是指尝试新决策以期获得更好结果 的倾向。在与环境交互过程中，智能体观察环境状态，并 依据特定策略执行动作。根据所执行的动作，环境状态发 生变化，智能体随之收到奖励或惩罚。智能体希望长期最 大化其累积奖励（或最小化其累积惩罚）。每次智能体观 察环境状态并执行动作后，都会从该经验中学习并优化其 策略。此过程不断重复，直到找到次优决策为止。后续部 分将给出详细说明。

A.预备定义

首先，我们假设根控制器包含一个强化学习代理，该 代理了解此架构所需的网络信息，即每个控制器的控制域、 控制器负载以及控制器响应时间。换句话说，
我们假设根控制器代表将执行学习过程的强化学习代理。
对于LBDSA，我们定义状态集、动作集和奖励如下。
状态：强化学习代理观察到的状态由每个控制器管理 的数据平面组件、控制器负载、控制器的响应时间（1） 以及实现的负载均衡水平LB给出。
Actions:动作表示为数据平面组件si ∈ S选择控制器 ck ∈ C作为最终控制器的决策。为了定义强化学习代理的 全局动作，我们首先定义可用于迁移 si的动作集合为 C， 即控制器的集合。我们将数据平面组件si的动作记为
ai ∈{c1, c2,…, cn}。如果 ai是数据平面组件 si的初始控
制器，则意味着该数据平面组件将不会被迁移。
强化学习代理同时为每个数据平面组件 si选择一个动 作。因此，我们定义了强化学习代理的全局动作，记为 a， 它表示为一个大小为 |S| = m的向量，其中
a [a1, a2,…, am]。注意，全局动作向量 a等价于关联矩
阵 X(n×m)，因为向量 a中的每个元素 ai对应于数据平面 组件 si的主控控制器。如果全局动作 a满足LBDSA问题 的约束(7b)、(7c)和(7d)，则它是可行的。
奖励。在对所有数据平面组件执行动作并获得全局动
作后，强化学习代理会收到一组奖励，记为{R(ai, a−i)
}i∈{1,2,…m}。每个奖励R(ai, a−i)既取决于为数据平面组件
si选择的动作 ai，也取决于全局动作 a。我们定义 R(ai,
a−i)属于{δ1,…, δ4}，其中 δ1, δ2, δ3和 δ4为任意实数且满足
δ1> δ2> δ3> δ4。对于 j ∈{1, 2, 3, 4}，若条件 ζj成立，
则奖励 R(R, a−i)被设为 δ j 。条件 ζ j如下所示： 1) ζ1：全局动作 a是可行的，数据平面组件si尚未迁移， 且负载均衡因子已降低。2) ζ2：全局动作 a是可行的，数 据平面组件si已完成迁移，且负载均衡因子已降低。3) ζ3： 全局动作 a是可行的，数据平面组件si已完成迁移，且负
载均衡因子已增加。4) ζ 4: the global action a is not feasible.
接下来，我们定义智能体如何对每个动作做出响应，以找到一 个次优策略。我们的方法基于著名的学习规则赢留输变算法[24]。

B.双赢得留输变算法(2WSLS)

为了解决基于强化学习框架的LBDSA问题，我们开发 了2WSLS算法，即双赢留输变算法，该算法源于赢留败变 学习策略。在原始的WSLS算法中，一个动作要么是获胜 动作，要么是失败动作，而在我们的算法中，我们考虑了 两种类型的获胜动作，因此得名2WSLS。给定控制器与数 据平面组件之间的初始关联后，2WSLS旨在在满足约束条 件(7b)、(7c)和(7d)的前提下，通过寻找负载均衡与迁移 成本之间的次优权衡来求解问题P。接下来，我们将描述
授权使用的范围限于：中央密歇根大学。下载时间：2021年5月14日16:17:20协调世界时，来源：IEEEXplore。适用限制。
菲拉利等：面向延迟敏感应用的基于机器学习的抢占式SDN负载均衡 15957
算法1：用于数据平面组件 si的2WSLS。
输入： A, τ1, τ2, ε, πi 输出：动作 ai
1:如果 R(ai, a)= δ1 那么
2: πi[ai] ← πi[ai]+ τ1(1 − πi[ai])
3:对于 aj ∈ A执行
4:如果 aj= ai则
5: πi[aj] ← πi[aj] − τ1πi[aj]
6:否则如果 R(ai, a)= δ2则
7: πi[ai] ← πi[ai]+ τ2(1 − πi[ai])
8:对于 aj ∈ A执行
9:如果 aj= ai则
10: πi[aj] ← πi[aj] − τ2πi[aj]
11:否则如果 R(ai, a)= δ3 那么
12: πi[ai] ← πi[ai] − ε 13: πi[cinitial] ← πi[cinitial]+ ε
14:返回 ai
算法的第一次迭代、学习过程和终止过程。
1)第一次迭代：强化学习代理为每个数据平面组件独 立模拟2WSLS。每个数据平面组件从其动作空间C中随机 选择一个动作 ai。一旦每个数据平面组件都选择了动作，
强化学习代理便形成全局动作 a=[a1, a2,…, am]，并计
算每个控制器的负载和响应时间。如果全局动作是可行的， 则智能体根据约束 ζ1、 ζ2、 ζ3和 ζ4计算奖励。
根据计算出的奖励和制定的全局动作，强化学习代理 可以获得有关为数据平面组件选择的某些动作的可靠性的 信息。事实上，当全局动作是可行的时，智能体可以判断： （i） si不迁移是否能够增加LB因子，即R(ai, a−i)= δ1； 以及（ii） si的迁移是否会降低或增加LB因子，即分别为 R(ai, a−i)= δ2或 δ3。而当全局动作不可行时，智能体无 法知道特定数据平面组件的迁移或不迁移是否有益。智能 体应高效利用所获得的信息，以便在未来选择更优的动作。
因此，我们为每个 si ∈ S定义一个大小为 n= |C|的概率向
量πi=[πi[a1], πi[a2],…, πi[an]]。其中每个元素πi[ak]（对
所有 k ∈{1, 2,…, n}）对应于强化学习代理为数据平面组
件si执行动作 ai= ck的概率。部分由强化学习代理为数据
平面组件 s i执行的2WSLS伪代码如算法1所示。
2)学习过程：一旦强化学习代理计算出奖励并将其关 联到数据平面组件，它将如算法1所示更新数据平面组件 的概率向量。这些更新应有效反映强化学习代理接收到的 结果，以改进学习过程。在赢留输变中，存在两种类型的 动作：(i)获胜动作，如果获得的奖励较高；(ii)失败动作， 如果获得的奖励不理想。在获胜动作的情况下，强化学习 代理将在未来的迭代中继续执行此动作；而在失败动作的 情况下，强化学习代理应尝试其他动作
另一个动作。WSLS原始学习算法已被证明常用于二元奖 励选择问题。然而，对于强化学习代理在每次迭代后获得 非二元奖励的问题，必须对模型进行修改和改进，这正是 LBDSA中的情况。
由于在2WSLS中存在一个权衡设计问题，单一的获胜 动作无法正确建模多目标。因此，我们定义了两个获胜动 作和一个失败动作。第一个获胜动作产生 δ1 reward，第 二个获胜动作产生 δ2 reward。我们认为第一个获胜动作 优于第二个（δ1> δ2），因为我们的目标是最小化负载均 衡因子以及迁移成本。因此，对应于更低的负载均衡因子 且无迁移的 δ1应获得最高的奖励。在第二个获胜动作中， LB因子降低，但会产生与数据平面组件迁移成本相对应 的开销。因此，为了提高在学习过程结束时收敛到这两个 获胜动作的可能性，必须增加执行这些动作的概率，但优 先考虑第一个获胜动作。相应地，对于 si ∈ S，两个获胜 动作对应的概率更新如下：
πi[ai]={πi[ai]+ τ1(1 − πi[ai]), if R(ai, a−i)= δ1, πi[ai]+ τ2(1 − πi[ai]), if R(ai, a−i)= δ2,(6)
其中 τ1和 τ2表示获胜增量因子，使得 τ1> τ2，因为第一 个获胜动作优于第二个。为了保持 πi中概率的总和等于1， 所有满足 aj= ai的概率 πi[aj]必须按相同的因子减少，如 下所示：
πi[aj]={πi[aj] − τ1πi[aj], if R(ai, a−i)= δ1, πi[aj] − τ2πi[aj], if R(ai, a−i)= δ2. (7)
当奖励等于δ3时，我们认为所选择的动作是一个失败 的动作，因为它不仅导致LB因子增加，还导致数据平面 组件的迁移，从而增加迁移成本。因此，选择该动作的概 率降低，而不迁移相关数据平面组件的概率提高，即选择 初始控制器的概率提高。通过这种方式，我们教导强化学 习代理最好完全不进行迁移。因此，概率向量按如下方式 更新：
π i[ai] = π i[ai] − ε, (8) π i[cinitial] = π i[cinitial] + ε, (9)
其中 ε表示失败递减因子， c initial 是数据平面组件 s i 的初始控制 器。
最后，当奖励等于 δ4时，全局动作不可行。在这种情 况下，我们无法判断特定数据平面组件的迁移或不迁移是 否有利于最小化LB因子和迁移成本。因此，强化学习代 理不进行任何概率更新。换句话说，强化学习代理必须倾 向于探索，以找到更优的解决方案。
授权使用的范围限于：中央密歇根大学。于2021年5月14日16:17:20协调世界时从IEEEXplore下载。限制适用。
15958 IEEE车辆技术汇刊，第69卷，第12期，2020年12月

表IV仿真参数

3)2WSLS终止：

当迭代次数达到预定义阈值或概率向 量收敛时，强化学习代理终止2WSLS算法的执行。然后， 智能体选择最后一个可行的全局动作 a，该动作表示最终
关联矩阵 Xfinal n×m 。

IX.仿真结果

我们使用三种不同数量数据平面组件（交换机）的拓 扑结构进行仿真，即分别包含20、25和30个组件。对于 所有这些拓扑结构，控制器的数量设置为5，并且为了简 化起见，假设所有控制器具有相同的容量 α。我们假设数 据平面组件发送的Packet_In消息数量是随机的。为了引 发控制平面中的负载不平衡状态，我们通过生成大量 Packet_In消息对至少一个控制器施加较大压力。优化问 题(5)在AMPL[36]中建模，并使用Knitro求解器求解以 获得全局最优解OPT。在所有仿真中，我们进行了100次 独立随机实现，然后取其平均值。表IV总结了仿真的关键 参数。
为了对我们的2WSLS算法进行基准测试，我们实现了 文献中的两种算法，分别是用于基于迁移能力的负载均衡 的MCBLB[17]和用于基于响应时间的SDN多控制器负载 均衡策略的SMCLBRT[11]。为了在SDN控制平面中平衡 负载，MCBLB使用迁移和交换操作在控制器之间迁移交 换机。移位操作是将交换机从过载控制器迁移到欠载控制 器的一种简单迁移操作。然而，在某些情况下，移位操作 并不总是可行的。例如，当卸载控制器的唯一解决方案是 迁移一个重载交换机时，但该交换机可能会使最终控制器 过载。在这种情况下，交换两个交换机可能有利于负载均 衡。在SMCLBRT中，利用控制器的响应时间来判断控制 器是否过载。实际上，根据适当的阈值，控制器被划分为 过载控制器和欠载控制器。然后，将重载交换机同时从过 载控制器迁移到负载较轻的控制器。我们通过采用我们定 义的控制器响应时间（1）以及表IV中定义的控制器响应 时间阈值对该算法进行了调整。为了公平地基准测试 2WSLS相对于[11]和[17],中两种算法的性能，我们的仿 真参数选择与[11]和[17]中使用的参数相似。
我们分两个阶段评估2WSLS的性能。首先，我们分析该 算法的参数，即获胜
增量因子 τ1 和 τ2，失败递减因子 ε 以及迭代次数 R。
然后，我们将2WSLS与最优解OPT、MCBLB和 SMCLBRT进行比较。
在讨论2WSLS的性能之前，我们首先通过AMPL建模 并使用Knitro求解器求解优化问题(5)来分析所获得的结果。
图11a、11b和11c分别显示了包含20、25和30个数据平面 组件的三种拓扑结构下的 LB因子(2)和迁移成本Tm(4)值。
对于每种拓扑结构，我们绘制了不同权衡调节权重 w ∈[0, 1]对应的 LB和 Tm值。结果如预期所示，策略越
偏向 LB导向(w> 0.5)，迁移成本 Tm的牺牲越大（即 Tm
增加），反之亦然。该值在三种拓扑结构 m= 20、 m= 25和 m= 30下几乎相同。从这些图中可以看出，优 化问题(5)的帕累托解大约出现在 w= 0.65附近。因此，在 后续的所有仿真中，选择 w= 0.65作为LBDSA问题的一 个高效且非劣解。

A.2WSLS的参数

2WSLS算法的性能取决于其参数的选择，即获胜递 增因子τ1和 τ2、失败递减因子 ε以及迭代次数 R。因此， 应谨慎选择这些参数以获得良好的结果。图12、13、14、 15和16展示了这些参数对目标函数(5)的影响。
为了确定获胜增量因子 τ1的最优值，我们将2 WSLS在不同 τ1取值下的性能与OPT进行比较。换句话说， 在给定 τ1的情况下，2WSLS相较于最优解在最小化式5中 的目标函数方面能达到多好。图12a、12b和12c表明，存 在一个 τ1的最优值，在该值下2WSLS的性能接近由 τ1= 0.5给出的OPT值。对于三种拓扑结构 m= 20、 m= 25和 m= 30，该最优值几乎相同，这是一个非常 好的重要观察结果，说明我们提出的学习算法具有可扩展 性。我们注意到，对于所有这些拓扑结构，较小的τ1值会 阻碍强化学习代理收敛到获胜动作，从而导致2WSLS的 性能下降。另一方面，当 τ1值较高时，选择相应获胜动 作的概率也会较高。因此，强化学习代理将不会探索可能 带来更好性能的新动作，而是会通过简单利用当前信息快 速地选择少数几个动作。类似地，图13a、13b和13c显示， 对于这三种拓扑结构，存在一个获胜增量因子 τ2的最优值， 由 τ2= 0.04给出，在该值下2WSLS的性能接近OPT。同 样，图13也展示了2WSLS的可扩展性。
为进一步验证我们提出的2WSLS算法的可扩展性，我们 将其在不同控制平面拓扑结构下的性能与OPT进行比较，即
n= 5、 n= 7和n= 9。换句话说，通过仿真表明， τ 1和
τ 2 的最优值在 n= 5、 n= 7和n= 9下几乎相同。为验证 2WSLS算法在密集网络拓扑下的可扩展性，数据平面组件的 数量被设置为
授权使用的范围限于：中央密歇根大学。于2021年5月14日协调世界时16:17:20从IEEEXplore下载。限制适用。
菲拉利等：面向延迟敏感应用的基于机器学习的抢占式SDN负载均衡 15959

图11.权重因子（ω）对不同数据平面拓扑的负载均衡因子和迁移成本的影响 ies.

图12.赢留输变中获胜增量因子（τ1）对不同数据平面拓扑结构的影响。

图13.赢留输变中获胜增量因子（τ2）对不同数据平面拓扑结构的影响。

对不同控制平面拓扑结构的影响。)

图14.赢留输变中获胜增量因子(τ1) 对不同控制平面拓扑结构的影响。

30，适用于所有这些控制平面拓扑结构。图14a、14b和14c
表明，我们所提出算法的性能在 τ 1 = 0.5下分别对于 n= 5、 n= 7和 n= 9接近OPT性能。图15a、15b和15c显示，对
于这三种控制平面拓扑结构，存在一个由τ 2 = 0.04给出的 τ 2
的最优值，在该值处2WSLS具有接近最优性能。
这些结果与图12和图13中所示的结果一致，并展示了我们的 2WSLS算法的可扩展性。

图15.赢留输变中获胜增量因子（τ2）对不同控制平面拓扑结构的影响。

图16.迭代次数对2WSLS的影响。

图16展示了不同 τ 1取值下迭代次数 R对2WSLS的影响。
我们注意到， τ 1的最优值即 τ 1 = 0.5的性能优于其他取值 的性能。这些结果证实了
授权使用的范围限于：中央密歇根大学。于2021年5月14日协调世界时16:17:20从IEEEXplore下载。限制适用。
15960 IEEE车辆技术汇刊，第69卷，第12期，2020年12月
![图17](图17.赢奖增量因子（τ1）对不同